Flocking Simulation with Boids Algorithm in JavaScript and p5.js

[00:00:00](train whistle blows) - Hello and welcome to a coding challenge.

[00:00:03]In this coding challenge, I should probably go eat lunch but I'm going to just try this coding challenge.

[00:00:08]I am going to attempt to program this.

[00:00:10]This is a flocking simulation.

[00:00:11]What you're seeing right now is an example that I made many years ago of a flocking simulation, a Boids system running in processing.

[00:00:20]I'm going to try to make exactly this or close to it in JavaScript with the p5 library starting from no code at all.

[00:00:28]Obviously besides the dependencies.

[00:00:30]Okay, so this is the example running.

[00:00:32]Let me just give you a little bit of background here.

[00:00:34]If you want to learn more about the flocking algorithm as invented by Craig Reynolds, you can go to this link to read this explanation of it.

[00:00:45]And find many other links and resources down here, whoa, that's a lot of stuff.

[00:00:49]Have fun, see you in a few weeks.

[00:00:52]You can also check out this YouTube video of the original 1986 flocking simulation.

[00:00:59]Wow, that's amazing.

[00:01:01]This is so cool, oh my God, I love that.

[00:01:04]You can also find an explanation of it as part of my Nature of Code book online with some diagrams and code written in Processing and an exercise that you can try which I'll refer to back at the end.

[00:01:16]But I'm going to start from this, a blank slate.

[00:01:19]I just have the canvas, you have some amount of pixels in it.

[00:01:23]There is nothing happening in the console.

[00:01:27]I've got this code set up and draw.

[00:01:30]So I'm going to write this code without worrying about being perfectly organized and being able to scale it very easily.

[00:01:36]I just want to get the algorithm working but of course, where is the button?

[00:01:42](pop music) If you want to see a refactored example of it, you can probably go and look and actually, at my finished version in the Nature of Code which I'll also link to.

[00:01:51]The first thing that I want to do though is I want to add another JavaScript file called particle.js.

[00:02:02]Actually, I should rename this to boid.js.

[00:02:07]What is this term Boid?

[00:02:09]When Craig Reynolds invented this algorithm for simulating a flocking system like a flock of birds or a swarm of bees, I suppose he didn't want to use the term bird, but it is kind of like bird, so Boid, it's kind of like droid but Boid.

[00:02:26]Go read the original paper about steering behaviors and flocking systems and you'll find out more about the history about this.

[00:02:33]But I'm going to make a class called Boid and I am going to use the p5 vector object.

[00:02:46]I'm going to make Boid objects and each time I made a Boid object, I need a constructor and I am going to give each Boid a position.

[00:02:58]I'm going to give each Boid a velocity.

[00:03:04]I'm going to give each Boid an acceleration.

[00:03:09]All of those are going to be vectors.

[00:03:10]I'm doing this is 2D.

[00:03:11]You should, after you watch this, if you watch this, you should make your own 3D version of this.

[00:03:16]All of the math will work exactly the same way but you'll just need to rethink how you're visualizing this.

[00:03:23]Just to give things a start, let's just put the position in the middle of the window and let's write a function called show which will just draw them as a circle right now.

[00:03:36]Actually, I'll just even use point, like strokeWeight 16.

[00:03:42]Stroke 255, point this.position.x.

[00:03:49]I think Visual Studio code will do this for me.

[00:03:52]No, where does it?

[00:03:54]It fixed that for me once, whatever.

[00:03:57]This PointerEvent, I'm not a PointerEvent, I'm a point.

[00:04:03]So now, if I were to then here make a flock, which is an array, and I should probably make a flock class, that might be a thing to refactor later.

[00:04:16]But I'm just going to say a flock.push new Boid and then I just want to say for every Boid in the flock and I'm using of, I'm using a for-of loop but I said in because that's the way I feel right now.

[00:04:33]A boid.show and then I need to make sure I am also referencing boid.js in my index HTML so I have the basic Boid class, which just creates a position, velocity, acceleration and draws it as a point and then I have my sketch where I make one Boid and I draw it in the center of the screen.

[00:04:53]There it is, there's my boid.

[00:04:55](bell rings) Step one complete.

[00:04:57]I probably should plan this out but I have one Boid, that's good.

[00:05:00]Now, let's have that Boid move.

[00:05:03]Let's actually write in the Boid object a function called update and this I probably covered ad nauseum in a lot of other videos in my whole Nature of Code series.

[00:05:14]But the idea here is that position is updated based on the Boid's velocity and its velocity is updated based on the Boid's acceleration.

