quote: Original post by MikeD

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

Thanks! Now I understand what you were suggesting.

Eric

That''s not good enough Eric, I want marks out of ten and a gold star for achievment ;-).

Mike

Thanks for the link. I''m still going through the info. However some things have been going through my head meanwhile.

First, there is some information on a D*(Dynamic A*) algorithm on gameai.com which is to be implemented for dynamic terrain. You might find it useful.
Second, In a game like Total Annihilation, Warcraft,Tribal Rage e.t.c. The NPCs do not seem to be calculating a path from the beginning to the end, but rather just to a point that would bring them closer to thier destination. This, when well done gives the impression of a character ''searching'' intelligently for the best path (e.g. walking along a wall which brings it closer to it''s destination only to find the wall is blocked and it has to turn back). This would reduce the processing necesary becuase you only have to find a definite path to a point which you heuristically determine to be closer to the destination. although you will have to keep track of that path in case you have to backtrack. This will also slightly address the issue of changing terrain simply bacuase a shorter path will be easier to search for dynamic obstacles.
Third, in these games the characters have statuses (hold, moving, attacking, e.t.c.) if you have this in your game you can tell whether an object in your path is still going to be there when you get there simply by checking whether or not the status of the object indicates it is stationary or moving.
Hope this helps.

Adios!!

Illusion is meaningless, unless it affects reality.