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

Accepted answer
Score: 39

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).

Score: 10

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 []
``````
Score: 5

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 []
``````

More Related questions