r/Python • • Mar 27 '20

I Made This Boids - organic motion from 3 simple rules

2.2k Upvotes

147 comments sorted by

158

u/[deleted] Mar 27 '20 edited Mar 27 '20

This is one of the rendering of my recent project: Boids. Source code can be found here. Inspired by Code Parade's video.

Here's u/Ph0X's interactive browser version :)

13

u/renaissancenow Mar 27 '20

Thanks! Just read through the source code; it was very instructive. It's practically a tutorial.

3

u/[deleted] Mar 27 '20

Thank you! :)

1

u/chriscorf Mar 28 '20

For sure! Compared to most other projects that are posted here, reading the source code for this project was a pleasant surprise. The code is very well written and practically reads itself :)

5

u/TackoFell Mar 27 '20

Would be cool to program in a couple “herding dogs”

6

u/[deleted] Mar 27 '20

That would indeed be nice, go ahead and do it! :)

2

u/AGI_69 Mar 27 '20

Why do you use GitLab ? Just curious

22

u/[deleted] Mar 27 '20

Dunno.. made the switch when Microsoft bought GitHub. Also because GitLab is FOSS, and maybe for the automatic CI/CD, which GitHub didn't have when MS acquired it and which I might use someday (hopefully)

3

u/beje_ro Mar 27 '20

Maybe also for the fact that you can have private repositories if you do not go over certain transfer threshold...

13

u/Sgt_Gnome Mar 27 '20

I may be wrong or misunderstanding but I'm fairly confident you can have a private repository on GitHub.

7

u/atseniuk Mar 27 '20

You can but that is only since MS bought them :) before it was a paid service

1

u/Sgt_Gnome Mar 27 '20

Do you know why the OP would have switched after MS bought them? Are there privacy concerns?

2

u/moi2388 Mar 27 '20

There are not. In fact, after ms bought it, free tier can also have private repos

1

u/atseniuk Mar 27 '20

Because many people in the FOSS community love to hate MS

5

u/Hawkfiend Mar 27 '20

About a year ago GitHub opened free unlimited private repositories for all users. Only limitation is you can only have 3 collaborators on each of those private repositories.

1

u/c3534l Mar 28 '20

People doing DevOps seem to love GitLab. It's more of an automated code deployment environment that happens to also host code than it is a collection of public gits.

1

u/8FIGMAN Mar 27 '20

Beautiful work there my guy!

0

u/[deleted] Mar 27 '20

[deleted]

16

u/[deleted] Mar 27 '20

I'm interested in the theory behind this. What is the field of study?

43

u/[deleted] Mar 27 '20 edited Mar 27 '20

[removed] — view removed comment

7

u/OzneroI Mar 27 '20

Seems like the kind of thing the military would be interested in for developing drone swarms

5

u/meepsi Mar 28 '20

Dude. Birds aren't real. They are military surveillance drones. Obviously they are already using flocking algorithms.

2

u/c3534l Mar 28 '20 edited Mar 28 '20

Not really. For one you can actually just coordinate drones. There's no need to simulate the flocking behavior of a school of fish / birds when you can actually just tell every bird or fish to move to an exact location at an exact time in an actually coordinated fashion. Also, kind of the whole point of boids is that it looks complicated, but it isn't. People used to marvel at how fish seemed to communicate with each other, which fish were being the marching leader, and how they knew to create and maintain flocks/schools and it turns out they don't; and they don't need to. They can follow other fish, but not so closely that they knock into them, and it gives the appearance of coordinated behavior. This isn't an issue with drone swarms because you can actually just coordinate them, that's not an issue we have.

Now, if you want to study systems theory, chaos theory, and emergent complexity then it's a fascinating area of math and computer science. But I don't think it has many obvious uses for the military.

2

u/[deleted] Mar 27 '20

[removed] — view removed comment

3

u/OzneroI Mar 27 '20

If the units are expendable and you have enough of them I don’t think it really matters

4

u/[deleted] Mar 28 '20

Found the Republican

1

u/[deleted] Mar 27 '20

It would be a first step, the goal would be to create autonomous distributed intelligence.

