# Craig Reynolds: boids flock

7 results back to index

Exploring Everyday Things with R and Ruby by Sau Sheong Chang

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

While not as spectacular as the starling swarms in Europe, which often number in the hundreds of thousands and are sometimes referred to as the “Black Sun,” the mynah swarms are interesting enough to start a train of thought that has eventually led me to this basic question: how and why do these birds flock the way they do? As usual, I started off my quest with some searches on trusty old Google, which brought up a number of intriguing results. As it turns out, there is a whole bunch of existing research on flocking birds and swarming insects, dating back to more than 30 years ago. One popular and well-known product of this research is the Boids algorithm created by Craig Reynolds in 1986. The Origin of Boids Boids is an artificial life program developed by Craig Reynolds to simulate the behavior of flocking birds. The name refers to the birdlike objects that populate the simulation. Instead of programming complex behavior for the boids, Reynolds provided three simple rules: Separation Each boid should stay away from its flockmates to avoid overcrowding.

The radii for the align and cohere rules are relatively larger, as we want the roids to collect in a single group rather than many small groups. There you have it—these three rules make up the original Boids flocking algorithm created by Craig Reynolds. Supporting Rules While Reynolds’s three rules suffice to make a rather compelling simulation, we need a couple more rules to make the simulation run smoothly: Muffle the speed of the roid. We don’t want roids to randomly speed up as a result of flocking. Real birds can’t speed up too much, so we must slow down the roids if they move too fast as a result of our flocking rules. Allow the roid to fall through from one side of the application window into the other. The alternative is to make the roids bounce around the application window. I personally dislike that—it makes the roid look like it’s a bouncing ball, and birds don’t bounce.

pages: 247 words: 43,430

Think Complexity by Allen B. Downey

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Heterogeneity What if all drivers are not the same; for example, what if they have different speed limits or following distances? Boids In 1987, Craig Reynolds published “Flocks, herds, and schools: A distributed behavioral model,” which describes an agent-based model of herd behavior. You can download his paper from http://www.red3d.com/cwr/papers/1987/boids.html. Agents in this models are called “boids,” which is both a contraction of “bird-oid” and an accented pronunciation of “bird” (although boids are also used to model fish and herding land animals). Each agent simulates three behaviors: Collision avoidance Avoid obstacles, including other birds. Flock centering Move toward the center of the flock. Velocity matching Align velocity with neighboring birds. Boids make decisions based on local information only; each boid only sees (or pays attention to) other boids in its field of vision and range.

set_goal computes the weighed sum of these goals, and sets the overall goal: def set_goal(self, boids, carrot): self.goal = (w_avoid * self.avoid(boids, carrot) + w_center * self.center(boids) + w_copy * self.copy(boids) + w_love * self.love(carrot)) Finally, move updates the velocity, position, and attitude of the boid: def move(self, mu=0.1): self.vel = (1-mu) * self.vel + mu * self.goal self.vel.mag = 1 self.pos += dt * self.vel self.axis = b_length * self.vel.norm() The new velocity is the weighted sum of the old velocity and the goal. The parameter mu determines how quickly the boids can change speed and direction. The time step dt determines how far the boids move. Many parameters influence flock behavior, including the range, angle, and weight for each behavior, and the maneuverability, mu. These parameters determine the ability of the boids to form and maintain a flock, and the patterns of motion and organization in the flock.

These parameters determine the ability of the boids to form and maintain a flock, and the patterns of motion and organization in the flock. For some settings, the boids resemble a flock of birds; other settings resemble a school of fish or a cloud of flying insects. Example 10-4. Run my implementation of the boid algorithm, and experiment with different parameters. What happens if you “turn off” one of the behaviors by setting the weight to 0? To generate more bird-like behavior, Flake suggests adding a fourth behavior to maintain a clear line of sight; in other words, if there is another boid directly ahead, the boid should move away laterally. What effect do you expect this rule to have on the behavior of the flock? Implement it and see. Prisoner’s Dilemma The Prisoner’s Dilemma is a topic of study in game theory, so it’s not the fun kind of game.

pages: 294 words: 82,438

Simple Rules: How to Thrive in a Complex World by Donald Sull, Kathleen M. Eisenhardt

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

