Why can't my A* implementation find a path out of an open room?

Question

I tried to follow this article with the following example, but in my attempts it always ends up with a dead end.

If we take G being 10 in a straight line or 14 in a diagonal, and H the distance in horizontal or vertical to the target point, then we restart this search for every tile that is the nearest one to the target point.

I have this result: if we take one or the other direction with 54, it ends up with a dead end. For example, if we go up from 40 to 54, then to 60, when we restart the search with G and H, it ends up with "4" (second shema) and comes back in a dead end:

Why does this happen and how can I solve it?

I also looked at the wiki, but I did not understand the system with the colors and the code shown.

Answer 1

You don't really backtrack.

Think of A* as having an outer “fringe” of nodes that it wants to consider (also called a “frontier”). This is the OPEN set. At every step it picks one of these and expands it, and moves that node into the CLOSED set. The ever-expanding fringe surrounding the start node will eventually eat up the whole map if you let it.

What you think of as backtracking is A* first expanding the fringe to the right, hitting a wall, and being unable to expand in that direction. But the rest of the fringe is still there. A* will expand other parts of it. It should eventually fill the interior room and go out the door to the north. Once it does that, it'll expand eastwards and then southwards until it reaches your goal.

Answer 2

you need to backtrack when you encounter a dead-end

the stock standard path search algorithm is:

Closed =[]
Open =[start]

while true
    current = select and remove a node from Open 
    add current to Closed 
    if current is goal return 
    for each node a that neighbors current
        if a is not in Closed 
            add a to Seen (or update a in Open)

the first line in the while is what differentiates all the algorithms from each other:

• in breadth first you select the node that has been there the longest (FIFO)
• in depth first you select the node that has been there the shortest (LIFO)
• in dijkstra you select the node with the lowest cost (this is G in the tutorial)
• in A* you select the node with the lowest cost+expectedCost (this is F in the tutorial)

if your map is finite then all variants will find a path eventually or fail only if there is no path

one mistake that I see here is that your heuristic (you expected cost) is not strictly underestimating (going diagonal costs 14 while the heuristic says it costs 20) this will make A* not behave correctly (it will still find a path but not necessarily the best one)

the nodes I expect A* to select are

1. startnode where it sets node 1 to 40, node 2 to 54, node 3 to 60, node above 4 to 74, node 4 to 80, node below 4 to 74, node 5 to 60 and node 6 to 54. adding them all to open
2. node 1, where it can't update anything
3. node 2, where it also can't update anything
4. node 6, ditto
5. node 3, where it would add the node in the gap with value 94 (cost 24 + heuristic 70)
6. node 5, where it can't update anything

and so on, the fact that you never get to the gap in the wall means that something is wrong in your logic, like not not including some neighbors

Answer 3

OK, so I found a good article that talked about Dijkstra algorithm (it is non-english speaking, so I will try to explain it here ) :

If you try to find the path between two cities, you will have 2 arrays : one with :

• the name of the node,
• the weight of the node (they all start at -1, except the first node, the starting point at 0)
• a bool to know if we already passed through this node to look for its children

Then a second array with :

• the name of the node,
• the previous node that leads to this node

Then, for each children of the current node, do the same thing :
If we want to go from London to Leeds, and the first child of London is Manchester :

Node : Manchester
have we already taken Manchester to search for its children?
=> No

is the weight of Manchester > the weight of London + distance London+Manchester ?
OR
weight of Manchester still undefined (= -1) ?
=> Yes, it is undefined

because it was YES :
weight of Manchester = weight of London + distance London-Manchester;
(in my case with a tilemap, the weight value depends wether it is a diagonal or not : I chose 14 if it is a diagonal, and 10 if it is not)
weight of Manchester = 0 + 10 = 10 ; previous node before Manchester = London

we check London to YES in the third parameter in the array (the bool of the first array).

And it looks fine for my example, so I guess it should work for others.

Thanks for all the answers @ratchetfreak, @amitp, @bummzack, @UnderscoreZero