# iOS Game Development Cookbook (2014)

### Chapter 11. Artificial Intelligence and Behavior

Games are often at their best when they’re a challenge to the player. There are a number of ways for making your game challenging, including creating complex puzzles; however, one of the most satisfying challenges that a player can enjoy is defeating something that’s trying to outthink or outmaneuver them.

In this chapter, you’ll learn how to create movement behavior, how to pursue and flee from targets, how to find the shortest path between two locations, and how to design an AI system that thinks ahead.

**Making an Object Move Toward a Position**

**Problem**

You want an object to move toward another object.

**Solution**

Subtract the target position from the object’s current position, normalize the result, and then multiply it by the speed at which you want to move toward the target. Then, add the result to the current position:

*// Determine the direction to this position*

GLKVector2 myPosition = ... *// the location where we are right now*

GLKVector2 targetPosition = ... *// the location where we want to be*

**float** movementSpeed = ... *// how fast we want to move toward this target*

GLKVector2 offset = GLKVector2Subtract(targetPosition, myPosition);

*// Reduce this vector to be the same length as our movement speed*

offset = GLKVector2Normalize(offset);

offset = GLKVector2MultiplyScalar(offset, self.movementSpeed * deltaTime);

*// Add this to our current position*

GLKVector2 newPosition = self.position;

newPosition.x += offset.x;

newPosition.y += offset.y;

self.position = newPosition;

*Figure 11-1* illustrates the result.

*Figure 11-1. Intercepting a moving object*

**Discussion**

To move toward an object, you need to know the direction that your destination is in. To get this, you take your destination’s position minus your current position, which results in a vector.

Let’s say that you’re located at [0, 5], and you want to move toward [1, 8] at a rate of 1 unit per second. The destination position minus your current location is:

Offset = [1, 8] - [0, 5] = [1, 3]

However, the length (or magnitude) of this vector will vary depending on how far away the destination is. If you want to move toward the destination at a fixed speed, then you need to ensure that the length of the vector is 1, and then multiply the result by the speed you want to move at.

Remember, when you normalize a vector, you get a vector that points in the same direction but has a length of 1. If you multiply this normalized vector with another number, such as your speed, you get a vector with that length.

So, to calculate how far you need to move, you take your offset, normalize it, and multiply the result by your movement speed.

In order to get smooth movement, you’re likely going to run this code every time a new frame is drawn. Every time this happens, it’s useful to know how many seconds have elapsed between the last frame and the current frame (see *Calculating Delta Times*).

To calculate how far an object should move, given a speed in units per second and an amount of time measured in seconds, you just use the time-honored equation:

Speed = Distance ÷ Time

Rearranging, we get:

Distance = Speed × Time

We can now substitute, assuming a delta time of 1/30th of a second (i.e., 0.033 seconds):

Movement speed = 5

Delta time = 0.033

Distance = Movement Speed * Delta Time

= 5 * 0.333

= 1.666

Normalized offset = Normalize(Offset) * Distance

= [0.124, 0.992]

Muliplied offset = Normalized offset * Distance

= [0.206, 1.652]

You can then add this multiplied offset to your current position to get your new position. Then, you do the whole thing over again on the next frame.

This method of moving from a current location to another over time is fundamental to all movement behaviors, since everything else relies on being able to move.

**Making Things Follow a Path**

**Problem**

You want to make an object follow a path from point to point, turning to face the next destination.

**Solution**

When you have a path, keep a list of points. Move to the target (see *Making an Object Move Toward a Position*). When you reach it, remove the first item from the list; then move to the new first item in the list.

Here’s an example that uses Sprite Kit (discussed in *Chapter 6*):

**-** (**void**) moveToPath:(NSArray*)pathPoints {

**if** (pathPoints.count == 0)

**return**;

CGPoint nextPoint = [[pathPoints firstObject] CGPointValue];

GLKVector2 currentPosition =

GLKVector2Make(self.position.x, self.position.y);

GLKVector2 nextPointVector =

GLKVector2Make(nextPoint.x, nextPoint.y);

GLKVector2 toTarget = GLKVector2Subtract(nextPointVector, currentPosition);

**float** distance = GLKVector2Length(toTarget);

**float** speed = 50;

**float** time = distance / speed;

SKAction* moveAction = [SKAction moveTo:nextPoint duration:time];

SKAction* nextPointAction = [SKAction runBlock:^{

NSMutableArray* nextPoints = [NSMutableArray arrayWithArray:pathPoints];

[nextPoints removeObjectAtIndex:0];

[self moveToPath:nextPoints];

}];

[self runAction:[SKAction sequence:@[moveAction, nextPointAction]]];

}