While designing computer-graphics software, Reynolds grew interested in how to simulate coordinated activity in animals, such as the flocking of birds. Reynolds created avian avatars, which he dubbed “boids,” and wrote a software program in which each boid followed three simple rules based on the position and behavior of nearby flock mates. The three rules are: (1) avoid collisions, (2) head in the same direction as your nearest neighbors, and (3) stay close to your nearest neighbors. These three rules are all that boids need to coordinate with one another and produce their amazing group-level flocking behavior, closely matching that of real birds. Behavioral biologists, who tested Reynolds’s rules in the wild, found that they could explain collective behavior in a wide range of settings, including how mosquitofish shoal, starlings flock, and pedestrians self-organize into orderly lines on busy streets.

He studied at Cambridge, practiced as a barrister, published twenty books on nature, and is acknowledged as a pioneer of ethology (the study of animals in their natural habitats). Instead, his telepathy theory is a testament to how mysterious bird flocking is, even to someone who studies it carefully. (A YouTube search of “starling murmuration” will give you a sense of the mystery of synchronized flight.) Fellow ornithologists wisely dismissed thought-transference but could not come up with a better explanation of flocking behavior. For fifty years after Selous published his book, the question of how starlings orchestrated a murmuration remained unanswered. The solution to how starlings flock came unexpectedly from a software engineer working in a computer lab, not from an ornithologist traipsing around a field. Craig Reynolds studied at MIT, where he wrote his bachelor’s and master’s theses on computer animation. While designing computer-graphics software, Reynolds grew interested in how to simulate coordinated activity in animals, such as the flocking of birds.

. [>] After three decades: Edmund Selous, Thought-transference (or What?) in Birds (London: Constable & Co, 1931). [>] Reynolds created avian: Craig Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics 21 (1987): 25–34. [>] Behavioral biologists: Ballerini et al. review the models of collective animal behavior and summarize that all agree on three behavioral rules: “move in the same direction as your neighbors, remain close to them, avoid collisions.” Michele Ballerini et al., “Interaction Ruling Animal Collective Behaviour Depends on Topological Rather than Metric Distance: Evidence From a Field Study,” Proceedings of the National Academy of Science USA 105 (2008): 1232–37. [>] In flocks, however: C. C. Ioannou, V. Guttal, and I. D. Couzin, “Predatory Fish Select for Coordinated Collective Motion in Virtual Prey,” Science 337 (2012): 1212–15. [>] Even today, locusts: Vishwesha Guttal et al., “Cannibalism Can Drive the Evolution of Behavioral Phase Polyphenism in Locusts,” Ecology Letters 15 (2012): 1158–66. [>] In 1955 a group: Janet Coleman, The Compass: The Improvisational Theatre That Revolutionized American Comedy (Chicago: University of Chicago Press, 1991).

pages: 293 words: 88,490

The End of Theory: Financial Crises, the Failure of Economics, and the Sweep of Human Interaction by Richard Bookstaber

In an early simulation of that emergent phenomenon, Craig Reynolds, a software engineer and Academy Award winner,3 built a dynamic model for a flock of artificial “boids” based on three simple rules: 1. Separation: don’t get too close to any object, including other boids. 2. Alignment: try to match the speed and direction of nearby boids. 3. Cohesion: head for the perceived center of mass of the boids in your immediate neighborhood. Boids can be structured as a cellular automaton along the lines of Life, with each boid seeing only its immediate surroundings and acting based on simple rules. Indeed, cellular automatons such as Life provide us with a paradigm for emergence: the higher-level features of a world, which clearly are the result of the activities of the individual agents, arise with a complexity and intricacy of design that seem totally at odds with the simple, on-off rules of the individual agents.

