javascript - 群星寻路

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

反对象基本上意味着您将拥有一个绑定(bind)到您的游戏 map 的“群体 ai”，而不是拥有单独 ai 的机器人。

---

p.s.:这是另一个关于一般寻路的链接(可能是最好的在线引用): http://theory.stanford.edu/~amitp/GameProgramming/index.html