1
\$\begingroup\$

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:

enter image description here

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ From the way you describe your algorithm, you only have one active open path. A* creates a path going each direction at each node and stores them in a list then repeats the process for the lowest path until it finds the end. \$\endgroup\$ – UnderscoreZero Dec 5 '13 at 16:31
  • \$\begingroup\$ @UnderscoreZero what if you the path arrives at a dead-end, how to know until which node to come back? \$\endgroup\$ – Paul Dec 5 '13 at 17:17
  • 2
    \$\begingroup\$ @Paul You seem to misunderstand A*. There's no single "path" and you don't go backwards when you hit a dead end. You just have a list of candidate tiles and you always expand on the one with the lowest cost. The path is only built via backtracking when you actually hit the target node. Maybe this helps: gamedev.stackexchange.com/questions/15/… \$\endgroup\$ – bummzack Dec 6 '13 at 7:56
  • \$\begingroup\$ OK, thanks for the link! I added an answer below, thanks for your help \$\endgroup\$ – Paul Dec 6 '13 at 16:44
17
\$\begingroup\$

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.

A* expands its fringe until it exits the room

\$\endgroup\$
  • \$\begingroup\$ thanks @amitp, can I ask you a question? When it reaches a dead end, we should not let the pink button restart the same path and come back to the dead end, but... how to let him know that the previous path was wrong, and still use the same first squares to take this time another path? \$\endgroup\$ – Paul Dec 6 '13 at 7:12
  • \$\begingroup\$ @Paul the open set holds all potential paths so when the current node can't go on any more, it can select another node and continue with that one \$\endgroup\$ – ratchet freak Dec 6 '13 at 7:27
  • \$\begingroup\$ perfect, I added an answer, thanks for your help \$\endgroup\$ – Paul Dec 6 '13 at 16:43
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ thanks ratchet, I wrote node 4 and above as if we were on node 3, after we passed through 1, 2 and arrived to 3. In your example, when do you restart the search for each tile? In my mind, it starts again each time it switches the current to a new tile (with a lower value), which makes it turn around the green cross. (And, how do you find 80 for node 4? +10 for G, and +6 * 10 for H, F = 70 ? (I wrote 64 instead of 70, because I compared it from node 3) \$\endgroup\$ – Paul Dec 5 '13 at 17:29
-2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Dijkstra's is usually not suitable for game pathfinding due to searching more nodes than necessary. The advantage of A* over it is that it uses a heuristic to reduce the number of nodes searched. See this page for an illustrative comparison: theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html \$\endgroup\$ – congusbongus Dec 7 '13 at 5:56
  • \$\begingroup\$ This doesn't answer the question either, it's really more of a follow-up post. \$\endgroup\$ – Josh Dec 7 '13 at 19:46
  • \$\begingroup\$ @congusbongus thanks, I will try that. JoshPetrie: no, I disagree with you, I needed to know 'how', because it was confusing to just know how it works from a large point of view. A more precise idea of 'how' the algorithm works is better and the article explained it very well. Now, adding a down vote to the answer that the OP checked is a bit of a contradiction to me. But, well, if this can help others in the same situation, it is better to share. \$\endgroup\$ – Paul Dec 7 '13 at 20:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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