**Discussion**

To calculate a path from one point to another, use a path algorithm (see *Calculating a Path for an Object to Take*).

**Making an Object Intercept a Moving Target**

**Problem**

You want an object to move toward another object, intercepting it.

**Solution**

Calculate where the target is going to move to based on its velocity, and use the move to algorithm from *Making an Object Move Toward a Position* to head toward that position:

GLKVector2 myPosition = ... *// our current position*

GLKVector2 targetPosition = ... *// the current position of the target*

**float** myMovementSpeed = ... *// how fast we're moving*

**float** targetMovementSpeed = ... *// how fast it's moving*

GLKVector2 toTarget = GLKVector2Subtract(targetPosition, myPosition);

**float** lookAheadTime = GLKVector2Length(toTarget) /

(myMovementSpeed + targetMovementSpeed);

CGPoint destination = target.position;

destination.x += targetMovementSpeed * lookAheadTime;

destination.y += targetMovementSpeed * lookAheadTime;

[self moveToPosition:destination deltaTime:deltaTime];

**Discussion**

When you want to intercept a moving object, your goal should be to move to where the target is going to be, rather than where it is right now. If you just move to where the target currently is, you’ll end up always chasing it.

Instead, what you want to do is calculate where the target is going to be when you arrive, by taking the target’s current position and its speed, determining how fast you can get there, and then seeking toward that.

**Making an Object Flee When It’s in Trouble**

**Problem**

You want an object to flee from something that’s chasing it.

**Solution**

Use the “move to” method, but use the reverse of the force it gives you:

GLKVector2 myPosition = ... *// our current position*

GLKVector2 targetPosition = ... *// the current position of the target*

**float** myMovementSpeed = ... *// how fast we're moving*

GLKVector2 offset = GLKVector2Subtract(targetPosition, myPosition);

*// Reduce this vector to be the same length as our movement speed*

offset = GLKVector2Normalize(offset);

*// Note the minus sign - we're multiplying by the inverse of*

*// our movement speed, which means we're moving away from it*

offset = GLKVector2MultiplyScalar(offset, -myMovementSpeed * deltaTime);

*// Add this to our current position*

CGPoint newPosition = self.position;

newPosition.x += offset.x;

newPosition.y += offset.y;

self.position = newPosition;

**Discussion**

Moving away from a point is very similar to moving toward a point. All you need to do is use the inverse of your current movement speed. This will give you a vector that’s pointing in the opposite direction of the point you want to move away from.

**Making an Object Decide on a Target**

**Problem**

You want to determine which of several targets is the best target for an object to pursue.

**Solution**

The general algorithm for deciding on the best target looks like this:

1. Set bestScoreSoFar to the worst possible score (either zero or infinity, depending on what you’re looking for).

2. Set bestTargetSoFar to nothing.

3. Loop over each possible target:

a. Check the score of the possible target.

b. If the score is better than bestScoreSoFar:

i. Set bestTargetSoFar to the possible target.

ii. Set bestScoreSoFar to the possible target’s score.

4. After the loop is done, bestTargetSoFar will either be the best target, or it will be nothing.

This algorithm is shown in code form in the following example. The bestScoreSoFar variable is called nearestTargetDistance; it stores the distance to the closest target found so far, and begins as the highest possible distance (i.e. infinity). You then loop through the array of possible targets, resetting it every time you find a new target nearer than the previous ones:

**float** nearestTargetDistance = INFINITY;

Enemy* nearestTarget = nil;

GLKVector2 myPosition = ... *// the current position*

NSArray* nearbyTargets = ... *// an array of nearby possible targets*

**for** (Enemy* enemy **in** nearbyTargets) {

*// Find the distance to this target*

GLKVector2 = enemy.position;

GLKVector2 toTarget = GLKVector2Subtract(targetPosition, myPosition);

**float** length = GLKVector2Length(toTarget);

*// If it's nearer than the current target, it's the new target*

**if** (length < nearestTargetDistance) {

nearestTarget = node;

nearestTargetDistance = length;

}

}

