[HN Gopher] Boids
___________________________________________________________________
Boids
Author : jonbaer
Score : 277 points
Date : 2020-03-28 07:30 UTC (15 hours ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| timtimmy wrote:
| 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
|
| [0]: https://twitter.com/timd_ca/status/1243941167005192192?s=20
|
| [1]: https://wickedengine.net/2018/05/21/scalabe-gpu-fluid-
| simula...
|
| [2]: https://prism.ucalgary.ca/handle/1880/111493
|
| [3]: https://youtu.be/6CsxADBpal0
| banana-slug wrote:
| Here is a thematically-related boids simulation from 2006:
| https://www.red3d.com/cwr/papers/2006/PSCrowdSandbox2006.pdf
|
| Did 10,000 to 20,000 agents at 60 fps. Puny compared to yours,
| but not bad for 14 years ago!
| https://www.youtube.com/watch?v=Jpy5rJSVLj8
| https://www.youtube.com/watch?v=ZZoy-8xK0YI
| carapace wrote:
| That's insanely cool!
| gdubs wrote:
| 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.
|
| 1:
| https://www.instagram.com/p/B4t4ewCplfR/?igshid=1uxnng6idsqb...
|
| 2: https://developer.nvidia.com/gpugems/gpugems3/part-v-
| physics...
|
| edit: Here's a low-res animated GIF for anyone who doesn't want
| to click an instagram link:
| http://gregorywieber.com/assets/images/art/murmuration.gif
| afro88 wrote:
| 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 :/
| anotheryou wrote:
| Beautiful example:
|
| https://twitter.com/OskSta/status/1219340987299966976
|
| https://twitter.com/OskSta/status/1219343599336333319
|
| https://twitter.com/OskSta/status/1225037781858234368
| mshafer wrote:
| 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.
| anotheryou wrote:
| A real challenger to the Return of the Obra Din Devlog :)
|
| https://forums.tigsource.com/index.php?PHPSESSID=qvfvkcqtfr9.
| ..
| glouwbug wrote:
| StarCraft 2 used boids, and I'm using boids to rewrite Age of
| Empires II:
|
| github.com/glouw/openempires
| marktangotango wrote:
| 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?
| glouwbug wrote:
| 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!
| pugworthy wrote:
| Here's an answer I put up on gamedev stackexchange a while
| back with that idea in mind ->
| https://gamedev.stackexchange.com/questions/166448/rts-
| attac...
| jbverschoor wrote:
| I remember boids was one of the example programs with the
| direct3d sdk back in the '90s
| qubex wrote:
| 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.
| SanderSantema wrote:
| That's right, currently reading it for my uni course :)
| juanuys wrote:
| 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" :)
|
| https://github.com/juanuys/boids
| matsemann wrote:
| 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.
|
| [0]: https://matsemann.github.io/boids-workshop/ [1]:
| https://github.com/Matsemann/boids-workshop [2]:
| https://news.ycombinator.com/item?id=9300142
| nitrogen wrote:
| 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 :).
| parhamn wrote:
| I had fun playing with the parameters, thanks! Now, I want a
| wallpaper version of this with low maxSpeeds. Very relaxing.
| zanderwohl wrote:
| 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.
| kpgiskpg wrote:
| That's fun, thanks!
| jonbaer wrote:
| https://github.com/search?q=boids
| banana-slug wrote:
| Note that this one (https://github.com/meshula/OpenSteer) is
| the "semi official" port of OpenSteer, a library for steering
| behaviors, which is the generalization of the ideas underlying
| boids, as described in
| http://www.red3d.com/cwr/papers/1999/gdc99steer.html
| ur-whale wrote:
| 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.
| glouwbug wrote:
| 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
| jonbaer wrote:
| Boids in 3D Unity: https://github.com/SebLague/Boids and the
| excellent related video
| https://www.youtube.com/watch?v=bqtqltqcQhw
| juanuys wrote:
| Does it use the GPU?
|
| https://github.com/SebLague/Boids/blob/master/Assets/Scripts...
|
| If so, then awesome :)
| semi-extrinsic wrote:
| Blender also has boids you can play with. Here are some fishy
| ones:
|
| https://m.youtube.com/watch?v=zN2bhKyCJwk
|
| It looks really good even though the "fish" are just made from
| two pyramids.
| mehmetoguzderin wrote:
| WGSL [0] implementation of Boids:
| https://dawn.googlesource.com/tint/+/refs/heads/master/test/...
|
| [0]: http://gpuweb.github.io/gpuweb/wgsl
| bschne wrote:
| Dan Shiffman over on The Coding Train has a nice walkthrouhg of
| implementing this in P5.js
|
| https://www.youtube.com/watch?v=mhjuuHl6qHM
| mar77i wrote:
| Recently did that code as presented using pygame, but I haven't
| uploaded it anywhere yet, that might be a good idea, though.
| [deleted]
| robotresearcher wrote:
| Reynolds put up a page about Boids in 1995 and added links to
| related work for a few years. Great stuff.
|
| https://www.red3d.com/cwr/boids/
| miniatureape wrote:
| I posted this simple boid drawing toy a year or two ago:
| https://miniatureape.github.io/boiddraw/
| DonHopkins wrote:
| I've confirmed with Craig Reynolds that yes indeed, then name of
| Boids was inspired by The Producers:
|
| https://www.youtube.com/watch?v=aL6mTMShVyk
|
| >"He's up on the roof with his boids. He keeps boids. Doity,
| disgusting, filthy, lice ridden boids." -The Concierge, not a
| Madam
| rootbear wrote:
| I had no idea! I would have guessed it was a contraction of
| "bird-oid", or something like that.
| DonHopkins wrote:
| That too, but it's only the cover story for people without a
| New York Metropolitan accent!
|
| https://en.wikipedia.org/wiki/Boids
|
| >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".
| jaltekruse wrote:
| 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!
| banana-slug wrote:
| You need a better dictionary: https://www.merriam-
| webster.com/dictionary/boid
|
| Long before the flocking model, "boid" referred to snakes of
| the Boidae family, like boas and anacondas.
| fanf2 wrote:
| Scrabble doesn't use any dictionary:
|
| https://scrabble.merriam.com/finder/boid (for the USA and
| Canada)
|
| https://www.collinsdictionary.com/scrabble/ (for English in
| the rest of the world)
| contingencies wrote:
| 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
| jzting wrote:
| I also have an implementation [0] that shows the paths of the
| boids. Based on the parameters, some very interesting patterns
| emerge!
|
| [0] http://jzlabs.com/
| dang wrote:
| Related from 2015: https://news.ycombinator.com/item?id=9298338
|
| 2011: https://news.ycombinator.com/item?id=2504652
|
| 2014: https://news.ycombinator.com/item?id=7293350
|
| One comment from 2018:
| https://news.ycombinator.com/item?id=17167077
|
| (Links for the curious. Reposts are ok after a year:
| https://news.ycombinator.com/newsfaq.html)
| [deleted]
| anoopelias wrote:
| Now who doesn't have an implementation of Boids of their own...
| :)
|
| https://anoopelias.github.io/boids/
| postnihilism wrote:
| It's a classic :)
|
| I made a little framework for building these types of models:
| https://github.com/jrhdoty/SwarmJS
|
| Here's a boids implementation using it:
| http://jrhdoty.github.io/SwarmJS/
| foreigner wrote:
| 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".
| banana-slug wrote:
| Nice boid-related tutorial:
| https://www.youtube.com/watch?v=bqtqltqcQhw
| diggan wrote:
| 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.
|
| Some links if you want to try it out:
|
| - https://docs.blender.org/manual/en/latest/physics/particles/...
|
| - https://www.blendernation.com/2019/07/06/how-to-use-boids-in...
|
| - https://www.blendernation.com/2008/01/05/simulating-flocks-h...
|
| - http://feeblemind.tuxfamily.org/blog/index.php?post/2007/12/...
| jsilence wrote:
| Could that be used to simulate the pandemic?
| wwwhizz wrote:
| 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.
|
| For a nice visualization and simulation of a spreading virus
| and why social distancing is a good idea:
| https://www.washingtonpost.com/graphics/2020/world/corona-si...
| qubex wrote:
| 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.
| [deleted]
| jonbaer wrote:
| 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.
| DonHopkins wrote:
| 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".
|
| https://www.youtube.com/watch?v=T2iZPRif2i4
|
| http://www.red3d.com/cwr/steer/
|
| http://www.red3d.com/cwr/papers/1999/gdc99steer.html
|
| http://www.red3d.com/cwr/steer/gdc99/
|
| https://forum.unity.com/threads/opensteer-for-unity3d.26906/
|
| https://code.google.com/archive/p/opensteerdotnet/
|
| https://github.com/ricardojmendez/UnitySteer
|
| http://opensteer.sourceforge.net/
|
| 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.
|
| Last modified: October 25, 2004
| vortico wrote:
| 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.
| pinkfoot wrote:
| #3Blue1Brown has decent (simple) SIR epidemic simulation
|
| https://youtu.be/gxAaO2rsdIs
| timtimmy wrote:
| It's a great video. His source is here: https://github.com/3b
| 1b/manim/blob/shaders/from_3b1b/active/...
| escot wrote:
| > Incidentally, "boid" is also a New York Metropolitan dialect
| pronunciation for "bird".
| diekhans wrote:
| It is a beautiful paper, well worth reading the original.
___________________________________________________________________
(page generated 2020-03-28 23:00 UTC)