algorithm - 人工智能可以导航随机生成的二维城市

Question

我正在编写一个 iOS 游戏(使用 UIView)，其中有一个随机生成的 2D 城市。我需要攻击 A.I.，它将采取智能路径找到玩家(不会与建筑物发生碰撞)。有人可以指出我将使用哪种算法来实现这一目标的正确方向吗？

编辑:我决定使用 A*。我将在 map 上创建一个网格，测试每个网格交点，如果该点在建筑物内，我将使该点无效。攻击性的 A.I.然后玩家将从其当前位置移动到更接近其目标的有效网格点(在其位置的特定半径内)。

Answer 1

您正在寻找一类名为 pathfinding algorithms 的算法.您可以使用多种方法。

这里的经典算法是Dijkstra's algorithm和 A* search ，它可以沿着最佳路径将物体从一个位置引导到另一个位置。这些算法通过将 2D 世界建模为 graph 来工作。然后在该图中找到从对象的起始位置到目标位置的最短路径。这两种算法广泛用于 AI 和寻路，我强烈建议花时间阅读更多有关它们的信息。有一个 solid tutorial on A* search如果您愿意，可以在线获取。

如果您有许多不同的对象需要在不干扰的情况下移动到目标，您可能需要查看势场，这为让多个对象接近目标提供了一个简单而灵活的框架。 the Berkeley "Overmind" StarCraft AI 使用了这种方法, 常用于机器人运动规划。直观地说，这种方法的工作原理是为每个位置分配一个“潜在”值，然后让对象不断从高潜力移动到低潜力，直到它们击中目标。这种方法要正确使用起来有点棘手，但一旦它奏效，它往往会带来灵活、可定制且行为智能的 AI。

希望这对您有所帮助!