title: Need help cracking the A* (A star) algorithm in python
body: <pre><code>import math
  import heapq
  
  class Node:
      def __init__(self, location, parent, pathCost, goalLocation):
          self.location = location
          self.parent = parent
          self.g = pathCost
          if not isinstance(parent, Node):
              self.pathValue = pathCost
          else:
              self.pathValue = parent.g + pathCost
          self.h = math.sqrt((location[0] - goalLocation[0]) ** 2 + (location[1] - goalLocation[1]) ** 2)
          self.f = self.g + self.h
  
      def __eq__(self, other):
          if self.f == other.f:
              return True
          else:
              return False
  
      def __lt__(self, other):
          if self.f &lt;= other.f:
              return True
          else:
              return False
  
      def __str__(self):
          return &quot;Location: [&quot; + str(self.location[0]) + &quot;,&quot; + str(self.location[1]) + &quot;] | MoveValue:&quot; + str(self.g)
  
      def __repr__(self):
          return &quot;Location: [&quot; + str(self.location[0]) + &quot;,&quot; + str(self.location[1]) + &quot;] | MoveValue:&quot; + str(self.g)
  
  def getNeighbors(location, grid):
      neighbors = []
      if location[1] != 0 and grid[location[1] - 1][location[0]] != 0:
          neighbors.append([location[0], location[1] - 1])
      if location[0] != 0 and grid[location[1]][location[0] - 1] != 0:
          neighbors.append([location[0] - 1, location[1]])
      if location[1] != len(grid[0]) - 1 and grid[location[1] + 1][location[0]] != 0:
          neighbors.append([location[0], location[1] + 1])
      if location[0] != len(grid[0]) - 1 and grid[location[1]][location[0] + 1] != 0:
          neighbors.append([location[0] + 1, location[1]])
      return neighbors
  
  def expandNode(node, grid, clist, olist, goalLocation):
      neighbors = getNeighbors(node.location, grid)
      #print(neighbors)
      for n in neighbors:
          child = Node(n, node, grid[n[1]][n[0]], goalLocation)
          if child in olist:
              if child.g &lt; node.g:
                  heapq.heappush(olist, child)
              if child in clist:
                  clist.remove(child)
          elif not child in clist:
              heapq.heappush(olist, child)
  
  grid = [[0, 2, 1, 3], #the top right is [3,0] the starting location
          [1, 1, 1, 0],
          [0, 4, 1, 3],
          [1, 1, 1, 1]] #the bottom left is [0,3] the goal location
  
  goalLocation = [0, 3]
  startLocation = [3, 0]
  
  firstNode = Node(startLocation, 0, grid[startLocation[1]][startLocation[0]], goalLocation)
  olist, clist = [], []
  heapq.heappush(olist, firstNode)
  
  for i in range(6):
      node = heapq.heappop(olist)
      print(node)
      print(str(i) + &quot;| Open list: &quot; + str(olist))
      print(str(i) + &quot;| Closed list: &quot; + str(clist))
      if node.location == goalLocation:
          print(&quot;Found Goal&quot;)
          break
      clist.append(node)
      expandNode(node, grid, clist, olist, goalLocation)
  
  </code></pre>
  <p>I have been trying to create a simple version of the A* algorithm in python that can traverse a 2-dimensional list. I believe that the algorithm itself is working but for some reason, it won't create a Node object for the position [2, 2] in my grid. Because of this, it is possible to not find the optimal solution. If anyone can see the logical error that I am missing or can point out how if the algorithm isn't correct.</p>
  <p>Currently, it prints out:</p>
  <pre><code>Location: [3,0] | MoveValue:3
  0| Open list: []
  0| Closed list: []
  Location: [2,0] | MoveValue:1
  1| Open list: []
  1| Closed list: [Location: [3,0] | MoveValue:3]
  Location: [2,1] | MoveValue:1
  2| Open list: [Location: [1,0] | MoveValue:2]
  2| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1]
  Location: [1,1] | MoveValue:1
  3| Open list: [Location: [1,0] | MoveValue:2]
  3| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1]s
  Location: [0,1] | MoveValue:1
  4| Open list: [Location: [1,0] | MoveValue:2, Location: [1,2] | MoveValue:4]
  4| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1, Location: [1,1] | MoveValue:1]
  Location: [1,0] | MoveValue:2
  5| Open list: [Location: [1,2] | MoveValue:4]
  5| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1, Location: [1,1] | MoveValue:1, Location: [0,1] | MoveValue:1]
  
  </code></pre>