在功能较弱的设备上，是否有任何移动游戏(例如rts)的路径查找技巧和策略？

Question

我正在开发一个2d游戏，rts游戏，有点像COC (部落冲突)。很酷的手机游戏哈。但是我在路径查找方面遇到了一些问题，就像往常一样，当每个代理都被用手指触控放置在屏幕的某个位置时，我就会执行路径查找算法，但在某些情况下，这会导致性能损失，而且当代理突然同时增加时，您的手机会变得非常热。

实际上，无论我使用什么路径查找，例如a*，dijkstra，或者一些特殊的(可能是最优的)，它总是在整个游戏循环中消耗时间，特别是在不太强大的移动cpu上的大量代理。据我所知，像这样的游戏，最短路径不是焦点(人们会关心路径代理故意通过吗？)而不是高效自然地寻找路径。所以我想出了一些解决办法，也许是不切实际的。

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

解决方案2:对ai模块进行路径查找，例如对路径查找算法调用的上限，即这些代理的一个或两个代理得到了规划，让其余的代理在几个游戏帧后规划。正如你所知，它的缺点是显而易见的。

以上就是我所想的。希望你的游戏开发人员能给我一个绝妙的主意，技巧，我会学的。非常感谢。

编辑:这是我的相关伪代码，以及我的游戏逻辑的过程。path_list的队列最终被可视代理用来向前移动的//inside logic thread procedure putonagent if (need to put agent on world space) //do standard a* path-finding for an agent path_list=do_aStar_path_finding(attacktargetpos,startpos); and then enqueue path_list; ...... end。有什么暗示吗？

Answer 1

查一查“分层寻路”，说你要开车去一个很远的城市，你没有在上车前规划整个道路！

路径查找通常是分步骤进行的，就像它不是一个函数调用一样，经过N次迭代之后，它将返回(并表明它还没有完成)，因此可以在下一个可用时间运行它。基本上，与使用局部变量的函数不同，operator()和state变量是类的成员。

为了使它更快，你可以用A*寻路来做启发式的废话，假设我使用了一个10*的启发式算法，它可能找不到最短的路径，但它会有一个强烈的偏好，去目标的方向，而不是“扇出”，在封闭的区域进一步探索。