A * Algorithm does not find the shortest path

Question

I am trying to implement the A * algorithm in python, but ran into a problem while finding the path to this map:

XXXXXXXS = 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 

I use the Manhattan method. My implementation really finds a way, but not the shortest. The error begins with the second move - after moving to the right. At the moment, it can move up, and the heuristic value - four (three on the right, one down) or down (three on the right, one up). Is there any way that he chooses to get the shortest path?

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 > ng: 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) 

Answer 1

It seems you are creating a new open list for each node that contains only node neighbors. This essentially makes your search a depth search, while A * should be a better search.

You need to use one open list, which will be updated with each neighbor of the node when visiting this node. Old nodes in the open list should remain there until they pass and go into the closed list.

Regarding what you said in your question, it’s OK for the search to try to climb to the bottom (since, according to the heuristic, they are at the same distance from the target). The important thing is that ultimately the chosen path will be the shortest.