我正在开发一款2D的实时策略游戏，类似于《部落冲突》。这款游戏很酷，对吧？但我在路径查找方面遇到了问题。通常，我会在玩家通过触摸屏幕放置单位时进行一次路径查找算法计算，但在某些情况下，这会导致性能下降，当单位数量突然增加时，你的手机会变得非常热。

实际上，无论我使用哪种路径查找算法，例如A*、Dijkstra或其他特殊（可能是最优）的算法，整个游戏循环中这都是一个耗时的过程，尤其是在处理大量单位的低性能移动CPU上。据我所知，像这样的游戏，最短路径并不是重点（人们会在意单位走过的路径吗？），而是高效且自然的路径查找。因此，我想到了一些解决方案，可能不太实际。

解决方案1：使用一些更便宜的路径查找算法，可以是与图相关的或其他，因为最短路径并不重要。

解决方案2：对AI模块进行限制，以处理单位的路径查找，例如在一定时间间隔内对路径查找算法调用设置上限，也就是说，只有一两个单位进行路径规划，其余单位在几帧后再进行规划。正如你所知，其缺点是显而易见的。

以上是我所想的。希望你们这些游戏开发有纪律的人能给我一些绝妙的想法和技巧，我将不胜感激。非常感谢你们。

编辑：这是我相关的伪代码，以及与我的游戏逻辑对应的过程。//在逻辑线程内procedure putonagent if (需要在世界空间中放置单位) //为单位进行标准的A*路径查找 path_list=do_aStar_path_finding(attacktargetpos,startpos); 然后将path_list入队;......endpath_list的队列最终由视觉单位用于前进。有什么提示吗？

回答：

查找“层次路径查找”。假设你要开车去一个远方的城市，你不会在上车前就规划好整个路径！

路径查找通常是分步骤进行的，不是一次函数调用，经过N次迭代后它会返回（并指示它未完成），以便在下一个可用时间运行。基本上，与其考虑带有局部变量的函数，不如考虑operator()和作为类成员的状态变量。

为了使其快速，你可以使用A*路径查找中的粗略启发式假设，假设我使用10倍直线距离的启发式假设，它可能不会找到最短路径，但它会强烈倾向于朝向目标前进，而不是“展开”并探索更远的封闭区域。