A.I. that can navigate a randomly generated 2D city

Question

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).

Answer 1

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!