[00:05:27]If I now actually create a p5.vector, a random 2D.

[00:05:35]I believe this is a function that will give me a random velocity vector and I now go in here and say boid.update.

[00:05:46]Oh I just spelled it wrong.

[00:05:47]I thought I missed the this dots.

[00:05:49]Here we go, look, it's moving.

[00:05:51]It's moving with a random velocity each time.

[00:05:54]Okay, now let's just make a bunch of these.

[00:06:02]Now I have a system of 100 Boids but it's interesting, look at this, it fans out in the perfect circle.

[00:06:08]Do you know why that is?

[00:06:10]Because I make a Boid and I give it a random velocity.

[00:06:17]That random vector is always of unit length one.

[00:06:21]The direction is something different so they're all actually moving with the same speed.

[00:06:25]If I wanted them to have, and this is not an important detail to the flocking stuff, but just to sort of get a sense of how this vector stuff works, I could say this.velocity.setMag, which is set the magnitude to a random value between 0.5 and 1.5.

[00:06:45]Now, you can see now they're all moving with a slightly different velocity.

[00:06:49]This is by the way, a nice little almost like explosion motif and I could have them with a real big burst then they slow down.

[00:06:56]There's all sorts of physics-y stuff I could do with this but I just want to do flocking.

[00:07:00]How, how, how do I do flocking?

[00:07:03]Let's return to this paper here.

[00:07:06]This is the key behind Craig Reynolds' flocking algorithm.

[00:07:11]Three rules.

[00:07:14]Separation: steer to avoid crowding local flockmates.

[00:07:19]Alignment: steer towards the average heading of local flockmates.

[00:07:24]Cohesion: steer to move toward the average position of local flockmates.

[00:07:30]Something so crucial in that description is the word local, local.

[00:07:35]Local, what does that mean?

[00:07:37]Let's just do, I think the easiest one to do actually is alignment.

[00:07:43]Let's say there are five Boids.

[00:07:47]Actually, let's make a lot more of them.

[00:07:49]These are all of my Boids.

[00:07:52]This is the one that I'm currently operating around.

[00:07:55]It has a velocity vector like this.

[00:07:57]Let me just make up, let's just pretend like the ones around it are kind of moving all in the same direction.

[00:08:02]Because that'll be easier to think about.

[00:08:05]This is the current one that I'm looking at.

[00:08:08]And maybe some of these others are also moving in other directions also.

[00:08:14]I could take the approach to say this particular Boid needs to align itself to everything.

[00:08:21]But this is not really how complex systems in nature actually work.

[00:08:27]The emergent phenomena comes from this Boid having a limited perception of its environment.

[00:08:33]So maybe, it's actually only able to see things that are in front of it or behind it or to the right or what's probably the most simplest thing to implement is within some radius.

[00:08:43]So I only want to look at the Boids that are within this radius, meaning this one, this one, this one, this one, this one.

[00:08:50]What if I iterate over all these ones that are within some distance, average all of their velocities and shift this velocity in the direction of all those velocities.

[00:09:01]That's what we want to do.

[00:09:03]I am going to write a function now.

[00:09:07]I'm going to put it in the Boid and I'm going to call it align and it's going to get presumably an array of other Boids.

[00:09:15]The idea is this function align this Boid with all the other Boids.

[00:09:20]So what do I need to do?

[00:09:22]I'm going to make a variable called average which is going to be a vector then I am going to iterate over and I could do all of these with reduce probably in some higher order array functions.

[00:09:36]That's a great thing for you to do.

[00:09:38](pop music) Refactor it later but I'm just going to do it this way, I'm actually going to use i because that's maybe going to help me.

[00:09:51]I'm not really sure but I'm going to use i right now.

[00:09:54]Actually, no, I'll still use a for-of loop.

[00:09:56]Let other, I'm going to call it other of Boids and I'm going to just say average.add other.velocity.

[00:10:09]So I'm adding up all of the velocities.

[00:10:12]This is how you do an average, right?

[00:10:13]Vectors, again you might want to go watch my videos about how vectors work, but a vector, a p5 vector just holds an x and a y or a x and y and a z.

[00:10:22]So I want to average the vector, represented as an arrow with an x component and a y component.

[00:10:27]If I want to average, just like I might average an array of numbers, I add them all up and divide by the total.

[00:10:32]Then I would say average.divide by Boids.length.

[00:10:38]This would be a way of getting the average velocity of all the Boids but remember I only want the ones within some distance.

