[ACCEPTED]-Python - Speed up an A Star Pathfinding Algorithm-a-star

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

openSet   = set()
closedSet = set()

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

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

Also, I 11 would follow aaronasterling's idea of using 10 iteration instead of recursion, but also, I 9 would append elements to the end of path and 8 reverse path at the end. The reason is that 7 inserting an item at the 0th place in a 6 list is very slow, (O(N) I believe), while 5 appending is O(1) if I recall correctly. The 4 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 3 return path at the end because it appeared 2 that it should from your code.

Here's the 1 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 []

As suggested above, make closedSet into a set.

I tried 2 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 1 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 []