instead of calculating a path in one frame cycle, why not why not do long pathfinding calculations in several cycles? by that you dont hang the game when long calc is needed and let units get close toward thinking simultainiusly? Gil

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.

This could be done using threads? I don''t use them as I don''t know how to get the debugger to work when they are on. But you
can assign a time slice for each critter and when the creature uses up its time slice it is suspended till the next update.

I think Deans method is the best though. Are there any articles out there that discuss this method? What happens if the path finder takes you in one direction and it turns out to be too expensive and it starts searching another way.

I remember Baldurs Gate did this and got really annoying. The guy would go halfway round the map and then change his mind.

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

MikeD, i actually find the road->highway example more appealing, but thats another system,
cause you have 3 steps: find the way to the "highway" where to get out of the "highway"
and where to go once you got out of it. i remember a tutorial like this which
even says that you should find the primary ways and use them to avoid long pathfinding.

Gil

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

quote: Original post by Dean Harding
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 were some great papers done on this at the last couple of GDCs...check out
www.gdconf.com and poke around in the convention papers
section.




Ferretman

ferretman@gameai.com
www.gameai.com

From the High Mountains of Colorado

I was wondering about the highway path finding method. Is that where you have predifined "highways" around the map that connect each part. So all the unit has to do is find a way to the highway and follow it, taking the correct turnoffs, until he arrives a point close as he can get to the spot. Then he hops off and takes a path that is easy to calculate to the spot. How well does this work? What if the spot is close to you and the highway is right behind you.? The unit gets on the highway and does a roundabout way to get to a section of highway closer to the destination. This could be very inneffiecent. Any thoughts on this?


RELIGION IS THE ROOT OF ALL EVIL

I assume that the "highway, road" is an analogy or model. What happens is that the path-finding algorithm i.e. usually A* would be applied in a hierachical fashion at different resolutions.

The highways aren't "predefined" and don't have to be "high-ways" in the real-life sense. They are prooduced by applying the pathfinding procedure at a different resolution.

For example, to navigate from London to Glasgow (I'm british) instead of applying the route finding algorithm in a low level manner you can progressively apply it at a global fashion i.e. find the path from county to county (i.e. state to state) then town to town within the county till you exit, then apply it high res from road to road to the towns. Then reapply high res to the next chunk of map. Hence at any given time, the chunk of map is a smaller finite space, which is a major benefit (neccesity almost) for path-finding algorithms, in terms of speed, space and managebility.

It doesn't give you the most optimal path (at road level) but it is a great deal more efficient in pratical terms and should generally give a very good map.

This is my own interpretation so forgive me if I'm wrong However, this seems similar to the human planning process.

--
Supercytro

Edited by - supercytro on October 31, 2001 4:55:15 AM

One newbie question for a pathfinding thread, What foes A* stand for and how does it work? I hear it used as the standard pathfinding, but i have never used it (i am new to game programming). Any response appreciated.

RELIGION IS THE ROOT OF ALL EVIL