Game Creation with XNA/AI/Artificial Intelligence in Games

Games always provided an environment for developing artificial intelligence. So in the last decades it became one of the most important components of games. Nowadays games that have sophisticated AI are state of the art. Some simpler and some more sophisticated algorithms you will need in many games. It is used in many situations, some are:

• control of NPCs
• pathfinding
• dynamic game difficulty balancing
• combats / fights

History

Already in the very beginning of game development, in the 1970s, programmers and developers came face to face with the field of game artificial intelligence. But at this time AI was simple and so to say humble and that status didn’t change until few years ago.

"AI has been quietly transformed from the redheaded stepchild of gaming to the shining star of the industry" - Steve Rabin, AI Game Programming WISDOM, 2002, p. 3

The first games featuring a single player mode and therefore AI in its very beginning like the Atari game “Qwak!” didn’t have AI like we would describe it today. Enemy movement was mostly predefined and stored as patterns. Only with the improvement of the hardware like the incorporation of microprocessors, that allowed way more computation, further random elements could be implemented. Games resulting from that were for example Space Invaders, Galaxian, and Pac-Man. Those games presented e.g. an increasing difficulty level, complex and varied enemy movements, events depending on the players input and even different personalities for each enemy. Along with the loom of new game genres in the 1990s new AI tools were developed and used. Among these tools were for example finite state machines. In the newer games AI became the main aspect of game. The improvement of AI didn’t only depend on the given hardware components. Well, in fact it definitely was a very important aspect. There were some problems that couldn’t be solved without significant processor resources. But it should be added that in the beginning of game development programmers simply didn’t take AI overly serious. Mostly AI was done in the very end after completing all the high-priority tasks.

Today AI climbed up the games ladder to be the highest-priority task.

Techniques

There are countless in-game scenarios crying for artificial Intelligence. So how do you solve chasing, flocking or path finding? Smart programmers and developers puzzled out some clever techniques and algorithm giving your games a touch of brain. Some interesting algorithms and AI situations I will explain in the following. I won't assert a claim to a complete list. But I will present you the basic scenarios you will be faced with.

Chasing and Evading

No matter what kind of game you have chances are that you will be faced with chasing and evading.

Basic Algorithm

The simplest way to describe chasing and evading in form of an algorithm is to firstly find out the distance between predator and prey and than in case of chase decrement it and in case of evade increment it.

Chase	Evade
if (predatorPos > preyPos) predatorPos --; else if (predatorPos < preyPos) predatorPos ++;	if (preyPos> predatorPos ) preyPos++; else if (preyX < predatorPos ) preyPos-- ? > ;

Well it works but clearly that is not a very natural approach.

Line-of-Sight Chasing

Way more realistic is to let the predator take a straight line towards the prey.

simple chasing vs. line of sight chasing

The algorithm for finding the direct way is a little more complicated. You need to find the direct and shortest way without unnecessary steps between predator and prey. Out there are a lot of useful algorithms that could help us out with our problem. Think about those line drawing algorithms build for a pixel environment. Those algorithms are built for finding a direct way from a starting point to a destination. But another criterion our algorithm has to fulfill is to find the shortest way. So it is time to ask Bresenham. Bresenham’s algorithm offers us what we want. Here you are.

Intercepting

Even more effective for the predator could it be for it to intercept the prey at some point along the prey’s trajectory.

intercepting

The intercepting point should be selected depending on the relative positions and velocities of predator and prey. To predict that point you have to consider three values. Those are position, direction and velocity.

Calculation steps

1. Relative velocity (closing velocity)

   $v=vPrey-vPredator$

2. Relative distance (range to close)

   $d=posPrey-posPredator$

3. Time it will take to travel the relative distance at a speed equal to the closing speed (time to close)

   $t={\frac {\left|d\right|}{\left|v\right|}}$

4. Predicted position of the prey (target point)

   $pos=posPrey+(vPrey*t)$

Vector FindInterceptingPoint(void)
{
  Vector v, d;
  Double t; 
  v = Prey.v - Predator.v; // closing velocity
  d = Prey.pos - Predator.pos; // range to close
  t = d.Magnitude() / v.Magnitude(); // time to close
  return Prey.pos + (Prey.v * t); // target point
}

