Python - 加速 A Star 寻路算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4159331/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python - Speed up an A Star Pathfinding Algorithm
提问by DizzyDoo
I've coded my first slightly-complex algorithm, an implementation of the A Star Pathfindingalgorithm. I followed some Python.org adviceon 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.
我已经编写了我的第一个稍微复杂的算法，A Star Pathfinding算法的实现。我遵循了Python.org关于实现图的一些建议，因此字典也包含每个节点链接的所有节点。现在，由于这完全是为了游戏，每个节点实际上只是节点网格中的一个图块，因此我如何制定启发式方法以及我偶尔对它们的引用。
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.
多亏了 timeit，我知道我可以每秒成功运行这个函数一百多次。可以理解，这让我有点不安，因为没有任何其他“游戏内容”，例如图形或计算游戏逻辑。所以我很想看看你们中是否有人可以加快我的算法，我完全不熟悉 Cython 或者它的亲属，我无法编写一行 C 代码。
Without any more rambling, here is my A Star function.
废话不多说，这是我的 A Star 函数。
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
采纳答案by John Kugelman
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 inand not intests O(1) instead of O(n).
这将使所有in和not in测试 O(1) 而不是 O( n)。
回答by hughdbrown
As suggested above, make closedSetinto a set.
如上所述，制作closedSet成一套。
I tried coding openListas a heap import heapq:
我尝试编码openList为堆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:
但是，您仍然需要搜索if tile not in openList，所以我会这样做：
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 []
回答by Justin Peel
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.
我会像上面说的那样使用集合，但我也会使用堆来找到最小元素（将是下一个元素current）。这需要同时保留一个 openSet 和一个 openHeap，但内存应该不是问题。此外，在 O(1) 中设置插入并在 O(log N) 中设置堆，因此它们会很快。唯一的问题是 heapq 模块并没有真正使用密钥。就个人而言，我只会修改它以使用密钥。应该不是很难。或者，您可以只在堆中使用 (tile.H,tile) 的元组。
Also, I would follow aaronasterling's idea of using iteration instead of recursion, but also, I would append elements to the end of pathand reverse pathat 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:
此外，我会遵循 aaronasterling 的使用迭代而不是递归的想法，而且，我会将元素附加到末尾path并path在末尾反转。原因是在列表的第 0 个位置插入一个项目非常慢（我相信是 O(N)），而如果我没记错的话，追加是 O(1)。该部分的最终代码将是：
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 []
