The boid algorithm is a well known simulation of the flocking behavior of birds and other animals. In the algorithm, each “boid” flies in such a way as to stay close to its neighbors without getting too close, while also trying to fly in the same general direction as its neighbors.
Extending this algorithm to five dimensions gives us a space of two spatial coordinates and three color coordinates. Click here or on the image below to open up an HTML5 canvas application based on this idea. Be sure to wait a little while for the emergence of flocking behavior. Clear the canvas every once in a while using the “clear” button, or check “clear on redraw” to watch the boids fly without leaving their traces behind. Be sure to play around with the drawing settings to see some interesting variations. More information about the code is below.
The complete code can be downloaded here: ColorBoids.zip
Below are a couple more images drawn using the application. You can find some more in this flickr set.
The main idea
The boid algorithm can produce animations of flocks in two or three dimensions. Whatever dimension is used, the algorithm is the same; one simply needs to calculate positions and velocities in two or three dimensions as desired. But what about higher dimensions? There is nothing about the algorithm which prevents it from being computed in five dimensions. In such a higher dimensional space, we have the same notions of velocities and distances measured by a similar Euclidean geometry. Distances are computed the same way as in lower dimensions: you take the square root of the sum of the squares of the coordinate differences.
The application here uses two dimensions for spatial coordinates, while the three remaining coordinates are used to define the color of each boid in terms of its independent red, green, and blue components.
When you watch the boids fly around the canvas, remember that if they are not similarly colored, then they are not in fact close to each other in the 5D space where they are flying. Interaction doesn’t occur until they are both close to each other on the canvas and also close to each other in color.
The boid algorithm
In the boids algorithm, each boid flies around while following three basic rules:
- 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.
There seems to be some variation in how exactly these rules are applied: for example, when we calculate the cohesion force, do we always normalize it to a consistent magnitude? And do nearby neighbor boids have more of an effect (or less) on separation than the ones that are not as near? I have seen different approaches and methods in use. I came up with my own implementation, but the same basic ideas are at play.
In this application I chose to have the boids avoid the rectangular walls, in both spatial and color coordinates. There is really no easy way to “wrap” color components. Also, I have found that using a rectangular canvas rather than a square helps to avoid some regular periodic motion. This non-square aspect is also used in the (hidden) color space, to avoid periodic color changes.
I used another variation of this boid algorithm to create a color cellular automaton in a previous post.
Drawing the boids to the canvas can be done in many different ways, using different shapes. In this application, you can select basic dots or squares, or have the path of each boid drawn as a continuous line. You can clear the canvas on each redraw just to watch the boids fly around, or let them leave their colorful trails behind.
The “line from center of mass” option does just what it says: a line is drawn from the current center of mass of all of the boids to each boid, in the color of the boid. An interesting variation occurs when you translate the canvas so the center of mass is always drawn at the center of the canvas. That variation is not available here, but I’ll leave you to download the code and experiment.
Could be Optimized More
The code is fairly well optimized in terms of using minimal calculations, and a linked list for the boids instead of an array. But a more significant optimization of the algorithm can be accomplished by using a binary space partitioning (BSP) data structure. In my code, each boid is checked against all other boids to see whether they are close enough to interact, which is wasteful. In a future version perhaps I’ll introduce space partitioning, which in this case would be not be a quadtree (for 2D) or an octree (for 3D), but rather a 32-tree!
I can think of other ways to use particles in higher dimensions to draw pictures, but I’ll leave you to come up with your own ideas. Even in the current form of this application, different color palettes can be achieved by finding new ways to map three coordinates to a subspace of RGB space (or perhaps you might want to drop down to four dimensions and use only a two-dimensional color space). I hope you’ll have fun experimenting!