Python - Speed up an A Star Pathfinding Algorithm

Question

I've coded my first slightly-complex algorithm, an implementation of the A Star Pathfinding algorithm. I followed some Python.org advice 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.

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.

Without any more rambling, here is my A Star function.

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

Answer 1

An easy optimization is to use sets instead of lists for the open and closed sets.

openSet   = set()
closedSet = set()

This will make all of the in and not in tests O(1) instead of O(n).

Answer 2

I would use the sets as have been said, but I would also use a heap to find the minimum element (the one that will be the next current). This would require keeping both an openSet and an openHeap, but the memory shouldn't really be a problem. Also, sets insert in O(1) and heaps in O(log N) so they will be fast. The only problem is that the heapq module isn't really made to use keys with it. Personally, I would just modify it to use keys. It shouldn't be very hard. Alternatively, you could just use tuples of (tile.H,tile) in the heap.

Also, I would follow aaronasterling's idea of using iteration instead of recursion, but also, I would append elements to the end of path and reverse path at the end. The reason is that inserting an item at the 0th place in a list is very slow, (O(N) I believe), while appending is O(1) if I recall correctly. The final code for that part would be:

def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

I put return path at the end because it appeared that it should from your code.

Here's the final code using sets, heaps and what not:

import heapq


def aStar(graph, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()

    def retracePath(c):
        path = [c]
        while c.parent is not None:
            c = c.parent
            path.append(c)
        path.reverse()
        return path

    openSet.add(current)
    openHeap.append((0, current))
    while openSet:
        current = heapq.heappop(openHeap)[1]
        if current == end:
            return retracePath(current)
        openSet.remove(current)
        closedSet.add(current)
        for tile in graph[current]:
            if tile not in closedSet:
                tile.H = (abs(end.x - tile.x)+abs(end.y-tile.y))*10
                if tile not in openSet:
                    openSet.add(tile)
                    heapq.heappush(openHeap, (tile.H, tile))
                tile.parent = current
    return []

Answer 3

As suggested above, make closedSet into a set.

I tried coding openList as a heap import heapq:

import heapq

def aStar(self, graph, current, end):
    closedList = set()
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList = [(-1, current)]
    heapq.heapify(openList)
    while openList:
        score, current = openList.heappop()
        if current == end:
            return retracePath(current)
        closedList.add(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.heappush((tile.H, tile))
                tile.parent = current
    return path

However, you still need to search at if tile not in openList, so I would do this:

def aStar(self, graph, current, end):
    openList = set()
    closedList = set()

    def retracePath(c):
        def parentgen(c):
             while c:
                 yield c
                 c = c.parent
        result = [element for element in parentgen(c)]
        result.reverse()
        return result

    openList.add(current)
    while openList:
        current = sorted(openList, key=lambda inst:inst.H)[0]
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                openList.add(tile)
                tile.parent = current
    return []