Python的 - 加快一个A星寻路算法 [英] Python - Speed up an A Star Pathfinding Algorithm

问题描述

我有codeD我的第一个稍微复杂的算法，阿星寻路的实现算法。我跟一些 Python.org建议上实现图形这么一本字典包含了所有每个节点都连接得节点。现在，因为这是所有游戏中，每个节点是在节点的格真的只是一瓦，所以我是如何工作了启发和我偶尔提到他们。

由于timeit我知道，我可以运行该功能成功多一点，第二个一百倍。可以理解的是这让我有点不安，这是没有任何其他的游戏东西正在进行，如图形或计算游戏逻辑。所以我很乐意看到是否有任何可以加速我的算法，我完全不熟悉用Cython或它的亲属，我可以在c不是codeA行。

在没有任何更多的散漫，这里是我的阿星的功能。

 高清爱仕达（自我，图，目前，结束）：
    openList = []
    closedList = []
    路径= []

    高清retracePath（三）：
        path.insert（0，C）
        如果c.parent ==无：
            返回
        retracePath（c.parent）

    openList.append（电流）
    同时的len（openList）不为0：
        电流=分钟（openList，键=拉姆达研究所：inst.H）
        如果目前的==结束：
            返回retracePath（电流）
        openList.remove（电流）
        closedList.append（电流）
        瓷砖在图[当前]：
            如果瓷砖没有closedList：
                tile.H =（ABS（end.x-tile.x）+ ABS（end.y-tile.y））* 10
                如果瓷砖没有openList：
                    openList.append（瓦）
                tile.parent =电流
    返回路径
 

解决方案

这是很容易的优化是使用套，而不是列出了开放式和封闭式套。

  openSet =集（）
closedSet =集（）
 

这将使所有和不是测试O（1）而不是O（<我> N ）。

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.

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.

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()

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

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