java - 最大限度地减少 gme 中的 AI 使用

Question

我一直在开发 2D 自上而下的射击游戏，我已经实现了游戏的大部分内容，并在 JOGL 中从头开始编写了引擎，但我遇到了一个小问题，想了解其他人的看法如何最好地解决问题。所以我让小兵在 map 中的随机位置生成，并且每个小兵都使用 A* 路径查找，它已经过优化以最大程度地减少不必要的检查，但 map 很大，可以是从 10x10 到 200x200 瓷砖的任何东西，唯一会减慢速度的东西游戏的显着下降是人工智能，我还尝试实现一种基于距离的解决方案，其中小兵空闲直到我处于一定范围内，但这仍然会大大减慢游戏速度，因为产生了很多小兵。任何建议将不胜感激。

Answer 1

有多种方法可以加快代码速度。

首先 - A* 算法有很多修改，可以使用，例如:

• 分层A*，这是游戏中经常使用的方法，在多个分辨率级别上分析 map ，从“总体规划”到“局部路径搜索” http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/
• 跳跃点搜索 A*，对于具有大量开放空间的 map (例如 RPG 游戏)，可显着加快 A* 速度 http://gamedev.tutsplus.com/tutorials/implementation/speed-up-a-star-pathfinding-with-the-jump-point-search-algorithm/

其他修改可能更具体于应用程序，如果您的 Creep 正在搜索通往玩家的路径(所有 Creep 都有一个目标)，那么您可以将搜索更改为以下算法之一:

• 使用 Dijkstra 算法计算玩家到 map 中每个点的距离，对于 200x200 来说会非常快(使用 O(nlgn) 算法计算 40,000 个顶点)，并且只需将你的小兵移动到与玩家距离小于当前点的任何相邻点
• 从玩家到任何 Creep(例如具有最低 ID)运行 A* 搜索，一旦找到路径 - 将目标更改为下一个 Cree，但不要重置算法本身，让 if显然，使用已经计算出的路径和距离(因为它们已经是玩家的最佳路径) - 如果在执行过程中遇到另一个蠕变，那么你的目标 - 你只需记录它(找到的路径是最佳的)。

如果您的 map 在某种程度上是特定的(包含某些部分的门/入口)，则可以应用另一种可能的修改，即放置触发器，“启用”小兵人工智能。这是 O(1) 解决方案，但需要特定类型的 map 。

最后一个想法是实现一些次优解决方案，例如:

• 首先，计算每个 Creep 的 A*
• 如果到玩家的距离小于某个阈值T，则在下一次迭代中 - 重新计算您的路径，因此不会出现延迟
• 否则 - 在进行另一次路径搜索之前，请遵循您的路径至少 10-50 次迭代

还有无数的优化，但我们需要有关您的游戏的更多详细信息以及您希望在这些优化上花费的时间。