我一直在开发一款2D俯视角射击游戏，我已经实现了大部分游戏内容，并从头开始使用JOGL编写了引擎，但我在开发过程中遇到了一些小问题，想听听大家对如何最好地解决这个问题有什么看法。我的地图上随机位置会生成小怪，每个小怪都使用A*路径查找算法，我已经对其进行了优化以减少不必要的检查，但地图非常大，从10×10到200×200不等，唯一显著拖慢游戏速度的就是AI。我还尝试过实现一种基于距离的解决方案，让小怪在进入一定范围内之前保持空闲，但由于生成的小怪数量众多，这仍然会大大拖慢游戏速度。任何建议都将不胜感激。
回答：
有许多方法可以加速你的代码。
首先 – A*算法有很多变体，可以使用，例如：
- 层次A*，这是一种在游戏中常用的方法，其中地图在多个分辨率级别上进行分析，从“总体规划”到“局部路径搜索” http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/
- 跳点搜索A*，对于有很多开放空间的地图（如RPG游戏）可以显著加速A* http://gamedev.tutsplus.com/tutorials/implementation/speed-up-a-star-pathfinding-with-the-jump-point-search-algorithm/
其他修改可能更具体应用于你的情况，如果你的小怪是在寻找通往玩家的路径（所有小怪有一个共同的目标），那么你可以将你的搜索改为以下算法之一：
- 使用Dijkstra算法计算从玩家到地图上每个点的距离，对于200×200的地图，这将非常快（40,000个顶点，
O(nlgn)算法），然后简单地将你的小怪移动到距离玩家比当前位置更近的任何相邻点 - 从玩家开始运行A*搜索到任何一个小怪（例如，ID最低的小怪），一旦找到路径 – 将目标改为下一个小怪，但不要重置算法本身，让它使用已经计算出的路径和距离（因为它们已经是从玩家到小怪的最优路径），显然 – 如果在执行过程中遇到另一个小怪而不是你的目标 – 你只需记录它（找到的路径是最优的）。
另一种可能的修改，如果你的地图有某种特定性（包含门/入口通往某些部分），可以设置触发器来“启用”小怪的AI。这是一个O(1)的解决方案，但需要特定类型的地图。
最后一个想法是实现一些次优解决方案，例如：
- 首先，为每个小怪计算A*
- 如果到玩家的距离小于某个阈值
T，那么在下一次迭代中重新计算路径，以避免延迟 - 否则 – 在进行下一次路径搜索之前，至少跟随当前路径10-50次迭代
还有无数更多的优化方法，但我们需要更多关于你的游戏的细节以及你希望花在这些优化上的时间。
