A* Pathfinding in Unity

in this video we're going to learn how to implement a star path finding in unity we're going to set up our world in a grid with some areas blocked and implement the algorithm to calculate valid paths then in the future video we're going to apply this same algorithm using unity dots let's begin [Music] hello and welcome I'm your code monkey and this channel is all about helping you learn how to make your own games with nf2 torrents made by a professional indie game developer so if you find the video helpful consider subscribing okay so this one we want to create over here is our map with the grid visible and you can see some black squares which represent the areas that are not walkable now in here I have my character and I can click to tell him where to go when I click the path is calculated and he then follows that path we can enable the debug view in order to see what's going on inside the algorithm so over here you can see the various values that the algorithm uses and you can see it and looking around for all the neighbors after going through the entire process you can see that it located the correct path all right so this is our goal let's get to it so before we get to the code let's first check out the theory the goal of the a-star path finding algorithm is to search to find a path from A to B so the algorithm already detects one couple and unwalkable areas and correctly identifies the surance path from A to B our map won't be grid based from each grid position we can move in all eight directions on each node essentially we have three values first we have the G cost that is the walking cost from the start node so for example to go from this node into this node it has a cost of 1 and we can also move diagonally so from this node into this node has a cost of 1.4 now in order for our code to work with ends instead of floats we're simply going to multiply our values by 10 so horizontally we have a cost of 10 and diagonally cost of 14 then we have the H cost this is the heuristic cost to reach our final goal so it's essentially an estimate to try to reach the goal our calculation is simply assuming there are no wall so moving straight towards our goal so in here our hitch cost more commonly going from here to here to here again this is just a basic guess to figure out which notes you prioritize and finally we have the F which is simply G + H so this combines our actual cost from the start combined with an estimate to reach the goal and we have our found number using this we can prioritize nodes with lower F since those are more likely to be closer to the goal the algorithm finally stops when our current node is our goal node so if we start here first we check on the neighbors these are unwelcome also they are ignored so it checks this one then checks these two neighbors then this one has a lower F value so it checks this one checks the neighbors for down then it starts locating that one and it says that this one is a go so we have our path so here as you can see the G cost is constantly increasing and the F cost is constantly decreasing then our path is traced back from the final node into our original so each node also knows what the previous path node was then for the algorithm to work we also have two lists for our notes the open list and the close list the open list is where we have all the nodes that are queued up for searching and the cause lists are all the nodes that have already been searched so we keep going until we find the current node on the open list or our open list is empty so we no longer have an or to search so there's no path okay so this is the theory now let's implement it so over here is my starting scene let's start off by making a knee you see sharp script call this our path line now in here let's get rid of all this and get rid of the motor behavior and let's make a constructor that receives a width and a height okay now we want to set up our path finding in a grid so for that let's use the grid commands that we created in the previous video here is a class it manages a grid with a certain width and height now we created this completely from scratch in a previous video so go check the link in the description if you haven't seen it already so using this class let's go into our path finding and in here and let's create our grid so appear with the final film for our grid and now in here we require a grid object so let's make one in here let's make a new C sharp script and let's call this the path node so this won't represent a single node in our path finding grid so let's make a constructor here on let's receive the normal stuff that we create in our grid okay we have our basics now we're also going to have a int for the G cost then for the H pass and the F cost okay so these are the three families that we need to calculate and finally we're also going to have a path node reference for the node that we came from previously so let's call it came from node so this is a node that we came from in order to reach this one this is what we're going to use in the end in order to trace back our steps to find the final path so now we can go back into our path finding and in here we make a grid of task node and call it our grid all right so just like this we are in Senshi ating our grid again check the link in the description to see how we made this grid class completely from scratch so now in here let's make sure that everything is working back in the editor and let's make a nice testing script let's make a testing game object and attach the script okay now here in our testing let's create our pathfinding just like that okay final let's go into our grid and here just make sure that we have show debug set to true so just like this we should be able to see our grid let's test and if there it is we have our grid correctly being instantiated all right great now let's get to work and implement the actual algorithm so we're here on the pathfinding let's make our function this will return a list of path note for our entire path let's call this fine path in here will receive an input the start X for the start y for the MX and for the end one so retaliating a path from these coordinates into these coordinates so in here first let's set up our open and closed lists and here we also add the start node to our open list and Nicolson list remains empty so to get the start node we go into the grid we get the grid object on start X and start line and we start with the start node on the open list again the open list are the ones that were queuing up for searching and the cantos only started ones we've already searched so we start off with the start node Kutub and nothing on the cons list now let's initialize our grid so we need to cycle through all of our nodes and set their G cards to infinite and calculate their F cost so to initialize we set the G cost to infinite so in that max family and then we calculate the F cost so let's make a function to do that so back here on the path node we simply make this and again the F cost is simply equals to the G cos plus the 8th class okay here it is now in order to initialize our own list we also need to set the came from node back into no so it doesn't contain an in data from the previous path ok so now let's begin by calculating the costs for our start node so the start node G cost this is the start node so the G score is 0 since we start right in here then we need to set the start node H cost so in here we're going to have a function and let's call this calculate distance since that's pretty much what the H cost is it's a distance while ignoring all the apocryphal areas so here we have a commonly distance cost we take an A and a B and here we just want to calculate the quickest direct path so your horizontally as much as possible and then diagonally so let's go up here to define our basic costs so here we have the straight cost at 10 and diagonal cost at 14 the reason why it's 14 is essentially that is the mathematical value for a diagonal so we have a square root of 200 which is 14 ok so now we can go all the way down here and our final distance cost won't be the amount that we can move diagonally plus the amount that we have to move straight so the distance class is essentially our H cot so we can go up here in order to set the H fast for the distance cost between the start node and the end node ok so just like this and finally we can go into the start node and count like the F cost all right so this is our starting data for our algorithm and now in here we're going to have our cycle so we're going to do our cycle while the open list count is bigger than 0 so while we still have nodes on the open list in here we get the current node and now the current node will be the node on the open list with the lowest F cos so we're going to make a function to do that to return a pat node and let's call it get the lowest F cost node okay so here this we simply cycle through our entire node list and we get the only was staff cost note so now we can use this in here in order to get the current node we pass in the open list okay and now the first thing we do is check if this is our final note if it is our final node then we have reached our goal so here we return our calculated path to reach this node okay I'm let's just define this function in here it's going to return a list of path node and for now let's leave it empty we're going to make this function later okay for now let's keep going in here so if it is the end node then we complete the path that we took to reach that end node if it is not the end node then first of all we're going to remove the current from the open list so we're indicating that the current node has already been searched and we're going to add it into the code list okay so far so good now in here we're going to cycle through the neighbors of this current node so let's make a function to get our neighbors okay so here we have our neighbor code we simply take our current node then we check the one right to the left of it if it's valid so that's why we're checking above zero so if it is valid then we add on left one then we see if we have a node underneath and if so then we add the unless and down and then left up and then right right down right up down and up so just like this we have our eight neighbor positions if they are valid so we have our neighbor list and in here we cycle through it so we cycle through all the neighbors of the current node now in here first we check if the neighbor node is already on the closed list if the neighbor node is already on the constant list then that means we've already searched so we simply continue now if it isn't on the close list then we need to search in so in here on let's calculate a tentative G cos this is based on the current node G cost plus the movement cost to go from the current node into this neighbor node and now with this tentative G cost we're going to see if this one is lower than the actual G cost currently stored on the neighbor node so essentially we're trying to see if we have a faster path from the current node onto the neighbor node than we had previously if we do have a better path then let's obtain it we go into the neighbor we said he came from node to be our current node then we set the neighbor G cost to be our new tentative G cost finally we count only the new H cost to be distance between the neighbor and the end node and finally we calculate the F value okay so here we have updated all of the values for this neighbour node and then we simply check if it is not already on the open list so the open list does not contain our neighbour node then we add the neighborhood to the open list okay and that's it this is our complete algorithm cycle and now if we reach down here outside of the wild then that means we are out of nodes on the open list essentially this means that we search through the whole map and we could not find a path so in here let's simply return no so now finally the last thing we need is simile to implement this function here the account link path so in here again each path node contains a reference to the node that it came from so we can simply use this to retrace our steps so in here let's make a list of path node we start our path off on the end node then we calculate a current node which is going to start off with our end node and now we're going to do while the current node that came from node is not known so essentially while the current node has a parent we're going to add to the path the current node came from node and then we're going to update the current node to be the current node came from node so essentially we're constantly cycle through the parent until we reach one which no longer has a parent which won't be our start node so again here we're coming from the end going back into the beginning so in the end we simply need to reverse our path so path out reversed like that and we can finally return right great so we wrote quite a lot of code here now let's see if our algorithm has been correctly implemented for testing let's go into our testing script and in here let's test it on Mouse down so in here when we press the mouse down we get a vector3 for the mouse world position here I'm just using a function from the utility as long as you can download you Tony's for free from unity code Montcalm if you want to make it yourself here it is all we're doing is a warm camera screen to a point okay so we get the model on position then let's convert this into grid positions so we're going to the pathfinding we get the grid and then we get the XY positions and we pass in our mouse wrong position okay so now we have an x and a y that we can use so in here and let's calculate a path okay so here we have our function we get the mouse wrong position convert into an x and y we calculate a fine path starting from 0 0 onto our mouse position if we don't have a path then simply use draw a line north to draw our path okay did she do it let's see okay here we are with our grid now I can click and we're going to see a path starting from 0 0 going into the mouse so let's click right in here and click and there you go there's our very nice path as you can see you'll from there there there there there now I can click wherever I want and the path is already automatically calculated so just like this we have correctly implemented a star path finding awesome now over here I have prepared a nice script that we can use to visualize the inner workings of the path finding so for example let's try to move to this square right here so I click there's the path correctly calculated now let's see how this path was calculated I can press space to go step by step there we go on the very first step it calculates the F cost in the middle G cost up there and H cos down there so G cost is 0 since this is the start node the H cos is 24 which is the assumption to get there so we got 10 here and 14 in here so we have 24 and the F cos is right there so now I can press space to go for the next step and here we go we start searching for the neighbors so again this neighbor has a G cost of 10 since we moved from here to here so that's 10 and 14 to reach the goal she's here so 14 right there so the f course is still 24 now let's check the other neighbors sorry go with that neighbor account like the cost and that neighbor account with the cost so you can see the blue squares are the notes on our open list and now in the next cycle we're going to start searching from node with the lowest F so that means we're going to start searching either this one or this one but not this one so I hit space and there you go now this one is red which means it's on the close list so we have fully searched this node now we're searching this node so now we search the neighbors for this one search down one search down and then we also try to update any other neighbors now we go to the next one with the lowest cost which is this one I can remember this as our goal so now we check the neighbors on this one okay there it is you can see it completed all of the new neighbors and now we keep going and now we are searching our final node so the current node is our end node so we have finished our goal so we click and there you go there's our final path go from here to here to here so in this script we can easily visualize how the algorithm works so here I can click anywhere to view an animation of the algorithm at work and there you go as you can see constantly searching for the neighbors until it finds a path so click in here and there you go searching for those and constantly searching for neighbors constantly going from the lowest F cost and eventually it searches and it finds the goal alright so now with this working let's add some unwalkable areas let's go here into our path node and in here and let's add another field we're going to make this a boolean and college is walkable now by default adhere in the constructor let's set it to true and now all we need to do is go into our path finding and in here when we're inside our cycle when we're going through here cycling through all the neighbors in here all we need to do is check if the neighbor node if it is not walkable then we're simply going to add this to the close list and continue so here it is very simple we need to do is set this to false and now that node won't be ignore from our algorithm now over here I have a simple visual script all it's doing is drawing a quad on certain positions so where it's not walkable it's going to draw a black one if you'd like to see an end look into how this script works then check out the heatmap video linked in the description oh it's really doing is just drawing that black quad so in order for this crew to work on we need to do is concentrate in here so I to into our testing and here had a feel for the visual and we simply call set grid then we go to the path finding and get the grid alright now finally let's make it grid unwalkable by right clicking okay so when we right click we're simply swapping out the is walkable on this node so let's see okay so here we have our grid map now let's left-click and there you go there is the path like normal now let's right-click and there you go that one turns to black so that node is no longer walkable it's now found left click in here in theory it's going to go around this so click any of their yo our new path is calculated and it's avoiding the unwalkable area so I can walk a bunch of these ones then click out here and there you go there's the correct path going around everything so I can make this as complex as I want and as long as the path is possible it won't find it there you go just like that so you can view the inner workings of the algorithm there you go it's constantly checking all those checking all the neighbors now it's trying to go through there but it finds out that it can't go through but it's not trying to go until it reaches 146 on the lowest and keeps going keeps trying to search all that and nope and it finds through here so there you go there's our final path so regardless of whatever obstacles we place our algorithm will always find a path if there is one awesome so just like this our path finding algorithm is now working with blackberries now let's just make the map bigger and apply the path finding into a unit over here I have a simple script to move a unit it's already set up in order to follow a list of vector threes down here I have a function to set the target position and it's in here that we're going to complete our path so let's go into the path finding and now in here if we just have one path funny in our game then we can make it a nice singleton so we can easily access it so here we have a public instance we're setting it on the constructor so now using this we can go back into our character and in here let's set the path vector list and we go into the path finding X is the instance and now in here we want the find path so we want a version that returns a list of vector threes so in here let's make that let's make a function returns a list of vector trees wrong with find path and now in here let's also receive world positions so you're going to the grid to convert our world positions into grid positions then we use our normal function in order to find our path there in here first we need to check if the path returning was normal meaning if we did not find a path but if not then let's convert our own list of Pat nodes into a list of vector three so we cycle through all the path nodes in the path and we convert them into vector threes using the X and y I multiply it by the grid cell size all right so just like this we have this nice function it takes in a start world position a end world position and returns a list of vector trees that the unit can easily follow so if I can here we can use fine paths we pass in the start position which is this one so get position and then the end run position which will be our target position and just like this this returns a path vector on list and in here you can see the handle movement function if we do have a path vector list it grabs the next target position it's easy if it's far enough if so then we want to move towards it so you move our position towards our next Waypoint index and when we are close and we simply increase the index and if we are past account we stop moving sorry go very simple path finding movement and now we can go back into our testing and in here let's add a field for our character and when we on left-click let's our character to go to there so we set the target position into our mouths wrong position all right that should do it let's test so here we have our nice unit standing on 0 0 and now I can click somewhere let's see it move quick and there you it starts to move example like that and I click somewhere else and there you go the path is always correctly calculated now in here let's add some walls so at these walls now go down here now what's going here and there you go he goes around the walls so I can make the map really complex and now if I click all the way in here if there you go there he's going through down here down here down here and so on so as you can see the unit is automatically calculating the path and moving alongside it right awesome so just like this we have our a star path finding fully working we can calculate the path from any position into any other position now the class that we wrote here does work however in terms of performance it is far from optimal there are a lot of things down here that we can do to greatly increase our performance for example here on get Lewis F cast node in here on we're doing is a very linear search so the more nodes we have the worse this is going to be for performance something like a binary tree would be much faster and here on the neighbor code we're also dynamically identifying the neighbors for every single node we could improve this significantly by simply pre calculating all the neighbors as soon as we make the grid so as you can see over here we have plenty of ways that we can take this and continue improving upon it in order to make it a proper pathfinding script let me know in the comments if you don't like to see a video just focus on performance improvements now that this video is done I'm working on another video where I won't take this exact same class and convert it into using unity Docs so stay tuned for that as always you can download the project files in Ataris from unity code monkey comm subscribe to the channel for more unity tutorials post any questions I have in the comments and I'll see you next time [Music]

Channel: Code Monkey

Views: 197,997

Keywords: unity pathfinding, unity pathfinding 2019, unity a* tutorial, unity a*, unity a* 2d, unity a star pathfinding, unity pathfinding without navmesh, unity pathfinding 2d, unity a* pathfinding 2d, unity pathfinding algorithm, unity a star algorithm, unity pathfinding a*, unity a star, code monkey, brackeys, unity tutorial, unity game tutorial, unity tutorial for beginners, unity 2d tutorial, unity 3d, unity 3d tutorials, unity tutorial 2d, unity2d, unity3d, unity

Id: alU04hvz6L4

Length: 24min 38sec (1478 seconds)

Published: Sun Oct 20 2019