I know about the A* algorithm and also other pathfinding techniques, but my question is how do I apply this to a finite amount of work a unit can do per frame? For example, say I have 3 units that need to find a path to somewhere. Do I allow them to compute the path in one turn or do I break it up over multiple frames and if I break it up how do I accomplish this? Thanks in advance guys!

Compute the path, store it (or a reference to it) with the unit, and follow as much of it as possible each frame. When you get to the end, free the path.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions ]

But shouldn''t the "computation of the path" take longer than 1 game cycle?

And if so how do you break it up across multiple game cycles?

It''s best to compute the path over several frames.

If you compute the path for each unit, and all your units have reached their destination, a new path has to be calculated which results in a huge frame drop if the new destination is far away and/or you have alot of units.

R.

I can calculate numerous paths per frame. It shouldn''t be a problem in most cases. Anyway, that isn''t really what you asked, is it? My last post answered your original question. But if you find you don''t have time to calculate as many paths as you like in one frame, just add a path-request queue or something, and process as many as you can each time.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions ]

You could put the pathing in a separate thread, and just give the unit new sub-destinations during the calculation. Or you could just give it the whole path once the calculation is complete (although this is probably a bad idea in a dynamic world).

So each unit has a path it will follow. You run the pathing algorithm in a separate thread and update the unit''s path (or sub-destination) at particular points in the algorithm''s progress. Meanwhile the game loop is running in its own thread and just moves the unit along its path a particular length each cycle. How that path is generated doesn''t have to be part of the game loop.

Btw this is just an idea - there may be much better ways to do what you want.

It''s really easy to break A* up into various frames. The trick is that you have to make sure you''re not writing to any shared data structures (for example, your closed list should be a per-unit thing, not just a flag in the map data structure (which is a common optimizarion)).

Now, your basic A* algorithm looks like this:


while( !open.isempty() )
{
// ... etc...
}


You just change it to this:


int iteration = 0;
while( !open.isempty() && iteration < SOME_NUMBER )
{
// ... etc...

iteration ++;
}


At the end of the while loop, just check that you''ve actually found the path. If not, you''ve only gone part of the way. You can then have the unit just move in the direction of the target (which may be the wrong way, but at least it''ll be moving until it calculates the rest of the path).

You can also take the node on top of the open list and construct a path to that. It''s also often in the wrong direction, but more often than not, it''s in the right direction.

codeka.com - Just click it.

In my rts, most paths can be calculated over about 3 frames*, which coveniently is also the length of the cursor animation

To do this, when ever I call my path solver, I also give it a time in milliseconds which is is allowed to use. As soon as it runs out of time, it returns but stores what it has already done.

Units who are going to follow this path add a reference to the path (because of the way I calculate paths, multiple units can follow a path, regardless of their position - helps with group movement), once a unit gets to the destination, it removes its reference to the path.

Whenever a unit goes to move, firstly it checks if the path is complete, if not, it will just wait, if it is, I call the pathfinder again which has a really fast function which tells the unit the next square it needs to go to (basically all it does is compares all the surrounding squares and checks which one is best)

This method works fine, and I''ve never noticed a lag unless I play on a stupidly sized map.

Trying is the first step towards failure.

There is a problem that arises when implementing ANY search algorithm over multiple frames and having the unit begin executing its movement before a path has been found...

Quite obviously, how do you know which path to start moving along if you don''t know which one leads to the goal? The problem is that your search algorithm may not be aware of obstacles beyond the furtherest leaf node and so cannot correctly compute costs of each path... remember, A* uses only a heuristic cost beyond leaf nodes.

Here is one solution...

Compute the search from both the starting node and the goal node. I''ll call the two search trees the starting tree and the goal tree . Each frame, expand n nodes in the goal tree and highlight the lowest cost node found so far. Now use that point as the goal for the unit and expand m nodes in the start tree computing costs relative to the new goal. Mark the leaf node with the lowest cost estimate as the current destination of the unit. Once this computation is done for one frame (it''s not expected that a full path has been found in one frame, although it might) then start moving the unit to its destination. Rinse and repeat until the unit arrives at a leaf node on the goal tree... then have it follow the path up the goal tree to the goal node.

This method WONT return the optimal (shortest length) path nor return a path with minimal computation UNLESS certain conditions are met... like no obstacles... in which case, there are better methods to use... like regular (one-sided) A*.

This method can also be improved so that it will return a path nearer the optimal path if obstacles do exist, but at a higher computation cost. What this method DOES guarantee is that it will find a path if it exists!

Cheers,

Timkin