[OT] Pathfinding algorithm

[Gary Willoughby]

On Saturday, 21 September 2013 at 15:49:00 UTC, rasmus svensson 
wrote:
> Assuming the shortest path from from all nodes to every other 
> node is already pre-computed:
>
> What is a fast algorithm to update all paths, if one node is 
> marked as inpassible.
>
> Any good 3rd party library or research paper out there?

Maybe i'm wrong but i'm assuming you are pre-calculating the 
shortest paths from each node to all others is because you intend 
to traverse a path at some point in the future? The problem with 
this approach is that if a node is marked as impassable then you 
have to again do a lot of pre-calculation for every node it 
affects. Not only that but to avoid re-calculating them *all* you 
need to use an algorithm to find which are affected before you 
even start recalculating? To me this seems like too much work and 
could probably be solved by thinking a little differently.

Try implementing the A* algorithm which will give you a path from 
A to B *without* calculating paths to and from every node. Also 
if a node is marked impassable (even while running) you can just 
restart the algorithm from where you are back to B.

This sounds really scary stuff but A* is actually quite 
straightforward if you can find a nice resource to describe how 
it works.

Like these:
http://www.policyalmanac.org/games/aStarTutorial.htm
http://en.wikipedia.org/wiki/A*_search_algorithm