title: Python - Speed up an A Star Pathfinding Algorithm
body: <p>I've coded my first slightly-complex algorithm, an implementation of the <a href="http://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer">A Star Pathfinding</a> algorithm. I followed some <a href="http://www.python.org/doc/essays/graphs.html" rel="noreferrer">Python.org advice</a> on implementing graphs so a dictionary contains all the nodes each node is linked too. Now, since this is all for a game, each node is really just a tile in a grid of nodes, hence how I'm working out the heuristic and my occasional reference to them.</p>
  
  <p>Thanks to timeit I know that I can run this function successfully a little over one hundred times a second. Understandably this makes me a little uneasy, this is without any other 'game stuff' going on, like graphics or calculating game logic. So I'd love to see whether any of you can speed up my algorithm, I am completely unfamiliar with Cython or it's kin, I can't code a line of C.</p>
  
  <p>Without any more rambling, here is my A Star function.</p>
  
  <pre><code>def aStar(self, graph, current, end):
      openList = []
      closedList = []
      path = []
  
      def retracePath(c):
          path.insert(0,c)
          if c.parent == None:
              return
          retracePath(c.parent)
  
      openList.append(current)
      while len(openList) is not 0:
          current = min(openList, key=lambda inst:inst.H)
          if current == end:
              return retracePath(current)
          openList.remove(current)
          closedList.append(current)
          for tile in graph[current]:
              if tile not in closedList:
                  tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                  if tile not in openList:
                      openList.append(tile)
                  tile.parent = current
      return path
  </code></pre>