0

u/dozzinale Mar 27 '20

What’s the exact name of the algorithm or authors’ name?

1

u/c3534l Mar 28 '20

boids

edit: literally just boids: https://en.wikipedia.org/wiki/Boids

The algorithm is: fly/swim towards the other boids, in their direction, but also don't knock into a boid if that's about to happen.

It's famous because it's so simple, and it doesn't seem like it'd be that simple.

46

u/[deleted] Mar 27 '20

What are the rules?

101

u/[deleted] Mar 27 '20 edited Mar 27 '20

Each one has a view radius in which he senses other boids and then he tries to:

  • move in the same direction (alignment)

  • move to the center of those around him (cohesion)

  • avoid collisions (seperation)

Also, they avoid walls when they see one.

In the code, this happens in src/universe.py:reorient

12

u/allomanticpush Mar 27 '20

Are their view radii different for each individual boid? Does their color mean anything, or is it just random? Also, this is so cool, thanks for sharing.

15

u/[deleted] Mar 27 '20 edited Mar 27 '20

No, they all have the same view range (defined here).

The color is just random, to make it look more interesting. I play around a little with the palette.

2

u/timcotten Mar 28 '20

It would be neat to add a virtual 3rd dimension of moving up and down (shrink or enlarge the sprite +- 20%) and add that to the reorientation code.

So track three dimensions and let them arc and swoop using the same rules.

2

u/allomanticpush Mar 27 '20

Cool. That’s what I thought, thanks.

5

u/DuskLab Mar 27 '20

I think they need begin to avoid collisions with walls further away or separate more aggressively upon approach. When two groups are merging near a wall collision, things get a bit messy.

4

u/[deleted] Mar 27 '20

Yeah, I thought about that, but I actually like the simplicity of the 3 rules. I think in this video, that happens mainly because its a little crowded. When you create a bigger universe or spawn less boids, it happens rarely.

6

u/mountainwalker Mar 27 '20

things get a bit messy

Sounds pretty organic to me! 😄

3

u/wjs018 Mar 27 '20

This is a great visualization of one of these types of model. I have had to create similar models to this in the past for school, but they never look this good. This is essentially a modified Vicsek Model that is used everywhere in the scientific community to model emergent behavior of systems. I encourage you to explore tweaking rules, density, noise, speed, etc. and see what kinds of impacts it has on the resulting behavior. There is a reason that this type of model was developed in the 90's and is still actively used today.

3

u/[deleted] Mar 27 '20

Thank you :)

I didn't know about the Vicsek Model. I cant stop myself from playing around with all the parameters, especially the weights of the 3 rules.

What did you study to learn about those models?

5

u/wjs018 Mar 27 '20

I studied physics and a large portion of my department in grad school looked at active systems. That means that many of their assignments had that kind of focus and many of the department seminars were about active systems like this. One of the things that I see the Vicsek model used for a lot is to look at phase transitions. Essentially, the transition from random directional travel to an ordered motion in the "birds" can similarly represent the transition between two phases of some other system. For example, the change between a gas and a liquid of some fluid, or the transition between an isotropic and nematic liquid crystal. This is a really deep rabbit hole, but there is a lot there if that is something you want to pursue going forward.

2

u/[deleted] Mar 27 '20

Damn, sounds super interesting :)

10

u/Cryptokudasai Mar 27 '20

rule 1: A boid may not injure a human being or, through inaction, allow a human being to come to harm

-3

u/MrSydFloyd Mar 27 '20

Here are the rules

7

u/Fun-Visual-School Mar 27 '20

Excellent results. Although they seem at times too eager to spread around equally. It looks unnatural a bit. If you have other intriguing visual demos please consider sharing them in r/VisualSchool. Cheers!

2

u/[deleted] Mar 27 '20

Damn, nicely spotted! I acutally increased the weight of the seperation force by 10% (see this line) because personally I thought they were to bunched up sometimes. I'm considering changing it back now.

3

u/Fun-Visual-School Mar 27 '20

I think allowing for some randomness in this variable would make it look more natural. Harder to spot the rules in action. Now I'm itching to give it a try in Javascript :D

3

u/[deleted] Mar 27 '20

Yes please! A web based version would be really nice.

2

u/[deleted] Mar 27 '20

Neat! Thanks for sharing this.

A few questions and comments:

Why the walrus operator? Does it serve a functional purpose or did you just want to try it out?

On Ubuntu 18.04, the screen size defaults to something larger than full screen.

The exit button does nothing, I had to kill it with Ctrl-C

4

u/[deleted] Mar 27 '20

The walrus operator let's you make assignments in for example if statements. So instead of

temp = func()
if temp:
    do_something(temp)

you can write

if (temp := func()):
    do_something(temp)

I know it's not much but I makes some parts really simple and clean. I was super hyped when I saw it got added in 3.8 and I don't want to code without it now :)


Hm, that's weird, but you can set the resolution with the --res WIDTHxHEIGHT switch, so you might wanna try that.


Yeah, opencv sadly has no real way of detecting if a window is closed, so I had to use some unreliable work around. It's better to exit by pressing the key 'q'.

2

u/[deleted] Mar 27 '20

I see, thanks. The resolution worked well enough. I wonder if some of the math could be farmed out to cython routines to scale up the performance? It would be awesome to run this with a few dozen groups of boids at high resolution.

2

u/[deleted] Mar 27 '20

Well, you can do that, I just takes a while to render the video.. doing that in real-time is tough, as every boid has to loop over every other boid to find out which are his neighbours. That could be done in parallel for a performance boost, or, as u/masterpatricko suggested, you could use a quadtree.

2

u/prittiao Mar 28 '20

what libary did you use for graphics?¡

2

u/[deleted] Mar 28 '20

Its all opencv.

2

u/apivan191 Aug 08 '20

Is there a 3D package that I can code this in python with? It looks so fun

2

u/[deleted] Aug 08 '20

I haven't done anything 3D yet, and I don't think python is the ideal language for that. But you can definitely give it a shot, glut or vulkan look very capable to me, but they are only wrappers, so you might as well use some compiled language with native libraries for performance reasons.

46

u/MyreMyalar Mar 27 '20

Very relaxing to watch.

2

u/RascalMert Mar 28 '20

Happy cake day!

2

u/[deleted] Mar 27 '20

nice!

could you tell me how exactly things like this (like gravity simulations and all) are made? like what modules do you use?

5

u/[deleted] Mar 27 '20

So first of all, the rendering here and the preview window is done with opencv. You can look at there docs, but it's basically just the cv2.imgshow function and the cv2.VideoWriter class.

Then, what I do most of the time is, create 3 classes:

  • Canvas: handles all the drawing and rendering stuff (this is the only class to interact with opencv directly)

  • Some drawable object class: usually holds information like velocity, position, and other attributes of that particular thing (e.g. color, shape); in the gravity simulation, this class was Particle; here, it's Boid

  • Universe: this handles the group of drawbables (boids, particles), updates them, etc

2

u/[deleted] Mar 27 '20

damn

im only a beginner rn but hopefully ill be able to reach this level

great job btw

2

u/[deleted] Mar 27 '20

Just keep learning :)

2

u/WiggleBooks Mar 27 '20

What do you use to render it/make the actual visualization?

Is it possible to view it "in real-time" (like as a seperate window), or just render a seperate video file that you view afterwards?

2

u/[deleted] Mar 27 '20

It's all opencv.

There is actually a preview window. Then, after you closed it (with ctrl-c) you get asked if you want to save the video, unless you set the --preview-only option.

1

u/subject_K81 Mar 27 '20

Change the sprites from arrows to little balls of colored light, maybe add a small comet tail to them and that would make a very nice looking, mesmerizing screensaver

3

u/[deleted] Mar 27 '20

You just have to modify the Boid.draw method here ;)

1

u/pythonhobbit Mar 27 '20

So that's cool, but when will the simulation show how coronavirus spreads less quickly when some boids practice social distancing?

3

u/[deleted] Mar 27 '20

I tried to make a post about something that's not another corona virus simulation/visualisation (although they are quite interesting) ;)

2

u/pythonhobbit Mar 27 '20

Haha I know, I'm just joking around. This is very cool! Great job!

1

u/nirgoon Mar 27 '20

What's up with the lone red arrow?

5

u/[deleted] Mar 27 '20

Good eye! It's highlighted so your eyes have something to follow. It's normally disabled if you run it without the -H/--highlight option.

1

u/[deleted] Mar 27 '20

Fantastic and very neat - a 3D version next?

1

u/[deleted] Mar 27 '20

That's actually what Code Parade did. I think for me it's a little over my head, maybe some time in the future :]

1

u/hale-hortler Mar 27 '20

Cool project, just saw your source code, and i was wondering what the RenderStopped exception is. What is it’s purpose exactly?

2

u/[deleted] Mar 27 '20

It's to notify the caller that the user closed the preview or pressed ctrl-c. The Universe class excepts it in line 103.

Now that you say it, I think I might redo this and just pass this information on with a return value.

1

u/namnnumbr Mar 27 '20

This is excellent! I’d love to have this as a screensaver; do you have any idea how to hook this into an OS for use as a screensaver?

1

u/[deleted] Mar 27 '20

Well if you OS lets you use any video as a screen saver, you could just render a video and select it :)

I don't think that this would be a nice screensaver as it's actually quite performance heavy. Every boid has to loop over every other boid to check if it's im view range. That could be done in parallel to speed things up, but I don't plan on implementing that...

1

u/MasterPatricko Mar 27 '20

If you're interested -- this kind of 2D collision detection is efficiently done using a quadtree.

1

u/[deleted] Mar 27 '20

Ah, just googled it. I might implement this when I feel like it. Til then it has to wait on the todo. ;)

1

u/namnnumbr Mar 27 '20

Fair enough! Thx

1

u/cip43r Mar 27 '20

What algorithm did you use? I would like to think about my own solutions before checking your code. Or could you maybe just post a reference?

2

u/[deleted] Mar 27 '20

The 3 rules all boids follow are actually pretty simple:

  • they try to fly towards the center of mass of all nearby boids

  • they try to match the velocity of nearby boids

  • they try to avoid collisions with walls and other boids

In the readme I linked to a great youtube video about this.

1

u/EffectiveEgg5 Mar 27 '20

This is so similar to flocks of birds flying around

1

u/[deleted] Mar 27 '20

That's actually after what it's modelled. Flocks of birds, fish swarms, anything that moves in groups like that.

1

u/EffectiveEgg5 Mar 27 '20

Its beautiful. I can't comment on fish movement because I don't get to see that everyday, but it's a convincing model (for a layman like me) for bird flight

1

u/nyqu Mar 27 '20 edited Mar 27 '20

Nice, kinda like the old Boids simulation from the... 80s?

You’ve reminded me of a paper I read years ago that figured out how to accurately simulate starling murmurs. Had something to do with how many birds each bird monitors at once.

Edit: Found it.

By reconstructing the three-dimensional positions of individual birds in airborne flocks of a few thousand members, we show that the interaction does not depend on the metric distance, as most current models and theories assume, but rather on the topological distance. In fact, we discovered that each bird interacts on average with a fixed number of neighbors (six to seven), rather than with all neighbors within a fixed metric distance.

However, note:

A recent model for collective behavior locates the optimal range for antipredatory response in 2D between three and five individuals, to be compared with our 3D value of six to seven.

1

u/[deleted] Mar 27 '20

Uhhh, interesting! I might implement it when I have the time.

1

u/Humanist_NA Mar 27 '20

I just read the paper! Was this for school?

2

u/[deleted] Mar 27 '20

Nope, just for fun :)

1

u/Humanist_NA Mar 27 '20

That was seriously well written for fun.

1

u/[deleted] Mar 27 '20

Thank you :)

1

u/IveGotOdds Mar 27 '20

Can you infect some of them and add a toggle for social distancing behavior?

2

u/[deleted] Mar 27 '20

Nooooo, dont make this about corona again! ;)

1

u/TheLowestAnimal Mar 27 '20

Interesting. . . Was thinking about doing something similar in Unity. Wondering thoughbif you leave the simulation running long enough in a contained space like this do they all coalesce into one giant mass?

1

u/[deleted] Mar 27 '20

If you look in the readme of the repo, you can find Code Parades youtube video. He actually did it in Unity.

No, they would stay separate as they can't merge. I did a gravity simulation some time ago. There, with some starting configurations, all particles merge into one big particle.

1

u/WhenitisIsntwhatitis Mar 27 '20

That moment when a new programmer fully realizes the notion of data structures. Thanks for posting the source.

1

u/[deleted] Mar 27 '20

Glad you like it. :)

It's those "Ahhh." moments I love when learning something new. Like you start out and there's all those things you don't understand, and then, slowly, you grasp more and more, until you have a somewhat good overview.

1

u/NaifAlqahtani Mar 27 '20

How do you get smooth animation using python? All libraries I used are missing Vsync and AA...

2

u/[deleted] Mar 27 '20

Opencv has a function to draw antialiased polygons, circles, etc. You just has to set a flag. If you search for 'antialias' in the repo you can see how :)

2

u/NaifAlqahtani Mar 28 '20

What IDE did you use to program this? VSC?

Edit: thanks for the reply btw :P

1

u/[deleted] Mar 28 '20

I use Microsoft's VisualStudio Community (not Code) with a plugin called VSVim. It reads my .vimrc and sets up vim-like keybindings.

1

u/MikeTheWatchGuy Mar 27 '20

Cool to see it's been updated!

I did a PySimpleGUI port of it last year.

https://github.com/MikeTheWatchGuy/boids-PySimpleGUI

It was using P5 at the time I think. Will take another look to see if I can use the new version.

1

u/[deleted] Mar 27 '20

Nice, good job!

1

u/MikeTheWatchGuy Mar 27 '20

Thanks... it was fun to work on.

You might want to consider creating a version that doesn't require 3.8 to run.

1

u/[deleted] Mar 27 '20

Why? I mean, yeah, sure, it wouldn't even take long to do. Just search for := and replace those lines. But why? You'll have to install python 3.8 at some point, might as well be now.. ;)

0

u/MikeTheWatchGuy Mar 27 '20

I was just trying to give you a tip to get more users. No offense meant.

1

u/[deleted] Mar 28 '20

None taken, sorry if I sounded too aggressive :]

2

u/MikeTheWatchGuy Mar 28 '20

👍 It's all good! Really great what you're doing.

2

u/MikeTheWatchGuy Mar 28 '20

I should have been clearer. As a provider of a package or a piece of software others are to use, your goal is to get it into people's hands so that it's used. I assume that's your goal, people using your stuff.

If you're after users, then you want to be able to run on as many systems as possible. You want to remove as many barriers as you can. Make it as easy as possible.

Looking at the stats of people installing PySimpleGUI from PyPI one day this week, their Python versions were:

3.8 24%

3.7 52%

3.6 15%

3.5 2%

2.7 4%

Let's assume we have the exact same users. This means your software will run on 24% of the user's machines. Some % of the other 76% will be willing to upgrade just to use your code, but I doubt it's going to be very high. It takes a lot to get people to move Python versions. The question then becomes - what Python languages features do you use that makes it worth leaving those 76% of the users behind?

I want my package to have as broad of appeal as possible. Raspberry Pi's are still running 3.5. As a result of wanting those Pi users, I write my code to be able to run on 3.5 and up. It means for my core code I don't get to use f-strings, which really really sucks. But everything else I need in my code is handled by 3.5 with no problems.

TLDR - It's different writing code for yourself than writing packages for others. Writing for least common denominator configuration will maximize your reach.

2

u/RGerdedgit Mar 27 '20

2

u/VredditDownloader Mar 27 '20

beep. boop. I'm a bot that provides downloadable links for v.redd.it videos!

I also work with links sent by PM


Info | Support me ❤ | Github

2

u/crazypistolman Mar 28 '20

I would love to see "air resistance" added.

2

u/wizcheez Mar 28 '20

This would totally make for a super cool digital art piece.

2

u/Oatilis Mar 28 '20

Is there a subreddit for this kind of projects?

1

u/wingtales Mar 27 '20

Thank you for sharing this!

1

u/anant80535 Mar 27 '20

beautiful

1

u/katze1123 Mar 27 '20

almost hypnotic

1

u/alanbosco Mar 27 '20

I always wanted to do this. Thanks for the inspiration.

1

u/existentialnoodle Mar 27 '20

I must watch too much TWD. I thought “ahh how zombie hoards form”

1

u/OnlyWarrior Mar 27 '20

This triggers the same part of my brain that makes me want to watch the Roomba

1

u/CobbwebBros Mar 27 '20

BOIDS is amazing

the original 3d animations are so cool

1

u/zzmej1987 Mar 27 '20

Very nice.

1

u/CypherWight07 Mar 27 '20

The natural progression of this: add z-axis, add predator avoidance, add predator blip, submit as simulation of starling murmuration for study.

1

u/nshire Mar 27 '20

Any inspiration from the Boids of half-life?

1

u/timcotten Mar 27 '20

This is beautiful!

1

u/Rwanda_Pinocle Mar 27 '20

Very nice! I always wanted to see if I could find rules that would recreate that thing where you and another person are walking towards each other but neither of you can decide on which side to defer to.

1

u/Darth_Marino Mar 27 '20

They move like sheep

1

u/psych_0man Mar 27 '20

That is so cool. !!

1

u/zoute_haring Mar 27 '20

Thanks, now I can't stop watching.

1

u/[deleted] Mar 27 '20

This can be brilliant live wallpaper

1

u/Dante_Des_Cartes Mar 27 '20

Interesting. Does it converge? Maybe all of them moving together?

1

u/Sovanna Mar 27 '20

Woooa nice work indeed, thx for sharing!! Really appreciate!

1

u/wizardinthewings Mar 27 '20

Super chill.

Oids fan?

1

u/muonzoo Mar 27 '20

ah yes Boids. Original paper : https://dl.acm.org/doi/10.1145/37402.37406

If you aren't doing this in Lisp. ... ;-)

-7

u/Anazucch Mar 27 '20

Too slow. Its annoying me

7

u/[deleted] Mar 27 '20

Then clone the repo and change the BOID_VEL constant in src/__init__.py!

Happy coding :)

0

u/[deleted] Mar 27 '20

[deleted]

9

u/[deleted] Mar 27 '20

Thats pretty much exactly how those boids behave. Each one has a view radius in which he senses other boids and then he tries to:

  • move in the same direction (alignment)

  • move to the center of those around him (cohesion)

  • avoid collisions (seperation)

0

u/[deleted] Mar 27 '20

[deleted]

8

u/[deleted] Mar 27 '20

Absolutely just for fun. I saw this and was inspired to do something similar, although he does it waaay cooler in 3d and stuff.

3

u/Ph0X Mar 27 '20

That's the most fascinating thing about this algorithm, by adjusting the parameters you can get it to stimulate all sorts of wild life, from flocks of birds to schools of fish to herd of animals. It was derived way back in 1987 and been used in many places since, including games like Half-Life and films like Batman Returns.

The simplicity is what I fell in love with though. It really is 3 simple rules anyone can understand, and implementing it is fairly straightforward too. Definitely recommend giving it a try and playing with the parameters. Lots of fun.

I actually have an interactive web version if anyone wants to play around: https://ehsankia.com/cjs/cs521/

Open the flocking menu in the panel and press initialize, then open parameters submenu.

2

u/[deleted] Mar 27 '20

Awesome! Yes, I too can't stop myself from playing around with the parameters :)

Can I link to your interactive version from my main comment in this thread?

1

u/Ph0X Mar 27 '20

Sure, go for it :)

It was a final project for a class, the code is also not minified, though it's transpiled from Typescript which is why it looks a little strange. I should upload the sourcemaps.

0

u/[deleted] Mar 27 '20

[deleted]

2

u/[deleted] Mar 27 '20

Well, you just have to modify the Boid.draw method here ;)