Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds and coordinated behaviour fish schools. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference. The name refers to a "bird-like object", or "bird-oid", which could also refer to any animal exhibiting coordinated travel in groups.
Introduction
editReynolds proposed the Boids algorithm in his SIGGRAPH paper entitled "Flocks, Herds, and Schools: A Distributed Behavioral Model".[1] The method was created to simulate a distributed behavioural model, like the instinctual tendencies of a natural flock, based on the movements of individual actors. A flock, which Reynolds defines as "a group of objects that exhibit [a] general class of polarized, non colliding, aggregate motion", consists of "boids" that adhere to various rules in order to simulate perception; as a result the flock is simply formed by the interaction between the behaviors of discrete boids.
During the late 1980s the traditional technique used to animate flocks consisted of manually scripting the movement of the entire aggregate flock. Animators also did not utilize the computer's capabilities to implement any type of automated motion, but instead used it to directly describe the motion and physical properties of their models. Unlike these traditional methods of scripted animation, the boids method uses behavioral animation, which models the behaviour of the individual character; different behaviours could range from path planning to emotional interactions between characters.[1] Using this animation model the boids method could more effectively present the visually complex phenomena of flocking, since the simulated characters animate themselves.
The movement of Boids can be characterized as either chaotic (splitting groups and wild behaviour) or orderly. Unexpected behaviours, such as splitting flocks and reuniting after avoiding obstacles, can be considered emergent.
Boids Algorithm
editAs with most artificial life simulations, Boids is an example of emergent behavior; that is, the complexity of Boids arises from the interaction of individual agents (the boids, in this case) adhering to a set of simple rules. The rules applied in the simplest Boids world are as follows:
- Collision Avoidance: Each boid will steer itself accordingly in order to avoid collisions with nearby flockmates.
- Velocity Matching: Each boid will attempt to match the speed and direction, or heading, of nearby flockmates.
- Flock Centering: Each boid will attempt to stay within the vicinity of nearby flockmates.
Here each procedure is listed in order of decreasing precedence. The code below shows the main loop of the boids program written in pseudocode.
//example pseudocode as shown on http://www.kfish.org/boids/pseudocode.html
initialise_positions()
LOOP
draw_boids()
move_all_boids_to_new_positions()
END LOOP
The initialization describes the main loop broken down into two seperate tasks: first the computer will render the boids at the current state (of position, direction, etc.), and then the second task will change all of the boids values to the next state; The code that consists of the boids algorithm resides in the second task:
//example pseudocode modified from http://www.kfish.org/boids/pseudocode.html
PROCEDURE move_all_boids_to_new_positions()
Vector v1, v2, v3
Boid b
FOR EACH BOID b
v1 = flock_to_center(b)
v2 = avoid_collisions(b)
v3 = match_velocity(b)
b.velocity = b.velocity + v1 + v2 + v3
b.position = b.position + b.velocity
END
END PROCEDURE
Each rule in the moving function is calculated seperately for each boid, and each result will yeild a vector quantity (describing both speed and direction). Summing the vector values relates to how far the boid will move during the next rendering task, and current position is added to the velocity gain the final position of the boid for the current iteration.[2]
Flock Centering
editFlock centering is the idea that each boid wants to be near the center of the aggregate flock. Since each boid has a localized perception of the flock the actual center refers to the center of the nearby flockmates. If the boid is within the center of the aggregate flock the urge to move to the center is diminished, since it already resides within the area where the boid density is the same in all directions. If the boid is displaced near the side of a flock its urge to move is stronger. The following code approximately summarizes this concept:
//example pseudocode modified from http://www.kfish.org/boids/pseudocode.html
PROCEDURE flock_to_center(boid bJ)
Vector pcJ
FOR EACH BOID b
IF b != bJ THEN
pcJ = pcJ + b.position
END IF
END
pcJ = pcJ / N-1
RETURN (pcJ - bJ.position) / 100
END PROCEDURE
This code calculates the precieved center of the localized boid by considering all boids present in the scene. It then returns a value that moves the boid a fraction of the way toward the precieved local center.[2] An improvement to this code in actual implmentation would quantify an area known as a neighborhood to reduce the unrealistic perceptiveness of the entire flock, to only the boids contained in the local neighborhood.
Collision Avoidance
editEach boid, in order to move in an uninterrupted manner, must have the ability to avoid collisions with other local flockmates. Collision avoidance allows the boids the steer away from an imminent impact, which takes into consideration the relative posisiton of the flockmates and ignores their velocity. The following code approximately summarizes collision avoidance for boids:
//example pseudocode modified from http://www.kfish.org/boids/pseudocode.html
PROCEDURE avoid_collisions(boid bJ)
Vector c = 0;
FOR EACH BOID b
IF b != bJ THEN
IF |b.position - bJ.position| < 100 THEN
c = c - (b.position - bJ.position)
END IF
END IF
END
RETURN c
END PROCEDURE
This pseudocode takes each boid and checks it against an area condition: if the boid is within this space move it farther away; by subtracting the vector c from the displacement of each nearby boid. This method ensures a sort of smooth acceleration for boids near each other, since this rule will apply for both of them.
Velocity Matching
editVelocity Matching is the idea that each boid must maintain the same speed and heading (or direction) when apart of an aggregate flock. This rule is the converse of Collision Avoidance, since it considers only the velocity and ignores the positions of the neighboring boids. With Collision Avoidance the boid seperates from others, and Velocity Matching requires the boid to maintain that acceptable distance. The following pseudocode approximately represents this concept:
//example pseudocode modified from http://www.kfish.org/boids/pseudocode.html
PROCEDURE match_velocity(boid bJ)
Vector pvJ
FOR EACH BOID b
IF b != bJ THEN
pvJ = pvJ + b.velocity
END IF
END
pvJ = pvJ / N-1
RETURN (pvJ - bJ.velocity) / 8
END PROCEDURE
This procedure performs similarly to the avoid_collisions() method, since it simply takes the velocities and averages them; This calculates the precieved velocity of the flock. Similarly a fraction of the aggregated velocity is added to the current velocity.
Method Extensions
editMore complex rules can be added, such as obstacle avoidance and goal seeking.
The basic model has been extended in several different ways since Reynolds proposed it. For instance, Delgado-Mata et al.[3] extended the basic model to incorporate the effects of fear. Olfaction was used to transmit emotion between animals, through pheromones modelled as particles in a free expansion gas. Hartman and Benes[4] introduced a complementary force to the alignment that they call the change of leadership. This steer de?nes the chance of the boid to become a leader and try to escape.
References in Media
editThe boids framework is often used in computer graphics, providing realistic-looking representations of flocks of birds and other creatures, such as schools of fish or herds of animals. It was for instance used in the 1998 video game Half-Life for the flying bird-like creatures seen at the end of the game on Xen, named "boid" in the game files.
At the time of proposal, Reynold's approach represented a giant step forward compared to the traditional techniques used in computer animation for motion pictures. The first animation created with the model was Stanley and Stella in: Breaking the Ice (1987), followed by a feature film debut in Tim Burton's film Batman Returns (1992) with computer generated bat swarms and armies of penguins marching through the streets of Gotham City.[5]
Other Usages
editThe boids model has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations.[6] It has also been used for visualizing information[7] and for optimization tasks.[8]
See also
editReferences
edit- Reynolds, Craig (1987), "Flocks, herds and schools: A distributed behavioral model.", SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, Association for Computing Machinery: 25–34, doi:10.1145/37401.37406, ISBN 0-89791-227-6
{{citation}}
: Cite has empty unknown parameter:|month=
(help)
- ^ a b
"Flocks, herds and schools: A distributed behavioral model". SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques. Association for Computing Machinery: 25–34. 1987. doi:10.1145/37401.37406. ISBN 0-89791-227-6.
{{cite journal}}
: Cite has empty unknown parameter:|month=
(help) - ^ a b
Conrad Parker (Sep 06 2007). "Boids Pseudocode". Retrieved 4 October 2012.
{{cite web}}
: Check date values in:|date=
(help) - ^
Delgado-Mata C, Ibanez J, Bee S; et al. (2007). "On the use of Virtual Animals with Artificial Fear in Virtual Environments". New Generation Computing. 25 (2): 145–169. doi:10.1007/s00354-007-0009-5.
{{cite journal}}
: Explicit use of et al. in:|author=
(help)CS1 maint: multiple names: authors list (link) - ^ Hartman C, Benes B (2006). "Autonomous boids". Computer Animation and Virtual Worlds. 17 (3–4): 199–206. doi:10.1002/cav.123.
- ^ Lebar Bajec, I. and F. H. Heppner (2009). "Organized flight in birds" (PDF). Animal Behaviour.
{{cite web}}
: Cite has empty unknown parameter:|coauthors=
(help) - ^
Ibanez J, Gomez-Skarmeta A F, Blat J (2003). "DJ-boids: emergent collective behavior as multichannel radio station programming". Proceedings of the 8th international conference on Intelligent User Interfaces. pp. 248–250. doi:10.1145/604045.604089.
{{cite conference}}
: Unknown parameter|booktitle=
ignored (|book-title=
suggested) (help)CS1 maint: multiple names: authors list (link) - ^
Moere A V (2004). "Time-Varying Data Visualization Using Information Flocking Boids". Proceedings of the IEEE Symposium on Information Visualization. pp. 97–104. doi:10.1109/INFVIS.2004.65.
{{cite conference}}
: Unknown parameter|booktitle=
ignored (|book-title=
suggested) (help) - ^ Cui Z, Shi Z (2009). "Boid particle swarm optimisation". International Journal of Innovative Computing and Applications. 2 (2): 77–85. doi:10.1504/IJICA.2009.031778.