Tutorial - Flow Field Pathfinding in Unity

hello everybody and welcome to today's video where we're going to be making a goal-based vector field for path finding this is something that's also known as a flow field and today we're going to be implementing it in the unity game engine now this video is a part of a series of videos that i'm doing on the flow field and if you want an example of what a flow field looks like you can see it playing right behind me and if you do want some more information on what exactly the flow field is and how the whole algorithm that we're going to be implementing today actually works under the hood definitely go check out the first video in the series that i made i'll link it in the card as well as in the description below again that's going to serve as an introduction to this whole series to get yourself familiarized with what flow fields are before we can go ahead and implement them like we are doing today so today like i said i'm going to be implementing it in the unity game engine we're just going to be using some typical unity mono behaviors but i wanted to do this as a little bit of an experiment because i also want to implement this with unity's new data oriented technology stack using their entity component system and then kind of once we have these two different flow fields we can compare the performance between the two and i think it's going to make for some really interesting videos so anyways to make sure that you don't miss out on any of those fantastic videos make sure you are subscribed to the channel of course if you have any questions on any of the stuff that i'm going over today feel free to drop that all down in the comments section below and if you did find this video helpful i'd really appreciate if you hit that like button as well so today's video is going to be broken up into a total of five sections and so those sections should all be displayed down in the timeline below so essentially what we're going to be doing today is we're first going to break up our world into a grid after that we're going to be able to implement our cost field then we'll do our integration field and once we have that we can actually make our flow field then once we have our flow field i'm going to show you how we can actually have some objects in our game move around our game world using the flow field now there are a few additional things that i'm going to be doing in today's video that fall slightly out of the scope of all of this so i'm going to be just kind of explaining what that is and not necessarily going into any detail but if you do have any questions on that stuff you can ask it down in the comment section below as well and i should mention that all the project files and scripts and everything will be available using some links down in the description below alright so here we are in unity i just have a mostly empty project and i've just imported a couple assets but basically we're going to be creating a 3d world although we're going to be working in 2d space so you'll see that i have this camera set to orthographic projection here so we can just basically leave this in top down 2d mode for now so basically this is kind of our game world is just this big patch of grass here and so the first thing that we need to do is actually break it up into a grid and so our grid is basically going to be made up of a number of cells so we can go ahead into our scripts folder here and we'll go ahead and create a new c-sharp script and we can just call this cell so just go ahead and open this up in your ide of choice and go ahead and clear out everything in here now the first thing is we're just going to need to of course import the unity engine library so here we'll just create our public class called cell and you'll see that it's just a plain old c-sharp class it's not inheriting from monobehavior or anything like that so of course we want to know where our cell lives in the world so we're just going to create two public variables one is a vector three for world position and the other is a vector two for int for the grid index and so that's going to represent essentially the x y coordinates of where this cell lives on the grid so now we'll just go ahead and create a constructor for this class which is going to take in a vector 3 for the world position and a vector 2 int for the grid index and then of course we can just set those values in the instructor and that's all we need to do for now for our cell class so we can just go ahead and save this and come back to unity so now that we have our single individual cell the next thing that we want to do is actually create a grid of all these cells so here we'll just go ahead and create a new c-sharp script and this is going to be our flow field class so again we can clear out most of the stuff we're just going to do another plain old c sharp class for this flow field so first we're going to start off with a couple of public variables the first is going to be a two-dimensional array of cells which we can just call grid and this is going to allow us to access any of the cells on our grid as you can see we have set it to public get and private set next up we have a vector 2 int for the grid size again this is a public get and a private set and then finally we have a public float for cell radius again public get private set and we do just need one private float variable for cell diameter there are a couple cases where it's going to be nice for us to have a cell radius and a cell diameter component so now we'll create the constructor of our class of course it's going to be a public flow field and it's going to take in a float value for the cell radius and a vector 2 in for the grid size then here we just set the cell radius cell diameter and grid size so of course one of the most important functions we're going to need is a create grid function so it can actually initialize all the values on the grid so here we'll just initialize our grid array to be the same size as we defined in the grid size value so now we'll just do a nested for loop starting at zero going all the way up to grid size dot x and grid size dot y so at each of those locations we're going to go ahead and define the world position of our next cell so we'll just create a new vector 3 and then for the x value we'll just do cell diameter multiplied by the current x value and we'll add in cell radius for just a small little offset set the value of y to zero and then for the z value we'll do cell diameter multiplied by y and then add in the cell radius again just for that little offset so in a grid position x y will create a new cell passing in values for the world position as well as the current grid index which of course is x y so we're all finished up with the flow field for now now we'll come back to unity and we'll create another script here so i'm going to create a grid controller class and this is what we're going to be using in unity to set the values for our grid as well as call functions like actually creating the grid let's just go ahead and clear out the start and update functions so we're going to start off with a couple public variables so the first one is going to be a public vector 2 int for the grid size so this is going to be where we actually are modifying the grid size within the unity editor next we'll do a public float for the cell radius and so we'll set that equal to 0.5 f so that each cell is going to be one unit wide and if we ever wanted to change it in the editor that's right where we can do this from and then finally we'll just have a public flow field for the current flow field now we'll just create a private function to initialize our flow field and within there we'll just go ahead and set the current flow field equal to a new flow field passing in our cell radius and grid size which we've set in the unity editor and then we can just call curveflowfield.creategrid so now to actually call the initialize flow field right now we're just going to go ahead and go into our update function and for now we'll just set it to when we click the mouse button we'll just go ahead and initialize the flow field so when we're back in unity we're just going to go ahead and create an empty game object and so this is going to be our grid controller i'll just bring the grid controller component onto it and with how i have it set a grid size of 40 by 22 and a cell radius of 0.5 should basically make a grid across this whole field here so of course we can hit play and then when we click it will actually generate the grid of all the cells however we can't see it so i've created this little debug class and this is one of those things that i'm not going to go into super detail on so here i just have the grid debug class and within the on draw gizmos function basically it just calls this draw grid so we can get a visual representation of the grid within our game world so now with this grid debug component that i made basically we can kind of get an idea of how big this grid will be when it's in our game world and then if we actually enter play mode and click you'll see that the grid changes green to basically confirm that we've actually initialized the grid and this is the size of all the cells so now that we have our game world broken up into a grid the next thing that we're going to do is implement the cost field now this is the part that's kind of up to you as a developer basically the way that i'm going to be doing it today is we're going to be having some kind of patches of rough terrain and then we're going to be doing a check to see if any of these grid boxes fall on top of that rough terrain in which case we'll go ahead and increase the cost and then also we're going to have some impassable walls that our flow field is basically going to navigate around now again this is really up to you as a developer about how you want to implement your cost field so just kind of play around with some of the values and find what fits right for your game so one thing that we're going to do is just go over to the project settings and we're going to create a couple new layers so we're gonna have a layer eight is going to be impassable and then layer nine is our rough terrain layer so what i'm gonna go ahead and do right now is create some of this in our game world so for the rough terrain it's basically just going to be some planes that are on the rough terrain layer and then for the impassable walls they're going to be some cubes which are on the impassable layer all right so i just created a super basic little scene of course we just have some rough terrain in here as well as some impassable walls just to get an idea of kind of how this flow field flows around all the impassable walls and tries to avoid some of this rough terrain in some cases so we'll come back to the cell class and go ahead and add in a public byte for cost so a byte is just an integer value that can be anywhere from 0 to 255 and so we're going to use this as the cost of our individual grid cell now in our constructor just by default we can go ahead and set this cost equal to 1 because that's essentially the default value of cost on a flat ground so now we need some way to increase the cost of a given cell so we're just going to go ahead and make this increase cost function which takes in an integer for the amount to increase by so first we just got to do some checking just to see if the cost is already equal to byte.max value which is 255. if that's the case we can just return out of the function because we can't increase the cost any higher also if the amount plus the cost is greater than 255 we're just going to go ahead and clamp the value of the cost to 255. again it being a value of 255 makes this an impassable sell otherwise we can just go ahead and add in the amount to the current cost value all right so now in the flow field class we're just going to go ahead and create a new function called create cost field so basically what i'm doing here is just looping through every cell in our grid and doing a physics.overlap box at the world position of the current cell and that overlap box is basically just on this one terrain mask which just looks at the impassable and rough terrain layers and if it hits anything on any of those layers if it is impassable terrain we're just going to go ahead and do dot increase cost by 255 which will bring it all the way to the max value of 255. otherwise if it did collide with some rough terrain we're just going to go ahead and increase that cost by three and also have this has increased cost flag right here and the reason i do that is because if there's like a cell that's collides with two pieces of this rough terrain i don't want to increase the cost twice i just want to increase it one time so again this is my implementation of how to create a cost field and this is something again that's up to you as a developer to figure out how you actually want to generate your cost field and then in our grid controller right after we initialize the flow field we can just do a curve flow field dot create cost field and then in my grid debug class i'm just going through every cell and doing a handles.label basically just debugging the current cell cost and so if we go over to unity and enter play mode and just click anywhere on the field you'll see that it creates this full cost field here now you'll notice that basically everything on this grass is a one everything that's touching this rough terrain is a four and then everything that's touching these impassable walls is a 255. that is a beautiful looking cost field all right so next up is the integration field and with the integration field we're basically going to be adding up all these cost values so we can create our full integration field all right so for the integration field we're going to need some notion of directions so we can kind of look at some of the neighboring cells this is the grid direction class that i've created and i'll just give it a quick scroll here but you can see that basically what we're doing is we have this vector 2 integer for a direction and that direction corresponds with one of the directions you know like north south east west as well as some of the intercardinal directions like north east south east southwest and northwest and so i've also included these static lists for all directions cardinal and intercardinal directions and cardinal directions and this is going to be shorthand for us to get some of the neighboring grid cells again you can download this using the link in the description below alright so in the cell class we're just going to go ahead and create a public u short best cost so u short is an unsigned short integer and in our constructor we'll just go ahead and set the best cost equal to u short.max value and max value is 65 535. so by default we just want this best cost to be set to a really high number so then when we compare it with some of the other numbers around it then they're going to be lower and then that's how we can kind of determine the best direction for our flow field all right so in the flow food class we're just gonna go ahead and create a public cell for the destination cell because now that we're doing the integration field we actually need to know where our final destination is going to be and then at the bottom we'll just go ahead and create a new public function called create integration field which takes in a cell type called destination cell so of course we'll just go ahead and set the destination cell in our class to the destination cell that we're passing into the function so now we'll just set the cost and the best cost of destination cell to zero so here we'll just go ahead and initialize a new queue of cells called cells to check and then we're just going to go ahead and do an enqueue which basically just adds the destination cell to the end of the queue and because the queue is brand new it's going to be the only element in the queue and so we're going to be doing a while loop so we're going to be doing all these steps as long as we have cells within our queue so we'll use the dq function to grab the cell at the front of the list and cache that as cursel so next we're going to get a list of the neighboring cells in the top down left and right directions and so i do that through a helper function called get neighbor cells so basically here we just pass in the grid index of the current cell as well as the directions that we want to look for neighboring cells in this case we're just going to do the cardinal directions which are north south east and west so then here's the helper function for the neighboring cells so then basically we just take this list of directions and we loop through that and then we use another helper function called get cell at relative position and here again we pass in the node index and the direction and then the get cell at relative position basically just finds the neighboring cell in the position that we're looking so not super important how the flow field works but basically this is just a way to get a list of the neighboring cells so now we're just going to go ahead and loop through that list of neighboring cells and so first we'll look to see if the cost of the neighboring cell is equal to the max value in which case it is an impassable cell so we can just go ahead and skip that so now we're going to check to see if the cost of the current neighbor that we're looking at plus the best cost of the current cell that we're looking at is less than the best cost of the current neighbor so what exactly does that mean so if we're starting at the destination and the best cost of the destination is zero and then we're looking at up down left and right all those neighboring cells are going to have a cost of one and if you remember all the regular cells by default are set to a best cost value of 6535 so now of course if we add the current neighbors cost of one with the best cost of the current cell of zero then of course that's going to be less than 65 535 so we'll go ahead and set that value to be the best cost of that current neighboring cell and then after that we're just going to go ahead and add that neighboring cell into the cells to check q so now if you think about it when we go to that neighboring cell its best cost is going to be one and then we look at its neighboring cells which are all by default going to have a cost of one we can add the best cost of the current cell which is one with the cost of the neighboring cell which is also one so we get a value of 2. again that's going to be less than 65 000. so then there we'll set the new best cost to be a value of 2 and then we're going to go ahead and add that to the open list and so this just kind of like simple arithmetic and comparisons is basically how we can find the most efficient path from any possible spot on our grid all the way to the destination cell and then one last thing i do need to add in another helper function so this is get cell from world position and so what this is going to do for us is when we click somewhere on the grid then we can actually get the cell that we're clicking on and then we can set that as our destination cell all right so now we'll just go ahead and come to our grid controller class we'll go ahead and get a reference to the mouse position just using input.mouse position x and y now we'll convert that from screen space to world space using the camera.mains screen to world point function next we're going to get a reference to the destination cell and we're going to again find that by going to the current flow field and doing a get cell from world position which is that helper function that i just implemented passing in the world position of the mouse and then after that we can just do a curve flow field that create integration field passing in our destination cell and then one more time here is the grid debug class where we're going to be debugging the best cost using the handles.label so that's how we can see the integration field so now you'll see when we click on the grid you'll see right where i click we now have a zero for our destination cell and then if i go over to my grid debug and i change the current display type to the integration field now you see the integration field is displayed so now at the destination we still have a zero and then going out from there we now increase by one two three four five six seven eight nine ten and so on and then you'll notice when we get over to this rough terrain these values start increasing by four so we have 11 12 13 17 21 25 29 33 37 38 and so after that we'll see that we have a number 35 which is lower so that's probably because it found a shorter path back to the destination as opposed to going over this rough terrain and then you can kind of also see on the impassable walls basically we have the values of 65 535 set for the best cost of these impassable walls so that is the integration field and now comes the part that you guys all came here for which is making the flow field so in the cell class we'll just go ahead and add a new public grid direction called best direction and then in our constructor we can set the best direction equal to grid direction dot none so now in the flow field class we can just sneak in a new function called create flow field and we're just going to go ahead and iterate through every cell in our grid so again we're just going to go ahead and get a list of all the neighboring cells this time around we're going to use grid direction.all directions and so that's how we can not only get north south east and west but all the directions in between so you know like north east northwest and the all directions also includes direction.none so we actually are going to be comparing it with itself so to keep track of the current best cost we're just going to take an integer best cost we'll set that equal to cursel.bestcost so now we'll actually loop through all the neighboring cells and so if the best cost of the neighboring cell is less than the best cost that we've already found now we're going to set the best cost equal to the best cost of that neighboring cell then after that we'll assign the best direction of the current cell using a helper function on the grid direction class which i call getdirection from v2i so this is a helper function where we pass in a vector2 int and then we get a direction from that so here we can pass in the currentneighbor.grid index minus the cursel.grid index and this is basically going to return a vector that starts at the current cell and points to the current neighbor and so that's how we can have a reference to the best direction so anyways basically we're just going through every cell on the grid and comparing it with its neighboring cells and finding which cell has the lowest cost and whichever cell is the lowest cost we're basically going to point to that now the only time that a cell will have a lower cost than all of its neighboring cells is when that cell is the destination cell and one thing to note is that in my implementation the impassable cells also will have a direction and the reason for that is in my implementation you'll see that i have the walls and they're not perfectly aligned with the grid so even though the cell is impassable it's possible for some of the units to actually navigate onto that impassable spot on the grid and basically i just wanted a way to kind of push the object back into a valid location on the grid of course in the grid controller we're just going to need to do a curve flow field dot create flow field and for the grid debug for this one it gets a little bit more complicated but basically i just have some sprites that are going to be displayed depending on whichever direction is the best cost so when we come back to unity and enter play mode you'll see that now when we click on the grid so you'll see that we have this destination cell here and then we've marked off all these cells which are impassable and then on this rough terrain you can kind of see that things are trying to avoid some of the thicker areas of rough terrain and so you'll see that we can click around on all different spots on our grid and a new flow field is generated each and every time so now that we have our flow field finally finally finally being displayed in our world the last step that we need to do is actually create some objects that will spawn in our world and can follow this flow field all the way to its destination so i've just went ahead and created this pink little sphere called unit and i've set it to a scale of 0.25 in all directions only other special thing that i've done is went ahead and add a rigid body component to it so we just go ahead and drag this into our prefabs folder here and just delete this one out of the game world so now in our hierarchy i'm just going to go ahead and create a new empty object and this is going to be our unit controller and so this is what we're going to use to actually control the units so we can just go ahead and create a new cfs script of course this is going to be the unit controller and we can just drop that right on our unit controller object so here we have the unit controller script and i know this video is probably getting really long already so i'm just going to kind of breeze through the main points here so basically what's going to happen is when we press the number one key we're going to go ahead and spawn some units into our world depending on how many units that we've specified up here for the number of units per spawn and if we hit the number 2 key we're just going to go ahead and destroy all the units so you can see here these are the spawn units and destroy units functions basically it just spawns some units somewhere randomly on the grid making sure that we're not on an impassable tile or overlapping with another unit alright so all the actual movement is happening in the fixed update function so basically if there's no flow field we can just return out of the function otherwise we're going to iterate through every unit that's in our game of course if you've been following along with some ecs content you might see how ecs can kind of work into some things in the future anyways we'll just get a reference to the cell that is below the current unit and we're just going to be using the get cell from world position which is the same function that we use to determine which cell that we're clicking on so once we have that we can set this new vector3 to the move direction and we'll set that using the values of the bestdirection.vector.x and the bestdirection.vector.y of the cell that we're currently on top of now here we'll just get the rigidbody component of the unit and then we'll just influence the velocity equal to the move direction multiplied by the move speed and the move speed is just one of these public values that we're setting at the top here so now when we come back to unity we're just going to make sure that we remember to set our grid controller bring in our unit prefab we'll say do 50 prefabs per spawn we'll give it a move speed of three alright so when we enter play mode and then we set a destination of course i've turned off all the arrows so it's a little bit easier for us to see the movement we can just hit one a couple times and you'll see that things start spawning into our world and then it follows the most efficient path all the way to the destination you can set another destination and you'll see how it kind of follows the flow field and it just goes to the destination just how you want it to i mean can't be simpler than that right so i mean i definitely do hope that you guys go ahead and implement your own flow fields because these are a ton of fun to play with again this is just kind of the mono behavior implementation of all this and i do want to use uh ecs and the data oriented technology stack to see if we can come up with some more efficient versions of the flow field pathfinding you may have already noticed some places where the entity component system would do really well for these flow fields so anyways i'm super excited about that i hope you guys are all too so make sure you are subscribed to the channel so you don't miss out on any of those videos by the way if you do have any questions on any of this or suggestions for any upcoming videos you can always leave those down in the comments section below i really hope that you learned something today if you did i'd really appreciate if you hit that like button don't forget you can also download the project files from this video using the link down in the description below anyways that's it for today so i hope you have a fantastic rest of your day and i'll see you in the next one [Music] dang i've been recording for over two hours at this point and my computer is starting to melt some cables oh well

Channel: Turbo Makes Games

Views: 22,423

Keywords: flow field, flow field pathfinding, flow field unity, flow field pathfinding unity, flow field math, flow field meaning, goal based vector field pathfinding, goal based vector field, unity3d tutorial, unity3d tutorial 2020, how to make a flow field in unity, flow fields in unity, game development unity, intermediate unity tutorials, unity scripting tutorial c# intermediate, unity c# intermediate tutorials

Id: tSe6ZqDKB0Y

Length: 24min 48sec (1488 seconds)

Published: Fri Aug 14 2020