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!

Improve this question
\$\endgroup\$
  • 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\$ – Richard Marskell - Drackir Feb 13 '12 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 Feb 13 '12 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\$ – Richard Marskell - Drackir Feb 14 '12 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 Feb 14 '12 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\$ – Richard Marskell - Drackir Feb 14 '12 at 21:21
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.

Improve this answer
\$\endgroup\$
  • 3
    \$\begingroup\$ +1 that's the one, another name is D* (D*, focused D* and D* Lite) \$\endgroup\$ – Jonathan Dickinson Feb 13 '12 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 Feb 13 '12 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.

Improve this answer
\$\endgroup\$
  • 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\$ – Richard Marskell - Drackir Feb 14 '12 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 Feb 14 '12 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\$ – John McDonald Feb 14 '12 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 Feb 15 '12 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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.