[0:02]Welcome to this video on path finding. So in this first episode we're going to be taking a look at how the A-star algorithm actually works. So that uh once we begin programming it in the future episodes, you've got a pretty good understanding of why it works and uh where we're going. All right, so here we have a grid of nodes. The white nodes representing the walkable areas in our map and the black nodes representing the obstacles. So um, of course we're trying to find the shortest path from node A to node B. And uh what we need to do first is decide uh how far apart the nodes are. So it'll be quite natural to say that the distance between two nodes is one. And uh therefore by Pythagoras, the distance diagonally is going to be the square root of two, uh which is approximately 1.4. So um, quite a common practice is just to multiply those two numbers by 10 and uh to use the nice integer values of 10 across and uh and vertically, and uh 14 for the diagonals. All right, so I've removed the obstacles for a moment so we can see how the algorithm's going to run when there aren't any obstructions. So um, the algorithm begins by going to the starting node, node A over here, and uh looking at all of its surrounding nodes and calculating some values for each of them. So the values in the top left corner of each node, uh are called the node's G cost, and that is quite simply, how far away that node is from the starting node. So this node in the top left corner has got a G cost of 14, since it's just one diagonal move away from node A. In the top right corner of each node is the node's H cost, which is basically the opposite of G cost. It's how far away the node is from the end node. So this node is two diagonal moves away from the end node. So it's got a H cost of 28. Now, the big number is the node's F cost, and that is very simply, G cost plus H cost. So now the algorithm is going to look at all of these nodes and it's going to choose the one with the lowest F cost to look at first. And that is, of course, this uh 42 in the top left corner. So it'll mark this now as closed. So it'll appear red. And um, it will then calculate all of these values again for all of its surrounding nodes. And uh, it's quite simple to see what's happening here. Um, these F costs are just staying the same as it moves towards the target because the G costs, the movement costs are increasing. And the H costs are decreasing, and they're just sort of balancing each other out. So uh, it basically explores the path straight to the end. Well, no point having uh path finding in your game if you're not going to have any obstacles. So let's add those back in and run through the algorithm once more and see what happens. So once again, we look at all of the surrounding nodes and calculate their F costs. And we'll go with this uh lowest F cost of 42. And uh now we have a scenario where we have three nodes each with an equal F cost of 48. And um, so what it'll do just to sort of uh decide which one to pick is we'll look at which one is closest to the end node, in other words, which one has the lowest H cost. This has an H cost of 38, this is also 38, and this one's 24. So we'll go with this one. Now, as you can see, the F costs are increasing each time, since uh we're not going in a straight line towards the end. So uh even though the H costs are decreasing by a little bit each time, the G costs are increasing by even more, resulting in a more expensive path. So now the two nodes with the lowest F cost on the map are these two 48s over here. They've got the same uh H cost, so we can pretty much choose one at random. Let's go for this one over here. And uh now we have to look at the other one. And at this point the most sort of uh promising node as it was, this 54 over here. And we explore that. So now we'll look at this other node with an F cost of 54. But uh one thing I'd like to draw your attention to quickly is the node just to the left of it with an F cost of 68. Um, if we look at its G cost, it is currently 38. But um, if we look how far away it is actually from node A, it's just 10, 20, 30 away.
[4:53]So um, as we explore this 54 over here and uh explore all of its surrounding nodes, uh you'll see how this 68 updates to reflect the new uh best path to this node. Uh, so it now has an F cost of 60, and it is the most promising node on the map. So we'll explore that. And uh, now we have a bunch of 62s to look at. Uh not much to say in the way of commentary here, just exploring, uh all of these lowest F costs. Until now we can come back to the 68, and we explore that. And uh we get to explore the other 68. And now we'll observe the same effect that we saw in the first example, where we've just got a straight line to the end node, and the, uh, the G costs and the H costs sort of are going to balance each other out, and the F costs won't change and we'll just go straight to the end. So hopefully you can see how this is uh guaranteed to find the shortest path, since um, as soon as you're not moving in a straight line towards the end, the F costs are going to increase, and then it will start looking at the other potential options. Let's look at one final example. Uh in this case, I have hidden the G costs and the H costs. And um, and instead showing these little arrows, which are basically indicating where these nodes have come from. So uh when we explore this 58 over here, you can see all of its surrounding nodes are now uh pointing to reflect that they uh sort of originated from this node. Um, of course, this 64 and this 58 over here, uh even though they are its neighbors have not updated to uh to show that they're coming from this node, since uh it would be a worse path. In other words, it would have a higher F cost if we were to get to say this node over here by going diagonally up and then uh down. Um, so it'll only update if it is in fact a better path that's being offered. So we continue by looking at this 58, and uh that yields a 66. So we go back to the 58 at the beginning. And uh now once again just to demonstrate this, you can see this 66 is coming on the sort of um slower diagonal path. So um, it would be much quicker to just go horizontally across. So as we explore this 58 and look at all of its surrounding nodes, uh that node is going to update to reflect that. And uh, as you can imagine, we just go straight to the end now. So the point of these arrows, of course, is just that now that we've reached the end node, we can sort of uh retrace our steps and uh find the path that we took to get there. All right, so while that is still hopefully uh fresh in your mind, let us look at how this would work in uh in terms of the actual programming. And so what I've got here is just a bit of pseudo code, um, meaning that it's not in any particular language, it's just basically a set of instructions. All right, so to start off with, we create two uh lists. The first is called the open list, and uh this list is for storing all of the nodes uh for which we've already calculated the F cost. So in the diagrams that I've been showing, uh all the nodes that were colored green, uh were the ones that were currently in the open list. Then the closed list is basically the set of nodes that have already been evaluated. So those are all of the ones that I sort of ticked off as red in the diagrams, uh once we'd looked at all of their neighbors. So once we've created those two lists, we uh add the starting node to the open list. So that's uh currently the only thing in the open list. And uh there's nothing, of course, at the start in the closed list. And then we enter a loop. So inside of the loop, we create a little um temporary variable called our current node. And this is equal to the node in the open list with the lowest F cost. So um at the beginning that will of course be the starting node since it's the only one in the open list. And uh we remove the, the current uh node from the open list, and we add it to the closed list. Then if the current node is the target node, then uh we can assume that we've found the path. And uh we can just exit out of the loop. Otherwise, um, we're going to go through each of the neighboring nodes of the current node. And uh, first of all, if it's not traversable or uh if it's in the closed list, then we'll just skip ahead to the next neighbor and ignore it. And if that's not the case, then we uh check a couple of things. So uh first of all, if uh the new path to the neighbor is uh shorter than the old path. So say for example that the neighbor is already in the open list, um, as we've seen in some of the diagrams, but then the new path is shorter, so we have to update that node to reflect that we found a better path to it. Um, so if, if that is true, or if the neighbor is not already in the open list, um, then we just add the neighbor to the open list. Which we do obviously by first calculating the G cost and the H cost. And then we set the parent of the neighbor to the current node. So that's what I sort of tried to show visually with the arrows. Uh we we sort of keep a reference to where that node came from, so that we can retrace uh the steps once we get to the end node. Then uh finally, if the neighbor is not in the open list, um then we just add the neighbor to the open list. And we keep looping this and eventually, um the current node is going to be equal to the target node. And the path will have been found. We'll uh exit out of the loop and we'll just run a quick little method to um to look at all of the parents going back from the from the end node until we find the starting node and that will be our path. All right, so that's pretty much all there is to it. Um, of course, as we begin actually programming this in C# in the uh future episodes, we'll look at a couple of things, um, a bit more in depth. But for now that should hopefully give you a pretty good understanding of, um, of how A* works. And uh, if you're unsure about anything, don't hesitate to uh leave a comment and I'll try to help you out. Um, otherwise, I've also linked a couple of really good articles in the description, which you could, uh, have a look at as well. All right, so thank you very much for watching. Cheers.
