海量星体寻路

Question

我正在尝试用Javascript创建一个塔防御游戏。

除了寻路之外，一切都很顺利..

我使用的是来自这个网站的astar代码：http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript，它使用二进制堆(我认为这是相当优化的)

我遇到的问题是，我想让人们阻止“攻击者”的路径。这意味着每个“攻击者”需要能够自己找到出口的方法(因为有人可以截断单个“攻击者”，而它需要找到自己的出口)。现在5/6攻击者可以在任何时间进行路径查找，而不会出现任何问题。但是假设10+攻击者的路径被阻塞，那么所有10个攻击者都需要同时启动它的寻路脚本，这将使FPS下降到大约每秒1/2。

对于任何在任何时候都有很多实体寻路的人来说，这肯定是一个常见的问题，所以我想一定有比我的方法更好的方法。

所以我的问题是:以最有效的方式向多个“机器人”实现大规模寻路算法的最佳方式是什么？

谢谢,

詹姆斯

Answer 1

使用反对象，这是获得廉价寻路的唯一方法，afaik：http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

反对象基本上意味着，你将拥有一个绑定到你的游戏地图上的“群ai"，而不是机器人拥有单独的ai。

附言:这里是另一个关于寻路的链接(可能是可用的最好的在线参考)：http://theory.stanford.edu/~amitp/GameProgramming/index.html

Answer 2

只需缓存结果即可。

将路径作为值存储在哈希表(对象)中，给每个节点一个UUID，连接UUID以形成唯一的哈希表关键字，并将路径插入其中。

当您从哈希表中检索到路径时，遍历该路径，并查看它是否仍然有效，如果不是，则重新计算并将新的路径插入其中。

您可以进行许多优化:)

就像c69说的，蜂群AI或蜂群思想出现在脑海中:P