我正在使用python中的实时等距RPG，并希望将移动设备作为平台 . 我遇到困难的主要领域是我的寻路 . 我尝试了一些算法，包括A *和一些调整，以更好地适应我正在使用的 Map .
我对我的算法结果很满意 - 它们在确定性的同时给出了一些智能的错觉，并且在任一方向上都是一致的，这样两个以两个角色为目标的角色就会在中间碰撞 .
我的问题是虽然结果在PC上看起来很好，我可以要求所有的处理能力，在我的手机上它是另一个故事，并且在计算算法时通常会有第二次或更多延迟 . 出于这个原因，我正在考虑用C编写的性能最密集的代码为此编写一个库，但是如果有一个现有的解决方案，或者更好的方法我可以做到这一点，我会全力以赴 .
我偶然发现了python-pathfinding但这似乎比我为自己的用例构建的要慢 .
我的用例：
我的 Map 是由水平建造的，这些水平被墙壁（可见或不可见）包围，并且必须通过门（可见或不可见）链接 .
我目前的方法是有两种不同的算法：
-
在一个房间内，我将单个图块搜索为节点，每个边界作为等成本边缘，在目标位置的方向上使用深度优先
-
在每个门都是节点的房间之间 . 使用第一算法计算通过房间（从门到门）的最短路径，并将其存储在哈希表中作为这些节点之间的边缘成本 . 然后计算可以遍历从一个节点到另一个节点的边集，并将其存储在散列表中，并且不允许在同一路径中多次包含相同的边 .
我在启动时产生了一个单独的过程，它使用第一个算法生成第二个算法的图形，这解决了我的许多问题，房间往往相对较小，因此保留了即时路径查找的惩罚低于其他情况，然后长距离：
-
第一种算法用于计算从当前位置到当前房间中每扇门的距离 .
-
第一种算法用于计算目标房间内每扇门到目标位置的距离 .
-
第二算法的输出用于获取房间之间的路径集
-
这些费用加到了第一扇门和最后一扇门的费用上
-
解决方案集按成本排序，使得相同成本的路径顺序始终保持一致
-
选择了解决方案集中的第一项 .
4 回答
首先，我知道一个非常有效和通用的库来处理A *搜索算法 . 这是lib2dp . 您可以轻松地将python生成的图形插入此库并获得快速答案 .
其次，A *基本上很适合找到最佳路径：
您有关于周围环境的完美和完整信息 .
您的周围被视为'static' .
如果您违反其中一条规则，您可能需要考虑一种名为“D*”的替代算法 .
当然，这在性能方面具有巨大的成本 . 因此，您可以找到最适合您的计划的权衡 .
如果你可以将你的游戏环境缩小为图形，那么http://networkx.lanl.gov/有很多很好的内置算法用于此类事情 .
如果您已经拥有一个python版本，那么为什么不通过py2cmod运行它？这应该可以让你获得当前算法的c版本 .
另一种选择是psyco，虽然它有很高的开销 .
您可能想要查看libtcod和
libtcodpyPython包装器 . 但就个人而言，我不是非常Pythonic，是一个不必要的单片脚本，过多使用函数名前缀（至少，我最后一次使用它） . 我在某一点重构了包装并为Python 3修复了它，但那是一年前的事情，所以事情可能已经发生了变化 .