我编写了我的第一个稍微复杂的算法,这是A Star Pathfinding算法的一个实现 . 我在实现图形时遵循了一些Python.org advice,因此字典包含每个节点也链接的所有节点 . 现在,因为这是游戏的全部,每个节点实际上只是节点网格中的一个区块,因此我如何计算启发式和偶尔引用它们 .
感谢timeit我知道我可以成功运行这个功能一秒钟一百多次 . 可以理解这让我有点不安,这是没有任何其他'游戏的东西'继续下去,如图形或计算游戏逻辑 . 所以我很想知道你们中是否有人可以加速我的算法,我完全不熟悉Cython或者它的亲属,我不能编写一行C.
没有更多的漫步,这是我的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
3 回答
一个简单的优化是使用集合而不是列表来打开和关闭集合 .
这将使所有
in
和not in
测试O(1)而不是O(n) .我会使用已经说过的集合,但我也会使用堆来查找最小元素(将是下一个
current
) . 这将需要保持openSet和openHeap,但内存不应该真正使用它来使用键 . 就个人而言,我只是修改它来使用密钥 . 这应该不是很难 . 或者,您可以在堆中使用(tile.H,tile)元组 .另外,我会遵循aaronasterling的使用迭代而不是递归的想法,但是,我会将元素追加到
path
的末尾并在最后反转path
. 原因是在列表中的第0位插入一个项目非常慢,(我相信是O(N)),而如果我没记错的话,追加是O(1) . 该部分的最终代码是:我把返回路径放在最后,因为它似乎应该来自你的代码 .
这是使用集合,堆和最后代码的最终代码:
如上所述,将
closedSet
设为一个集合 .我尝试将
openList
编码为堆import heapq
:但是,你仍然需要在
if tile not in openList
搜索,所以我会这样做: