34

我编写了我的第一个稍微复杂的算法，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
4

3 回答 3

39

一个简单的优化是对开集和闭集使用集合而不是列表。

openSet   = set()
closedSet = set()

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

于 2010-11-11T21:19:46.183 回答
10

我会使用已经说过的集合，但我也会使用堆来找到最小元素（将是下一个元素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 []
于 2010-11-12T00:23:51.160 回答
5

如上所述，做成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 []
于 2010-11-11T21:53:51.997 回答