title: A star search extremely slow with python
body: <p>here is some code I wrote for an A* pathfinding algorithm. However as soon as I make the start and end nodes slightly far away, the program takes minutes to run. Why is this? The code below ran in 2 minutes yet the start and end node are so close. Thanks for the help. I feel like it has to do with the part of getting the lowest f value in the open list, however I am not sure.</p>
  <pre><code>import cProfile
  
  class Node(object):
      def __init__(self, parent = None, position = None):
          self.position = position
          self.parent = parent
          self.g = 0
          self.h = 0
          self.f = 0
  
      def euclidean_distance(self, x_end, y_end):
          return math.sqrt(abs(self.position[0]-x_end)**2 + abs(self.position[1]-y_end)**2)
  
      def pos(self):
          return self.position
  
  
  
  maze =  [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
  
  def astar():
  
      openlist = []
      closed = []
  
      current = Node(None,[0,0])
      destination = [4,8]
      openlist.append(current)
  
      adjacent = [[1,0],[0,1],[-1,0],[0,-1]]
  
      while len(openlist) &gt; 0:
          cur_index = 0
          for index in range(len(openlist)):
              if openlist[index].f &lt; openlist[cur_index].f:
                  cur_index = index
          
          current = openlist[cur_index]
          openlist.pop(cur_index)
          closed.append(current)
  
          if current.pos() == destination:
              print(&quot;ok&quot;)
              path = []
              current_node = current
              while current_node is not None:
                  path.append(current_node.position)
                  current_node = current_node.parent
              return path
  
          for candidate in adjacent:
              x = candidate[0]+current.pos()[0]
              y = candidate[1]+current.pos()[1]
              if x &gt; (len(maze) - 1) or x &lt; 0 or y &gt; (len(maze[len(maze)-1])-1) or y &lt; 0:
                  continue
              if maze[x][y] != 0:
                  continue
              next = Node(current,[x,y])
              neighbour = next
              if neighbour not in closed:
                  temp = current.g + 1
                  if neighbour in openlist:
                      if neighbour.g &gt; temp:
                          neighbour.g = temp
                  else:
                      neighbour.g = temp
                      openlist.append(neighbour)
  
              neighbour.h = math.sqrt(abs(neighbour.pos()[0]-destination[0])**2 + abs(neighbour.pos()[1]-destination[1])**2)
              neighbour.f = neighbour.g + neighbour.h
              
              # for val in openlist:
              #     if neighbour == val and neighbour.g &gt; val.g:
              #         continue
              # openlist.append(neighbour)
  
  cProfile.run('astar()')
  path = astar()
  
  new = []
  for r in range(len(maze)):
      temp = []
      for g in range(len(maze[r])):
          if maze[r][g] == 1:
              temp.append(&quot;#&quot;)
          elif [r,g] in path:
              temp.append(&quot;^&quot;)
          else:
              temp.append(&quot;.&quot;)
      new.append(temp)
      print(&quot; &quot;.join(temp))  
  </code></pre>