是否有用于python的可用路径查找库？

Question

我正在研究python中的实时等距RPG，并希望将移动设备作为一个平台。我遇到困难的主要领域是我的寻路。我尝试了一些算法，包括A*和一些调整，以更好地适应我正在使用的地图。

我对我的算法的结果很满意--它们在确定性的同时给出了一些智能的错觉，并且在任何一个方向上都是一致的，这样两个字符以对方的位置为目标就会在中间发生碰撞。

我的问题是，在我所能要求的所有处理能力的PC上，结果看起来不错，但在我的手机上，情况就完全不同了，在计算算法时，通常会有一秒钟或更长的延迟。出于这个原因，我正在考虑用C编写性能最密集的代码来编写一个库，但是如果有一个现有的解决方案，或者更好的方法，我会全神贯注的。

我偶然发现了python-寻路，但这似乎比我自己为用例构建的要慢。

我的用例：

我的地图是建立在水平，是由墙壁包围(可见的或无形的)，必须通过门连接(可见或无形)。

我目前的方法是有两种不同的算法：

• 在一个房间内，我搜索单个瓷砖作为节点，每个边界作为一个等价线，使用深度优先于目标位置的方向。
• 每扇门都是一个节点的房间之间。使用第一种算法计算房间(从门到门)的最短路径，并将其存储在哈希表中，作为节点之间的边缘成本。然后计算可以遍历以从一个节点获取到另一个节点的边缘集，并将其存储在哈希表中，并且不允许在同一路径中多次包含相同的边缘。

我在启动时生成了一个单独的进程，使用第一个算法生成第二个算法的图形，这解决了我的许多问题，房间往往相对较小，因此对飞行路径查找的惩罚比其他方法要低，然后对于更远的距离：

• 第一种算法用于计算从当前位置到当前房间中每个门的距离。
• 第一种算法用于计算目标房间内每扇门到目标位置的距离。
• 第二种算法的输出用于获取房间间的路径集。
• 这些费用加到第一扇门和最后一扇门的费用之外。
• 解决方案的集合按成本排序，使得相同成本的路径顺序总是一致的。
• 选择一组解决方案中的第一项。

Answer 1

首先，我知道一个非常有效的通用库来处理A*搜索算法。是lib2dp。您可以很容易地将您生成的python图形插入到这个库中，并得到一个快速的答案。

第二，从本质上说，A*很好地找到了一条最优的路径：

• 你拥有关于你周围环境的完美和全面的信息。
• 你的周围被认为是“静态的”。

如果您违反了这些规则之一，您可能需要考虑另一种名为“*”的算法。

当然，这在性能方面有很大的成本。所以，这取决于你为你的计划找到最好的权衡。

Answer 2

如果您可以将您的游戏环境简化为一个图形，那么http://networkx.lanl.gov/就有许多很好的内置算法用于这类事情。

Answer 3

如果您已经有了一个您满意的python版本，那么为什么不通过py2cmod运行它呢？这将使您获得当前算法的c版本。

另一种选择是精神科，尽管它的开销很高。