[00:10:49]So actually, let's implement that right now.

[00:10:53]Let's have some sort of distance like max.

[00:10:58]I'll call it perception equals let's just make it arbitrarily like 100 and then I'm going to now say if the distance between this.position.x.

[00:11:10]You know what?

[00:11:12]I think there's a p5.

[00:11:13]This is fine.

[00:11:14]It's just going to be, it's kind of long the way I'm writing this but I don't mind.

[00:11:17]Let's actually make it in a variable.

[00:11:19]D = the distance between this Boid's position and the other Boid's position, x and y.

[00:11:34]If that distance is less than 100, look at that.

[00:11:40]Look at this fancy thing that it's doing.

[00:11:42]I have some prettier stuff that doesn't want to let me write a long line of code.

[00:11:46]I guess I'll keep that in there for right now.

[00:11:49]So I'm calculating the distance between this Boid's position and the other Boid's position.

[00:11:53]If that distance is less than 100, I'm adding it up and I should also probably have a total number, total = zero.

[00:12:03]Add it up.

[00:12:04]I also should probably ignore myself and if other does not equal this, right?

[00:12:16]So I basically, I might as well put that first.

[00:12:19]As long as the other thing is not me and the distance is less than 100, add it up and then divide by the total.

[00:12:28]But obviously, I only want to divide by the total if total is greater than zero.

[00:12:37]All right, so this is kind of a little bit of a long-winded algorithm now.

[00:12:41]And perception.

[00:12:42]If d is less than perception.

[00:12:46]So I'm starting with a perception, a radius of 100.

[00:12:49]Maybe that would be better if I called it perceptionRadius, that's really what it is.

[00:12:55]Starting with a perception radius of 100, an empty vector, adding up the velocities of any vector, any Boid that's near me, dividing by the total and as long as I've found one, dividing by that total.

[00:13:08]Now here's the thing.

[00:13:09]I could just say, for example I could do something weird, this will be really weird.

[00:13:13]I could just say this.velocity equals average.

[00:13:17]What if I did that?

[00:13:19]Then I said Boid, like here I said boid.align flock.

[00:13:27]I don't know what's going to happen here, but let's refresh this.

[00:13:31]They just basically don't go anywhere.

[00:13:33]Because they're all instantly equal to each other's velocity.

[00:13:37]That's not really a good way.

[00:13:38]What I need to do now is if I don't want to actually assign its velocity to that average directly.

[00:13:44]I want to steer towards it.

[00:13:48]This is where Craig Reynolds' steering formula comes in.

[00:13:52]A steering force equals some desired velocity minus the current actual velocity.

[00:14:02]It's kind of like the error.

[00:14:04]If I am moving this way.

[00:14:08]Sorry, if I'm moving this way but I want to move this way, the way I want to move minus the way I am moving is the steering force meaning push me in that direction.

[00:14:21]Apply a force.

[00:14:22]Maybe I'm going to turn the steering wheel.

[00:14:24]You can think of these as bees or cars or birds or whatever.

[00:14:27]This formula desired minus velocity will give me the steering force and what is the desired velocity here?

[00:14:35]The desired velocity is actually that average.

[00:14:37]I'm actually going to rename this to desired and I'm going to add it up and divide by total and then I'm going to say this.velocity equals, no, I'm not going to say that.

[00:14:48]I'm going to say steering equals.

[00:14:57]I should actually call this steering because I could do all of this.

[00:15:02]I don't need to save anything as I'm going.

[00:15:04]I'm going to call that the steering force.

[00:15:06]I'm going to add all the velocities.

[00:15:09]I'm going to divide by the total and then, I'm going to say steering force is the desired subtract this.velocity.

[00:15:20]And I'm going to say return steering.

[00:15:23]I want this function to basically, I want this function to return that force.

[00:15:28]So really what I should be doing is I should have, I'm going to write a function called flock.

[00:15:33]That's maybe more like, yeah.

[00:15:36]Flock with some number of Boids and then I'm going to say alignment equals align with those Boids.

[00:15:49]So I'm going to get this force and I suppose steering is here, so you know what?

[00:16:02]I should always return steering.

[00:16:04]I want to always return a vector but if it didn't find anything, I'll just return the zero vector.

[00:16:10]Then, what I'm going to do is I'm going to say acceleration add alignment.

[00:16:17]The idea, the way that a physics engine works, and this has to do with, this is a very simple crude physics engine.

[00:16:26]Force equals mass times acceleration.

[00:16:29]This is Newton's Law of Motion.

