人工智能可以在随机生成的 2D 城市中导航 [英] A.I. that can navigate a randomly generated 2D city

问题描述

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

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

解决方案

您正在寻找一类名为 寻路算法.您可以使用多种方法.

这里的经典算法是 Dijkstra 算法 和 A* 搜索，它可以将对象沿着最优路径从一个位置引导到另一个位置.这些算法的工作原理是将 2D 世界建模为 graph，然后找到最短路径从对象的起始位置到该图中的目标位置.这两种算法广泛用于人工智能和寻路，我强烈建议花时间阅读更多关于它们的信息.如果您愿意，可以在线获取关于 A* 搜索的可靠教程.>

如果您有许多不同的对象需要移动到一个目标而不干扰，您可能需要研究潜在的领域，它提供了一个简单而灵活的框架，可以让多个对象接近一个目标.伯克利Overmind"星际争霸 AI 使用了这种方法，并且经常用于机器人运动规划.直观地说，这种方法的工作原理是为每个位置分配一个电位"值，然后让物体从高电位移动到低电位，直到它们击中目标.这种方法要正确处理有点棘手，但一旦奏效，它往往会导致行为智能的灵活、可定制的 AI.

希望这有帮助！

I'm writing an iOS game (Using UIView), which has a randomly generated 2D city. I need attacking A.I., that will take an intelligent path to find the player (without colliding with buildings). Can someone point me in the right direction as to what kind of algorithms I would use to achieve this?

Edit: I've decided to use A*. I will create a grid on the map, test every grid intersection point, if that point is inside a building, I'll invalidate the point. The attacking A.I. player will then move from its current location, to a valid grid point, which is closer to its goal (within a certain radius of its location).

解决方案

You are looking for a class of algorithms called pathfinding algorithms. There are many approaches you can use.

The classic algorithms here are Dijkstra's algorithm and A* search, which can guide an object from one location to another along the optimal path. These algorithms work by modeling the 2D world as a graph and then finding the shortest path from the object's start location to the destination location in that graph. These two algorithms are used extensively in AI and pathfinding, and I would strongly suggest investing the time to read more about them. There is a solid tutorial on A* search available online if you'd like.

If you have many different objects that need to move to a target without interfering, you may want to look into potential fields, which give a simple and flexible framework for having multiple objects approach a target. This approach was used by the Berkeley "Overmind" StarCraft AI, and is often used in robot motion planning. Intuitively, this approach works by assigning a "potential" value to each location, then having the objects keep moving from high potential to low potential until they hit the target. This approach is a bit trickier to get right, but once it works it tends to lead to flexible, customizable AI that behaves intelligently.

Hope this helps!

这篇关于人工智能可以在随机生成的 2D 城市中导航的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！