SteeringSim
Steering Behaviors Simulation
This is a project that showcases different steering behaviors such as flocking, random wandering, and object avoidance. The concept is based on Boids by Craig Reynolds, and is closely related to emergent behavior, which says that complex behavior can arise out of a combination of relatively simple behaviors. A great example is flocking, which can be seen in a combined simulation of separation, alignment, and cohesion.
The project was created with Processing, references used include works by Conrad Parker and Daniel Shiffman. Some interesting (and cool) examples of flocking simulations can be found here and here.
Behaviorial Simulation
The central idea is that each agent in the swarm is treated as a particle, and carries properties such as position, velocity, orientation, and more (depending on the programmer's needs). During each iteration of the rendering loop, we loop through each agent, compute a new steering velocity based on its surroundings, then updates its position and redraw the agent. Also, during each iteration, we need to check the new velocity against a maximum velocity. If the new velocity is larger, we limit it to the maximum velocity, to make sure our agent doesn't go too fast.
When computing the new steering velocity, we compute the velocity and orientation contributions of all applicable steering behaviors, such as object avoidance or wandering, then take the sum of those velocities and orientation angles and limit it to a user-specified upper limit.
The simplest way to combine the steering forces is to add them, but that won't work in all situations, for example, the "wander" steering force is point toward a wall, while the "avoid" steering force is pointing away from it, we obviously want to head away from (or along) the wall. Many methods exist to solve this problem, from state machines, to weighted sums (multiply each steering component by a user-specified weight), to fixed priority coordination (some behaviors always have priority over others based on the agent's surroundings). I used a combination of weighted sum and priority coordination.
For this project's purposes, since the goal was to create a simple simulator, each agent object only comes with three main variables: position, velocity, and acceleration, all other necessary information are (for the most part) derived from those.
Individual Behaviors
Below are some general ideas behind how each individual steering behavior was implemented.
Seek/Flee
This is the most straightforward behaviors to implement. After determining a target, simply find the vector pointing from the current agent position to the target, and set it as the steering force.
For fleeing, simple take the opposite of the seeking steering vector (multiply it by -1, for example).
 |
// Seek
e = target - position;
distance = e.magnitude();
if (distance > 0) {
e.normalize();
e = e*maxspeed;
steer = e - velocity;
}
|
Arrival/Departure
Similar to seek and flee, except as the agent approaches the target, it slows down (and for departure, the closer it is to the target, the faster it moves away).
To accomplish this, the same code for seek and flee is used, but we create a spherical zone around the target (the radius is determined by the user). As the agent gets within the circle's radius, it begins to slow down as the speed of the agent is weighed by its distances to the target with respect to the circle's radius.
Also, for departure (and flee as well), it's a good idea to set a radius around the target (of which the agent is fleeing from) such that the agent stops fleeing after having passed it, unless you want the agent to keep going to the edge (or outside) of the simulation screen.
 |
// Arrival
e = target - position;
distance = e.magnitude();
if (distance > 0) {
e.normalize();
if (distance < ARadius)
// Damping
e *= maxspeed*(distance/ARadius);
else
e *= maxspeed;
steer = e - velocity;
}
|
Pursue/Evade
Really simple once you have seek/flee working. For the predator, set the prey's position as its target. To make the predator look smarter, you can even use the prey's current velocity and heading to predict where it will go (offset pursuit). As for evasion, it's almost the exact same thing as pursue, when the predator is within a certain radius, we want to flee from the predator. Also, for some interesting discussion on selfish behaviors within a flock:
A simple strategy for a predator animal is to chase the closest prey animal in its vicinity. This is reasonable because it expends the least amount of effort for the predator.
Then a strategy for a prey individual is to try to keep as far away from predators as possible: if predators only attack the closest prey individuals, then all the others should be safe. You can consider each prey individual as having a "domain of danger" surrounding it. This is the area around it comprising the points around it to which it is the closest prey. For example, a lone individual would have a "domain of danger" which is a large circle around it, whereas each individual in a pack would have a small "domain of danger" around it. Then the strategy is to reduce the "domain of danger" as much as possible. This is achieved in the pack formation, where all the prey individuals try to stay together, each one of them selfishly trying to reduce its own "domain of danger". However, the individuals on the edges of the pack have a much greater "domain of danger" than those in the interior. Thus, the individuals on the edge of the pack try to move towards the interior of the pack, which moves other individuals to the edges.
This strategy correlates well with the boids rules. Each individual boid tries to move towards the centre of mass of the pack, which very simply implements the reduction of the "domain of danger". Of course, they cannot all move to the very centre: there is a limit to the closeness of individuals, such that they all have enough room to move. This is also implemented as a rule for Boids.
Wander
Wandering simply means the agent is wandering around randomly. Although it sounds simple at first, a little effort is required to produce more realistic wandering behaviors. Consider the agent in the center of a circle, in the simplest case, we can just pick random points on the circumference as targets and use the seek algorithm from before to steer toward that target. However, the movement from this method is too "twitchy." We want natural-looking turns and sustained orientation.
An improved method is to put a smaller circle around the previous target (the one on the big circle), pick a random point on that small circle, then use the difference between that point and the previous target on the big circle as the displacement for that iteration, doing so will ensure there are no large erratic movements (one could also simply pick a random point between a small positive and negative number as the displacement to achieve similar results).
In the 3D case, simply replace the circles with spheres.
 |
// Wander // Find center of circle direction = velocity.normalized(); center = position + direction*length; // Random walk wdelta += random(-Rrad, Rrad) // Lazy... x = Vrad*cos(wdelta); y = Vrad*sin(wdelta); offset = vec3(x, y); target = center + offset; steer = seek(target); |
Object Avoidance
A bit harder than the others, object avoidance can be thought of as a simplified pathfinding algorithm (which in itself is a major topic).
Craig Reynolds suggested two methods. The first one places a rectangle (or a circle of a certain radius) some distance in front of the agent, then check whether that rectangle is intersecting with any obstacles. As a result, all objects in the scene should be places in a spherical (or rectangular) bounding volume for easier intersection tests.
There are many ways to go about implementing this method, one of which is to first convert the agent and the object into the agent's local coordinate (for simpler calculations), then draw a vector from the agent's position to the center of the object's bounding sphere. If the x component of that vector is greater than the rectangle's width (which is rectangle's x component), we know the two shapes are not intersecting, otherwise there is a potential intersection, in which case we compare the y component of each. Refer to the image for a better idea of how this is done. If there is an intersection, we calculate a vector pointing away from the object's bounding sphere using the agent's current velocity and orientation.
The second method suggested by Reynolds (which he calls "containment") tests for points a certain length directly in front of and to the left/right of the agent, if a point intersects with an object or a wall, a vector normal to the object/wall is calculated based on the location of the probe point and the intersection, and is used as the target for steering. Check here for improvements to this method using exclusion tests and fuzzy logic. Another good read on the subject is Craig Reynolds's paper Not Bumping Into Things.
Both methods have their shortcomings. The first one only works with objects within bounding volumes. The second one, while applicable to object of any shape, fails when the agent is facing a concave corner (for example, the corner of a room). To handle these cases, we can either hard code some specific cases, or use a more complicated path-finding algorithm. Since I tried not to make things too complicated, for this project I only implemented a very simplified avoidance algorithm based on the first method.
First, I place a sphere of avoidance around the agent (with a specific radius). If any obstacle comes within the sphere, I check the direction of the agent's current velocity, if it's heading away from the object, I do nothing, if it's heading toward the object, I calculate a steering force that will lead it around or away from the object based on its current velocity, position, and heading.
 |
// Object Avoidance
if ||dx|| <= Lb {
if ||dy|| <= rb + ro {
n = -1*d.normalize(); // Direction
e = ((rb + ro) - ||dy||)/(rb + ro)
e *= maxspeed;
steer = e*n;
}
}
|
Flocking
Possibly the most popular steering behavior (and one that's been simulated to death). Unlike the previous behavioral algorithms, flocking and its constituents (namely alignment, cohesion, and separation) are group behaviors, meaning they depend on neighboring agents.
To accomplish this, we first check the position/velocity of agents around the current agent, then calculate the alignment, cohesion, and separation forces. Adding those forces (place more importance on certain variables by multiplying it with a larger weight constant) together will naturally result in flocking.
Separation: When an agent tries to avoid bumping into local flockmates. To do this, we go through other agents within a certain radius of our agent and accumulate the inverse (opposite) of a fraction of each agent's velocity, then add it to the current agent's velocity, so it will try to move away from where the rest of its flockmates are heading toward, but not so far as to stray from the flock.
Alignment: When an agent tries to match the velocity of its neighbor flockmates. This can be done by finding the average velocity of the current agent's flockmates within a certain radius, and set that as the current agent's velocity.
Cohesion: When an agent tries to steer toward where the rest of its flockmates are heading. We accomplish this by finding the average position of the current agent's flockmates within a certain radius, and set that as the target (then pass that target to the seek algorithm) of the agent.
A great explanation of these behaviors and their psuedocode can be found on Conrad Parker's website.
Result
Download SteeringSim for yor operating system of choice:
We have also created a Java applet for the simulation to be run in the browser.
