71² – The ramblings of two 30-something developers

Steering AI

I’ve just finished getting some steering AI working and I thought I’d share what I’m doing.

For some time I’ve been trying to work out how to get my baddies to follow cool paths on screen. The game I’m doing at the moment, with the code that’s going into these tutorials, is a top town retro shooter. I think most people like to blow things up :o)

In a previous game prototype I created in Java I ended up using Cubic Splines to define nice curved paths for my baddies. The problem with that was that I didn’t understand ANY of the maths used and the classes I found were not parameterized, which means I could not get the baddies to travel at a constant speed along the path meaning they slow down when they go around corners.

For my iPhone work I didn’t want to have to go down a route that complex, so I came up with the idea of just defining points (waypoints) on the screen and giving the baddies some AI which would allow the to steer themselves toward each point in turn, providing me with cheap path following.

I hunted around for a while to find info on steering AI and there is a lot out there. Again, a lot of it I didn’t understand, but I did come across a great site which both described and demoed a number of different steering techniques. The site can be found here and I’ve put a link in the links section as well.

For my needs I’ve taken the seek AI which steers the entity to a given target. The concept of steering is important. It’s simple enough using something like Atan2 and working out an angle to a point and then just moving the entity in that direction, but I wanted the entity to steer towards the target point to provide a much smoother looking path. For this steering seemed perfect. The algorithm applies a steering force to the entity caused the entity to steer towards the point not just change direction immediately.

Now, at the moment this is pretty basic and can come up with some interesting effects if you play with the speed and steering force limits, but with a little fiddling its been working really well for me.

My idea is that I will have a path factory that can provide a path on request. The path will just be an array of points which the entity then starts to follow. Once a point is reached it then takes the next one in the list and steers towards that and so on.

Below is the code I’m using to calculate the steering force and applying that force to the entities current vector. I’m not great at vector math, but this has been a lot easier to understand than Cubic Splines.

// Calculate the steering force needed to move from the current position to current waypoint
// as we are seeking the target
Vector2f steeringForce = Vector2fSub(wayPoint, position);

// Subtract current velocity from the steering force
steeringForce = Vector2fSub(steeringForce, velocity);

// Multiply the steering force with delta
steeringForce = Vector2fMultiply(steeringForce, theDelta);

// Limit the steering force to be applied
GLfloat vectorLength = Vector2fLength(steeringForce);
GLfloat maxSteeringForce = MAX_STEERING_FORCE;
if(vectorLength > maxSteeringForce) {
	steeringForce = Vector2fMultiply(steeringForce, maxSteeringForce / vectorLength);
}

// Add the steering force to the current velocity
velocity = Vector2fAdd(velocity, steeringForce);		

// Limit the velocity
vectorLength = Vector2fLength(velocity);
GLfloat maxVelocity = MAX_VELOCITY;
if(vectorLength > maxVelocity) {
	velocity = Vector2fMultiply(velocity, maxVelocity/vectorLength);
}

// Add the velocity to the entities position
position = Vector2fAdd(position, velocity);

// If the entity gets to within a defined # of pixels from waypoint move to the next waypoint
if((position.x - wayPoint.x) > -WAYPOINT_DISTANCE &&
   (position.x - wayPoint.x) < WAYPOINT_DISTANCE &&
   (position.y - wayPoint.y) > -WAYPOINT_DISTANCE &&
   (position.y - wayPoint.y) < WAYPOINT_DISTANCE)
{
	// Increment the current waypoint counter
	currentWayPoint++;
		// Check to see if we have reached the end of the entity path
	if(currentWayPoint > wayPointCount) {
		currentWayPoint = 0;
	}

	// Set the next waypoint from the entity path
	wayPoint.x = entityPath[currentWayPoint].x;
	wayPoint.y = entityPath[currentWayPoint].y;
}

You will see that I have some function I’m using such as Vector2fAdd etc. I created these are part of the particle emitter class I’ve written and for which a tutorial is being made at the moment. They are inline C functions which perform useful vector maths quickly. Using inline functions for things like this which are called a lot helps performance. There is overhead to calling Objective-C methods which using functions like this can avoid.

These functions are just define within a .h file. That .h file is included in the .h of any class which needs to use then and you then call them just like any other function. My common.h file is below with these definitions.

/*
 *  Common.h
 *  Tutorial1
 *
 *  Created by Michael Daley on 19/04/2009.
 *  Copyright 2009 __MyCompanyName__. All rights reserved.
 *
 */

#import 

#pragma mark -
#pragma mark Macros

// Macro which returns a random value between -1 and 1
#define RANDOM_MINUS_1_TO_1() ((random() / (GLfloat)0x3fffffff )-1.0f)

// MAcro which returns a random number between 0 and 1
#define RANDOM_0_TO_1() ((random() / (GLfloat)0x7fffffff ))

// Macro which converts degrees into radians
#define DEGREES_TO_RADIANS(__ANGLE__) ((__ANGLE__) / 180.0 * M_PI)

#pragma mark -
#pragma mark Types

typedef struct _Color4f {
	GLfloat red;
	GLfloat green;
	GLfloat blue;
	GLfloat alpha;
} Color4f;

typedef struct _Vector2f {
	GLfloat x;
	GLfloat y;
} Vector2f;

typedef struct _Quad2f {
	GLfloat bl_x, bl_y;
	GLfloat br_x, br_y;
	GLfloat tl_x, tl_y;
	GLfloat tr_x, tr_y;
} Quad2f;

typedef struct _Particle {
	Vector2f position;
	Vector2f direction;
	Color4f color;
	Color4f deltaColor;
	GLfloat particleSize;
	GLfloat timeToLive;
} Particle;

typedef struct _PointSprite {
	GLfloat x;
	GLfloat y;
	GLfloat size;
} PointSprite;

#pragma mark -
#pragma mark Enums

enum {
	kGameStateRunning = 1,
	kGameStatePaused = 2
};

#pragma mark -
#pragma mark Inline Functions

static const Vector2f Vector2fZero = {0.0f, 0.0f};

static inline Vector2f Vector2fMake(GLfloat x, GLfloat y)
{
	return (Vector2f) {x, y};
}

static inline Color4f Color4fMake(GLfloat red, GLfloat green, GLfloat blue, GLfloat alpha)
{
	return (Color4f) {red, green, blue, alpha};
}

static inline Vector2f Vector2fMultiply(Vector2f v, GLfloat s)
{
	return (Vector2f) {v.x * s, v.y * s};
}

static inline Vector2f Vector2fAdd(Vector2f v1, Vector2f v2)
{
	return (Vector2f) {v1.x + v2.x, v1.y + v2.y};
}

static inline Vector2f Vector2fSub(Vector2f v1, Vector2f v2)
{
	return (Vector2f) {v1.x - v2.x, v1.y - v2.y};
}

static inline GLfloat Vector2fDot(Vector2f v1, Vector2f v2)
{
	return (GLfloat) v1.x * v2.x + v1.y * v2.y;
}

static inline GLfloat Vector2fLength(Vector2f v)
{
	return (GLfloat) sqrtf(Vector2fDot(v, v));
}

static inline Vector2f Vector2fNormalize(Vector2f v)
{
	return Vector2fMultiply(v, 1.0f/Vector2fLength(v));
}

I will be covering this in a tutorial, but I thought it would be useful to get the code and idea out in the open so people can have a play and we can see what other ideas people have in this area.

Let me know what you think.

Mike

8 Comments

Leave a Comment

Username :
Email :
Web Site :
Comment :

Notify me of followup comments via e-mail