title: A* Algorithm does not find shortest path
body: <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 &lt; other.f
          return False
  
      def __gt__(self, other):
          if other != None:
              return self.f &gt; 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 &lt;= full_y &lt; len(map) and 0 &lt;= full_x &lt; 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 &gt; 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>