Steering
In the last half of the 20th century, science gave many examples of complex phenomena can arise from simple rules and simple equations. Chaos Theory and Multi Agent Systems were among the fields the were born when scientists realized this. For game development this is really important, because you have to give an imersive, fun and realistic (looking at least) expirience to the player, and this must be done at least 40 frames per second. One of the most important aspects of game simulation that leads to imersion is the movement of the characters throughout the game environment. That’s what Steering is for.
Craig Reynolds published a paper in SIGGRAPH 87 about the simulation movement of group of simple animals, like fish and birds, and called it BOIDS (more about this in a minute). This simulation is based on a most fundamental set of algorithms called Steering. He gave a seminal lecture at GDC 99 defining the main concepts of this field. Steering defines a direction of movement for an agent, game character, and most often called vehicle in the Steering terminology, and, based on the desired behavior for this vehicle, a force is applied to it in order to have the desired movement.
Reynolds defined 8 types of movement behaviors that could be simulated with Steering:
- Seek: the vehicle move to a specific fixed or moving point.
- Flee: the opposite of seek, the vehicle moves away from a fixed or moving point.
- Arrive: almost identical to seek, but in this case the vehicle stops when it reaches the point.
- Pursue: a seek improved. The vehicle tries to predict where its target will be in the future based on the target’s velocity and goes to that location, not the target’s location at the present.
- Evade: the opposite of pursue.
- Wander: the vehicle defines a heading direction and goes to it, choosing another random direction after some time.
- Object Avoidance: the vehicle tries to perceive objects on its current path of movement and changes steers to avoid them.
- Path Following: given a path, based on a curve or a set of points, the vehicle does its best to stay on the path.
I’ve made a simple simulation in XNA 4 to demonstrate these behaviors. A video showing the results is here
Raynolds also created an opensource lib (in C++) to show all these ideas. It hasn’t been updated in a while, but you can get the code at the official web site OpenSteer.
But, it’s not finished yet. Steering is a set of algorithms to simulate the movement of one vehicle. Whatif I have more than one vehicle and I want them to behave like a ordered and organic crowd, like flocks of birds or schools of fishes? That’s what the first work of Reynolds in this area was about. BOIDs. It defines 4 rules (3 in the original) that can simulate realistically the movement.
- Every vehicle perceives only the other vehicles close to based their distance and their angle with respect to it. (This is the rule that was implicitly defined on the 1987 paper)
- Separation: steer to avoid crowding local flockmates.
- Alignment: steer towards the average heading of local flockmates.
- Cohesion: steer to move toward the average position of local flockmates.
I’ve also include a simple simulation of BOIDs in the video above, but you can find many of them around the internet. There’s also a good lecture by Steven Strogatz at TED where he talks about synchronization of systems which includes BOIDs. You can improve your player’s perception of your game with these simple algorithms. Give it a try and it will be woth the effort for the player fun. Again, if you have any question about the ideas discussed here, just send me an email. Have fun.
End of Line