the*_*oom 12 c python performance path-finding
我正在使用python中的实时等距RPG,并希望将移动设备作为平台.我遇到困难的主要领域是我的寻路.我尝试了一些算法,包括A*和一些调整,以更好地适应我正在使用的地图.
我对我的算法的结果感到满意 - 它们在确定性的同时给出了一些智能的错觉,并且在任一方向上都是一致的,这样两个以两个角色为目标的角色就会在中间碰撞.
我的问题是虽然PC上的结果看起来很好,我可以要求所有的处理能力,在我的手机上它是另一个故事,并且在计算算法时经常会有第二次或更多延迟.出于这个原因,我正在考虑用C编写的性能最密集的代码为此编写一个库,但是如果有一个现有的解决方案,或者更好的方法我可以做到这一点,我会全力以赴.
我偶然发现了python-pathfinding,但这似乎比我为自己的用例构建的更慢.
我的地图是从水平建造的,这些水平被墙壁(可见或不可见)包围,并且必须通过门(可见或不可见)链接.
我目前的方法是有两种不同的算法:
在一个房间内,我将单个图块搜索为节点,每个边界作为等成本边缘,在目标位置的方向上使用深度优先
在每个门都是节点的房间之间.使用第一算法计算通过房间(从门到门)的最短可能路径,并将其存储在哈希表中作为这些节点之间的边缘成本.然后计算可以遍历从一个节点到另一个节点的边集,并将其存储在散列表中,并且不允许在同一路径中多次包含相同的边.
我在启动时产生了一个单独的过程,它使用第一个算法生成第二个算法的图形,这解决了我的许多问题,房间往往相对较小,因此保留了即时路径查找的惩罚低于其他情况,然后长距离: