Python - 加速星寻路算法

Question

我编写了我的第一个稍微复杂的算法,即A Star Pathfinding算法的实现.我遵循了一些关于实现图形的Python.org建议,因此字典包含每个节点都链接的所有节点.现在,因为这是游戏的全部,每个节点实际上只是节点网格中的一个区块,因此我如何计算启发式和偶尔引用它们.

感谢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

Answer 1

一个简单的优化是使用集合而不是列表来打开和关闭集合.

openSet   = set()
closedSet = set()

这将使所有in和not in测试O(1)而不是O(n).

Answer 2

我会使用已经说过的集合,但我也会使用堆来查找最小元素(将是下一个元素current).这将需要保持openSet和openHeap,但内存不应该是一个问题.另外,在O(1)中设置插入,在O(log N)中设置插值,这样它们就会很快.唯一的问题是heapq模块并没有真正使用它的密钥.就个人而言,我只是修改它来使用密钥.这应该不是很难.或者,您可以在堆中使用(tile.H,tile)元组.

另外,我会遵循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

我把返回路径放在最后,因为它似乎应该来自你的代码.

这是使用集合,堆和最后代码的最终代码:

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

如上所述,制作closedSet成套.

我尝试编码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

但是,你仍然需要搜索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 []