Pattern Movement

Patterns for different movements and maneuvers are predefined. Computer controlled character using those complex patterns give the illusion of intelligent behavior. The standard algorithm uses lists or arrays of encoded instructions. These instructions tell computer controlled character how to move each step through the game loop.

Example

Following pattern was borrowed from the book "AI for Game Developers" from O'REILLY:

Pattern[0].turnRight = 0;
Pattern[0].turnLeft = 0;
Pattern[0].stepForward = 2;
Pattern[0].stepBackward = 0;
Pattern[1].turnRight = 0;
Pattern[1].turnLeft = 0;
Pattern[1].stepForward = 2;
Pattern[1].stepBackward = 0;
Pattern[2].turnRight = 10;
Pattern[2].turnLeft = 0;
Pattern[2].stepForward = 0;
Pattern[2].stepBackward = 0;
Pattern[3].turnRight = 10;
Pattern[3].turnLeft = 0;
Pattern[3].stepForward = 0;
Pattern[3].stepBackward = 0;
Pattern[4].turnRight = 0;
Pattern[4].turnLeft = 0;
Pattern[4].stepForward = 2;
Pattern[4].stepBackward = 0;
Pattern[5].turnRight = 0;
Pattern[5].turnLeft = 0;
Pattern[5].stepForward = 2;
Pattern[5].stepBackward = 0;
Pattern[6].turnRight = 0;
Pattern[6].turnLeft = 10;
Pattern[6].stepForward = 0;
Pattern[6].stepBackward = 0;
.
.
.

The instruction encoded ins this pattern are:

1. move forward 2 distance units
2. move forward 2 distance units
3. turn right 10 degrees
4. turn right 10 degrees
5. move forward 2 distance units
6. move forward 2 distance units
7. turn left 10 degrees

Flocking

Sometimes in games it’s more realistic to let non player characters move in cohesive groups. Let’s consider birds, sheep and all these gregarious animals always hiding in the safety of their flock. Or what about those big computer controlled human, troll or orcs units. Flocking definitely is a common performance in games. See the clip side that I borrowed from roxlu here http://vimeo.com/5352863.:

Basic Algorithm

There are some basic flocking algorithms implementing our wished behavior. We will look at the Craig Reynolds algorithm. This implementation is leaderless. All individuals of the boid (term coined by Craig Reynolds referring to simulated flocks) are following the group itself.

Rules

The algorithm is following three simple rules:

• Separation

  steer to avoid hitting the neighbors

• Alignment

  steer so as to align itself to the average heading of the neighbors

• Cohesion

  steer toward the average position of the neighbors

Example

You can find an explanation of the algorithm and its implmentation here: http://oreilly.com/catalog/ai/chapter/ch04.pdf

Path finding

There are thousands of individual path finding problems. You won’t find one algorithm as sure formula for all kind of them. Even the A* algorithm – actually an ideal solutions for many problems – is not the appropriate for every situation.

Basic algorithm

The algorithms in chapter Chase and Evading do some basic path finding. We clarified that the Line-of-Sight algorithm creates a way more realistic movement. Now let’s have a look at obstacle avoidance:

Obstacle Avoidance

The easiest way to implement obstacle avoidance is the following:

if Player In Line of Sight
{
  Follow Straight Path to Player
}
else
{
  Move in Random Direction
}

Problem here is due to its simplicity this will only work with a few obstacles. A little more effective is it to let the character trace around an obstacle: When the character borders on an obstacle it traces around it. It stops tracing once the destination is in the characters line of sight.

Breadcrumb Path finding

Here the player itself is defining the way for the non player character. This way the computer controlled player seems very intelligent. The player is leaving markers on the road every step it takes. The non player character will only follow those footsteps.

Path Following

Path following you will need for example in a car racing game. There is no definite destination to head to. There is only a predefined road that has to be followed.

Way Point Navigation

Path finding is a very time consuming task. Especially when you have a big environment with a lot of obstacles. Waypoint reduces this problem. The main idea is it to place nodes in the game environment and then use them for inexpensive path finding algorithms.

