Hacker News Reader

Comment by londons_explore | Hacker News Reader

How exactly is pathfinding an NP complete problem?

Surely a simple Dijkstra search across all grid squares would do the job?

Edit: Perhaps it's 'find an optimal strategy for everyone to get to their destination while nobody collides with anyone else'?

I didn't think real time strategy games normally did much collision avoidance between units though... The number of times I've seen an army just walk through another...

View on HN

The RTS games I know definitely do collision detection. StarCraft 2 disables collision detection in a few cases: workers harvesting resources, adept shading, and the colossus walking over ground units. To see what no collision detection would look like, see how the air units stack and move across each other.

I think collision avoidance might be overkill. It's fine if two units bump into each other while going in the same direction. Collision is bad if some units are moving through a choke point and the units in back turn around to take a different route because there's no open grid squares to walk forward through.

I'm currently playing through the StarCraft 1 campaign and the pathing differences with 2 are huge. Imagine being in line at Disneyland and every ten seconds, the people in front of you decide the entrance is blocked and turn around to try finding another way in. Then they bump into you and turn around again. Or maybe they just keep bumping into you for a bit.

I wrote a paper on this a number of years ago. Here were my primary sources:

https://arxiv.org/abs/cs/0007021

https://arxiv.org/abs/1203.1895

I believe the second depends on the first.

Reply on news.ycombinator.com