A deep dive into Boids using Niagara in Unreal Engine

hey what's up youtube in this video i'm going to do a breakdown of this niagara particle system i created it's based on the boyd's algorithm i'll put the wikipedia link in the video description below in case you want to read more about it it's an old algorithm invented in the 80s to create emergent behaviors which can be used to mimic how birds and fishes behave in groups the idea is quite simple actually you have a bunch of points or particles each one representing a bird or a fish or whatever and you encode some basic rules that will drive their individual behavior based on the neighboring particles the original boyd's algorithm has three rules alignment which will make particle tend to move in the same directions and neighboring particles do cohesion which will make a particle tend to move towards the center of mass of nearby particles and there's separation which will make a particle turn to move away from nearby particles then you can weight those rules meaning give more importance to let's say the alignment or cohesion and quite magically if you do this just right you may see these flock patterns emerge particles will then have a tendency to form a huge single swarm or a few smaller ones or many even smaller ones depending on the weights you set for this alignment cohesion and separation parameters it's quite fascinating so yes that's the basic idea and something i try to replicate in niagara no i don't think there's one single right way to implement voids it's an id right the algorithm provides guidelines and disclaimer what i'm going to show here is definitely my own interpretation and implementation of this algorithm it's probably not the best but probably not the worst either i'd say it does a job quite well so feel free to take all i'm going to say and show here with a grain of salt and come up with your own unique version i actually pushed the algorithm a little bit further for my own needs and so i implemented some extra features one is a field of view constraint so normally fishes are able to see pretty much all the way around them so it doesn't make too much sense to implement this but i think a fish when behaving in a flock doesn't care so much about other fishes that are behind it they care more about what's ahead and what the flock is doing in front of it so this field of view constraint is a way to cheaply do this but more on this later i also implemented two other rules a fish may not only try to match the flux movement direction but also its movement speed and how quickly it can change its direction so it's a little bit more involved than the basic boyd's algorithm that being said the good news is that the boys algorithm in itself isn't that complex and it's a little part of its beauty and the beauty of emerging behaviors i can only recommend you to take a look at conway's game of life veritasium did a mind-blowing video about it for simple voids there's basically just three rules we need to program alignment cohesion and separation and we'll see in a minute that's not so hard to do and adding even more rules once you have the foundation to code at least one is quite trivial however i'd say boyd's comes with two main difficulties still one is controllability it can be quite finicky to fine tune to have the exact look and behavior you're looking for and sometimes if not implemented quite right or not configured quite right i'd say it can be a bit unstable like the simulation can end up stuck in some repetitive patterns or something for instance at one point i had an issue where fishes were always ending up going round and round in a circle it was driving me mud it looked nice but it was not what i was looking for and it wasn't just due to the boy's weights but also how the flock behavior was interlinked with other constraints i had put in my niagara particle system like distance and altitude limit it was messing everything up but more on that later so yeah it can be quite finicky to work with and then i would argue the second great difficulty that comes with voids is a technical one what i mean by that well the idea of this algorithm is that each particle's behavior is based on all other nearby particles right and so if you implement this naively in c plus plus or in your own game engine or whatever you may end up with a problem which complexity grows squared let's assume we have 10 particles each single one of them need to check for every other particles so that be around 100 checks now let's say you have 100 particles that's almost 10 000 checks what about 10 000 particles that's a lot but it's not so unreasonable i can see that happening next chain right well that'd be almost 100 millions checks so you see it grows at an uncontrollable rate and that obviously wouldn't work for something that is just meant to be a cool video game ethics so you'd have to come up with a way smarter way to do this unfortunately niagara offers us precisely a way to do that so we don't have to work too hard we just need to learn how to use it i'm speaking of the grid 3d interface i already had a brief opportunity to speak of the interface in my niagara state machine video go check it out if you're interested to summarize though niagara allows us to split some parts of the world into cells of a given size to create a 3d grid each cell is unable to reference a specific amount of particles next any particle may convert its wall position into a grid index to know in which cell it's in and ask niagara hey i want to know one or multiple attributes position velocity or anything else really of all particles that are referenced in that same cell and possibly in the neighboring cells as well and so we went from each particle having to query all other existing particles two each particle being able to only query the most nearby particles which is orders of magnitude faster that's what we may call special hashing i'll link this great article in the video description below in case you might want to get more familiar with the id and the neighbor with 3d interface now that interface comes with some constraints like i said for performance concern we need to limit how many particles we may register in one single cell at a time so you might actually have for real let's say 40 particles in a cell but that cell may only register up to 20 particles so half of them would be left out if you will this may be an issue a particle might query that cell data and the cell would be like hey i'm aware of those 20 particles and so if you use that cell data to make a particle avoid nearby particles it may give you an approximate result because it would only be able to see those 20 particles out of the 40 actually there but that's fine we may work around that and accept that some particles will collide and intersect with each other every now and then it's some kind of visual effects for a video game right so it isn't meant to be a scientific simulation so we can live with some approximations if it means drastically better performance plus if you have 5 thousand fishes swimming around with a very nice grip behavior i would argue that players will tend to see the effect as a whole rather than immediately pick up on the tiny details and limitations the other constraint that comes with this grid 3d interface is how it needs to be set up if i may say you have controls for both its size and amount of cells right and the flock behavior you might want to get is kinda tied to this because let's say you just have one single giant grid cell that can reference all particles and you have this scenario for some reason one particle is related quite distant from the flock that particle would get the cell's data get the information of all nearby particles and see that there's this flock over there and naturally based on the poet's algorithm it will tend to gravitate towards it and so you will tend to have one big giant swarm of particles now let's say you have multiple cells but same scenario that particle is now only able to query the nearby cells but there's no particles around here so it isn't able to see the flock over there and so the more you had cells the less a single particle might be able to see the bigger picture on what's going on overall but again we do this for performance reason and so it's a limitation we have to understand and work with that's why i'm spending some time explaining all this i feel like it's important to understand how grid 3d works if you want to properly tweak this emitter or do your own and make the flock behave exactly like you want to again it's a bit finicky and it's all tied up the emitter's volume the amount of particles the flock behavior you're looking for the grid 3d cell size and count and max amount of particular cell might register and so expect having to tweak a lot of settings here and there and experiment a bit until you get the desired result anyway enough of technical talk i heard you're here for boyds so let's finally dive in i guess the two most important modules happens in the simulation stages down there now they both involve custom hlsl code so hopefully you're somewhat comfortable with that we begin with the field grid module that's a basic logic used to register particles in each cell it's nothing to fancy it's usually always the same logic used to fill the grid i really recommend you to take a look at the content examples project and investigate the niagara maps they are filled with examples including ones that showcase basic usage of the neighbor grid 3d interface there's also the niagara fluids plugin that includes some more examples like this sound emitter which is great to study the neighborhood with 3d interface note that the grid interface changed a bit going from unreal engine 4.27 to 5 so there may be some small differences in how things are done depending on if an example was built for ue 4 or 5. feel free to reach out to me in the comments below if you have any questions by the way anyway basically what's going on there we get the particles x y z position convert it to an xyz grid cell unit make sure that cell exists in the grid and if that cell hasn't yet reached its particle limit we add our particle's execution index into that cell moving on from the field grid we then have the query grid module and that's where most of the magic happens it has this big chunk of code now half of it is common so don't be too scared again the core logic to make use of the neighbor with 3d interface here is pretty standard i'd recommend once again studying the examples given by epic anyway here i'm just initiating all my output variables to zero and i'll come back to this in a minute here i'm initiating the setup to work with the grid 3d interface so convert the particles xyz position to xyz grid cell position then to a grid cell index then get how many grid cells we have on the maximum amount of particles a single cell may reference then we have a first for loop here that goes through the 26 cells neighboring a particle's position plus the cell that particles is in each time we get the cell index we'd like to access and that's what this list is for it says begin with the grid cell that is in that box corner here to eventually end up with a grid cell in the opposite corner there we make sure that the grid cell exists because we might be let's say in that cell and in that case there's no grid cells here and then for each of these cells we loop through all particles they may have registered now all examples of this given by a peak that i am aware of showcase looping through the maximum particle count and i am assuming epic's engineers know what they do but i was under the impression that this was a bit wasteful a cell might have no particles and so i was wondering at first why always loop through that cell's maximum amount of particles if we know it has no particles to begin with and we know how many particles the cell may contain or reference using that function and so i try to loop only for as many particles each cell had registered expecting way better performance but it was actually performing way worse so yeah i don't know maybe i made a mistake or maybe it has to do with the way gpu thread works or how for loop behave in gpus i don't know it's way beyond my skills and knowledge shadow by the way to both death ray and amit mehar for the help on this go give them a follow on twitter they both do really awesome stuff using niagara anyway i was saying looping through the max amount of particles each cell may register okay side note i'm strongly emphasizing how much gpu computation this may require and i'm strongly suggesting to be kind of humble with the particle count and the max particle count you may set in the neighbor grid thread interface the higher this number the more precise that say the boys algorithm will be but the cost of this dual for loop can kinda skyrocket so i'd suggest starting with a somewhat high value based on your particle count if you have 1000 particles let's say and have five cells per grid axis then somewhat like 30 or 40 should be more than enough at first then lower down as much as possible right before the boy's effect you're looking for starts to break down usually i can get decent results with values as low as 8 or 10 but that again may depends on the grid cells and grid size so your mileage may vary i'm running a 970 gtx by the way and with 2.5 k particles and 12 max particles per cell this seems to take on average around 0.3 milliseconds to run so it's not that bad but i consider this to be quite a gpu-intensive niagara system nonetheless be aware of that definitely not sure if it's doable at all on mobile for instance anyway moving on for each particle i sell my content get its linear index and then get the particle index and make sure it's valid and it's not ourself then get the position of the particle compare it with our own position and derive a direction from it use this direction to compare with our own movement direction and since we are aligned to where we are going it's also the direction we are facing and that's the check we may use for the field of vision feature if that is close to 1 that other particle is straight in front of us if it's close to -1 then it's right behind us and so if the particle is inner field division get the square distance that's a little trick using a dot product of that same vector will return that vector's square size here we don't really care how close precisely we are to that particle we only need to check if we are close enough so instead of using the real distance and comparing that to a distance we use the squared distance and compare that to the distance squared it will give the same result and that allows us to skip the square root needed to compute the real distance which isn't the cheapest operation at all and so if this loops i don't know 500 000 times why not skip it if possible by the way i'm really new to hlsl and i borrowed with 3d interface as well to be honest so hopefully i did all this right if not or if you see things that could be improved here and there please let me know in the comments below anyway then i'm checking if we are close enough to that other particle to fade in our boat's separation effect if so based on how distant we are from it we compute a 0 to 1 linear gradient which will be 0 if we are right at that separation distance limit and one if we are basically right on top of that other particle i use that value to fade the position delta and add it to an offset vector that may be used later to push us away from it like two opposite magnets and here i use the inverted direction to that other particle to inside us to move away from it and here i keep track of how many particles we are trying to separate from so we may then average those direction and offset values once the loop is done similar principle here for the cohesion effect if we are close enough to that other particle for the boyd's cohesion effect to kick in add that other particle's position so we may then later on average a rough center of mass approximation same for alignment if close enough get that other particle's movement direction and add it here so we may average an overall flock movement direction and same for speed and turn speed really if close enough get speed and turn speed of that other particle add them so we may average those values as well once we're done looping through every potential particles that were in all nearby cells we average all those values so here if we may want to separate from at least one nearby particle average that separation direction and offset same for cohesion direction which is the direction from our own position to the average center of mass i don't think it's mathematically correct here but assuming every particle weighs the same i think it's kinda close to the geometric center i believe so whatever and same for direction speed and turn speed and then if we specified at least some weights average the three alignment cohesion separation directions this is not a normalized direction right this will be added as is to our own intended direction and then normalized so the bigger this vector is the stronger a particle will react according to the nearby particles in zarzani and that's the basic of the void's algorithm you see it may look intimidating with all this code but it's not that complicated it's just a matter of using the grid 3d interface to average the direction speed and turn speed of all nearby particles now though that gives us two floats on a vector and we still have to make use of them and i guess it's precisely the right time to show you how i approach this it's done in this flock behavior module here i have my particles in tendon movement direction so i'm just adding the flock direction based on some weights i may further specify and then it's normalized same for speed and turn speed basically here i process that offset value that may help prevent particles from collapsing onto each other again i'm referring to the maximum amount of particle a cell may register and so our board's separation direction might not make us precisely deviate from all nearby particles if there's just too many of them in a cell so i'm using this vector like a magnet force that tries to keep particles at a safety distance from each other so i'm not changing this particle's movement direction right but it's positioned directly so it may be pushed backward a little bit but it'd be barely visible if you keep this weight low enough and it does help a bit to prevent collision and penetration and all but i'm sure this is all still very confusing so let's actually take a step back and disable pretty much everything in that emitter and start from scratch so my approach was i first tried to do my best at creating a decent individual behavior each particle first tried to apply its own movement and a movement is made of four components a destination an intent direction intense speed and intent turn speed let's begin with the destination i'm going to turn this back on and it will complain because i actually set some dependencies for all these modules to ensure that they all are pretty much ordered as they should i recently made a long tweet about niagara module dependencies if you want to learn more about it it's way beyond the scope of this video and it's already long enough so i'm not going to bother but basically that module asks for two other modules one is the initiate destination that is here turn this back on in there i'm just making sure the three variables used by the destination modules are set to zero nothing from z then it complains about needing the apply movement module so turn it back on in turn that module complains about needing to generate speed turn speed and direction modules so let's turn them back on and they will all complain that they need their own initiate modules as well those initiate modules are nothing fancy i'm just making sure that the variables used by whatever module are correctly initiated to 0 or to some default values you may specify when that makes sense so with that and actually i'm going to spawn one single particle so we may focus on it we have some pretty basic motion going on now what is the destination all about to debug this i'm going to turn on those two rounders on this module this one is a basic sprite renderer but the position bindings has been overwritten to be the destination position and that one is a mesh renderer that uses a material to offset a mesh based on those two wall space locations as sent to the material location and destination here we go the destination is a point inside the 3d grid if a particle is near enough its destination a new destination is generated or if a particle has spent enough time going towards the target it may generate a new destination as well that time is randomized so a particle may sometimes chase its destination for a while and sometimes it may be a bit erratic and choose a couple of new destination points in a short period of time and go left and right in all kinds of directions i really wanted to have that unpredictable erratic motion you usually see in fishes i may also use a bit of noise to shift that destination point around so particles doesn't just go in a straight line from destination to destination that destination point is constrained to the grid 3d and it may also be aware of obstacles using distance fields to try and avoid generating a destination inside an obstacle if you do turn obstacle on a particle may also choose to generate a new destination if it gets too close to an obstacle at first i had another approach which just involved an intent direction that i was tweaking if a particle was going too far away from the emitter's origin but it led to all kinds of complications it allowed me at the time to experiment with a cool concept though i could force a particle to turn clockwise or counter-clockwise if too distant and so particles could be forced to form a sort of doughnut shape even without any boiler glass amount but yeah i wasn't happy with that approach and eventually decided to go for the destination point method it's from the destination point that i derive a direction in the generate direction module it's super simple and actually both generate turn speed and speed are even simpler it just forwards an input value to those two values so we have a basic movement we have a destination from which we derive a direction we have a speed that will determinate how fast we move in that direction on a turn speed which will dictate how fast we change from our current movement direction to the new direction apply movement down there let me ensure a maximum speed limit and let me specify how fast a particle may accelerate to reach its intended speed if its current speed is below that and how fast it may decelerate for the other way around or you could use a simpler float interpolation it's a bit cheaper and a bit more fluid so you might want this or not feel free to try this out we also interpolate our current turn speed to reach that newton speed in case it changes to smooth out the behavior the turn speed will dictate how quickly we may move towards new direction and we may derive an angular acceleration based on our current movement direction and the new one we computed that's sent to the sheller to drive how much a fish mesh bends more on that later a linear acceleration is also computed in here based on our current speed and the new speed for this frame and the delta time pretty standard okay cool now let's take a step further and modify our speed with a curve that complains about needing its initiate module so let's turn it back on here we may set how long in seconds that curve should be by default it's 30 seconds so that curve here describes how much the intent speed of a particle changes in that amount of time when a particle is bound its current time is randomized so not all particles are in sync on the curve one might start here one other might start there and so on and that curve describes how much in percent or intense speed is tweaked so around here it's 20 faster here 75 percent slower we may further increase or reduce this with that alpha value so here the curve effect is halved because i felt it was a bit too strong cool so that changes our movement speed a bit over time and introduce some variation let's add burst to do this we'll enable all the necessary modules every x seconds a burst will be generated and will last x seconds and during that time we increase the intent speed by that much so we can tweak the delay duration multipliers and so on again i really was looking for those erratic sudden bursts of movement you tend to see in fishes not all of them obviously do that they can be chill on coast but i'd say most of the time it's pretty erratic so that's what i was trying to do you can turn this off anyway if you don't like it okay cool what else let's check the altitude limit that's pretty straightforward you may say hey particles may not go above or below those altitude limits so if it's in local space that'd be 400 units above the emitter's origin if in all space that'd be 400 units in z inward space and simulation is one or the other depending on the emitter setting here so that may be used to clamp the particle's position but that can be a bit ugly because a particle could move upward and then suddenly hit that invisible wall and keep trying to move in that direction so you may also use that altitude limit to smoothly constrain the movement direction and same for destination a new destination might be cramped to those altitude limits to ensure that no particles is inside to move towards an unreachable target a quick side note though depending on where you set those limits you might end up wasting some of the 3d grid cells we use for the flock behavior so try to work around that maybe set a lower height for the grid 3d and lower grid count in z to account for those altitude limits if you do set some what else ok let's talk about generate flow it will complain about needing both to initiate flow and flow apply modules no big deal the idea here is really simple we have some flow vector that is increased by sampling some low frequencies 3d noise and faded out over time and we use that vector to have set the particle's position this is precisely made so this flow motion isn't registered as a velocity it's added the same way though meaning a delta movement times delta time but it's directly fed into the particle's position that way it doesn't alter the velocity in any way and i wanted that because our particle mesh rounder aligns the particles towards our velocity and so we might then get a particle moving backward if the flow force is strong enough but still oriented forward and it would look like a fish is fighting and swimming against the current which is exactly what i wanted that flow may also be constrained by the min and max altitude limits so no particles are pushed by the flow higher or lower than they are allowed to i may also limit this flow by some other value here i don't want particles to be pushed way out of the grid 3d a little bit fine but definitely not too much so i'm using this distance weight that the flock module outputs to control that but more on that in a minute great we are making some good progress we are pretty much there let's talk about obstacles they are the first obstacle constraint here so when particles are spawned in this box they might be safely placed outside obstacles as much as possible it's quite straightforward get the particle's position in wall space sample the nearest surface and offset the particle's position from the surface if it's too close to it or inside it and transform that position back to simulation space and actually that same constraint is used down there to ensure that particles do not go through obstacles so when the movement flow on everything is applied i do this to ensure that all this movement hasn't led me inside an obstacle before the movement is applied but after it's been generated though i may alter both the intended direction speed and turn speed based on how close to an obstacle i am and how much my intended direction is making me go towards that obstacle so i may be close to an obstacle but that's fine as long as i'm moving at most perpendicular to that surface or away from it else the intended direction is modified and i may be given some extra speed and turn speed to move away from that nearby obstacle the flow can also be constrained by obstacles because again flow is applied as a position of set so we should try our best not to push particles inside obstacles despite our constraint down there and showing this as a very last safety precaution so i already sampled the nearest surface in this obstacle module right so i might just keep resampling it again in this module and so i may use the values this obstacle module output then i check if the flow force is pushing me towards an obstacle and depending on how close i am to that obstacle kills the flow so even if i'm very close to an obstacle if the flow is pushing me away from it it's fine the other way around though not so much okay we are almost there there's this simple point avoidance behavior you might want to add so particles may flee from a given predator or your character whatever you may set that user expose vector and blueprints to send your character's location and then this module will modify our intended direction speed and turn speed just like the obstacle avoidance behavior module does so once we have that intended move direction however modified if it had to be by that obstacle and point avoidance behavior models we may choose to limit how much in z a particle may move because fishes don't usually swim straight up or down and more importantly if a particle has no movement in x or y and there's no planar velocity niagara will not know in which direction to iron the mesh so this here simply clamps the movement direction to a max z value both in positive and negative directions note this may actually prevent a particle from moving away from an obstacle like it intended to but it's fine that's also why i put this safety obstacle constraint down there right once we have all that we might start to fail in the boyd's algorithm so turn on the flock behavior and initiate flock modules which again this one is just here to ensure that all variables used by the flock behavior module are all properly initiated to zero and flock weight which is just a helper module to output a value that will control how much flock behavior to fade in it starts with a weight of one and will decrease the more particle might need to behave on its own so if it needs to flee from an obstacle or a given point in space like a predator or character it should do this straight away on its own and not wait for the flock to react right so the more we avoid an obstacle the less will fade in the flock behavior same for point avoidance and although if we're getting close to the grid 3d borders and actually this module outputs the grid border gradient that i can use in that flow drag constraint down there so the flow is killed when a particle is nearing the 3d grid borders that allows me to skip computing that 3d box gradient twice so once i have that global flow weight computed and set here on the flow behavior module i may choose how much of this individual flock behavior direction speed turn speed and also that offset which is the opposite magnet first i talked about a while ago are influenced by that global weight i would definitely assume that you do for the direction speed and turn speed but maybe not so much the offset one you probably might want to have particles repelled by each other despite them avoiding an obstacle or something right but anyway then i may further tweak each individual weight for those parameters let's say direction the higher this value the more this particle is going to match the flux direction remember that the overall floc boils direction right so it's the one computer down there based on those three individual ways so you definitely might want to tweak this the distance threshold as well and how much overall voice direction you're end up adding to that particle so my approach was one try to create interesting individual behavior first and then have that be enhanced by the boyd's algorithm so it kind of acts as a post-process effect right it's added pretty much as the very last step once everything is computed and just before movement is applied oh almost forgot those two the animation module is quite straightforward first interpolate over time the acceleration because it may change quite abruptly so i wanted to smooth it out and same for angular acceleration and then i increment an overall animation time based on the acceleration and speed and that's a value used in the material to drive the swim animation so a fish may coast and swim at least a little bit based on its speed but also swims super fast when it accelerates and then these four values are sent to the material using a dynamic material parameter speaking of materials there's one cool thing i have to mention though i really wanted to have those fish curl when they turn because if not they feel super rigid right it looks like they are made of wood and it doesn't look too believable so i tried to tweak the mesh using wall position offsets to have that tail whip action when they turn at first i tried to do this with a simple rotate node and some mask along the length but i couldn't get this to work i had some extreme distortions and i didn't want to bake poses or vertex animation into texture users like i experimented with when i was fooling around with my shark and one day i was using blender on its cool bend modifier and i thought it was exactly what i wanted so i had a look at its source code and eventually managed to part it to a new engine using this custom node i wrote huge shout out to daniel for suggesting me a way to fix the normal is an engineer working at epic go give him a follow on twitter on youtube and also amit mehar once more for suggesting me to use the pre-skin location node which i thought was for skeletal meshes for some reason but turns out it works for static meshes as well and returns the local vertex position so you can skip a transform that's neat anyway this bend amount is driven by how much the particles turn at a given time that's the angular acceleration i computed in niagara based on how much a particle changes direction over time back to niagara last module is the leds that's really straightforward i have these four mesh renderers down there each having a unique visibility tie and then in there i get the camera's position in word space compared to the particle's position in word space as well and so based on the distance between the two on those lod distances i set the correct visibility tag so three here is for the most distant renderer that uses the most simple mesh and that's it i think did i forget something probably not sure this is a big chunky emitter so yeah anyway hopefully you could make some sense of all of this feel free to use the comment section below to ask me questions if you have any alright files are available as a tier 2 reward on my patreon it's been crazy this month it grew so much and i'm very grateful for all your support let's end this video with a chill time-lapse of me modelling sculpting and texturing that little fish thank you for your time and support i'll see you in the next video take care of yourself [Music] so [Music] so [Music] [Music] [Music] [Music] family [Music] [Applause] [Music] [Music] [Music] [Applause] [Music] me [Music] so [Music] [Music] [Music] [Music] [Music] [Music] [Music] so [Music] [Music] oh [Music] [Music] so [Music] [Music] [Music] [Music] so [Music] [Music] [Music] [Applause] [Music] [Music] you

Channel: Ghislain Girardot

Views: 19,402

Keywords:

Id: 9iDA6WMqEyQ

Length: 54min 38sec (3278 seconds)

Published: Sun Jul 03 2022