我从事 2D 自上而下的射击游戏已经有一段时间了，我已经实现了大部分游戏并在 JOGL 中从头开始编写引擎，但我遇到了一个小问题，并希望让其他人了解如何做到最好接近问题。所以我在地图中的随机位置生成了小兵，每个小兵都使用 A* 寻路，它已经过优化以最大程度地减少不必要的检查，但地图很大，可以是 10x10 到 200x200 瓷砖的任何东西，唯一的就是放慢速度大大降低游戏的是AI，我还尝试实施基于距离的解决方案，其中小兵空闲直到我处于一定范围内，但这仍然会大大减慢游戏速度，因为产生了很多小兵。任何意见，将不胜感激。
问问题
86 次
1 回答
1
有很多方法可以加速你的代码。
首先 - 可以使用 A* 算法的许多修改，例如：
- 分层A*，这是游戏中常用的方法，其中地图在许多分辨率级别上进行分析，从“总体规划”到“本地路径搜索” http://aigamedev.com/open/review/near-optimal-分层寻路/
- Jump Point Search A*，对于有大量开放空间的地图（如 RPG 游戏），可显着加快 A* http://gamedev.tutsplus.com/tutorials/implementation/speed-up-a-star-pathfinding-with-跳转点搜索算法/
其他修改可能更针对应用程序，如果您的小兵正在搜索玩家的路径（所有小兵都有一个目标），那么您可以将搜索更改为以下算法之一：
- 使用 Dijkstra 算法计算玩家到地图中每个点的距离，对于 200x200，它将非常快（使用
O(nlgn)算法 40,000 个顶点），并且只需将您的小兵移动到与玩家距离小于当前距离的任何相邻点 - 一旦找到路径，从玩家到任何小兵（例如具有最低 id）运行 A* 搜索 - 将目标更改为下一个小兵但不要重置算法本身，如果使用已经计算的路径和距离（因为它们是已经是玩家的最佳路径），显然 - 如果在执行期间您遇到另一个蠕变然后您的目标 - 您只需记录它（找到的路径是最佳的）。
另一种可能的修改，如果你的地图是特定的（包含门/入口到它的某些部分），可以应用它是放置触发器，它“启用”小兵 AI。这是O(1)解决方案，但需要特定类型的地图。
最后一个想法是实施一些次优的解决方案，例如：
- 首先，计算每个蠕变的 A*
- 如果到玩家的距离小于某个阈值
T，那么在下一次迭代中 - 重新计算你的路径，所以没有滞后 - 否则 - 在另一个路径搜索之前按照你的路径至少 10-50 次迭代
还有无数的优化，但我们需要有关您的游戏的更多详细信息以及您希望在这些优化上花费的时间。
于 2013-08-20T16:01:47.260 回答