1
\$\begingroup\$

I'm trying to get a grasp on the A* pathfinding algorithm. Using the image I attached. originally posted as http://i62.tinypic.com/23hlgcg.jpg

If the green square represents the start, and red represents the end. wouldn't the algorithm bring me up towards the top of the grid, and then circle me back around, because of the wall?

It would seem the algorithm would never start by moving downward first because the F cost would initially appear more expensive?

Is this a problem with the basic manhattan heuristic? Or am I just missing something?

| improve this question | | | | |
\$\endgroup\$
1
\$\begingroup\$

A* keeps a list of visited cells and a frontier. It will first explore the top of grid as you say but once all the possibilities there are explored, the A* will begin to go downwards. Think of it as a greedy breadth first search. See http://www.redblobgames.com/pathfinding/a-star/introduction.html.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ I was thinking that but won't i get trapped by my already closed out tiles? given the size of that grid in my screenshoot? when i ran this simulation on an applet using this same setup, the final path did not include traversing upward first and then coming back down. \$\endgroup\$ – michelle Dec 16 '14 at 4:23
  • \$\begingroup\$ A* stores on each cell the path that will reach the cell. It will return the shortest path to destination. Well not so much as storing the full path but which cell it came from. Then at the end the path is reconstructed via this linked list of came froms. \$\endgroup\$ – user55564 Dec 16 '14 at 4:27

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