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!

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!