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?

\$\endgroup\$
  • \$\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 '15 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 '15 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 '15 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 '15 at 17:09
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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