A* Pathfinding in Godot 3D (Godot A* 3D Tutorial #1)

in this video we'll go over how to write your own a star pathfinding system in a 3d godot game i'll show you how to do it in an easy and scalable manner that works for any number of nodes as long as you're using the same y-plane and then in future videos we'll show you how to better debug your pathfinding and dynamically update when there are obstacles that update your path let's get started alright so let's really briefly just talk about what a star is if you're familiar just skip this part but if you've never used a star you don't really actually have to know any of how it works under the hood but what it is is it's a grid traversal algorithm it's a best first search which means it's looking specifically for the best path from one point to another and this is different to other algorithms that are pretty famous like dextrose which is a breath first search algorithm a star is really optimized and there's a reason it's used in game development all the time is because it's meant and optimized for quickly finding a pretty good path from one point to another and that's why we're gonna use it and another quick note too is that no games just have a pathfinding algorithm i'll show you how to use a star in your own game but most other games are going to have their path finding and then they're also going to incorporate a bunch of other mechanics that will help make their pathfinding smoother like steering behaviors collision avoidance just kind of slightly adjusting path a little variance just to make movement feel more natural because no one moves from one point on the path to another making all of these tight corners so there are tons of ways that you can add other systems on top of your a-star to make your path finding a little bit more natural but we are going to make a really nice a-star system that you can use for any game that just has regular meshes and you'll notice the key here with a-star is that it's based on a grid so if you're using a tile map in 2d or if you're using a grid map in 3d you've already got some basic things in godot you can use to get a grid but because 3d nodes and meshes aren't necessarily in a grid we're going to have to impose a virtual grid on top of our node system we're going to have to impose and create our own virtual 3d grid on top of the nodes that we have existing in our scene and i'll show you how to do that and it's going to be super easy and extensible so let's swing over to godot and get started implementing all right so over in godot you can see that i've set up this little demo system that we're going to use for this tutorial and over on the left on the scene tree you'll see i've got a camera a directional light a player and these two different ground meshes these are just static bodies with a cube mesh and just a simple matching collision shape so none of this really matters too much you can just you know do whatever you want in your own game if you want my character controller you can get that in the code for this project which you'll find in the github repo down in the description below but basically all it's doing is that whenever i click on a place in world space whenever i click on one of these meshes it's going to try and route the player there by getting a path from our a-star system so it won't work right now but just so you know that's how we'll test our a-star pathfinding is that i've got it in place where if we click around our player will try and get a path to that position so this is the scene that we're going to use let's actually start implementing our a star system and in order to do that i'm just going to add a new node to our main scene and this is just going to be a spatial node we don't want to use anything special here godot has a built-in navigation node so if i hit command a and look for navigation you'll see it but the problem in godot 3 is that this navigation node it works great but it can't dynamically update it can't bake in any obstacles and so it makes it kind of useless for most games where you have your path might change or things might move around and so because of that a star is still i think until good04 when they have the new navigation server by far for most people the best case unless you have completely static levels the best case or easiest way to add pathfinding to your game so we've got our new spatial node here let's rename it to a star because that's what it's going to do and so now that we've got our a star node let's add a script to it which we'll just call a star and i'll do that and i've already scaffolded out the basics of our a-star script there's a couple functions we're going to need to add and we'll make more later but for now we'll start here and we're going to need our ready function just the built-in godot one we're going to need a function called add points and you'll notice that before all of these ones i've added this underscore because these are private functions we're not going to call them anywhere except from within the same script so we'll need add points and then we'll need connect points so these are our two private functions that in tandem we're going to call to actually build and connect all of our a star grid and then finally we're going to have a function called find path and you'll notice that find path is not private there's no underscore here and this is going to be our external interface our api as you will into our a-star system and so this is the function that other nodes that are not our a-star node can call to get a path from a certain vector to another vector 3. and what this is going to do is it's going to return an array of vector threes so it's going to return the vector3 points that form altogether the path from a specific vector to another vector and so these are the functions we're going to start with implementing here and in order to do that first let's actually talk very briefly about how we want to do this so we just looked at what makes up an a-star grid or algorithm and remember we're going to have to impose our own virtual grid on top of our meshes and so the way i'm going to do that is that actually in godot for any of your mesh instances you can actually get the bounding box of that mesh and this works for even non-cube meshes so if you've got a circle for example with a radius of one you can get its bounding box and it'll be a cube with a height and width of 1 because that's the radius of your sphere or sorry a height and width of 2 i'd imagine since your radius is 1 not the diameter but you can get this bounding box for any mesh even if it's not a cube and i want to do that and what that assumes again this is it's really hard to make a pathfinding system that works for every game it'd probably be better to use collision shapes to build your grid but for the sake of this i'm going to assume that your collision shapes match your meshes pretty closely and we're just going to use meshes to build so your collision shapes if they vary significantly from what your meshes look like then that means that following this video your pathfinding your a-star grid is also going to be a little bit different from your actual collision shape so you can use a collision shape to do it just takes a little bit more work so we'll stick with mesh instances but shouldn't be too hard to adapt either way that said the way that we are going to determine our floor basically the way we're going to determine where we actually build our a-star grid is by getting the meshes of all of the nodes all of the static bodies or kinematic or whatever any physics body that we have that we want to be walkable and in order to do that we're going to add those nodes to a group so if i select our ground one here which is just our gray ground box and come to node and go to groups i'm going to add it to a group called pathable and you can name this whatever you want you could call it walkable or you should name it should be included in a star you can make it as long or short as you want but basically this is the group that any node any scene that is part of this group we're going to use it to build our pathfinding system so you'll notice that for both our ground one and our ground two i've added them to this pathable group and that means that we are going to build our grid on top of these two nodes so with that in mind let's actually go into our a star script here and then i'm going to replace this pass on line 5 and i'm actually going to say variable pathables again call this whatever you want and what i'm going to do is say get tree and i'm going to get the nodes in our pathable group which we do by saying get tree dot get nodes in group is i'm just going to pass in pathable and so this just needs to match the name of your group which you'll remember is pathable so what this is going to do is return whenever this node reads up it's going to return an array that has our ground 1 and our ground 2. easy enough and so what we need to do then is actually pass in this list of pathables to our add points function so i'm going to say add points and call that and pass in our pathables and you'll notice that add points doesn't actually take a parameter right now so i'm going to copy this add it as a parameter and we'll type this as an array because it is an array we can also in our ready function add a call to connect points we're not actually going to do anything in that function right now it's just a pass but we'll add it there because the way this is going to work is first we want to add and build up all of our points we're going to create our grid and then later on after all the points have been added we're gonna go back through and connect them all so the way that this is gonna work is we're gonna kind of do a two pass system where we build up our grid and then we go back through and connect all the points to each other okay and before we actually start implementing our add points function let's add a couple of necessary variables to the top the first one we add is going to be a variable that we'll call grid step and i'm going to set this to 1.0 it's important that this is a float here and what this means is remember we don't actually have a grid we're imposing a virtual grid so we can make that grid each cell each basically each square in our grid as small or as big as we want and this is what grid step is going to be it's going to be our cell size so if you want to call it cell size 2 that works i'm going to call it step because it represents the step between one part of our grid to another one cell to another now i would actually recommend this not being smaller than 1.0 with the system we're going to build you could make it 0.5 but i think what you'll actually find is that the smaller your cell sizes are the more erratic that your movement is going to look because you're going to have such a big path that just goes from tiny steps to each other it's going to look really weird so i would start with 1.0 and actually only move upward from there but you can do whatever works best in your game i would recommend though you might find some issues if you try doing something that isn't one or a multiple of 1 or 0.5 so if you do like 0.25 you might run into some issues again experiment in your own game but i would recommend sticking with a grid size of 1.0 or bigger so we've got our grid step here another variable we're going to need is i'm just going to call this points and this will make a lot more sense in a minute but what i'm going to set this to is really just be an empty dictionary which is just these two brackets with nothing in them and what we're going to do remember a dictionary has key value pairs and when we're talking about a star when we're when we're looking at our game we're only ever dealing in world coordinates we're only ever thinking in terms of vector threes what position does this cube start at what position is our player at it's all vector threes right it's world coordinates well when you use a star you add points to the a-star grid in world coordinates but you refer to those points by a specific point id so when you add a point in your a-star grid which we'll have an example of in just a minute you're going to get an id for that point back and whenever you need to get a path you have to pass in the point ids so even though our whole game is running on vector 3s and that's how we think when we're talking to our a-star system we're going to actually have to use these point ids which don't mean anything outside of our a-star system so we've got to have a way to convert between world vector threes to our specific a-star points so that'll make more sense in a minute but just remember that for when we get going and the final variable we need is just going to be variable a star and godot actually has a built-in a-star resource a built-in a-star system that we can use and so we'll just say a star dot new because we have to create a new a star resource or new a star object that's going to do this calculation and store our points for us so now that we have that we're ready to keep moving through in our add points function and start adding points to our a star grid okay so let's start doing this let's start implementing add points and the first thing we need to do is loop through all of our pathables that we're getting in and use them to build up our grid so let's say for pathable in pathables we'll make this a for loop here and what i want to do is get access to the bounding box of the mesh of each of our pathables and so the way i'm going to do this is say variable mesh and i'm going to say pathable dot get node and this is going to rely a bit on that both of our ground instances here just have a node called mesh instance and there's tons of ways to get around this in your own game but either whatever you do whether it's saving in each of your pathables saving your meshes of variable that they can just get or having a function in your pathables whatever we're going to need access to the meshes underlying each of our pathable nodes or scenes and for me it's easy enough to just say mesh instance because i'm you know these are just simple nodes but you might have to do a little bit more work here in your own game but shouldn't be too hard but i'm just going to say pathable.getnode and then we'll type in mesh instance here because that's what they're called and so in this way we're going to get the mesh for each of our past bulls and now more than that though we actually need to get the bounding box and if you've never used aabb which is a acronym that stands for axis aligned bounding box it's something built into not just godot but it's a common concept in 3d graphics and the way we can do that is actually say aabb so that's going to be the variable we save it to we'll say variable a b equals mesh dot get transformed a b b and there's actually two functions we can do here there's a function that's just get aabb and you can look all these up on the godot docs for mesh instance but you can just get a bb which will return the bounding box but it will return it in relative or local coordinates and we want world coordinates so if we rotate or scale or transform our mesh we want the aabb to be updated to reflect the actual bounding box in 3d coordinates and so this get transformed aabb function does that it takes in the rotation scale and position or transformation of the bounding box and then returns that so make sure you're not calling get aabb but you're calling get transformed aabb so real quick let's talk about how we can use our aabb which is really just a cube it's a bounding box it has three properties we're going to need to use position end and size position and end are two vector threes that represent two different as far away as you can get vertices on the rectangle so for example if we look at our ground one here this gray box our position might represent this back left and lower vertices this one right here not the top one but the lower one and then the polar opposite is going to be our n property which will represent if i come back over here our front right upper vertices so position is the left back lower and end is the front right upper and then that other property size just represents basically if you do end minus position size represents how wide how tall and how deep it is if we do position plus size it will equal end so position and end are just the points but if we add our size to position we'll also get n so again it's just a cube and these are helpful properties built in to help us make use of the size of the cube so we have our aabb here and what we want to do is get the start point for our grid and this is the point that we're going to use from there to keep iterating over our aabb to keep iterating over the size of our mesh so in order to do that let's create a new variable it'll be variable start point and then start point is just going to be a b b dot position because remember this is going to be the farthest back point this is going to be the farthest corner and i'm actually going to type this as aabb just so we get some better autocomplete here so we're going to have our start point and then the next thing that we want to do actually is figure out how many x and z steps we're gonna need to totally cover the size of our bounding box here because we want to add as many points on our grid as we need to to totally cover the width and the depth of our bounding box and it's important to note too that in this video we're not going to deal with differing y values we're going to assume that all of our meshes are at the same y value that our walkable plane is a plane it's all the same y value now let's go back to our grid view for a minute here because we've we have already set what our grid size is which let's say is one because that's the value we're using here so this is our grid size right let's imagine theoretically our mesh our bounding box is has a size of five so it's five wide and five deep well we need to determine how many cells are gonna make up our grid basically we're trying to determine how many cells can fit over our bounding box for our mesh and so if it's five what we need to do is have five different cells like so but because we will have different mesh sizes and will have different grid sizes or different cell sizes we need to actually use some math so that if we change either those two values it'll still work and the formula we need to use to do that is to take our x size over our step and that's going to tell us how many cells we can fit in the x direction and we also need to do the same for our z direction also over our steps and these together are going to tell us how many cells we can fit in the x and how much we can fit in the z direction and those together are going to form our grid and so if we go back to godot we can actually do this by saying variable x steps and i'm going to do the math here by just saying a a aabb.size.x because remember we talked about aabbs these bounty boxes have a position and an end which are the vector3 spaces and they've also got a size which represent the distance in each of the three directions from position to end so we'll get the size of our bounding box in the x direction and we will divide that by our grid step and so again let's say our size is five if our grid step is one this will equal 5 which tells us that we can fit 5 cells if our grid step was 0.5 so if we were doing a different cell every 0.5 units then 5 divided by 0.5 would be 10 which would make sense because we could fit 10 cells in the x direction so this formula is really simple but it'll make our algorithm here easily adjustable and it'll just work as we change the size of our grid and our meshes so let's copy this and do the same in the z direction and again remember we're not doing y right now just to keep it simple this is something you'd probably have to change too if you did want to do a changing in the y direction but we'll just do in both of these so we'll do z steps in the size.z direction and this is going to tell us how many cells we need to create for this specific pathable and so now that we know that we can actually loop through these steps and so i can say 4x in x steps and if you're not familiar with the syntax you might be wondering why am i saying for x in an integer basically and good o automatically if you say 4x in an integer it will automatically turn that integer into a range so if this is 10 it's going to say 4x and 10 and x will go from 0 to 9. so this is just a really easy handy way for us to loop through all the steps we need so i already did this in the x direction let's also do it in z so i'll say four z in z steps and so basically what we're doing is we're going to be adding these together to create the specific coordinate or define the specific coordinate for our next cell so we're going to be moving in the x in the z directions basically going because we're doing x on top we're going to be doing one row and then moving over one x value to the next row etc so now that we have this we can actually find our point to add and because x and z are both going to be zero at the beginning we can just we don't have to do anything special for our start point we can just add it and so i'm going to say variable next point in other words the next point that we need to add to our a star grid which at the beginning will just be our start point is going to be equal to start point which is just the start of our bounding box and then we're going to add a vector with our x and z step values as an offset so i'm going to say plus vector 3 x and then 0 because we don't want to change our y value and then z we're going to add those two as an offset to our start point so we're building outward from our start point the other important thing too that we need to add here is i can't just say x or z because as our grid step changes these steps are always going to be integers that increment in a value of 1. so it'll go from zero to one to two to three but our grid step might be less or more than that and so what we actually need to do is multiply this by our grid step so i'll say x times grid step and then z times grid step okay so now we're actually generating our next point we're generating what point in world space we need to add to our grid but we're not actually adding it and in order to do that i'm going to say underscore add point not add points just singular add point and i'm going to pass in next point and this is a function we haven't created yet so let's add that right underneath this and we'll say function underscore add point just singular and we're going to pass in a point which is just going to be a vector 3 because it's in world space it's a world space point that we're adding and what we want to do for this function is do some sanitization first so we've been largely not dealing with the y value here but we want to have a standard y value for our grid so let's go up to the top and i'm going to say variable grid y and i'm going to set this to 0.5 because i know that's our ground meshes go up to a y value of 1 or maybe 0.5 this should actually put it right on top of the ground but it doesn't really matter this is just going to be the y value that our grid all of our points live at so it's consistent it's one less direction we have to look up or down and we just look left and right and forward and back so we'll have our consistent grid y here and what i'm going to do and add point here is actually just say point we're going to grab our parameter and actually change it oh sorry we're going to say point.y change that point parameters y value to just be grid y so independent of whatever we're calculating and add points when we actually insert that point into our a star grid it's going to have a consistent y value with all the others so what we need to do now is you might remember again earlier when i said that when we're dealing with our a star grid we're actually dealing in specific point ids and not in world space anymore so first we need to get the next available id for us to do godot's a-star implementation actually has a function to do this so i can say a-star which you'll remember is just the a-star variable we created at the beginning of our script i'll say a star dot gets available point id and this is just a function that returns basically the next available integer that we can use as a point id so this is going to be our point id so this is the a star id that we're going to use for this point that we added and all we have to do now is say a star dot at point and it needs an id you'll see that's the first parameter so we'll say id and then it needs the actual world position and so we'll say point and this is going to be our point after we've adjusted the y value to be our normalized y value and that's it we are adding our point here so there's one other thing we want to do here and you might remember earlier we made this points dictionary which i started to explain a little bit but it was confusing and what we want to do is actually add this point value to our points dictionary and in order to do that remember we don't currently have a way to get this id of our point we can get we can figure out or ask for a specific position in world space but in order to get a point from our a-star grid or to get a path we need to get its id it's a star id and we don't have any way to translate between those or any lookup that we can use to get the idea of a point and so what we're going to need to do is actually build a function that's going to convert from a world coordinate to an a-star id that's a little incorrect our our points dictionary is going to do that lookup what we need to do is build a function that will convert our world point into a string that we can use as an easily referenceable key in our points dictionary so let's just build this function and i'll explain as i go and it'll make more sense in a minute so let's just call this function world to a star and all that means is that it's going to convert a world point to an a-star point and we're going to say world point and this is just going to be vector 3 and it's going to return a string and so all that we want to do for this function here is we're going to make a couple variables an x y and a z variable and we're going to say variable x and this is going to be stepify and i'll explain what that does in just a second we're going to stepify and then world dot x and then stepify takes a second a second parameter which is the step and we're going to pass in 0.5 and so what stepify does is you pass in a flow or an integer and it locks it to the nearest multiple of whatever value you pass in here so if we pass in 0.5 what it's going to do is lock in or round our flow value to the nearest 0.5 so if our value is 0.33 it's going to round it up to 0.5 if our value is 0.92 it'll round it up to 1 because that's the nearest iteration of 0.5 and so step 5 is a really useful function and you can give it really any second number you want here float or integer or whatever and it'll round it to the nearest multiple of whatever you give it now we're going to use 0.5 here you could actually really just set this to be your grid step that's probably the best thing to do but make sure that your grid step is never lower than what your stepify is so let's set this to be grid step and that means we are going to round it to our nearest grid step and in this case because our grid step is one this will just basically round it to the nearest whole number okay so that's our x value let's do the same with our y and z and you might be able to see how this is going to go so i'll change it to variable x y and z and then change the corresponding world call so we'll get the correct world coordinate for each of these and now that we've got these stepified x y and z coordinates we're going to actually convert them to a string that we can use as the key so that any time we pass the same world point vector 3 it's always going to return the same string which we can map onto our points dictionary so we're going to return and then i'm going to say percent e comma percent d comma percent d and if you're not familiar with this syntax the percent d just means to pass in a digit or decimal but what we're going to do is we're basically saying hey these three percent d values we're going to pass in replacement or template values that you're going to insert for them and we can do that by using the percent operator after our string and then because we have multiple values we actually have to pass in an array so we'll pass in an array that has x y and z all comma separated there and so this is going to take this string and insert these flow values as the string on this whole time i'm so sorry i wrote world here instead of world point because that actually let's let's just call our parameter world and then it'll line up here so this is our world point and we're going to go through and step if i basically round our x y and z to a consistent value and then return it and again the values coming in should already be conformed to our grid step but the reason we especially need to use stepify is especially with floats sometimes you get rounding errors or you get the like you know point zero zero zero one off or something like that just because floats are imprecise decimal storage options and so because we're storing it into a string if one of these digits is like 25.000 instead of just 25 we're never going to actually be able to get it again so we need to make sure that the strings we're putting into our into our dictionary into our points dictionary are going to be correct so we've got that now let's come back up to add point and we need to add the like we said before we need to add this point into our points dictionary so that we can look up its unique a star id later on so i'm going to say points here because we're going to just add it in and we need to pass in the key here and the key is going to be our string world to a star conversion our string lookup code so we're going to say world to a star and here we're just going to pass in point because we pass in a vector 3 and we're going to so that's going to be the key so we're inserting an entry where the key is our vector3 string and the value is going to be our a star id and you'll see how this is useful and why we need this later on but again what it's doing is just creating a lookup table so that for any world point for any world vector 3 we can look and see if there's an a star point that matches that and get its a star id which is how we're going to get our actual paths from one point to another okay i know this is a lot again i hope you're hanging through but we are almost there and now what we need to do is actually go through and connect and so the way we're going to do that is first in our connect points function say four point in points because we're going to loop through all the points that we've stored in our lookup table and look for their neighbors and so first you'll remember again that all of our points here this is actually going to be a string basically whatever is stored in our point variable here in our loop is going to be this string that we've inserted in our points array so let me actually show you what that looks like if i set a break point on our add point function anywhere and run our game you'll see that our current point that we're adding is negative 10 0.5 and negative 10 and if i keep moving through you'll see we're going down the z values we keep adding them eventually we'll start to get to the new x value let me just show you that so this is exactly what we hope for right we're going through through the top of our bounding box and just adding our we're imposing a virtual grid on top of it and you'll see that our id here our a star id continues to increment so that's good and let's look at our points grid right now and if i scroll down to this dictionary here let me make this a little bit bigger you'll see how this is all coming together this dictionary shows us all of the points so what it's saying is hey at the world coordinates of negative 10 1 and negative 10 that is our a star point id 0. at the world coordinates of say negative 10 1 and negative 7 the a star unique id for that point is three and so this is a lookup table that's letting us go between our world position and getting our a star id and you see how we're building this all into our points dictionary here and so what we can do now is use in our connect function is we can use these values here to look at our neighboring points but before we do that we need to actually deconvert these strings back into vector threes so that's going to be our next task let me get rid of this break point stop the game and we'll come back here so now what we need to do is say first variable so right now our vector3 is stored as three comma separated values so let's just say position stir this is a throwaway variable but all we need to do is say point and remember point is a string here and then split which is a function on a string and then split it on the comma and so this is going to give us an array with three different values which are going to be our actual numbers but now we need to convert it first we convert it from a string to an array now we need to go from an array to our vector3 i'll say our world position because this is going to be our actual world position we'll say vector3 and then all we need to do is say position stir of zero and we're gonna use the same call for all the others so of zero one and two and remember it's because we have an array here position stirs in a ray of size three where the first value is x second is y and third is z so we're just accessing each of those values individually and putting them back into a world position vector three so now we have a vector three which is our world position here now we can actually look at other nearby positions in our world and in order to do that we need to think about how we connect points in our grid so let's come back into our handy dandy grid over here and just to show what we need to do in code let's say this is the current point we're looking at well we need to try and connect it to all of its adjacent neighboring points which are here here here here here here here and here so there's actually eight points that we need to try and if you think about these coordinate coordinates if this if our point is at zero zero this is negative one in the x and one in the x and this is also negative one in the z and one in the z so if we loop through negative one 0 and 1 in the x and also negative 1 0 and 1 in the z we're going to be going through each of these points and able to connect them the only thing we don't want to do is when we're looping through 0 0 that's just our point itself so we don't actually want to connect that okay so like we just saw we need to go through negative one to one in the x and z direction to get all of our adjacent points so what i'm going to just do is say variable and i'm just call a search chords and call it whatever you want but i'm just going to make an array from negative 1 0 and 1. and again all we're going to do is just loop through these so i'm going to say 4 x in search chords and then 4 z in search chords and again what it's going to do is it's going to go through each the search chords negative 1 0 and 1 and put these numbers in these x and z values and what we're going to do is add them as an offset to our world position and again we'll have to multiply search chords here basically by whatever our grid step is because if our grid step is 0.5 then this should be negative 0.5 0 and 0.5 so we'll take care of that don't worry but again all we're trying to do here is find our adjacent all of our neighboring points in world space so now that we've got this first let's say variable search offset and this is just going to be turning our chords here into a vector so we'll say vector 3 and we're going to add our current search chords so this will be x zero and z because remember these are the things we're currently looping through and what we want to make sure too is remember i said that if our offset here is just zero zero zero then we're looking at the current point itself so we need to skip that so we can say if search offset and we'll just say equals vector 3.0 it's got that handy dandy helper and we'll just say continue we can just skip this one we don't want to actually break out of the loop we'll just continue and skip it because if this is zero zero zero like i said we're just looking at the same the point we're already looking at so there's it's not a neighboring point so we don't need to connect it and actually i'm just realizing let's um in our search chords here i kind of just said this but let's just change these to be grid step because we want to go from a negative grid step to a positive grid step rather than just multiplying it later on below let's just make these the numbers we loop through so again if your grid step is 5 this will be negative five zero and five so whatever your grid step is as long as it's a grid and it's consistently spaced this will still work and this is just gonna help us have a flexible system where we can increase or decrease our grid step okay so we are skipping the current point and making sure we're only going to connect adjacent points and what we need to do is test for each of these points we're looking at if it's a potential neighbor so we'll say variable potential neighbor and we're going to say world to a star because we've got this search offset now we need to see if this world position is an actual a-star point because what if it's a point that we're looking at that's not actually over a ground what if it's just empty space or what if it's just not valid we need to make sure that whatever we're looking at it's a valid world or a valid a star point before we try to connect it so here our potential neighbor is remember it's going to be our world position plus our search offset so we're going to say the our current points position and then a little bit up or left or right or wherever our neighbor is we're currently looking at so basically we're getting the world space coordinates of our potential neighbor and then we need to see we're going to turn that into a string and then we're going to see if this is an actual point in our point lookup table so we'll say if points our point lookup table dot has which is just to say if this if this potential neighbor is an actual point this new coordinates that we're looking at if it has potential neighbor and then if this is an actual adjacent neighbor we need to connect to then we can use the a star dot connect points function and just like it says on the tin this function is going to connect these two points but you'll notice here the reason i pulled this up is it's telling us that the first two parameters are point ids remember everything in the a-star system uses the point ids and it doesn't use world space so we need to get our point ids for both our current point and our new neighbor point so let's do that first before we connect them we'll say variable current id and this is just going to be points because remember we need to get our point id from our lookup table we only have its world position so i'll say points and remember we're actually we're looping through our points so we already have our world string key our vector key it's just point up here right so we can say point or points of point of our current point so we'll get the actual a star id of our current point and then we'll say variable neighbor neighbor id and this is going to be points of potential neighbor which is now our actual neighbor it's a confirmed neighbor and then what we can do is say a star dot connect points and we actually have the ids to pass in so i can say current id and then our neighbor id and so it's going to connect these two points now we're pretty much done here this is good to go except we should also make sure that these points aren't already connected so i can say if not a star dot r points connected again it's got a helpful function for that and we can say current id and neighbor id so if they aren't already connected then we'll connect them okay we are so close all we need to do is actually return our path now and there's only three lines of code we need to do this first just to prime what we're going to do i'm going to say return and then in godot's a star implementation the function you need to call to actually get a path is a star dot get points path and this is the function we're going to call and again like we'd expect and like we've seen before you'll notice that the parameters it takes are a from point id and a two point id now again our find path function is taking two vector threes because anything outside of our a star script our node shouldn't actually have to know about a star point ids it should just be able to pass in whatever coordinates it cares about in world space and so we're going to have to convert from these vectors to our coordinates and pass these in to our getpointpath function so let's start by saying variable start id and this is going to be the unique a star id for our from vector and actually rather than how we were doing our point lookup before using world to a-star and everything else godot's a-star implementation actually has built in a really helpful helper which is a star dot get closest point and so we can actually use this and it we just pass in the vector 3 and our a star implementation will find the closest point in world space in its graph to the vector we pass in so we don't even actually have to do a point lookup here all we have to do is just pass in the vector3 so it's our start id so we need our from because that's where our path is starting and i'm going to copy this line and paste it and then we'll set our we'll set this next variable to be end id and this is going to be two so we'll get the closest point on our grid to our start from our from and the closest point to our end our two and we'll pass in these ids so start id and end id and now we are getting an actual path from this a star grid that we've built alrighty so if i run our game now let me expand this just to make it a bit bigger if i click somewhere there we go our player actually goes and uses the pathfinding system and you can see that he's using it because he's making a bunch of little adjustments and he can move and if i click on even different meshes he will still be able to go from one to another wow this is super cool and i hope that this has been helpful for you i have planned another couple videos one to show how to add dynamic obstacles that will update the path and block certain parts of it on top of dynamic collisions i also want to show you how you can draw these cubes like you see here as a debug method i found this is a really helpful way for me to see what's going on with my path finding and later on when we do this i'll actually show you how to turn these red when you've got an obstacle over a certain grid but never fear it's super easy and helpful so stay tuned for more videos but i hope this has been super helpful you feel equipped and confident to make an a-star pathfinding system in your own game if this video has been helpful a like and subscribe to support the channel is much appreciated we'd love to have you in our discord server too link to that in the description below ask any questions there and if you do find my work helpful you can donate a coffee and buy me a coffee link to that is also in the description below thanks so much for watching everyone see you in the next video [Music] you

Channel: jmbiv

Views: 13,793

Keywords: godot, godot engine, godot tutorial, how to make a game in godot, game development, game development tutorial, game development for beginners, godot for beginners, game dev, indie game dev, indie game development, hobby game development, gamedev, godot game engine, jmbiv, godot a*, godot a* pathfinding, godot astar, godot pathfinding, godot pathfinding 3d, godot astar pathfinding, godot 3d, godot 3d tutorial, godot 3.4, godot 3d game tutorial, godot navigation, godot A*

Id: sTVk-Bx2aks

Length: 42min 1sec (2521 seconds)

Published: Sat Feb 19 2022