**Discussion**

It’s worth keeping in mind that there’s no general solution to this problem because it can vary a lot depending on what your definition of “best” is. You should think about what the best target is in your game. Is it:

§ Closest?

§ Most dangerous?

§ Weakest?

§ Worth the most points?

Additionally, it depends on what information you can access regarding the nearby targets. Something that’s worth keeping in mind is that doing a search like this can take some time, if there are many potential targets. Try to minimize the number of loops that you end up doing.

**Making an Object Steer Toward a Point**

**Problem**

You want an object to steer toward a certain point, while maintaining a constant speed.

**Solution**

You can steer toward an object by figuring out the angle between the direction you’re currently heading in and the direction to the destination. Once you have this, you can limit this angle to your maximum turn rate:

*// Work out the vector from our position to the target*

GLKVector2 myPosition = ... *// our position*

GLKVector2 targetPosition = ... *// target position*

**float** turningSpeed = ... *// the maximum amount of turning we can do, in radians*

*// per second*

GLKVector2 toTarget = GLKVector2Subtract(targetPosition, myPosition);

GLKVector2 forwardVector = ... *// the forward vector: rotate [0,1] by whatever*

*// direction we're currently facing*

*// Get the angle needed to turn toward this position*

**float** angle = GLKVector2DotProduct(toTarget, forwardVector);

angle /= acos(GLKVector2Length(toTarget) * GLKVector2Length(forwardVector));

*// Clamp the angle to our turning speed*

angle = fminf(angle, turningSpeed);

angle = fmaxf(angle, -turningSpeed);

*// Apply the rotation*

self.rotation += angle * deltaTime;

**Discussion**

You can calculate the angle between two vectors by taking the dot product of the two vectors, dividing it by the lengths of both, and then taking the arc cosine of the result.

To gradually turn over time, you then limit the result to your maximum turning rate (to stop your object from turning instantaneously), and then multiply *that* by how long you want the turning action to take, in seconds.

**Making an Object Know Where to Take Cover**

**Problem**

You want to find a location where an object can move to, where it can’t be seen by another object.

**Solution**

First, draw up a list of nearby points that your object (the “prey”) can move to.

Then, draw lines from the position of the other object (the “predator”) to each of these points. Check to see if any of these lines intersect an object. If they do, this is a potential cover point.

Then, devise paths from your object to each of these potential cover points (see *Calculating a Path for an Object to Take*). Pick the point that has the shortest path, and start moving toward it (see *Making Things Follow a Path*).

If you’re using Sprite Kit with physics bodies, you can use the enumerateBodiesAlongRayStart:end:usingBlock: method to find out whether you can draw an uninterrupted line from your current position to the potential cover position:

CGPoint myPosition = ... *// current position*

CGPoint coverPosition = ... *// potential cover position*

SKPhysicsWorld* physicsWorld = self.scene.physicsWorld;

__block **BOOL** canUseCover = NO;

[physicsWorld enumerateBodiesAlongRayStart:myPosition end:coverPosition

usingBlock:^(SKPhysicsBody *body, CGPoint point, CGVector normal, **BOOL** *stop) {

**if** (body == self.physicsBody)

**return**;

*// We hit something, so there's something between us*

*// and the cover point. Good!*

canUseCover = YES;

*// Stop looping*

*stop = YES;

}];

**if** (canUseCover) {

*// Take cover*

}

**Discussion**

A useful addition to this algorithm is to make some cover “better” than others. For example, chest-high cover in a shooting game may be worth less than full cover, and cover that’s closer to other, nearby cover may be worth more than an isolated piece of cover.

In these cases, your algorithm needs to take into account both the distance to the cover and the “score” for the cover.

**Calculating a Path for an Object to Take**

**Problem**

You want to determine a path from one point to another, avoiding obstacles.

**Solution**

There are several path-calculation algorithms for you to choose from; one of the most popular is called A* (pronounced “A star”).

To use the A* algorithm, you give it the list of all of the possible waypoints that an object can be at ahead of time, and determine which points can be directly reached from other points. Later, you run the algorithm to find a path from one waypoint to another.

First, create a new class called NavigationNode:

**@interface** **NavigationNode** : **NSObject**

*// The location of the node*

**@property** (assign) CGPoint position;

*// The list of nearby nodes*

**@property** (strong) NSArray* neighbors;

*// The "cost" that would be incurred if the path went through this node*

**@property** (assign) **float** fScore;

*// The "cost" from this point along the best known path*

**@property** (assign) **float** gScore;

*// Return the distance from this node to another node*

**-** (**float**) distanceToNode:(NavigationNode*)node;

*// Return the distance from the node's position to a point*

**-** (**float**) distanceToPoint:(CGPoint)point;

**@end**

**@implementation** **NavigationNode**

*// Return the distance from the node's position to a given point*

**-** (**float**)distanceToPoint:(CGPoint)point {

CGPoint offset;

offset.x = point.x - self.position.x;

offset.y = point.y - self.position.y;

**float** length = sqrt(offset.x * offset.x + offset.y * offset.y);

**return** length;

}

*// Return the distance from the node's position to another node*

**-** (**float**)distanceToNode:(NavigationNode *)node {

**return** [self distanceToPoint:node.position];

}

**@end**

Next, create a second class called NavigationGrid:

**@implementation** **NavigationGrid** {

NSMutableArray* nodes;

}

- (**void**)createNodesWithPoints:(NSArray *)points

maximumNeighborDistance:(**float**)distance {

nodes = [NSMutableArray array];

*// Create the nodes*

**for** (NSValue* pointValue **in** points) {

NavigationNode* node = [[NavigationNode alloc] init];

node.position = pointValue.CGPointValue;

[nodes addObject:node];

}

*// Determine which nodes are neighbors*

**for** (NavigationNode* node **in** nodes) {

NSMutableArray* neighbors = [NSMutableArray array];

**for** (NavigationNode* otherNode **in** nodes) {

**if** (otherNode == node)

**continue**;

*// If the distance to this node is shorter than or the same*

*// as the maximum allowed distance, add this as a neighbor*

**if** ([node distanceToNode:otherNode] <= distance) {

[neighbors addObject:otherNode];

}

}

node.neighbors = neighbors;

}

}

*// Find the nearest node to the given point*

- (NavigationNode*) nearestNodeToPoint:(CGPoint)point {

NavigationNode* nearestNode = nil;

**float** closestDistance = INFINITY;

**for** (NavigationNode* node **in** nodes) {

**float** distance = [node distanceToPoint:point];

**if** (distance < closestDistance) {

closestDistance = distance;

nearestNode = node;

}

}

**return** nearestNode;

}

*// Calculate the path from the origin to the destination*

- (NSArray*) pathFromPoint:(CGPoint)origin toPoint:(CGPoint)destination {

*// First, find the nearest nodes to the origin and end point*

NavigationNode* startNode = [self nearestNodeToPoint:origin];

NavigationNode* goalNode = [self nearestNodeToPoint:destination];

*// Reset the f-scores and g-scores for each node*

**for** (NavigationNode* node **in** nodes) {

node.fScore = 0;

node.gScore = 0;

}

*// The set of nodes that have been evaluated*

NSMutableSet* closedSet = [NSMutableSet set];

*// The set of nodes that should be evaluated, starting with the startNode*

NSMutableSet* openSet = [NSMutableSet setWithObject:startNode];

*// A weak mapping from nodes, used to reconstruct the path*

NSMapTable* cameFromMap = [NSMapTable weakToWeakObjectsMapTable];

*// Loop while there are still nodes to consider*

**while** (openSet.count > 0) {

*// Find the node in the open set with the lowest f-score*

NavigationNode* currentNode =

[[openSet sortedArrayUsingDescriptors:@[[NSSortDescriptor

sortDescriptorWithKey:@"fScore" ascending:YES]]] firstObject];

*// If we've managed to get to the goal, reconstruct a path*

**if** (currentNode == goalNode) {

NSArray* pathNodes =

[self reconstructPath:cameFromMap currentNode:currentNode];

*// Make an array containing just points (instead of NavigationNodes)*

NSMutableArray* pathPoints = [NSMutableArray array];

**for** (NavigationNode* node **in** pathNodes) {

[pathPoints addObject:[NSValue valueWithCGPoint:node.position]];

}

**return** pathPoints;

}

*// Move the current node from the open set to the closed set*

[openSet removeObject:currentNode];

[closedSet addObject:currentNode];

*// Check each neighbor for the next best point to check*

**for** (NavigationNode* neighbor **in** currentNode.neighbors) {

**float** tentativeGScore =

currentNode.gScore + [currentNode distanceToNode:neighbor];

**float** tentativeFScore =

tentativeGScore + [currentNode distanceToNode:goalNode];

*// If this neighbor has already been checked, and using it as part*

*// of the path would be worse, skip it*

**if** ([closedSet containsObject:neighbor] && tentativeFScore >=

neighbor.fScore) {

**continue**;

}

*// If we haven't checked this node yet, or using it would be better,*

*// add it to the current path*

**if** ([openSet containsObject:neighbor] ==

NO || tentativeFScore < neighbor.fScore) {

[cameFromMap setObject:currentNode forKey:neighbor];

*// Update the estimated costs for using this node*

neighbor.fScore = tentativeFScore;

neighbor.gScore = tentativeGScore;

*// Add it to the open set, so we explore using it more*

[openSet addObject:neighbor];

}

}

}

**return** nil;

}

*// Given a point, recursively determine the chain of points that link together*

*// to form a path from the start point to the end point*

- (NSArray*) reconstructPath:(NSMapTable*)cameFromMap

currentNode:(NavigationNode*)currentNode {

**if** ([cameFromMap objectForKey:currentNode]) {

NSArray* path = [self reconstructPath:cameFromMap

currentNode:[cameFromMap objectForKey:currentNode]];

**return** [path arrayByAddingObject:currentNode];

} **else** {

**return** @[currentNode];

}

}

**Discussion**

The A* algorithm is a reasonably efficient algorithm for computing a path from one point to another. It works by incrementally building up a path; every time it looks at a new point, it checks to see if the total distance traveled is lower than that traveled using any of the other potential points, and if that’s the case, it adds it to the path. If it ever gets stuck, it backtracks and tries again. If it can’t find *any* path from the start to the destination, it returns an empty path.

**Finding the Next Best Move for a Puzzle Game**

**Problem**

In a turn-based game, you want to determine the next best move to make.

**Solution**

The exact details here will vary from game to game, so in this solution, we’ll talk about the general approach to this kind of problem.

Let’s assume that the entire state of your game—the location of units, the number of points, the various states of every game object—is being kept in memory.

Starting from this current state, you figure out all possible moves that the next player can make. For each possible move, create a copy of the state where this move has been made.

Next, determine a score for each of the states that you’ve made. The method for determining the score will vary depending on the kind of game; some examples include:

§ Number of enemy units destroyed minus number of my units destroyed

§ Amount of money I have minus amount of money the enemy has

§ Total number of points I have, ignoring how many points the enemy has

Once you have a score for each possible next state, take the top-scoring state, and have your computer player make that next move.

**Discussion**

The algorithm in this solution is often referred to as a *brute force* approach. This can get very complicated for complex games. Strategy games may need to worry about economy, unit movement, and so on—if each unit has 3 possible actions, and you have 10 units, there are over 59,000 possible states that you could end up in. To address this problem, you need to reduce the number of states that you calculate.

It helps to break up the problem into simpler, less-precise states for your AI to consider. Consider a strategy game in which you can, in general terms, spend points on attacking other players, researching technologies, or building defenses. Each turn, your AI just needs to calculate an estimate for the benefit that each general strategy will bring. Once it’s decided on that, you can then have dedicated attacking, researching, or defense-building AI modules take care of the details.

**Determining if an Object Can See Another Object**

**Problem**

You want to find out if an object (the *hunter*) can see another object (the *prey*), given the direction the hunter is facing, the hunter’s field of view, and the positions of both the hunter and the prey.

**Solution**

First, you need to define how far the hunter can see, as well as the field of view of the hunter. You also need to know what direction the hunter is currently facing. Finally, you need the positions of both the hunter and the prey:

**float** distance = 30.0; *// the hunter can see 30 units ahead*

**float** fov = 90; *// the hunter can see 45° to the left and right*

**float** direction = ... *// the direction the hunter is facing*

GLKVector2 hunterPosition = ... *// the hunter's location*

GLKVector2 preyPosition = ... *// the prey's location*

Next, the first test is to calculate how far away the prey is from the hunter. If the prey is further away than distance units, then the hunter won’t be able to see it at all:

**float** preyDistance = GLKVector2Length(hunterPosition, preyPosition);

**if** (preyDistance > distance) {

**return** NO; *// can't see the prey*

}

If the prey is within seeing distance, you then need to determine if the prey is standing within the hunter’s field of view:

**float** directionRadians = GLKMathDegreesToRadians(direction);

GLKVector2 hunterFacingVector =

GLKVector2Make(sin(directionRadians), cos(directionRadians));

GLKVector2 hunterToPrey = GLKVector2Subtract(preyPosition, hunterPosition);

hunterToPrey = GLKVector2Normalize(hunterToPrey);

**float** angleFromHunterToPrey =

acos(GLKVector2DotProduct(hunterFacingVector, hunterToPrey));

**float** angleFromHunterToPreyDegrees =

GLKMathDegreesToRadians(angleFromHunterToPrey);

**if** (fabs(angleFromHunterToPrey) < fov / 2.0) {

**return** YES;

}

**Discussion**

Figuring out if one object can see another is a common problem. If you’re making a stealth game, for example, where the player needs to sneak behind guards but is in trouble if she’s ever seen, then you need to be able to determine what objects the guard can actually see. Objects that are within the field of view are visible, whereas those that are outside of it are not, as shown in *Figure 11-2*.

*Figure 11-2. An example of how the field of view works*

Calculating the distance between objects is very straightforward—you just need to have their positions, and use the GLKVector2Length function to calculate how far each point is from the other. If the prey is too far away from the hunter, then it isn’t visible.

Figuring out whether or not the prey is within the angle of view of the hunter requires more math. What you need to do is to determine the angle between the direction the hunter is facing and the direction that the hunter would need to face in order to be directly facing the prey.

To do this, you create two vectors. The first is the vector representing the direction the hunter is facing, which you calculate by taking the sine and cosine of the hunter’s angle:

**float** directionRadians = GLKMathDegreesToRadians(direction);

GLKVector2 hunterFacingVector = GLKVector2Make(sin(directionRadians),

cos(directionRadians));

The second vector represents the direction from the hunter to the prey, which you calculate by subtracting the hunter’s position from the prey’s position, and then normalizing:

GLKVector2 hunterToPrey = GLKVector2Subtract(preyPosition, hunterPosition);

hunterToPrey = GLKVector2Normalize(hunterToPrey);

Once you have these vectors, you can figure out the angle between them by first taking the dot product of the two vectors, and then taking the arc cosine of the result:

**float** angleFromHunterToPrey =

acos(GLKVector2DotProduct(hunterFacingVector, hunterToPrey));

The result is measured in radians. To deal with it in degrees, which are sometimes a little easier to think about, you use the GLKMathDegreesToRadians function:

**float** angleFromHunterToPreyDegrees =

GLKMathDegreesToRadians(angleFromHunterToPrey);

You now know the angle from the hunter to the prey. If this angle is less than half of the field of view angle, then the hunter can see the prey; otherwise, the prey is outside the hunter’s field of view.

**Using AI to Enhance Your Game Design**

**Problem**

You want to make sure your game uses AI and behavior effectively to create a fun and engaging experience.

**Solution**

The fun in games comes from a number of places (see *http://8kindsoffun.com* for a discussion). In our opinion, one of the most important kinds of fun is challenge. Games that provoke a challenge for the player are often the most enjoyable.

Judicious and careful use of AI and behavior in your games can help them stand a cut above the rest in a sea of iOS games. You want to create an increasingly difficult series of challenges for your players, slowly getting more complex and introducing more pieces the longer they play for.

Revealing the different components of gameplay as they play is an important way to stagger the difficulty, and it’s important that any AI or behavior you implement isn’t using tools that the player doesn’t have access to.

Reveal the pieces of your game slowly and surely, and make sure the AI is only one step, if at all, ahead of the player.

**Discussion**

It’s hard to make a game genuinely challenging without killing the fun factor by making it too difficult. The best way to do this is to slowly peel back the layers of your game, providing individual components one by one until the player has access to the full arsenal of things he can do in your game. The AI or behavior code of your game should get access to this arsenal at approximately the same rate as the player, or it will feel too difficult and stop being fun.