Vgaviria

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

Reynolds proposed the Boids algorithm in his SIGGRAPH paper entitled "Flocks, Herds, and Schools: A Distributed Behavioral Model". 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. 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

As 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.

Flock Centering

Flock 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. 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

Each 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

Velocity 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

More 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. 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 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

The 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.

Other Usages

The boids model has been used for other interesting applications. It has been applied to automatically program Internet multi-channel radio stations. It has also been used for visualizing information and for optimization tasks.

See also

• Swarm intelligence

References

• 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)

External links

• Craig Reynolds' Boids page
• Explanation of algorithm in pseudocode
• JavaScript implementation
• 3D Boids Simulation using OpenGL, used by the BBC's Natural History Unit

Category:Artificial life