Search code examples
path-findingshortest-patha-star

A* path finding: backed into a corner, now what?

I'm writing a tower defense game, and I'm implementing the A* path finding algorithm from tutorials and what not, but I've encountered a situation I can't code out of as of yet! Consider the graphic below. The cyan nodes represent the shortest path found so far, the violet nodes represent inspected nodes, and the dark gray nodes represent a wall.

From what I know of the A* algorithm, to calculate a path for the situation below, it...

  1. Starts at "start" and checks if the upper node is available. It is. It calculates its G and H scores. It does the same to the right, lower, and left nodes.
  2. Finds that the right node has the lowest F score (F = G + H). It then repeats the same method as step #1 to find the next node, marking the "start" node as the parent.
  3. Continues this pattern and lands on the node in the center of the "C trap," as this node has the lowest F score so far.
  4. Discovers that the upper, right, lower, and left nodes are all closed. A* then marks this node as closed and starts over, understanding to leave this node alone.

What happens immediately after #4? Would A* re-examine the G and H scores along the same path, skipping that newly-closed node? Also, when drawing this scenario with this SWF, it indicates that more nodes are discovered to make up for the trap, as suggested here. Why?

Graphic of an A* problem

Solution

  • What you seem to be missing is that A* is not like a single unit moving along the grid, and backtracking when it hits a wall; it's more like an observer looking at various nodes around the graph, always considering next the node "most likely" to be in the shortest path.

    So, step 4 above never happens. A* doesn't mark a node as closed when it determines it can't be part of the best-path - it simply puts every single node it vists in the closed list, as soon as it visits it. And it doesn't ever "start over" - it's always looking at the next "most likely" node, where "most likely" means the front of the priority queue ordered by f(x).

    So, in your example above, A* will jump to one of the blue-nodes next, since they are all in the open list, and all have the same f(x) value. Though it could technically consider any one of them next, if you use the correct tie-breaking criteria, it will take one of the two that are closest to the end.