I''m looking for a pathfinding implementation for c++ that will work with a dynamically changing map environment (realtime strategy style). The one I have is way to costly, as it has to be re-called every time the unit moves a square. Anyone have some ideas?

quote: Original post by greywolfe01

I''m looking for a pathfinding implementation for c++ that will work with a dynamically changing map environment (realtime strategy style). The one I have is way to costly, as it has to be re-called every time the unit moves a square. Anyone have some ideas?

Here is one suggestion.

Use an Astar derivitive path-finding algorithm and don''t call it each time the unit moves a square. Instead, call it each time the unit encounters an (moving) obstacle or needs a new path.

Good Luck,

Eric

Perhaps it would also be useful to have two levels of path transition, a planning layer, A* style, and a reactive layer that works more on close up object avoidance. This would mean that moveable objects would not require a rethink of the route. You could keep checking that the route value (checked every x seconds) did not change more than 10-20%. If it did change, maybe due to a build up of bad guys you wished to avoid _then_ you could reprocess the route.

In any case, it doesn''t make sense to reprocess the path unless there is a dynamic element that heuristically enough changes the value of a given path.

Mike

quote: Original post by MikeD

Perhaps it would also be useful to have two levels of path transition, a planning layer, A* style, and a reactive layer that works more on close up object avoidance. This would mean that moveable objects would not require a rethink of the route. You could keep checking that the route value (checked every x seconds) did not change more than 10-20%. If it did change, maybe due to a build up of bad guys you wished to avoid _then_ you could reprocess the route.

In any case, it doesn''t make sense to reprocess the path unless there is a dynamic element that heuristically enough changes the value of a given path.

Mike

Your very good point brings up a comment and another question.

First the comment, and that is that rethinking the entire route, just due to a local obstacle being encountered, is not always going to be needed. In actual practice (a FPS in 3D), I''ve found that just reploting (using an Astar) to a point past the obstacle that was on the original path was sufficient to bypass the obstacle and then continue onward without rethinking the entire route.

Now this begs the question. How does one determine if the dynamics of the game have spoiled the path much further along (ie. past the current local obstacle) if one does not rethink the entire path when the opportunity arises (as in encountering the current local obstacle)? BTW, I''m not seeking an answer per se, just offering this situation up for discussion.

Eric

If you keep a value with your path struct to denote it''s value and then check the overall cost of the path dynamically to see if it''s changed by your standard A* cost calculation (taking into account the parts of the path you have already been past) then a large difference in the two should tell you the path is not good any more.

Does that sound reasonable?

Mike

quote: Original post by MikeD

If you keep a value with your path struct to denote it''s value and then check the overall cost of the path dynamically to see if it''s changed by your standard A* cost calculation (taking into account the parts of the path you have already been past) then a large difference in the two should tell you the path is not good any more.

Does that sound reasonable?

Mike

I''m not sure I''m following your idea.

Let me see if I can rephrase it, and thus indicate I do understand. If an NPC has a 100 step path, you suggest to assign some value (how is this determined?) to the path that indicates it is open. Then at step 20 the NPC encounters an obstacle. At the same time at future step 60 there is also another obstacle now in place. So, the NPC needs a path around the first obstacle, and may need to know about the blockage caused by the second.

Then to "check the overall cost of the path dynamically to see if it''s changed by your standard A* cost calculation (taking into account the parts of the path you have already been past)" means to me, that the NPC would request pathfinding from its now current location to its original destination (step 19 to step 100). This path should have a different "value" than the "value" obtained from the 100 step path simply because of the difference in numbers of steps (as I would think of it).

So, I''m not seeing how this indicates the second blockage exists without re-calculating the path all the way to the destination (or at least all the way to the second blockage).

Eric

Yup, that''s the same way I read the message Eric. I have thought of a possible solution to the question, but first a question of my own... Is it worth it? I can''t think of very many situations in which it would be *realistic* for an NPC to know about and thus react to blockages farther down it''s path. That having been said...

Let''s assume you have a function "int blocked(Location x)". Now, suppose your NPC has a path "Location *path". So, perhaps it would be efficient to just call the blocked function every tick for the remaining locations in the path. If there is a block furhter down the path, then you recalc the path.

Of course, this could back fire. Suppose another NPC further down the path blocks it just by walking "across" it. This event occurs well before the first NPC ever gets there, but still it takes ther time to recalc its path.

I''d say just don''t bother with the whole mess. Deal with blockages when you get to them.

Right.

Here it comes.

When you generate a path you do this using A* building up a list of partial paths by expanding the nodes, from the start node, with the lowest overall heuristic cost. This cost is the cost per square (different square == different costs) plus a Manhatten distance. Once you''ve solved the path finding problem you take the solution path, in it''s entirety, and store with it it''s cost (which, most likely is already stored with it from the search process). As you traverse the path and get rid of old path squares and reduce the cost stored with the path for all the squares you''ve already moved along. This will give you the cost of the path from where you''ve got to until the end of the path based on the world state at the time you constructed the path. This is your basic path cost, which is updated based on your distance along the path.
Now, every so often, when you''ve got an ounce of spare processor time or every x seconds, go through all the squares of the path you''re traversing (don''t try and recalculate a new path or anything like that) and, based on the current world state, recalculate each squares cost. You now have two costs for this path, the cost for the remaining stretch when you first calculated the path and the cost for the remaining stretch with the new calculation based on the current world state. If the new cost is greater than the old cost by more than x% (say 33.3%) you know something is wrong and a blockage has appeared.
If this occurs, calculate a new path because it''s become worth it as the old path is becoming unreasonable to traverse.
You could, of course, look at the cost of the path every ten seconds then, if a cost increase is found, keep checking it once per second for the next five seconds to see if it clears, only replanning the path if it doesn''t.

To recalculate the path cost based on the current world state is computationally cheap as there''s no search going on just some number addition.

Make sense now?

Not necessarily brilliant but it should work and be computationally cheap.

Mike

Duh, I hate to be the one to ask the dumb question but...

What is the A* search algorithm.

(A link to the info will suffice.)


------------------------------------------

Illusion is meaningless, unless it affects reality.

quote: Original post by The_Lurch

Duh, I hate to be the one to ask the dumb question but...

What is the A* search algorithm.

(A link to the info will suffice.)


------------------------------------------

Illusion is meaningless, unless it affects reality.

You might consider visiting www.gameai.com and looking around the software solutions section. There are several links to pathfinding that will contain A* examples.

Good luck,

Eric