Pathfinding can be a fundamental component of your game. Truly understanding how it works gives you fine-grained control of how units interact with the environment.
Learn how A* pathfinding truly works by diving deep into the mechanics. We'll go step by step through each process as well as cover the edge cases not often talked about.
❤️ Become a Tarobro on Patreon: https://www.patreon.com/tarodev
🔔 SUBSCRIBE: https://bit.ly/3eqG1Z6
🗨️ DISCORD: https://discord.gg/GqeHHnhHpz
✅ MORE TUTORIALS: https://www.youtube.com/tarodev
[Music] [Music] [Applause] [Music] pathfinding is the concept of finding the shortest route between two points the most popular pathfinding algorithm found in games today is the a-star pathfinding algorithm the idea of this video is to help you truly understand how the a-star pathfinding algorithm works by showing you a bare-bones implementation saying that i will give you a few tips to further optimize as well as point you to some pre-built solutions by the way all the code will be provided in the description alright let's get into it a-star utilizes three main numbers to calculate the best path the g cost signifies the travel distance from the node to the start node the h cost is the opposite in that it represents the estimated travel cost from the node to the target node the h cost is optimistic in nature so it will either be spot on or it will underestimate the cost it will never give a cheaper than possible value take this grid for example the h cost of this node is three because it is three nodes from the target but if we put an obstacle in the way making three moves to the target impossible the h cost remains the same as it was only an optimistic assignment so to iterate the actual steps required from any node will always be equal or more than the estimated h cost the f cost is equal to the g cost plus the h cost the lower the f cost the more attractive it is as a pathfinding option the goal is to simply choose the lowest f cost over and over until we reach the target node okay let's look at a few examples of a star in action all right so i'll begin by placing my target here and we'll begin path finding so as you can see all the nodes have a g cost of one as we are just one node away from our start but the h costs vary depending on how far away they are from the target so first we'll find our lowest f cost so this will be four and we'll choose this so we will now move to this node and we will check our surrounding targets again and we'll choose the lowest f cost again and as you can see our g cost is getting larger as we're moving away from our start position but our h cost is getting lower as we're getting closer to our target and our f cost will stay the same as we are just raising one number and lowering the other until we find our target okay so another example i'll put my target here so we choose our lowest f cost and now we have three nodes with an f cost of five so what we do is we then turn to our h cost and we find the lowest h cost so the closest uh estimation to our target wins so we'll choose this one and now we've got three nodes with five as the f cost so we'll keep choosing the lowest h cost and we'll get to our target the reason i'm using hex grids in my examples is because every direction from the node has a movement cost of one whereas in a square or isometric grid the horizontal and vertical cost is 1 while the diagonal cost is 1.4 we usually multiply these numbers by 10 giving us the integers 10 and 14. i actually use the exact same pathfinding code across all three grid types the only difference is the distance calculations from node to node i won't be covering how to calculate the distance for all three grid types in this video as that falls onto general grid logic but the code for all three will be provided in the link below okay let's dive into the code so here is roughly what the node class looks like i've redacted a lot of miscellaneous functionality to keep you focused on what's required but as you can see we have a g and h floats with corresponding functions which update them as well as an f getter which just adds j and h together we also have a connection variable but we'll get into that a bit later alright so we begin by taking in two arguments the start node and the target node we create a list of our nodes that we need to search and as we're starting obviously from the start node we will add it to the list and we'll also create a list for our nodes that we have already processed so that we don't double up by the way the search nodes are green on the map and the process nodes are blue on the map so we begin by looping over our search nodes and we will do that for as long as there are nodes to search or until we've found a path now that we're in the context of one of our search nodes what we're going to do is find the current best f cost node so first we'll just set our current to the first index in the search list then we'll loop over all of our other search nodes to see if this new search node has a better f score than our current one and if so we'll set it or if it has the same f cost as our current one we'll check to see if it's got a lower h cost uh and if so we will make it the current but by the end of this four inch loop we will have our best choice to set as our current node so now that we've got our node and we're about to process it let's add it to the process list and then we'll remove it out of the to search list so that we don't uh process it again and now it's where it actually gets interesting so now that we've got our best f cost uh node we will loop over all of that node's neighbors uh to perform some logic here so the neighbors that we care about are the ones that are walkable and also that we haven't actually processed them yet so uh if they're walkable and we haven't processed them let's uh iterate over them so first i just cashed this boolean here just whether or not it's uh already in the search list because we're going to use that a few times and here is arguably the most complex part of the algorithm to actually get your head around so if you think about it our current node here is what we have chosen as the best node of the bunch right which means any neighboring node that we find here should technically come through our current node right because because as far as we know our current node is the best node so far so the cost to this new neighbor will be at least what it has cost to get to this tile plus whatever it takes to get to the next node which in uh hex grid is one so now that we've got this g cost we need to determine if we want to actually do anything with it if it's worthwhile to actually update uh the values in this neighbor so we do two checks here we say is it already in the search list and if it's not then yes we will be updating these because we haven't done it yet or if this new cost is actually more favorable than the one that the node already has set okay so i'm just going to explain to you how a node can get a new g cost so i'll set my target here and we'll begin pathfinding and we'll come up here now take note of this node here with a g cost of four now it has a g cluster four because it took one two three four trips to get here so now we need to look for the next node to process and it looks like this one will be it so just keep track of this node here so as you can see the g cost is now three and that is because we have uh found a better route to that tile which is one two three so that's how a j-class can change just when the tile gets re-evaluated for a better route so now we can head up and finish our path and now we have our route all right back to the code okay so now hopefully you know why we do this check and how this can occur just from the beginning we make this g cost we determine this new neighbor's g cost and then we say if it's not already in the search list or if this g cost is better than the current one that it's got let's action it and set its values so we'll set the g cost so basically in this function it's just saying neighbor dot equals this new cost we'll connect this neighbor to the current node this is what allows us to retrace our path once we're done it's all well in good processing until we get to our target node but if we don't know how to recharge our path we've really done nothing at all think of this like drawing a line from the current node to the new neighbor this connection may change in the future but for now it's accurate okay so just to show you how the connection hierarchy works i'm going to put my target there and we'll begin building our path and you can see one solid line there and then we thought that was a better path here so we have broken it and now our best path is here and straight down so there will always only ever be one solid path back to the start node okay so i hope that made sense so we set our connection and then we check to see if this block is in the search list so in this conditional obviously we checked to see if it wasn't in the search list but it may have actually already been in the search list and got through on this condition so we'll check if it's in the search list if it's not we'll set its h cost now i set the h cost in here a lot of the times i see this actually set here but the h cost is just heuristic and it never changes so uh i'll just set it the one time and then we'll add this neighbor into the search list because if you remember up here at the start of this while loop here we determine which node in our search list is the best node so who knows this neighbor may actually be the best node now there's actually one last thing we need to do and that is to check to see if our current node is actually our target node because if that's the case then we have reached our our goal and we can return the path so we can just slot this part in here so after we select our best node which if if the target node is available it will definitely be the best node so if the current node is indeed the target node we will set our current path tile to the target node create a new list to return we will start our while loop while this current node does not equal the start node and we will add the node into a list and then we will set the current path tile to the connection if you remember we were setting the connections throughout it so there will be a connection from all the way from the target node to the start node once we get back to the start node we will just return the path [Music] so there you have it that is the entire a-star algorithm so as i mentioned earlier this code was written for readability to ease the explanation and there's a few things you can do to optimize the algorithm so this part here is the slowest part of the algorithm finding the best fcos node and obviously the more nodes you have the longer it takes to iterate through them all so this could be replaced by a simple binary tree or otherwise known as a heap and that way you won't have to process every single node you'll just have to process a handful at a time alternatively instead of directly using the class here we could extract the pathfinding data out to a struct and then we could off load that to the job system codemonkey has a video detailing a very efficient a-star pathfinding algorithm using the burst compiler so check that out alternatively the a-star pathfinding project by aaron grauberg on the asset store is a fantastic paid solution with many different grid types and customization or if you'd just like to study the code that i have in this project i've included the link down below it has some regeneration and distance logic for all the three different grid types that i've shown in this video so that might be handy for you so if you enjoyed this video on pathfinding subscribe to the channel and i'll see you in the next one bye