Python - 加速 A Star 寻路算法 [英] Python - Speed up an A Star Pathfinding Algorithm

问题描述

我已经编写了我的第一个稍微复杂的算法，一个 A Star Pathfinding算法.我遵循了一些关于实现图的 Python.org 建议，因此字典包含所有节点每个节点也是链接的.现在，由于这完全是为了游戏，每个节点实际上只是节点网格中的一个图块，因此我是如何制定启发式方法的，并且我偶尔会参考它们.

I've coded my first slightly-complex algorithm, an implementation of the A Star Pathfinding algorithm. I followed some Python.org advice on 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.

多亏了 timeit，我知道我可以每秒成功运行这个函数一百多次.可以理解，这让我有点不安，因为没有任何其他游戏内容"，例如图形或计算游戏逻辑.所以我很想看看你们中是否有人可以加速我的算法，我完全不熟悉 Cython 或者它的亲属，我不会写一行 C.

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.

废话不多说，这是我的 A Star 函数.

Without any more rambling, here is my A Star function.

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

推荐答案

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

An easy optimization is to use sets instead of lists for the open and closed sets.

openSet   = set()
closedSet = set()

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

This will make all of the in and not in tests O(1) instead of O(n).

这篇关于Python - 加速 A Star 寻路算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！