Coding Adventure: Boids

hi everyone in this episode of coding adventures I'd like to play around with some boy it's this rather strange term is what Craig Reynolds uses to describe bird-like objects in his paper on flocks herds and schools so once I'd read through that I created some little flying triangles to represent these creatures to do anything interesting though they were going to need an awareness of their surroundings so I'll highlight one of them to be our subject of study this boy should be able to sense the others inside the circle which is its radius of vision we can also define a view angle so that it can't see directly behind itself now the paper describes three rules that determine the behavior of each Boyd rule number one is to steer away from any nearby Boyd's to hopefully avoid crashing into them so with this rule enabled you can see them fairly successfully dodging and swerving to avoid one another next rule number two tells them to steer to move in the same direction as nearby Boyd's this alignment also helps them to avoid bumping into one another and of course makes them behave more like an actual flock of birds finally rule number three this rule is to steer towards the center of any nearby Boyd's by itself this can cause them to form that all swirling patterns but let me now add the other rules back in suddenly the Boyd's are trying to not crash into one another while also simultaneously trying to align directions and sort of jostle for position at the center of their flock mates I think it's really cool how these three simple rules commonly referred to as separation alignment and cohesion combine to give rise to what looks like fairly complex and coordinated behavior these rules can also be applied to a three-dimensional world currently the boys are just transported to the other side of the cube when they hit a wall but I wanted them to instead avoid the walls as well as any other obstacles that there might be my idea was to simply cast rays after increasing angles until it clear path is found to apply this to three dimensions I needed a good way of generating points on a sphere and after surfing the web a little I found an approach will be first generate points inside a disc so I start with the loop for the number of points I want and inside there I define a distance which will just go from 0 to 1 over the course of the loop I'll then have an angle and each iteration that'll turn some fraction of a circle the distance in the angle can then be used to calculate a point so however X is equal to distance times the cosine of the angle and y is equal to distance times the sine of the angle and then I'll plot that point so initially all the points are just in a straight line but as the turn fraction increases we can start to see the spiral forming we can play around with different values for example at 0.5 we get two ends which makes sense since we're making a half turn each iteration and they sort of wrap around each other as the turn fraction increases to get a good distribution of points we want to avoid any of them lining up and so we should use a nice irrational number as the turn fraction what's recommended in particular is the golden ratio in case like me you only have vague recollections of what that is essentially say you have a line segment called a and another shorter segment called B when the length of both segments together divided by the length of the long segment is equal to the long one divided by the short one that's the golden ratio represented by this very fancy symbol Phi if we then do some maths we can find that the positive solution to this equation is one plus the square root of five over two or about 1.618 so let's plug that in is the turn fraction and as you can see this gives us a really nice distribution of points I wanted to play around with this some more because I think it looks kind of interesting so I added some code for highlighting every endpoint by checking of I plus some offset what the highlight value is equal to zero so here we can see what it looks like with every second point highlighted every third point and so on now I know people have been talking about sunflowers in the Fibonacci sequence for ages but I've never paid much attention to what the connection actually is so in case you're also a little late to the party what we can do is list the first few numbers in the Fibonacci sequence over here and I'll now highlight every 34th point or seed in a case of a sunflower this shows a curve coming from the edge of the disk to the center if I add an offset of 13 we hop over to the next curve notice the 13 is also a Fibonacci number two spots below 34 so hopping 13 each time we can count the number of curves as you can see there are 34 of them if I now highlight every 55th which is the next Fibonacci number up we get a curve going in the other direction I'll make the offset 21 and if we count again we'll see that there are 55 so pretty fascinating I think how these Fibonacci numbers are sort of embedded in the pattern with 55 arms going this way and 34 the other way it's perhaps not surprising then that 55 / 34 is particulars to the golden ratio and that's actually a property of the Fibonacci sequence that you get more and more accurate approximations of the golden ratio the higher up you go okay I've got a little sidetracked what I need to do now is stop the points from being so bunched up in the center so I'll raise the distance to some power in the code here that power is currently 1 but if I lower it to 0.5 which is same as taking the square root you can see how the distribution gets corrected making the power negative looks pretty cool too but I should probably get back on topic so projecting this - a sphere requires a few modifications and I'll link to the write-up I followed in case you want to read more about it and apparently not very good at following instructions though because they first ended up with this highly unspiritual shape I then swapped some sines and cosines around and got this and then finally after a bit of trial and error it worked it's kind of fun to play around with this turn fraction again now that it's a sphere but I should really get back to the Boyd's so I cannot specify the number of collision Ares along with the view angle and this generates an array of vectors once at the start the Boyd's then have a function that uses array to perform collision checks at increasing angles from their own forward direction until an unobstructed Direction is found I tried testing this with a single Boyd moving a block around to block its path and it seemed to work pretty well I then let a bunch of them fly around an empty room to see how this new obstacle avoidance force would interact with their existing separation alignment and cohesion forces and it seemed like they were still behaving quite nicely another thing I experimented with was adding a targeting force so that the try flight towards this sphere as I moved it around finally I wanted to test the obstacle avoidance in a more elaborate setup so I created a little course with an arch and some hoops and let the Boyd's fly loose in there [Music] I was having a big issue with performance though because each Boyd had to live over every other Boyd to find the ones nearby so I spent a while creating a spatial partitioning scheme where each Boyd is placed into a cell based on its position Boyd's then only need to worry about the other Boyd's in neighboring cells well this did help a lot I found it was actually faster to just do the crude loop overall Boyd's but inside a computer so there could be done in parallel of course combining the petitioning with the shader would be way way faster but I mean you to learn some more before I'm ready to tackle that now a little while back I made this underwater scene during my much in cubes adventure and many of you in the comments suggested bringing it to life with some fish well boy it is the perfect approach for that so I downloaded a little fish model and found a shader online that Wiggles the vertices of the model to make it look like it's swimming I'll link to that in the description so now I just need to board my submarine and go swimming with the fishes all right that's everything for this coding adventure thanks for watching edges

Channel: Sebastian Lague

Views: 1,566,912

Keywords: boids, flocking, simulation, programming, coding, algorithm, birds, computer science, video game, fish ai

Id: bqtqltqcQhw

Length: 8min 35sec (515 seconds)

Published: Mon Aug 26 2019