[00:16:31]Or acceleration equals force divided by mass or in a world where the mass of everything is one, acceleration equals force.

[00:16:39]So if I want to apply a force to this object, I just need to set the acceleration to that force.

[00:16:45]Actually, that's what I'm going to do just starting out here.

[00:16:48]I'm going to say acceleration equals alignment.

[00:16:53]So now, if I go back to sketch and I say Boid.flock Boids, we should now have all of Boids doing that with just implemented with that alignment rule.

[00:17:12]Let's see.

[00:17:13]Boids is not defined.

[00:17:14]Sketch.js line 14.

[00:17:17]Oh, it's called flock.

[00:17:17]Oh, this is my variable naming is terrible.

[00:17:22]But I'm going to leave it that way right way.

[00:17:25]Align is not defined.

[00:17:26]Boid.js align Boids.

[00:17:31]Oh, this.align, this.align Boids.

[00:17:35]Acceleration is not defined, oh my goodness.

[00:17:40](pop music) Let me actually not have them all start in the same place because that is just to see this effect happen, let me actually start them in random places on the screen.

[00:17:58]Let me change that.

[00:18:00]Let me make the perception radius a little bit smaller and I don't know why this matters, but let me draw them like a little bit smaller.

[00:18:08]Let me actually have them start out going quite a bit faster.

[00:18:17]You can see as they get near each other, they start to get each other's velocity.

[00:18:23]They start to average each velocity with their neighbor's.

[00:18:26]You start to see these clumps moving together.

[00:18:29]So much more to do on this.

[00:18:30]Oh my goodness, but first a couple things.

[00:18:34]One is I have now basically allowed these Boids to steer with infinite power in a way.

[00:18:47]We should probably have a variable.

[00:18:50]I'm going to call it maxForce.

[00:18:53]I'm going to set it equal to one for a second and then what I'm going to do is here, I'm going to say a steering limit this.maxForce.

[00:19:05]What this does is it limits the magnitude, the length of that vector to some maximum force so this should be exactly the same.

[00:19:12]We're not seeing anything different but if I were to make maximum force 0.01, like really small right now, you're going to see they're not actually changing their velocity.

[00:19:24]They are, but very, very slowly.

[00:19:27]The other thing we're really going to need to do is I just have to give up and do this.

[00:19:31]I'm going to add something for the edges here.

[00:19:34]I'm going to say if this.position.x is greater than the width, this.position.x should equal zero.

[00:19:45]Else, if this.position.x is less than zero, this.position.x equals width.

[00:19:52]Then I'm just going to do that for the y, with, with, x, x, y, y, y, x, x, x, x, with, with.

[00:19:59]All right, and now here, let's do boid.edges.

[00:20:07]We should see them reappear wrapping around and now, let's go back to the Boid and let's make this 0.2 is kind of reasonable-ish.

[00:20:23]Interestingly enough, they're kind of like it slows them down which is interesting.

[00:20:30]But I'm only doing alignment right now, but you can see how this works.

[00:20:33]You can see how they're all starting to align with each other.

[00:20:35]I could keep them going at some minimum velocity which might make sense.

[00:20:38]You can see how these are going back and forth.

[00:20:41]But you get the idea.

[00:20:42]Why are they all slowing down?

[00:20:46]Is that just a coincidence?

[00:20:48]One thing I could do is this is actually going to be worth it because I should also give them a maximum speed.

[00:20:56]This is going to be a parameter of a variable that's going to allow me to control the system pretty well and I could consider their desired velocity in the alignment to not actually be the actual average velocity but just the average direction because I could then say steering.setMag to this.maximum speed.

[00:21:19]So basically I'm saying I always want to go in the direction of my neighbor but at maximum speed.

[00:21:24]I don't know that that's really an important detail, but if I add that in here, we might get the effect that I was hoping to get.

[00:21:30]Now, this is what I was expecting to see.

[00:21:32]As they get near each other, they're all starting to align together.

[00:21:36]Let me refresh that one more time.

[00:21:38]You can see that they're clumping and as they group, they all start to align.

[00:21:42]This is the alignment rule.

[00:21:43]This is a very simple rule.

[00:21:45]It's predictable, it's obvious, this is alignment.

[00:21:48]Now, all we need to do is add cohesion and separation.

[00:21:52]Separation is going to be the hardest one to do.

[00:21:54]So let's do cohesion next.

[00:21:56]Same thing, we're going to look at our neighbors.

[00:21:59]We should go back to what the rule was actually defined as, let's go back to Craig Reynolds' original page.

[00:22:05]Cohesion: steer to move toward the average position of local flockmates.

[00:22:10]This is actually not going to be that hard because we've already calculated the average velocity of local flockmates.

[00:22:19]Now, let's just duplicate that code.

[00:22:21]I know, I know we could refactor it.

[00:22:22]I won't play the song.

[00:22:24]Because we could probably do this all in one fell swoop.

[00:22:26]There's so many possibilities but now I just want to get the average location of my local flockmates and steer towards that.

[00:22:33]So, the way I'm going to do that is I'm just going to go nuts and copy paste this whole thing and call it cohesion and I'm going to keep the perception radius, I'm going to keep this idea of steering, keep this idea of total.

[00:22:53]Go through all the Boids, check the distance between myself and the other ones, as long as I'm not myself and within the perception radius, what am I doing?

[00:23:01]Steering not the others' velocity but the others' position.

[00:23:05]This should clearly be refactored into its own function but whatever.

[00:23:10]Then as long as I have at least one, I'm going to divide by the total.

[00:23:16]Now I don't want to set the magnitude to the maximum speed so what I have now in steering is the average location.

[00:23:22]So if this is the average location, let's say it's over here, then what I need is a vector that, that's clearly not the average location.

[00:23:32]But let's just say it was.

[00:23:34]The average location is kind of like where this Boid is.

[00:23:36]But I want to steer in that direction so to get a vector in that direction, I take the average location minus the current position of me which is basically saying now what I want to do is say steering subtract this.position so subtract my position now, I've got a vector that's pointing from me to the average location, remember which is in the steering variable then let's say I want to go at maximum speed.

[00:24:06]Then, this is now my desired velocity.

[00:24:10]I'm going to subtract out my current velocity, limit it to max force and there we go.

[00:24:14]That's cohesion.

[00:24:15](bell rings) Now, in flock, let cohesion equal this.cohesion Boids and then oh, we have a big problem.

[00:24:29]This.acceleration equals alignment.

[00:24:31]This.acceleration equals cohesion.

[00:24:32]So how can I set the acceleration to two different forces?

[00:24:36]But before I even answer that, there's an easy answer to that question.

[00:24:40]Let's just comment out alignment and let's watch cohesion happen.

[00:24:48]We can see they start to group together.

[00:24:50]This is cohesion happening.

[00:24:51]And that neighbor radius, by the way, is a super important value.

[00:24:55]Right?

[00:24:56]That neighbor radius, if I were to change that and I have a different, that perception radius, if I were to change that to 10,000 they're all going to come together as one.

[00:25:10]Because they all see everybody.

[00:25:12]If I were to change that to 10, there's really little pairs.

[00:25:18]You can see they kind of get in groups of two.

[00:25:20]The force though isn't so strong.

[00:25:23]So if I were to change the maximum force to one, now you see them, almost like these little electron thingies that start, magnetic things that start to spin around each other and then fan off.

[00:25:37]There's so many possibilities here.

[00:25:42]I could make the maximum speed two.

[00:25:44]I'm not actually limiting it, you can see.

[00:25:45]There you go, that's what I was looking for.

[00:25:47]They get into these little groups but let me go back and say maximum speed is four.

[00:25:51]Maximum force is 22 and I realize this maximum speed is not actually a maximum speed because in update if I really wanted it to be a maximum speed, I would want to say this.velocity limit this.maxSpeed.

[00:26:08]Let's actually add that in and see what we get.

[00:26:12]Oh, and let's put the perception radius back at 100 and there we go.

[00:26:18]Now we have cohesion.

[00:26:20]We have cohesion, what happens if we have cohesion and alignment?

[00:26:23]How do we get cohesion and alignment?

[00:26:26]Okay, this is fun.

[00:26:27]This is really working.

[00:26:28]This is going to be a really long video.

[00:26:30]All right, cohesion and alignment.

[00:26:31]The problem rests here.

[00:26:35]This is actually a really easy thing to solve because this is called force, the answer here is force accumulation.

[00:26:42]In physics, if two forces are acting on an object, the resulting acceleration is the sum of those forces.

[00:26:49]So all I need to do is say acceleration.add alignment and acceleration.add cohesion because why is this not falling?

[00:27:00]Because the force of gravity is pointed this way and the other force of my hand holding it up is pointed in the other direction with an equal magnitude.

[00:27:09]Therefore, it is at rest.

[00:27:11]Those two forces added together have a net acceleration of zero.

[00:27:16]But obviously, all you do is add them together but there is this, if I actually do this right now, we're going to see some really crazy behavior.

[00:27:24]Looks like it's kind of working but it really isn't because what it should also have is this acceleration shouldn't accumulate over time.

[00:27:33]Every moment in time, I start with a net acceleration of zero and add all the forces together.

[00:27:39]So what I should do right before I flock is say this.acceleration set zero, zero.

[00:27:46]This is setting its values to zero and zero.

[00:27:49]Another way I could do that is just multiplying it by zero, because multiplying a vector by zero takes everything out.

[00:27:54]It could make a new vector, whatever.

[00:27:55]But this will work nicely and technically, this also might make more sense here because it's kind of like after I finish updating the velocity then I can reset the acceleration in case there's other things at play.

[00:28:07]Now we can see both cohesion and alignment are at play, look at this.

[00:28:15]Eventually, they're just all going to become this one clump.

[00:28:18]Come on, you can catch up, you got it, go go!

[00:28:21]Go, catch up!

[00:28:22]Yeah! One clump.

[00:28:24]One thing I would like to do.

[00:28:28]I really want to attach sliders to those parameters but I got to resist because we got to have separation.

[00:28:34]We've got alignment.

[00:28:35](bell rings) And cohesion.

[00:28:35](bell rings) Separation, this one is a little bit hard.

[00:28:39]Steer to avoid crowding local flockmates.

[00:28:46]Here's the me.

[00:28:48]That's me, here's my local flockmate.

[00:28:52]If this local flockmate is too close, it's within some sort of distance threshold, I want to steer to avoid that.

[00:29:01]What would be my desired velocity?

[00:29:03]My desired velocity would be to move in the opposite direction.

[00:29:09]So the idea is my desired velocity is in the observable.

[00:29:13]What if there is one here?

[00:29:16]My desired velocity would also be opposite direction so then my next desired velocity would be the average of these two.

[00:29:23]It even would make sense for the magnitude of that desired velocity to be proportional to the distance.

[00:29:31]So if this one is here, I maybe want to avoid it but I only really need to think about avoiding it a little bit.

[00:29:38]If this one's really close, I need to avoid it a lot.

[00:29:40]So the magnitude of the vector is inversely proportional to the distance of the local flockmate.

[00:29:46]This might end up with kind of like a desired velocity of something like this if I'm averaging those two together.

[00:29:52]So let's see if we can implement that.

[00:29:54]Not going to be super easy but let's do it.

[00:29:59]The nice thing is I'm going to start with cohesion because we've kind of, cohesion is close to separation.

[00:30:05]Again, boy.

[00:30:08](pop music) ♪ I will refactor this later ♪ ♪ You know I will refactor this later ♪ ♪ I will refactor this later ♪ - I should show you that I'm wearing my I will factor this later t-shirt, by the way.

[00:30:22]Okay, so separation.

[00:30:24]I'm going to leave this at 100.

[00:30:26]Steering, I think I might need to use, I like the idea of just having one vector that ends up as, it's sort of the average here then it's the difference but I think I need to think, one step at a time.

[00:30:45]I'm creating this vector.

[00:30:46]This is the same.

[00:30:47]If it's not me and it's within the perception radius, what do I need?

[00:30:52]I need a vector, I'm going to call it difference which is the other's.

[00:31:04]I want a vector, sorry, that points from the other to me.

[00:31:13]Because I want that to go to the opposite direction.

[00:31:16]So it's my position minus the other.

[00:31:21]I want a vector, the new vector which is the subtraction between my position and the other's position.

[00:31:34]This is a way of calling the subtract function which doesn't operate on a vector but subtracts two vectors and gives us a new vector which is difference.

[00:31:42]Then, I want the difference to be inversely proportional to the distance so I'm going to multiply it or set its magnitude something like that.

[00:31:54]Or divide by distance.

[00:31:57]I could just say divide by distance, right?

[00:32:00]It's inversely proportional, the farther away it is, the lower the magnitude.

[00:32:07]The closer, the higher the magnitude.

[00:32:11]The distance, I guess technically that distance could be zero and that would be problematic but with floating point math rule, it's never going to get a value of zero.

[00:32:18]Then I want to add.

[00:32:20]Then that is the thing I add up.

[00:32:23]That's the thing I want to average.

[00:32:24]All those vectors that are pointed away from the things near me, I think we're actually in pretty good shape here.

[00:32:30]This isn't as hard as I thought.

[00:32:32]This was the tricky part here.

[00:32:34]Get a vector that's pointing away from the local flockmate, make it inversely proportional to the distance, add it up, then this is the same.

[00:32:42]Because, oh no.

[00:32:44]I don't need to subtract position.

[00:32:46]I kind of don't know if I want to.

[00:32:49]Let's leave this whole always go at maximum speed thing and then the rest is the same.

[00:32:55]Once I have that, just average it, set it to max speed, subtract out the velocity and limit it to maximum force and that's the end.

[00:33:03]Okay, just to be sure this is right, let's go into Boid.

[00:33:09]Let's go to flock.

[00:33:12]Let's add let separation equal this.separation and then let's add in separation.

[00:33:26]I want to not bother adding cohesion and alignment.

[00:33:30]Are these separating?

[00:33:32]Yeah, it looks like they are.

[00:33:33]It looks like when they get close to each other, they're kind of moving away from each other.

[00:33:38]Weird, weird behavior.

[00:33:40]This doesn't look like exactly what I expected.

[00:33:42]Let's give the maximum force, like really let them be super strong about separating.

[00:33:49]There we go.

[00:33:50]So that's more like what I expected.

[00:33:52]That's way too strong.

[00:33:54]Yeah.

[00:33:55]Why do they feel like they're, something is weird here.

[00:33:59]Let's give it a much smaller perception radius.

[00:34:03]Oh yeah, this is what I expected to see and I think it wasn't really a bug in my code.

[00:34:07]It's sort of a bug in my conceptual sense of how this works.

[00:34:11]This is pretty good, this is what I want to see.

[00:34:13]This is separation only.

[00:34:15]Now, we should be able to see and let's I'm going to do this really quickly.

[00:34:21]I'm going to not be thoughtful at all about the interface but just so I can debug this effectively, I am going to go into sketch.js.

[00:34:32]I am going to say let alignSlider, cohesionSlider and separationSlider.

[00:34:43]AlignSlider equals createSlider.

[00:34:45]I'm going to give it a range between one and five.

[00:34:48]Actually, let's give it a range between zero, sorry, zero and five, with a starting value of one and increment value of 0.1.

[00:34:58]I want to do this for all of these sliders.

[00:35:00]Then in Boid, I want to say where I call in flock, I want to just scale them.

[00:35:07]I'm going to say separation.multiply separationSlider.value.

[00:35:16]I'm going to do this also for cohesion and for alignment.

[00:35:21]Now, by the way.

[00:35:22](bell rings) (train whistle blows) Flocking.

[00:35:26]This is now the flocking simulation.

[00:35:27]I didn't draw them as triangles.

[00:35:28]They're not rotating, but this is the flocking simulation.

[00:35:31]But just for the sake of argument, this should be what order did I make them in?

[00:35:35]They're not labeled.

[00:35:36]So let's just turn all the way up to separation.

[00:35:38]Oh boy.

[00:35:39]Let's turn off.

[00:35:43]This is only separation.

[00:35:46]Now, turn that off.

[00:35:47]Let's turn on only alignment.

[00:35:50]Whoa, that's oh they're just the alignment is so strong.

[00:35:54]When the alignment is so strong, it makes them go in circles around each other.

[00:35:58]I have to talk about why.

[00:36:00]Why did that happen that they were twirling in circles?

[00:36:02]Well, look at this.

[00:36:03]I'm updating them one at a time.

[00:36:06]The next one is flocking with the previous ones updated value, right?

[00:36:10]Instead of taking a snapshot of all their current velocities and then each one updates based on that snapshot, I start with a set of velocities.

[00:36:18]I update the first one based on the set of velocities and now its new velocity is there.

[00:36:22]So when the next one, it's actually updating itself based on the previous one that I updated which is not how the world works.

[00:36:27]It's not how time works.

[00:36:29]That's causing them to ripple into each other based on the order and go in circles.

[00:36:33]That is something that you might want to consider fixing.

[00:36:34]I'm not going to fix that but now I can really play with these, I can get different sort of qualities of flocking based on how strong I make these rules.

[00:36:43]So no alignment, a lot of cohesion.

[00:36:45]No separation, add a lot of separation.

[00:36:48]Less cohesion.

[00:36:51]Separation, I shouldn't make too strong but it's important and then let's add some alignment back in and there we go.

[00:36:56]Flocking.

[00:36:57](bell rings) Okay, this coding challenge is complete.

[00:37:01]It is done.

[00:37:02]I will be uploading the code, if you want you can look at the video description to find the code as a snapshot, that's exactly what it is.

[00:37:08]Let's go make a list.

[00:37:10]Let's make a list on the board of things you might try to do.

[00:37:14]Number one, snapshot of all velocities.

[00:37:20]That's going to be my code for that.

[00:37:21]Number two, an optimization you can do is called spatial subdivision or a quadtree optimization.

[00:37:31]One of the things that makes this really slow.

[00:37:34]And I'll just show you here for a second, is if I were to try to do this with a 1,000 Boids.

[00:37:43]Look how slow this is.

[00:37:44]But you have to realize, it's not a big deal for p5 to draw 1,000 things moving.

[00:37:52]Why it's fine drawing 1,000 things moving but as soon as I put the flock function in, it's super slow.

[00:37:58]The reason that is is because it's got to do and every Boid, check every Boid against every other Boid check.

[00:38:06]So there's a way of subdividing the space, spatial subdivision into bins or buckets and have the Boids only check ones that are near each other in the same buckets.

[00:38:17]That's called, I probably have a lot of distance calculation, I could reduce the number of times I call it.

[00:38:24]But for this, quadtree or just simple spatial subdivision.

[00:38:31]These are things you could try.

[00:38:32]These are just code refactoring, really.

[00:38:34]Actually, the other thing you could try is really build a more sophisticated interface and there's lots of other parameters that you could control and try.

[00:38:49]There's the perception radius, there's maximum force, there's maximum speed.

[00:39:00]Each rule could have a different perception radius.

[00:39:03]So many possibilities.

[00:39:06]This is the stuff that you could do to really control and tweak all the values and play with it.

[00:39:12]Another thing you could do is just design, visual design, like are they triangles, circles, are they flapping butterflies.

[00:39:21]How do you, design of the Boids?

[00:39:25]Make your own beautiful visualization of how you design and draw them.

[00:39:28]Tadpole-like, there's so many ideas there.

[00:39:32]Another thing you could try to do is 3D.

[00:39:35]Can you extrapolate this into 3D?

[00:39:38]If you see the word quaternian anywhere you start to research, you might want to turn back.

[00:39:43]But you could extrapolate this into 3D.

[00:39:46]Another suggestion which came from the chat, thank you, is Boids with different parameters.

[00:39:54]There's no reason why every Boid has to have the same max speed or maximum force.

[00:39:59]Or same perception radius.

[00:40:02]You could implement this thing called the view rule.

[00:40:06]There's two things about this one.

[00:40:07]Each Boid can see everything around it.

[00:40:10]But what if the Boid itself could actually only see if it's moving in this direction, things that are within its particular view in front of it.

[00:40:18]Maybe it doesn't deal with anything that's behind it.

[00:40:20]It doesn't try to do cohesion or alignment or separation.

[00:40:24]Then the view rule which is posited by Flake in the book A Computational Beauty of Nature, I'll link to that book also.

[00:40:31]It's a wonderful book with tons, probably like 90% of the things on my channel are all from the Computational Beauty of Nature book.

[00:40:39]But Flake posits this additional rule that you always want to keep your view empty.

[00:40:44]So if there is a Boid in front of you, you want to steer that way to keep your view empty, clear and this might result, the theory is that this will result in something that looks more like that pattern that you'll see of actual birds flocking where they kind of appear almost in this triangular pattern.

[00:41:05]What's interesting about this, you see a pattern like this, you think, "Ah ha."

[00:41:09]This is a top-down behavior.

[00:41:11]There is a leader, this bird, who is saying to all the other birds, "Fan out from me and follow me."

[00:41:16]But yet, this type of intelligent behavior emergent phenomena can come actually only from simple, local rules of interaction.

[00:41:26]This by the way, this is what this whole video was about, if you didn't gather that already.

[00:41:30]Other ideas might be adding obstacles, other forces, there's thinking about these living in a world where they're interacting with other things, maybe there's a predator that comes in and is chasing them.

[00:41:42]All sorts of unique and interesting possibilities.

[00:41:46]So thank you everyone for watching this coding challenge.

[00:41:50]Put your other ideas for things people could do in the comments and then if you make your own version of this flocking code, please go to the codingtrain.com challenge page and submit a link to what you made.

[00:42:01]I will also make a version of this that runs in the web editor and link to all those resources like the Craig Reynolds original paper about flocking, the video on YouTube and the chapter in my Nature of Code book, okay?

[00:42:12]Thanks for watching this coding challenge on flocking and I'll see you soon.

[00:42:15](train whistle blows) (upbeat music)