5

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

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Sosumi
  • 759
  • 6
  • 20

2 Answers2

6

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!

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
2

This question here: Pacman: how do the eyes find their way back to the monster hole? is a good survey of approaches to AI navigation of a random 2D grid in search of a moving player. The general consensus (and the approach used by Pacman) is not to worry about baking intelligent pathfinding algorithms in the AI, but instead to use the map itself to store information agout the location of the player. It's a fascinating read, particularly the second and third answers (and their external links) by ammoQ and Dan Vinton.

This link here Pacman scent antiobject pattern describes a cheap and effective approach.

Community
  • 1
  • 1
Tim
  • 5,024
  • 2
  • 30
  • 58
  • While I agree that this is a good approach, if the world is randomly-generated then you can't hardcode anything into the world and will need to use more complex algorithms to do the initial pathfinding. This also won't work if the player is constantly moving around unless you store a *lot* of extra information. – templatetypedef Jan 22 '12 at 21:59
  • Sorry @templatebydef, I was referring the questioner to the second and third links rather than the linked question's existing solution or the accepted answer - both of which do indeed suffer from the problems you point out. I have updated my question with a link to the interesting approach I want the OP to look at. – Tim Jan 22 '12 at 22:05