See also Conway’s Game of Life Conway’s Game of Life: as an agent-based model, 32–33, 122–123; and boids, 37; and computational irreducibility, 32; and context, 122–124; in the context of radical uncertainty, 123–124; emergence in, 32; rules of, 30–31; self-replication features of, 32; and Turing’s halting problem, 55 credit default swaps, 163–165 Cruise, Tom, 94 Darwin, Charles, 72–73 Dawkins, Richard, 181 decimalization, 149 deduction, 15, 107, 124, 180–183, 188–189 degenerative research program, 90–91 Demon of Our Own Design, A, 108, 157 Department of Defense, 158 Deutsche Bank, 165 diversification, 15–16 Dodd-Frank Act, 156–157 Dostoyevsky, Fyodor, 116 Duffie, Darrell, 152–153 dynamic stochastic general equilibrium model, 92 efficient market hypothesis, 116 emergence, 12; and boids, 37; and complexity, 38; and crises, 105; flock of birds movement, example of, 37; and Hajj stampede, 35–36; and heuristics, 65; and limits to knowledge, 52; and neoclassical economics, 83 (see also neoclassical economics); school of fish movement, example of, 36; and stability, 39; stampedes, example of 127–128; traffic example, 95, 97–98; and traffic flow, 17, 94 enclosures, 5 equilibrium, crises of, 104–105 ergodicity, 12, 17–18, 41, 196; context of, 40; history of, 40; and limits to knowledge, 52; and MGonz, 44; and neoclassical economics, 84 (see also neoclassical economics); in physical systems, 40; in physical versus social sciences, 85; testing models of, 177 essayism, 178 eternal recurrence, 60 fallibility, 59, 115, 117; and the rational expectations hypothesis, 175 Feynman, Richard, 54, 90 financial crises: fire marshal analogy, 127–129; financial crisis of 1987, 90; financial crisis of 2008, 92 (see also financial crisis of 2008); structure of, 129 financial crisis of 2008, 157; an agent-based view, 160; contagion during, 160; leverage and, 156, 176; liquidity and, 156; market-to-market difficulties and, 159–164; regulation and, 156; role of AIG in, 163–165; role of Bear Stearns Asset Management (BSAM) in, 161–162 (see also Bear Stearns Asset Management); role of Goldman Sachs in, 163–164 financial institutions: agents of, 99, 106; interactions between, 128–131 financial markets: complexity of, 108–109, 157; crisis in, 14–16, 108–109; environment of, 100–101; fire marshal analogy, 127–128; and Flash Crash, 147–151; and liquidity, 206; and reflexivity, 59; structure of, 128; weather analogy 113, 185–186 Financial Stability Oversight Council, 158 financial system: fire marshal analogy, 129; flows of, 131; multilayer schematic of, 131, 134; schematic system of, 129; structure of, 129, 131 fire sale, 107; asset-based, 138; funding-based, 139 Flash Crash, 147; effect of decimalization on, 149–150; effect of high-frequency trading on, 150; The Price is Right analogy, 148–150 Flaubert, Gustave, 116 Freudianism, 58 Frydman, Roman, 175 funding, 131, 134; cash providers of, 136; and collateral, 137; flows within financial system, 137; and hedge funds, 136; securities lenders for, 136 funding runs, 138–139 Funes, the Memorious, 75–78 Game of Life.

If you read the accounts by those who were in the middle of, say, the Bear Stearns implosion, the observations and actions don’t follow some model. The accounts are about stressed-out people packed around a table trying to puzzle out what’s going on and devise the best course of action As an example of the difference between focusing on dynamic interactions based on heuristics and a general model, let’s go back to the boids of chapter 3—modeling birds in flight. How do we explain the ability of birds to fly in V formations? A model consistent with the neoclassical approach would determine a utility function to optimize the effort and speed of the birds, dealing with the dynamics of flight. This will lead to a complex mathematical problem that can be the fodder for all sorts of follow-on manipulations. We do not know what heuristics a bird actually uses, but if we are going to take a stab at it, the simpler the heuristic we apply the better.

pages: 797 words: 227,399

Robotics Revolution and Conflict in the 21st Century by P. W. Singer

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

The beauty of the swarm, and why it is so appealing to military thinkers for unmanned war, is how it can perform incredibly complex tasks by each part’s following incredibly simple rules. A good example of this is a flock of birds. Hundreds of birds can move together almost as if they have a single bird in charge, speeding in one direction, then turning in unison and flying off in a different direction and speed, without any bird bumping into the other. They don’t just use this for what one can think of as tactical operations, but also at the strategic level, with flocks migrating in unison over thousands of miles. As one army colonel asked, “Obviously the birds lack published doctrine and are not receiving instructions from their flight leader, so how can they accomplish the kind of self-organization necessary for flocking?” The answer actually comes from a researcher, Craig Reynolds, who built a program for what he called “boids,” artificial birds. As an army report on the experience described, all the boids needed to do to organize themselves together as a flock was for each individual boid to follow three simple rules: “1.

As an army report on the experience described, all the boids needed to do to organize themselves together as a flock was for each individual boid to follow three simple rules: “1. Separation: Don’t get too close to any object, including other boids. 2. Alignment: Try to match the speed and direction of nearby boids. 3. Cohesion: Head for the perceived center of mass of the boids in your immediate neighborhood.” This basic boid system worked so well that it was also used in the movie Batman Returns, to create the realistic-looking bat sequences. From simple rules then emerge complex behaviors. There are many other examples of how complex, self-organizing systems work outside of nature. One is how big cities like New York never run out of food, despite the fact that no one is in charge of creating a master plan for moving food into and around the city.

The U.S. military hopes to do this by building what it calls “an unassailable wireless ‘Internet in the sky.’ ” Basically, it plans to take the kind of wireless network you might use at Starbucks and make it global by beaming it off of satellites, so a robot anywhere in the world could hook into and share information instantaneously. Of course, others think that this will make U.S. military doctrine inherently vulnerable to computer hacking, or even worse. As one military researcher put it, “They should just go ahead and call it Skynet.” Just as the birds and the boids follow very simple rules to carry out very complex operations, so would an unmanned swarm in war. Each system would be given a few operating orders and let loose, each robot acting on its own, but also in collaboration with all the others. The direction of the swarm could be roughly guided by giving the robots a series of objectives ranked in priority, such as a list of targets given point value rankings.

pages: 402 words: 110,972

Nerds on Wall Street: Math, Machines and Wired Markets by David J. Leinweber

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

But giving them a few simple rules, like “fly toward the closest bird,” “go with the flow,” and “don’t hit other birds,” could give rise to distinctly birdlike behavior. The original ALife flock is Craig Reynolds’ “Boids,” done at Symbolics in 1986.† Simulated herding and flocking turn out to be of some commercial interest. Those massive stampedes in Disney cartoons, with thousands of <insert fast, large mammal of your choice>, and all those schools of talking fish are descendants of the Boids. Hollywood showed its appreciation by giving Reynolds an Academy Award in 1998. *“The Santa Fe Institute is devoted to creating a new kind of scientific research community, one emphasizing multidisciplinary collaboration in pursuit of understanding the common themes that arise in natural, artificial, and social systems.” It was founded in 1984 (www.santafe.edu/). † . . . and still flocking after all these years at www.red3d.com/cwr/boids. 156 Nerds on Wall Str eet Like our early algos, the SFI artificial life was dumb, just obeying a few simple handwritten rules, without any ability to learn from mistakes.

pages: 287 words: 86,919

Protocol: how control exists after decentralization by Alexander R. Galloway

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

The ecologically minded Ray has gone so far as to advocate the institution on the Net of a wildlife preserve for digital organisms. He writes: “I proposed to create a very large, complex and inter-connected region of cyberspace that will be inoculated with digital organisms which will be allowed to evolve freely through natural selection”94—the goal of which is to model the 92. For other examples of artiﬁcial life computer systems, see Craig Reynolds’s “boids” and the ﬂocking algorithm that governs their behavior, Larry Yaeger’s “Polyworld,” Myron Krüger’s “Critter,” John Conway’s “Game of Life,” and others. 93. Tom Ray, “What Tierra Is,” available online at http://www.hip.atr.co.jp/~ray/tierra/ whatis.html. 94. Tom Ray, “Beyond Tierra: Towards the Digital Wildlife Reserve,” available online at http://www1.univap.br/~pedrob/PAPERS/FSP_96/APRIL_07/tom_ray/node5.html.

Some might say naive,” write the editors of 2600, a quarterly journal on hacking. “We believe in freedom of speech, the right to explore and learn by doing, and the tremendous power of the individual.”30 Yet this is a new type of individual. This is not the same individual who is the subject of enlightenment liberalism. It is an extension (perhaps) of the modern dream of individuality and independence. Yet this new resistive agent has more in common with the autonomous “boids” of Tom Ray’s Tierra than with radicals from protocol’s prehistory. “A true hacker is not a group person,”31 wrote Stewart Brand in 1972. Or, as he would write ﬁfteen years later: “Workers of the world, fan out”32—advice that inverts the message of resistance-through-unity found in Marx and Engel’s Communist Manifesto. Critical Art Ensemble agrees with this inversion, writing that “[t]he use of power through number—from labor unions to activist organizations—is bankrupt, because such a strategy requires . . . the existence of a centralized present enemy.”