Introduction

Many contemporary games use a data-driven approach to control various aspects of a game. In a racing game, for example, an external file may be used to specify the values for various physics parameters of a vehicle, or the behavioral parameters of an AI opponent. Deciding on values for these parameters can be a difficult task, since a change made to one parameter value might affect several aspects of behavior. Although it is sometimes possible to calculate the ideal values mathematically, in most cases a trial and error approach needs to be used.

In this article, I will discuss how we have used the Particle Swarm Optimization (PSO) algorithm to arrive at good values for both our physics and AI parameters. The first part of this article provides a quick overview of function optimization. This is followed by a discussion of the PSO algorithm, after which I will show how we have used PSO within our racing game.

Function Optimization

Algorithms such as PSO and Genetic Algorithms (GA) are generally used on functions that take several input parameters and return a single output value. The algorithm aims to find the input values that will generate the maximum (or minimum) output value, also referred to as the global optimum, within the valid range of input values. The number of parameters is referred to as the dimensionality of the function and the range in which valid input values can be found is referred to as the search space.

For example, consider the following one-dimensional function:

f(x) = sin(x) + sin(x/2)

Figure 1 shows a plot of the output values for all input values in the range 0.0 to 12.6. From this graph it is clear that the global optimum is somewhere around x = 11, at one of the low turning points of the function. At about x = 5.2 there is another low turning point. This is commonly referred to as a local optimum: an optimum within a sub-range of the global range.

	Figure 1: The graph of the function, sin(x) + sin(x/2), shows clearly the global and local minima.

Craig Reynolds's Flocking Model

Many of us are familiar with the name Craig Reynolds, whose work became the basis for many simulated swarms in games. Reynolds was intrigued by the behavior of swarms, such as a flock of birds or school of fish, which seem to move in a synchronized manner without any central control. He studied their behavior and came up with a model of their movement, from which he created a graphical simulation of bird-like objects flying around (he called them “boids,” from bird-oids). His model consisted of four steering behaviors: separation to make the boids avoid colliding with one another, alignment to make a boid steer in the common direction of his neighbors, cohesion to make a boid steer towards the common position of his neighbors, and avoidance to make a boid steer away from other obstacles [Rabin 2002].

In 1995, James Kennedy and Russell Eberhart applied Craig Reynolds's model to the problem of finding optima in a search space, which can be compared to a flock of birds looking for a food source, and created the PSO algorithm. They kept the alignment and cohesion behaviors of the Reynolds model, but did away with the behaviors of separation and avoidance.

In PSO, a collection of particles (called a “swarm”) move around in search space looking for the best solution to an optimization problem. All particles have their own velocity that drives the direction they move in. This velocity is affected by both the position of the particle with the best fitness and each particle's own best fitness. Fitness refers too how well a particle performs: in a flock of birds this might be how close a bird is to a food source, in an optimization algorithm this refers to the proximity of the particle to an optima.

Each particle's location is given by the parameters of the given optimization problem, and a particle moves around in search space by adapting and changing these parameter values. At each time step, the particle's fitness is measured by observing the parameter values (location) of the particle. A particle keeps track of the best position it has reached so far (called the personal best position), and is also aware of the position of the overall best particle at a certain time step (called the globally best position). At each time step the particle tries to adapt its velocity (i.e. speed and direction) to move closer to both the globally best position and the personal best position, in order to try and improve its fitness.

	Figure 2: This screenshot shows how particles “swarm” towards the global optimum, as indicated by the cross.

The PSO Algorithm

The standard PSO algorithm can be summarized as follows [Engelbrecht 2002]:

1. Set d equal to the dimension of the fitness function.
2. Create n particles, p₀ to p_n, each with a position vector, x, of dimension d.
3. Assign random position values to each particle
4. For each particle, p_i:
   1. Evaluate fitness (pass position vector values into fitness function and assign return value as fitness)
   2. If fitness better than personal best fitness, then assign current position as personal best position (x_pbesti)
   3. If fitness better than global best fitness, then assign current position as global best position (x_gbest)
5. For each particle, p_i:
   1. Update velocity, v_i:

v_i (t) = w v i (t-1) + l (x_pbesti - x_i (t)) + g (x_gbest - x_i (t))

1.  
   1. Update position, x_i:

x_i (t) = x_i (t-1) + v_i (t)

1. If criteria met, end simulation, else repeat from step 4.

The criteria for ending the simulation is usually based on whether the global best fitness is sufficient, or whether the simulation has run for the maximum amount of epochs (iterations). It is also important to note that in step 3, the personal best fitness of each particle, and the global best fitness need to be initialized to very poor values. At this stage, each particle's velocity is also usually set to zero, although they may be initialized to random values.

The number of particles, n, inertia weight, w, and the local and global component variables, l and g, are all system parameters of the PSO algorithm. These are discussed next.