I have an implementation here [0] if people want to play with it. Supports dynamically changing the controls, has obstacles and predators. Setting weights for separation, alignment and cohesion to zero and then increasing only one of them nicely shows which role each of them plays. It's actually made as a workshop [1] for my company, where the shell is provided and one has to implement it step by step. In Norwegian, though.
Update: Dang linked other discussions, and I see I commented on one from 2015 [2]. Someone there asked for the course content, and that's available (in English!) in a PDF in [1]. This workshop/implementation is actually an example of what I wanted the students to make at the time. Which I then retrofitted to a fun workshop for my colleagues.
Works great on my phone. I noticed that flocks tended to split when they wrap around the edge of the field, as if forces weren't being computed wrapped. Makes it hard to accomplish my goal of merging all the boids into a single flock :).
Yeah, the neighbourhood calculation doesn't wrap around. That's trivial to add, but then one has to account for the wrapping when calculating average neighbourposition so it's not completely off. Not too hard, but would have added complexity to the workshop.
These guys behave just like the implementation I wrote! I worked out how to do separation, cohesion, and alignment based on written descriptions as an exercise.
Boids are my favourite hello world for 3D simulation environments. For the last few weeks, I've been using boids to update my GPU programming skills and knowledge of related algorithms in Unity and Unreal.
Yesterday I got 0.5 million boids simulating in Unreal Engine at 45 fps on a GTX 1080 [0]. The bottle neck is rendering so many instanced cone meshes, the simulation without rendering can do 1 million boids at 120 fps. I'm borrowing a common data structure used in GPU fluid simulations, the dynamic hashed grid, to calculate the neighbourhood of each boid (cool tutorial here with full source code [1]). We need the neighbourhoods to calculate their urges. My code is a mess at the moment, but if there is interest I can post it to GitHub (Unity and Unreal).
Boids are an example of agent-based modelling and swarm systems. I used agent-based modelling in my PhD thesis to construct and simulate realtime, interactive 3D biomolecular models of mitochondria and neuromuscular synapses [2,3]. Now that I'm free (graduated), I'm building an iPad app to teach and communicate structural and molecular biology with immersive, and realtime simulations. Our vision is to make molecular and structural biology immersive and fun. It's not a textbook, it's a little more like Neil Stephenson's young lady's illustrated primer! :D
It wasn't Unreal Engine that gave you that perf. It was your GTX 1080. Unreal Engine (or any Engine) in this situation is doing next to nothing.
Sorry it's just this kind of thing pushed my buttons. I see someone showing their engine and claiming perf when their example is 99.999% GPU and 0.001% anything to do with their engine.
It's unrelated to boids, but I would not recommend using the Poly6 and Spiky kernels. That design originates from "Particle-based fluid simulation for interactive applications" (2003) by Müller et al., and they choose the spiky kernel on the assumption that a zero gradient at the origin is the reason why particles sometimes get stuck together. However, the clumping phenomenon was more closely studied by Dehnen and Aly in "Improving convergence in smoothed particle hydrodynamics simulations without pairing instability" (2012) [https://doi.org/10.1111/j.1365-2966.2012.21439.x]. They showed that you can predict pairing instability based on neighbour count, and that kernel functions that are everywhere positive within the Fourier domain do not exhibit that instability.
The Wendland family of kernel functions are thus recommended, as they fulfill that criteria. Though, for low neighbour counts a quartic B-spline is a good alternative.
Thank you for that Firehose of Fun! Especially the GPU dynamic hashed grid, which looks super useful.
Amazing work! LifeBrush is Emacs for Cytoplasm! I've read that those little thing-a-ma-bobs in your cells move around at something like 30 miles an hour, bumping into each other. Is that accurate? Does that simulation show them slowed down a lot? Would it just be a blur in real time? Is that software available, please?
You are right, they move insanely fast. The average speed of a medium-sized protein is about 5 m/s. Inside an E. coli, any two proteins will encounter each other at least once a second [0] (this book is incredible).
My simulation is inaccurate in terms of Brownian motion. It is slowed down and smoothed for illustrative purposes. It should be more violent. Nice idea with blurring, I'll think about that. The code is on GitHub. It requires a VR headset, and it is frankly a little clunky and "research code" in terms of the UI. But check it out :D [1]. The next version will support larger simulations on the GPU and a more friendly UI. I have friends at the Scripps institute who work on similar stuff, check them out [2].
Thank you for publishing the code as open source! I'll check it out. Do you have any idea how much work it would be to adapt it to Unity3D's ECS (DOTS: Data-Oriented Technology Stack) and shader system, or somehow get it running on WebGL? At least the simulation and rendering part, if not (yet) the VR stuff, so it can reach the widest audience.
2:58> The ribosome uses tRNA to match mRNA codons to amino acids. We paint a cloud of tRNA near the ribosome. tRNA, molecular agents, need amino acids. So we paint a cloud of of amino acids nearby. Brownian motion brings tRNA and ribosomes together. But that takes a long time. However, our system is interactive and immersive. So we grab the ribosome and move it around. Now we see how the ribosome marches along the mRNA, with tRNA depositing amino acids onto a growing poly-peptide chain in blue. We reach the end of the mRNA, and the mRNA and poly-peptide chains are released.
So in order to avoid waiting for brownian motion to do its thing over time, you just grabbed the ribosome's lazy ass and dragged him over near the mRNA, then threaded it into his jaws, and waved him around through a cloud of amino acids and tRNA to feed him, so he sucks up the tRNA pasta and mRNA meatballs and amino acid sauce, just like Lady and the Tramp eating spaghetti to Bella Notte, and then he pumps out useful proteins, just like the Golden Goose.
The immersive interactivity is (in a good way) like the Libertarian wet dream wish-fulfillment of the invisible hand of unobservable market forces, or the Intelligent Design pseudo-scientific fantasy of God directly intervening in the affairs of molecules! Ribosomes could be the next Tamagotchi! ;) Ribosomegotchi?
You obviously know this stuff well, but I want to mention that your videos "LifeBrush: Discrete element texture synthesis overview" and "LifeBrush: Bunny-planet design session" using Greg Turk's Stanford bunny impress me as an homage to his work on mapping bunnies with 2d textures, and Andy Witkin's work on reaction-diffusion textures, and also looks inspired by the Photoshop smart clone tool.
LifeBrush: Discrete element texture synthesis overview
Reaction Diffusion Textures. (animation) 1991. Nonlinear partial differential equations as a means of artistic expression. Shown at SIGGRAPH '91 electronic theater. mpeg (209K).
Reaction Diffusion Textures. 1991, with Michael Kass. Nonlinear partial differential equations as a means of artistic expression. This image won the Prix Ars Electronica '92 grand prix for computer graphics. postscript. pdf. citation.
Using Particles to Sample and Control Implicit Surfaces. 1994, with Paul Heckbert. Quasi-physical particles that float on an implicit surface. We use mutual repulsion and fissioning to quickly obtain a good sampling of the surface, and to maintain it as the surface deforms. postscript. pdf. citation. mpeg(23K). BIG mpeg (868K.)
I love the interactivity in your workshop sandbox. Is the bottleneck your Boid.findNeighbours function? (that was the first thing I tried on the GPU, except GPU parallelism let's us get away with 50,000 boids).
Yup, it's the neighbour function being the problem. And of course updating even more boids, but that just scales linearly, but its noticeable when decreasing the neighbour radius which gives each boid less other boids to adjust to.
My neighbourhood implementation is the naive n^2 loop, so it's probably trivial to make it better. Quadtrees, or even just simple caching / zoning would probably allow me to dish out many more boids.
It also doesn't help that in order to be easy as a workshop, it's written in a way that's easy to implement, but slow to execute.
In that Satisfactory demo, the guy took it to flabbergastingly ridiculous extremes of complexity, far beyond what the game designers intended, with thousands of factories consuming resources and pumping out and products, miles of tangled conveyor belts strung all around through the sky, stitched together with mergers and splitters, collected and buffered in storage containers, moving, mixing and diffusing millions of individual items all around the environment. But I get the impression that's hardly scratching the surface when it comes to biology.
Your Bunny Planet design session really illustrates how wonderfully your work applies to computer games:
Chaim Gingold (one of the developers of Spore) made "Earth: A Primer", a cool interactive educational simulation science book, also like your work, inspired by Neil Stephenson's young lady's illustrated primer, but on a somewhat different physical scale:
I sent Chaim some links to your work, and he loved it and said he has collaborator who will be delighted to learn about it too. He also teaches computer game design, and did his PhD thesis on "Play Design". You should work together, and fill in all the levels between planets and cytoplasm! ;)
If you're in 3D animation/modeling/whatever and have a little bit of experience, Blender has a pretty stable simulation of Boids that is lots of fun to play around with. It's been built-in into Blender since... For as long as I remember, and it has lots of properties you can play around with, and you can also make the boids be rigid bodies as well so they can interact with other elements in your scene.
>Boids is an artificial life program, developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds. His paper on this topic was published in 1987 in the proceedings of the ACM SIGGRAPH conference. The name "boid" corresponds to a shortened version of "bird-oid object", which refers to a bird-like object. Incidentally, "boid" is also a New York Metropolitan dialect pronunciation for "bird".
>"The motion of a flock of birds is... simple in concept yet is so visually complex it seems randomly arrayed and yet is magnificently synchronous. Perhaps most puzzling is the strong impression of intentional centralised control. Yet all evidence indicates that flock motion must be merely the aggregate result of the actions of individual animals, each acting solely on the basis of its local perception of the world." - Craig Reynolds
[...]
>References: "Artificial Life : The Quest for a New Creation" - Steven Levy
>A "Boid" is a virtual entity used in "Boids", an artificial life program simulating the behavior of birds or fish in their flocks or schools, respectively (with each other, as well as their environment), developed at Symbolics Inc. in 1986 by Craig Reynolds, an artificial life and computer graphics expert, and named "steering behavior".[1] The source code has been released a few years after 1986, allowing the creation of many variants since then, including Valve's creature (that even resembles the original Boids by Reynolds). It is also implemented in the free C++ library OpenSteer, designed to help construct steering behaviors for autonomous characters in games and animation.
>The term "Boid" is the abbreviation of "birdoid" ("like a bird"), as the program rules applied equally to simulated flocking birds and schooling fish. It was also inspired by a scene from Mel Brooks' 1968 film The Producers where the playwright's landlord complained about his keeping pigeons on the roof, referring to them as "boids", or "bird" in a stereotypical New York accent. The term also linked up with the ellipsoid-based 3D modeling tool by Tom Duff at the Graphics Lab of New York Institute of Technology named "soids".[2] Therefore, in regard of the source of the creature's name, its proper in-universe name remains unknown.
Alvy Ray Smith used Tom Duff's "soids" (short for "ellipsoids") for Chromagnon:
>It was also inspired by a graphics modelling and rendering system by Tom Duff when he was at the Computer Graphics Lab of the New York Institute of Technology. It used ellipsoids as its primitive shape and was called "soids".
>[You need to be using an Java-enabled browser to see this demo.]
(more information about this applet is available)
>In 1986 I made a computer model of coordinated animal motion such as bird flocks and fish schools. It was based on three dimensional computational geometry of the sort normally used in computer animation or computer aided design. I called the software boids.
[...]
Brunel University Artificial Intelligence Site / Artificial Life / Boids / Three "Boid" Term Sources
>I have learned (on extremely good authority!) that there were actually three sources of the term 'boid'! Here they are:
>"Boid" was an abbreviation of "birdoid", as his rules applied equally to simulated flocking birds, and schooling fish.
>It was also inspired by a graphics modelling and rendering system by Tom Duff when he was at the Computer Graphics Lab of the New York Institute of Technology. It used ellipsoids as its primitive shape and was called "soids".
>Finally, there was a Mel Brooks film called The Producers starring Zero Mostel and Gene Wilder which contained a scene where the playwright's landlord complained about his keeping pigeons on the roof ("You used to be able to sit on the stoop like a normal person, but not any more, 'cause of da BOIDS. Dirty, lousy, stinkin' BOIDS")
I recently implemented boids in a compute shader [1]. It’s using Apple’s Metal framework, and rendered in 3D. The boids are simple triangles, and I added a bit of specular shading to give them a little bit of a “shimmer” as they flock.
I implemented an NVIDIA algorithm for running n-body simulations on the GPU. The constraint is memory access, which can freeze up in a case like this. [2]. Converting from CUDA to Metal wasn’t too bad.
Love it, and the others on your instagram. You should start a dedicated account for them. I would like to follow your art, but feels weird seeing family photos of someone I don't know :/
Oskar’s tweets showing his city-builder are some of my favourite things on the internet. His combination of 3D rendering and artistic style is just black magic to me.
Might be a dumb thing to post on hacker news, but I tried using the word boid or boids in Scrabble and my competitive wife wouldn't let me because it wasn't in the dictionary. It fit so well too!
Previously we played with the Australian reference, the Macquarie Dictionary. Subsequently, as an international family finding that an expensive and static resource insufficiently engaged with international usage we began to play admitting anything in either dictionary.com or wiktionary with an English entry, excepting proper names and non-naturalized acronyms. As official scrabble cheat words cover a lot of random Scots/Welsh, you might choose to permit those (single result page on Wiktionary). It starts to get ridiculous fast. I personally love the learning aspect and we do not play the traditional "challenge" rule, in fact we actively encourage consultation of reference works before and after each play. I am a big fan of Wiktionary, occasionally adding to existing English and Middle Chinese entries.
For example, according to Wiktionary, boid (and its plural) should be permitted under etymology two, ie. member of the family Boidae of non-venomous snakes or etymology three, ie. Nonstandard spelling of bird representing the New York City pronunciation. We would not permit it under etymology one (computer program name). Now look - you learned something! https://en.wiktionary.org/wiki/boid#English
I recommend one of my favourite books, Gary William Flake’s 1998 The Computational Beauty of Nature to anybody interested in boids or other computational models of social, chemical, and physical phenomena.
Therein the author covers boids extensively and in detail. If I am not mistaken it is in section 16.3 that the author treats boids fairly extensively.
I made a Three.js boids implementation for an interview once. The role was for web dev, but the theme was "come and teach us about something that interests you" :)
Good old Boids! I implemented a clone of Boids in C as my senior project in high school. It included 3D wireframe graphics from scratch. My teacher said it was "A nice screensaver".
I’ve often pondered the feasibility of using boids (or a boid like rule system) to implement ancient combat formations like pike squares skirmish lines. Is that what you’re doing?
Yes, though I'm not at the formation stage just yet. Boids just know how to stear organically much like Zerglings do.
Boids just provide distancing at the micro level. Astar or Greedy First Best at the macro level ultimately provides the boid with a final destination, and the boids organically work together on path to their respective final destinations.
Rise of Nations did it almost perfectly in the early 2000s with left box drag for selection and right box drag for retangular placement. Rome Total War upped the antics a bit with 10,000 unit scales over Rise of Nations 200 unit scales, but suffered some serious bugs. In my opinion no one except Julius Caesar can "program" so many units to properly do their bidding!
Slightly OT, but this is a very interesting problem to implement on a GPU because it very much resembles in its structure the implementation of exact N-body simulator on massively parallel machines.
Yes boids are great for parallelization. Each boid must compute a stressor imposed by neighboring boids based on the three rules in the paper (separation, alignment, and drifting towards center of mass). The stressor for each boid is simply applied to each boids velocity. Given a thousand threads / cpus / cuda cores, what have you, each unit can be applied to a single boid
No, definitely not: ‘boids’ serve to show how synchronised collective behaviour can arise in swarms of agents that can observe only a handful of their closest neighbours whilst following pre-determined rules. Virii have no such perceptive capability.
S-I-R (Susceptible, Infected, Recovered/Removed) models of epidemiology are a far better place to begin for reasonably realistic and tractable modelling and prediction of epidemics.
Maybe, but a simulation is only as good as its model. If this model of boids does not have the same properties as the pandemic, the simulation is probably not good enough.
No. It's an unrelated set of rules. The best way to simulate a disease is to model each person in the country as an individual agent. Even a naive movement model for humans won't look like anything like bird flocking.
Physical movement. It struck me that movement of belief systems looks LOTS like boid flocking. It's even possible to map social connectedness by things like Facebook etc. to size of neighborhood, and probably limits on how large a 'neighborhood' can practically be when it represents the belief systems of those in contact with you.
I think (maybe) a better question might be if a boids strategy could somehow be used to avoid a pandemic(?) - if all information is known. Seems like we are all performing a 6ft. collision detection @ the moment.
Speaking of boids and social distancing, Craig Reynolds (author of Boids) has also developed the open source library/toolkit "OpenSteer: Steering Behaviors for Autonomous Characters". It's based on his GDC 1999 paper, "Steering Behaviors For Autonomous Characters". I think there's a Unity3D plugin that incorporates a derivative of that code.
In OpenSteer terms, social distancing would include "unaligned collision avoidance" and "separation" steering behaviors, which can be combined with other behaviors including "seek", "flee", "pursuit", "evasion", "offset pursuit", "arrival", "obstacle avoidance", "wanderer", "path following", "wall following", "containment", "flow field following", "cohesion", "alignment", and "leader following". You can also implement your own custom plug-ins, if you need something special like "curly floor spinning".
OpenSteer is a C++ library to help construct steering behaviors for autonomous characters in games and animation. In addition to the library, OpenSteer provides an OpenGL-based application called OpenSteerDemo which displays predefined demonstrations of steering behaviors. The user can quickly prototype, visualize, annotate and debug new steering behaviors by writing a plug-in for OpenSteerDemo.
OpenSteer provides a toolkit of steering behaviors, defined in terms of an abstract mobile agent called a "vehicle." Sample code is provided, including a simple vehicle implementation and examples of combining simple steering behaviors to produce more complex behavior. OpenSteer's classes have been designed to flexibly integrate with existing game engines by either layering or inheritance.
OpenSteerDemo's plug-in framework allows a game AI programmer to quickly prototype behaviors during game design, and to develop behaviors before the main game engine is finished. OpenSteerDemo allows the user to interactively adjust aspects of the simulation. The user can: start, stop and single step time, select the vehicle/ character/ agent of interest, adjust the camera's view and its tracking behavior.
OpenSteer is distributed as open source software in accordance with the MIT License. OpenSteer was developed with the generous support of Sony Computer Entertainment America. OpenSteer is supported on Linux, Mac OS X and Windows.
Update: Dang linked other discussions, and I see I commented on one from 2015 [2]. Someone there asked for the course content, and that's available (in English!) in a PDF in [1]. This workshop/implementation is actually an example of what I wanted the students to make at the time. Which I then retrofitted to a fun workshop for my colleagues.
[0]: https://matsemann.github.io/boids-workshop/ [1]: https://github.com/Matsemann/boids-workshop [2]: https://news.ycombinator.com/item?id=9300142