A* Path finding

The A* algorithm provides an effective solution to the problem of path finding.

Further Techniques

We looked at a lot of gameplay situations needing an AI approach. But those aren't nearly all. If your curiosity just have a look at O'REILLY's book "AI for Game Developers"

Examples

Pong

Pong was firstly released in 1972 by Atari. It consists of a black screen with 2 paddles, one on each side of the screen, and a ball. The paddles are controlled by players who can move them up and down to fetch the ball which is moving from side to side. If one of the players misses the ball, the opponent is credited with one point. The game ends if one players reaches a fixed number of points - e.g. 10 points.

AI in Pong

If you decide to play against the computer you are actually playing against an AI algorithm. You are always standing before the decision if you move your paddle up, down or not at all. And so is the computer:

1st approach

An easy solution for this problem is to analyze the current state of the ball (its position and its direction of movement) to decide which move to make with the paddle. By knowing the direction of the ball (an angle in degree) you can determine whether the ball wents up or down on the screen. The computer can now calculate the difference in the y-positions of ball and paddle and decide upon that knowledge to move the paddle down or up to decrease this difference until it is 0 in the best case. If it is nearly 0 then the paddle can stop and wait till the ball movement requires other actions to be taken.

int difference = ball.positionY – paddle.positionY;

if(difference >= 5 || difference <= -5)
{
	if(difference > 0)
	{
		paddle.moveDown();
	}
	else
	{
		paddle.moveUp();
	}
}

The benefit of this approach is that it is easy to implement. It does not need much calculation effort (good performance) and tends to do some mistakes or gets taken by surprise in some situations. There it seems more human-like and is beatable. One of these mean (for the computer AI) situations is when the paddle follows the ball up and then shortly before the ball reaches the side of the paddle it hits the upper wall and changes its direction to go down. Then it may occur that the paddle is too slow (especially with faster balls in higher levels) to react on this change in direction and loses the ball.

2nd approach

The 2nd approach is a little more sophisticated and needs more calculation. All you need is the current position of the ball and its current movement direction - that's what you can get from the game engine. Based on these values it is possible to determine the further way of the ball (including all wall collisions and direction changes) and at the end the position where it could possibly hit the paddle of the AI player. If you got this point - and this point will never change because normal pong has no suddenly occurring situations that could change the direction somehow - you just have to directly move the paddle to this point to catch the ball and kick it back in the opponents half. This approach could also be slightly modified by positioning the paddle in a way it hits the ball at the corners of the paddle to give it a little swerve.

Even if it's the more improved solution to this problem there are some disadvantages. It is more complicated to implement this algorithm, it may need longer and costs more resources to calculate the end position of the ball (maybe too long for slow systems like mobile phones, handhelds, etc.) and the most important point (in my opinion) is that you have a de facto unbeatable and perfect enemy because it always hits the ball as good as it's possible which could be annoying for a real player to compete with.

More Examples

• eliza
• tic tac toe

Difficulties

AI has to be calculated live (during the game), therefore (good) performance is very important to let the game run smoothly. To ensure that there are many simplifications, workarounds, cheats in the algorithms which approximate the ideal behaviour of the player. So they are fast and intelligent at the same time. When performance is an important issue, it is clear that stuff like bruteforcing all possible decisions is not the best way to deal with such situations in game AI.

Another essential fact is that the computer player should not play perfect even if he could. Cheating is a big word in that topic, because the computer knows all facts and has all kinds of information about the game world so it would be possible to let the AI player know things they realistically could not know. The player has to think he plays against a real enemy and not a computer, that is why firstly the AI has to be beatable (not invincible) and furthermore it has to act human-like (do mistakes, act randomly in some situations, etc.). If the AI does not behave in this way the game would be soon very boring for the player or just frustrating if he has no chance to win. Some games use approximation algorithms instead of perfect solutions and implement "wrong" (or worse) decisions in their algorithms.

half-dozen rules of thumb and heuristics, just enough to give a good gameplay experience

Authors

• iSteffi