0
\$\begingroup\$

enter image description here

Hello, can anyone tell me how can i implement backtracking in a a star search algorithm? I've implemented the a star search according to wiki, but it does not backtrack, what i mean by backtrack is that if the open list(green cells) contains 2,0 and 3,3 as shown in the picture, upon reaching 2,0 the current node would "jump" to 3,3 since the cost is now more than 3,3 and continue the search from there, how can it be done so that it would backtrack from 2,0->2,1->2,2... all the way back to 3,3 and continue?

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Do you mean you want to force multiple waypoints? If so, you'd have to use multiple layers of A*, first finding the shortest paths between waypoints, then finding the best combination of such paths to reach all waypoints. \$\endgroup\$
    – Mario
    Feb 4, 2015 at 8:51
  • 1
    \$\begingroup\$ For what purpose would you want the algorithm to revisit cells (2,1) (2,2) etc which it's already visited? The purpose of the open list in A* is to avoid such repeated computation, and focus exclusively on cells where something new might be learned. \$\endgroup\$
    – DMGregory ♦
    Feb 4, 2015 at 16:02
  • \$\begingroup\$ so it is more "human like" , in a real maze exploration you cant "jump" to that next best cell. rather we should backtrack to the next best cell and explore again from there. \$\endgroup\$
    – sutoL
    Feb 4, 2015 at 16:32
  • 1
    \$\begingroup\$ The open list is not where you are actually moving. It is where you are considering moving. A human is able to "jump around" when considering possible moves, and A* does that too. If you really want to backtrack then consider the Depth First Search algorithm instead of A*. \$\endgroup\$
    – amitp
    Feb 4, 2015 at 17:09

1 Answer 1

Reset to default
1
\$\begingroup\$

If you implemented A* correctly then you would have a "open" list of nodes to search sorted by the expected cost of a path through that node or d(start, node)+h(node, end)

This means that the 2,0 node should still be in the list. But The algorithm should continue with 3,3.

If it doesn't then the way you select the next node to investigate is flawed.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .