Ya, that''s done quite often. After you''ve gone a little way in finding the path, you can then just set your unit or character in the general direction of the path, and make any corrections as you find more and more of the path.

Another way is to break a large map into chunks, and store "connectivity" information about each chunk (i.e. "Chunk 1 is connected to chunks 2, 3 and 4", "Chunk 2 is connected to chunks 1, 3 and 5", etc). Then, you figure out which chunk you''re in, which chunk you''re going to and find a path like that. Then, and each chunk boundary, you''ve only got to find the (much shorter) path to the chunk boundary. This won''t give the "optimum" solution, but most of the time you don''t want the optimum solution anyway (since you''re supposed to modelling a real person, who would never find the optimum path anyway).

codeka.com - Just click it.

There can also be the memory overhead. If you have 500 troops all building A* paths then they''ve all got to keep a store of which nodes have been expanded for each of their own paths. With many long paths this can be a huge amount of stored nodes and not worth it. Alternatively, if all the nodes are stored inside one function and all pathfinding is done to completion before the function ends then you won''t have lots of semi-expanded paths in memory at once.

Of course if you partially plan a path, then plan the rest when you get to the end of the current section, you have the problem that certain maps, with dead ends and the like, will have your person going in circles as they traverse half the path, find it leads to a dead end, walk back to where they started (as that is part of the new path to the goal), get there and replan only to decide their original dead-end path is the new best idea (as they have no memory that it''s a bad path). This might not be a problem that arises often, but if it arises once it''s still a problem.

The idea of breaking the path up into chunks, as suggested by Dean is a good one. Just think of the world as areas and portals between areas. A* works the same on this higher level as it does on the lower level. You have one lot of path between chunks and a second lot within your current chunk. You could even break up the world into areas that don''t require paths, i.e. open areas and portals between those open areas.

Mike

quote:Original post by Dean Harding
Another way is to break a large map into chunks, and store "connectivity" information about each chunk (i.e. "Chunk 1 is connected to chunks 2, 3 and 4", "Chunk 2 is connected to chunks 1, 3 and 5", etc). Then, you figure out which chunk you''re in, which chunk you''re going to and find a path like that. Then, and each chunk boundary, you''ve only got to find the (much shorter) path to the chunk boundary. This won''t give the "optimum" solution, but most of the time you don''t want the optimum solution anyway (since you''re supposed to modelling a real person, who would never find the optimum path anyway).

There has been some good work done in solving these problems in the research field. The general problem of finding a plan in a world without complete information (in other words, you have limited information to act upon, not perfect knowledge of the complete world state) is called a Partially Observable Markov Decision Problem (POMDP). The idea of breaking the world into chunks corresponds to heirarchical planning in POMDPs. A common test environment for POMDPs is path planning for a mobile robot in an office building, where doors may or may not be closed, lifts may or may not work (or take a variable time to arrive) or other obstacles/obstructions may exist. If anyone is interested in reading current research into POMDPs I can provide some pointers.

Cheers,

Timkin