A friend and I are now thinking about how we are going to implement pathfinding in our rts game. At first A* seemed like the choice to go, but I think that finding a path dynamically may be too hard on the cpu, especially if we have to manage like > 200 units at once. I heard the way most rts game do it, is to input pre-determined paths in the map editor for units to follow. Just want some inputs from more people who have experience in the field.

I think you could do well by preprocessing the map into large sectors so that you can find a rough route almosg instantly, and you subsequently only need to recalculate the paths from one side of the sector to the other.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Most RTS games use a simple grid, and do NOT precalculate paths.

Anyway, one way to do dynamic pathfinding is to store a Distance Transform of the environment, and just hill-climb that data to move your unit along the shortest path. Then, switching to an alternate path when an area is blocked is trivial.

How does the Distance Transform work? Simple. Breadth-first floodfill out from the goal point; mark each grid cell with a distance one greater than it''s parent''s. When this finishes, you know, for any point P, the length of the shortest path from P to the goal. So if you''re at P, you check it''s 4 neighbors, and move to the one with the lowest value. Continuing to do this is guaranteed to get you to the goal using the fewest possible number of moves. It also tells you immediately if you can''t get there from here, since the floodfill wouldn''t have reached that cell. Anyway, now, if you''re on a cell and the best neighbor cell is blocked, just go with the second-best one. This is an easy way to deal with moving obstacles.

Pathfinding is a very difficult problem, getting it done right takes lots of work. In the post above this one, that distance transform algorithm is suggested to find a path. But what about the following scenario: the distance from the goal for each tile is found. But a potential path is blocked. The unit might walk along this path until where it is blocked. At this point, the next best move is to step back. But after stepping back, the best move is to step forward again. And then the unit is just stuck walking back and forth between two tiles, until the obstacle moves. So then you''d also need to keep track of what tiles were already visited to avoid getting caught in cycles like that. But then what to do to escape the cycle? Maybe just giving up, or recalculating the path. But the recalculated path must be sure to avoid the obstacle that caused the unit to get stuck in a cycle in the first place.

quote:Original post by TerranFury
Anyway, one way to do dynamic pathfinding is to store a Distance Transform of the environment, and just hill-climb that data to move your unit along the shortest path. Then, switching to an alternate path when an area is blocked is trivial.

Wow, all my babbling about the DTA has finally paid off... someone else is recommending it!

Timkin