PathFinding Algorithm: How to handle changing Weights Efficiently

Question

So, I have a simple pathfinding algorithm which precalculates the shortest route to several target endpoints, each of which has a different weight. This is somewhat equivalent to having one endpoint with a node between it and each endpoint, though the edges there have different weights. The algorithm it uses is a simple spreading algorithm, which in 1d looks this this (| means wall, - means space):

• 5 - - - 3 | - - - 2 - - - - 2
• 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
• 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
• 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
• 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
• Done. Any remaining rooms are unreachable.

So, let's suppose I have a precalculated pathfinding solution like this one, where only the 5 is a target:

- - - - | 5 4 3 2 1 -

If I change the wall to a room. Recomputing is simple. Just re-handle all distance nodes (but ignore the ones which already exist). However, I am not able to figure out an efficient way to handle what to do if the 4 became a wall. Clearly the result is this:

- - - - | 5 | - - - -

However, in a 2d solution I'm not sure how to efficiently deal with 4. It is easily possible to store that 4 depends on 5 and thus needs recaculation, but how do I determine its new dependency and values safely? I'd rather avoid recalculating the entire array.

One solution, which is better than nothing, is (roughly) to only recalculate array elements with a manhattan distance of 5 from the 5, and to maintain source information. This would basically mean reapplying the algorithm to a selected area But can I do better?

Answer 1

Hmmm. One solution I've come up with is this: Keep a list of nodes that are reachable most quickly from each node. If a node becomes a wall, check which node it was reachable from and grab the corresponding list. Then Recheck all those nodes using the standard algorithm. When reaching a node where the new distance is smaller, mark it as being in need of retesting.

Take all the neighbors of the marked nodes which are unmarked and reapply the algorithm on them, ignoring any marked nodes that this technique hits. If the reapplied algorithm increases the value of a marked node, use the new value.