5
\$\begingroup\$

I have implemented an A* library. Its most interesting feature is that it is "interruptible"; for example, you can stop the calculation loop on a game frame, and resume it later on the following frame.

The library works by creating "Nodes". Each node holds information about a cell in a grid: what is the cost to get there, what is the cell's "parent" (from which it is cheaper to get to the cell) etc. This information is stored until manually released; it is available for other uses if needed.

The "bestNode" is a pointer to one of such nodes. When the search starts, it is the "origin", and it gradually changes until the destination is reached.

Now I'd like to use that information to "partially recalculate" the node information when a node changes; the typical example is a door which opens/closes, allowing new paths/cancelling existing paths. Since I have already calculated the path from the origin to the "changed" node, I'd like to conserve that info, instead of re-calculating everything.

So far my thinking is:

function update(location)
  If the modified location is not in a node, return // not affected
  let node = self.nodes[location]
  let parent = node.parent
  delete all nodes that where created after parent
  add parent to the open list
  bestNode = parent
end

So I have two problems:

  • I don't know how to select the "nodes created after parent". Would a "unique increasing integer", like in a database, be enough?
  • This looks kind of complicated and clumsy. Is there a simpler way to do it?

Are there any other "partially-re-calculable" A* algorithms out there? I could not find anything on the subject.

Regards!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Have you considered what happens when, for example, a door closes and the best path is now in the opposite direction than the path up to that point? In this case the path would reach up to the door and then double back. It's probably best to just redo the search from the current position unless this doesn't matter to you/won't affect your game. \$\endgroup\$ Commented Feb 13, 2012 at 18:41
  • \$\begingroup\$ The thing is, right now, I have the information of the best path that reaches right to that door. The next iteration is going to calculate exactly that path again. That what I'm trying to avoid. \$\endgroup\$
    – egarcia
    Commented Feb 13, 2012 at 22:01
  • \$\begingroup\$ But if the door is closed, and the only other way to get past the door is BEHIND (assuming the door is forward) where the entity currently is, you would be calculating a path that goes to the door (the one you're reusing) and then comes back (the new path). \$\endgroup\$ Commented Feb 14, 2012 at 13:21
  • \$\begingroup\$ A* works by basically "filling up" all cells with information about what is the "best path" to get to them from the start. Before the door was closed, I had a "best path" from the start to the door (which then continued). When the door closes, I still have the best path possible up to the cell in front of the door (which probably isn't useful on itself, now that the door is closed. But I don't have to calculate it again). \$\endgroup\$
    – egarcia
    Commented Feb 14, 2012 at 17:24
  • \$\begingroup\$ As I understand it, that only happens when it's finding the path, once the path has been found, the extra data used to find the path is discarded and you're left with just the path. See John McDonald's answer (and my comment on it) for a better explanation of what I've been describing (including pictures!) :) \$\endgroup\$ Commented Feb 14, 2012 at 21:21

3 Answers 3

6
\$\begingroup\$

You'll probably get farther with Google with a bit of terminology: the usual jargon for a recalculation of an A* path is a "replan". In more specific direction, the situation you raise is the primary stated motivation of HPA*; it's a fairly well proven-out algorithm at this point and is likely to provide solid guidance.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ +1 that's the one, another name is D* (D*, focused D* and D* Lite) \$\endgroup\$ Commented Feb 13, 2012 at 20:28
  • \$\begingroup\$ Thanks! I have been investigating a bit and thanks to Amit's pages I found a different candidate. But your suggestion looks like a good way to reduce the memory footprint. \$\endgroup\$
    – egarcia
    Commented Feb 13, 2012 at 22:41
4
\$\begingroup\$

@RichardMarskell-Drackir in the comments has it right imo. Richard is trying to describe a scenario where more than just the subsequent A* calculations are invalid and you will will either have to completely recalculate the entire path from where you are now, or at a minimum find a way to roll-back the A* calculation even further than the changing tile. Here's the example Richard was explaining:

Recalc required for best route

You don't want the pathfinding algorithm to walk you right up to the closed door then turn around, you want to turn around right away. There may be shortcuts for certain specific scenarios, but in the general case, you'll want to recalc, or store the entire A* tree and be able to roll-back all invalid calculations.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Yes, this is what I was trying to describe. I modified your image (thanks!) to include the path as I understand it would be based on the technique the OP is asking for. Where the first segment of the light green line would be the "reused" path. \$\endgroup\$ Commented Feb 14, 2012 at 20:40
  • \$\begingroup\$ Ok I understand your concerns now. I didn't need to move the starting point though. In any case, +1 for the effort and artistry! \$\endgroup\$
    – egarcia
    Commented Feb 14, 2012 at 21:40
  • \$\begingroup\$ @egarcia, Everybody starts at the same location. If the door is open, your character will find the optimal path through the open door. While your character is walking toward the door, the door closes and causes the door node to change, requiring a new path be resolved somehow. Since the new best path is now behind you, the best way to resolve this is to completely recalculate your path, otherwise you're going to end up walking all the way up to the closed door, then back down (as per Richard's image edit). \$\endgroup\$ Commented Feb 14, 2012 at 21:47
  • \$\begingroup\$ That is what I'm trying to say - my character is not really moving. I need to recalculate the optimal path, but the character doesn't move. \$\endgroup\$
    – egarcia
    Commented Feb 15, 2012 at 8:47
3
\$\begingroup\$

I have found Lifelong Planning, which seems to do pretty much what I wanted - it "reuses" the previous calculations to compute "a difference".

There is a demo applet (java), too. Draw some walls, calculate the paths, then draw some more and calculate them again.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .