Archived

This topic is now archived and is closed to further replies.

dopeflow

Dynamic pathfinding too much on cpu?

Recommended Posts

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.

Share this post


Link to post
Share on other sites
My experience with truly dynamic FPS navigation is that you won''t be able to get 200 units working fully dynamically without greatly simplifying the problem (i.e. ignore some factors).

The algorithm can then be optimized based on these assumptions; offline pre-computation and cached path-tables (online) seem to be essential.

Alex

http://www.base-sixteen.com/Navigation/

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
quote:
Original post by InnocuousFox
I just marvel at how Empire Earth can process 1200 units at the same time. That''s fantastic!


for the first steps, until the final path is calculated, they just estimate the path, just go directly to the goal e.g.
I think that was described in Ai Game Programm wisdom



@$3.1415rin

Share this post


Link to post
Share on other sites
also, if the units are grouped, only one path has to be found that they all can follow. you have to work on the flocking behavior then.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites