Artificial Intelligence and Behavior - iOS Game Development Cookbook (2014)

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.

Intercepting a moving object.

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.

Objects that are within the field of view are visible

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.