StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POA* Algorithm does not find shortest path
text
Body
copied!<p>I am trying to implement the A* algorithm in python but have hit a problem when trying to find the path of this map:</p> <pre><code>X X X X X X X S = Start 0 0 0 X 0 0 0 E = End 0 S 0 X 0 E 0 X = Wall 0 0 0 X 0 0 0 0 0 0 0 0 0 0 </code></pre> <p>I am using the Manhattan method. My implementation does find a path, but not the shortest one. The error starts on it's second move -- after moving right. At this point it can move up and the heuristic cost would be four (three right, one down) or down (three right, one up). Is there a way so it chooses down to get the shortest path?</p> <p>Code:</p> <pre><code>class Node: def __init__(self, (x, y), g, h, parent): self.x = x self.y = y self.g = g self.h = h self.f = g+h self.parent = parent def __eq__(self, other): if other != None: return self.x == other.x and self.y == other.y return False def __lt__(self, other): if other != None: return self.f < other.f return False def __gt__(self, other): if other != None: return self.f > other.f return True def __str__(self): return "(" + str(self.x) + "," + str(self.y) + ") " + str(self.f) def find_path(start, end, open_list, closed_list, map, no_diag=True, i=1): closed_list.append(start) if start == end or start == None: return closed_list new_open_list = [] for x, y in [(-1,1),(-1,-1),(1,-1),(1,1),(0,-1),(0,1),(-1,0),(1,0)]: full_x = start.x + x full_y = start.y + y g = 0 if x != 0 and y != 0: if no_diag: continue g = 14 else: g = 10 h = 10 * (abs(full_x - end.x) + abs(full_y - end.y)) n = Node((full_x,full_y),g,h,start) if 0 <= full_y < len(map) and 0 <= full_x < len(map[0]) and map[full_y][full_x] != 1 and n not in closed_list: if n in open_list: if open_list[open_list.index(n)].g > n.g: new_open_list.append(n) else: new_open_list.append(open_list[open_list.index(n)]) else: new_open_list.append(n) if new_open_list == None or len(new_open_list) == 0: return find_path(start.parent, end, open_list, closed_list, map, no_diag, i-1) new_open_list.sort() return find_path(new_open_list[0], end, new_open_list, closed_list, map, no_diag) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload