Godot Top-down Shooter Tutorial - Part 20 (How to Write Your Own A* Pathfinding Algorithm)

hey everyone and welcome to part 20 of the godot top down shooter tutorial my name is joe and this is part one of a three-part series where we're going to implement pathfinding into our game we're going to be writing our own a star implementation and we're going to go through all the things you need to do that in godot in this first one we're just going to write the algorithm the next one will actually implement it into our game and then finally we'll add collision handling so that our units know how to avoid walls and optionally other players there's also going to be a follow-up fourth video on pathfinding where i'm just gonna show you how you can draw what your navigation grid looks like and what paths a unit is currently taking so that you can help debug a little bit better so with that let's get started okay so before we get started let's talk about what godot provides as far as navigation goes so godot actually has its own built-in navigation server that you can use in a navigation 2d node that we could use as you see here in the docs the problem though unfortunately is that the built-in godot navigation does not really handle runtime updating very well like it's really hard besides just baking it and having the navmesh exist when your game starts it's really not optimized for continuing to update and rebake that navigation mesh as your game runs additionally it's really hard to incorporate multiple sources of input so you can build a nav mesh from a tile map per se but if you've got other objects that should take away or block certain parts of your navigation mesh it's not built to take those inputs in so it doesn't really allow for collision avoidance with objects that are not part of the tile map or whatever you're using to create your nav navmaster navigation polygon in the first place so because of that we're not going to use godot's built-in navigation 2d now that being said this is going to get improved a lot in godot 4.0 as you can see here this pr that was done i think is google's summer of code is a big improvement to godot's built-in navigation server and it'll come with a lot of stuff including obstacles collision avoidance etc and runtime baking and continuous updates and you can see some examples here in this pr if you search it of just what that will look like but for now we don't have access to it's in gonna be in the 4.0 update so we're going to have to roll our own that said we do not need to implement a star completely from scratch so i believe under the hood this navigation 2d node that we looked at actually uses an a-star implementation which you can also access on its own so we can use godot's built-in a-star class in this case we'll be using the a-star 2d to kind of build our own navigation and pathfinding handling and so we don't have to implement a star so i'm not going to go through and talk about how you would implement it on your own or what a star is doing under the hood that'll be you know another video or something you can look up on your own but we will go over how we can use this a star 2d class to make our own custom pathfinding logic which is exactly what we're going to do so just wanted to go over that that's kind of the gist of what we're going to do and how we're going to do it we're going to use this built-in a-star 2d class and eventually first in this video we are just going to build the algorithm we're just going to build our handling around a star 2d and implement it into our game i'm not sure how many videos pathfinding is going to be it might be two it might be three um just because there's a lot to cover i'd also like to show you how to build your own like debug rendering so you can see the paths that all your agents are taking and you can see the navigation grid overlaid for debugging purposes it's really helpful but that'll be saved for the end first we're just going to build our algorithm then we're going to work on actually adding obstacles at first just like walls so helping our units avoid walls and then hopefully later on we'll get to actually helping them avoid other units so that's the plan i hope that sounds good and makes sense just as a heads up this is going to be pretty mathy we're going to have to do a lot of math and just a lot of calculations to figure out how how to build up our a star grid and with that being said too this is not the best implementation this is not super performant it's not amazing it's not production ready you definitely would need to do some tweaks on it but for our small game with you know 10 things using it and a small tile map it absolutely works and it's going to introduce you to everything you need to do some of those optimizations or changes on your own as needed so anyway with that enough talk let's get right into it and start thinking about how we're going to build out our algorithm so the way we're going to build our algorithm is actually really similar in some ways to the method described in this article on medium this is actually an article i read when i first got into godot over a year ago and i was trying to figure out how to use godot's built-in pathfinding so it's going to be pretty heavily changed for our use case and with some optimizations that i've made over time but if you want to read this article if you prefer reading and want to kind of do things on your own this is a great article to look at and i'll link that in the description to this video but just as a heads up credit where it's due to joseph frank for making this original tutorial that all those all the time ago help me get started so before we get into actual coding let's just think high level how we want to do this so with an a-star algorithm what you're effectively doing is you're drawing a grid so you're defining a set of vertices in the connections between those vertices and then what happens is that when you generate a path you're generating a path from one vertices to another vertices based on which vertices are connected so if we started right here for example oh wow that is not the thing i wanted but if we started right here for example and wanted to come right here well we'd have to travel along one of these edges here from this vertice of that vertices and so what we're trying to do is build up a grid of vertices and then connect them where appropriate and the way we're going to do that because we already have a grid right we have our tile map if i switch back over to godot here then you'll see that we've already got this grid based system we've got our ground and even though we have walls and ground decorations we really like our ground tile map determines where our game world is and it's already broken up into a grid of squares so we're going to use this as a basis just to make it a little bit easier you can absolutely build up an a-star grid without a tile map but because we already have a grid-based tile map we're just going to use that to make it a little bit simpler so before we start coding let's again just review some of the math and ways that tile maps and grids are stored in godot so that we have some knowledge of this heading in to building our a-star grid so i've got a tile map here this is a three by three tile map and on the left here this diagram represents what that tile map is stored internally and then this diagram on the right represents that same tile map but where each tile is in the world space so in this tile map each tile is 32 by 32 pixels that's the size down here and so internally when we have nine tiles like this a three by three square the first tile is going to be stored at zero zero and then one zero and then two zero so they're all going to be relative coordinates to the tile set itself it's just storing the it's like an indice number but in the world space since they're 32 by 32 these same tiles are actually going to occupy this first one is going to be from x equals 0 to x equals 32 and y equals 0 to y equals 32 so it's going to take up a 32 by 32 square in the world space same with this one instead of being 1 0 and tile coordinates it's going to be 32 it's going to start at that x value of 32 and go down to a y value of 32 and keep going so hopefully that just kind of makes sense again tile sets are stored internally in relative coordinates and then we're going to actually need to translate them into world coordinates over here and our a-star grid is stored the exact same way it's stored in these relative coordinates here so it's going to be really easy to convert from a tile set to our a-star grid because they're stored in the same relative coordinates um but we just need to know that anytime we have to figure out which tile we're standing on we're gonna have to convert from the like world coordinates that our player or enemy unit is on and convert those into the tile set or the tile index or tile indices for that specific tile so hopefully that makes sense i think we're ready to start jumping in and actually coding now okay so like i said we already have a grid that covers up basically our whole game world and its ground and so what you're going to want to make sure you do before we get started is make sure your ground tile set actually has a value in every square in your game even if it's covered up by something else so even though i've got decorations here and here and i've got walls here i need to make sure i still have ground tiles that cover that up because we're going to be building our a-star grid based on the tiles that are ground tile map uses so again just make sure that your ground tile map uses all the tiles in your game that there's a value there even if there's some other tile map that has something drawn on top of it alright so we're going to need a new node in our scene tree um really just a new script but we'll create a new node 2d and i'm going to call this pathfinding so do pathfinding and this node is going to be responsible for basically creating our a star grid so i'm going to attach a script to it i'll just call that pathfinding 2 for now and this script is going to handle creating and updating our a start grid as our game goes on so there's a couple things we're going to need here a few variables so the first one is we're going to need to save var and we'll say a star and this is going to be um and we'll do a star 2d dot new so we're going to create a new instance of the a star 2d class and this is going to be again our container for all of our a star operations it's where we're going to store our grid it's where we're going to tell it to update and get paths from etc so we're going to need an astar instance next we're going to need a tile map and basically we're going to use dependency injection to pass in our ground tile map from our main node here so remember pathfinding and ground are siblings here we don't want them directly talking to each other or like knowing they're there so we can use our main script to pass in our ground tile map through dependency injection so i'll set this to be a tile map we'll just keep it as null for right now and then a couple other things um remember that oops i need to do capital m um remember that all of the things in our game all of our tiles all of our players they're all centered at the top left actually that's not true for units but for our tiles they're centered at the top left so if i place a tile here at 0 0 this it's going to be indexed at 0 0 here the top left corner so whenever we want to get the center of a tile we're actually going to need to um basically add half the width of the tile to its position and so in order to do that we're going we're going to do that calculation one time and we'll just save it so i'll say half cell size and this will be a vector two because it's gonna have an x and a y and then we're gonna say var used rect and what this is gonna be it's gonna be basically the bounds of our ground tile map so we're going to store how big our game world is and we're going to assume that every cell inside of that rectangle is is a tile in our ground tile map and so this is going to be a rect 2 and we need these types specifically because we're going to get them from our tile map so you'll see how we use this in just a second so now i'm going to create a function and this is going to be create navigation map okay and we're going to pass in as part of this a tile map again this is going to be the function that our main script calls at the beginning of the game to generate our navigation map so what we're going to do here is first say self.tilemap equals tilemap so we're going to get our tilemap and store it there and now what we need to do is kind of store some of these variables away get these calculations out of the way so we can use them later so we'll say half cell size equals tile map and on any tile map you can get the cell size just by calling cell size the property and we'll divide it by two and so cell size is a vector so we're just dividing the x and the y coordinates of that vector in half and so now we can just add this half cell size onto the position of any tile to get the center of that tile so now we have that we can say use direct and again this is a function that tile maps provide so we can say get used wrecked and what this is going to return i think if i yeah do that you'll see it returns a rect 2. and it's basically a rectangle that has the extents or the bounds of the entire tile map so we're going to use this to figure out how wide and how tall our grid is going to need to be so now that we have that out of the way we can say var tiles and these are going to be the tiles that are going to actually make up our grid and in order to get those tiles we can just say tilemap that get used cells so this is going to return every single cell in the tile map that is filled in if there are holes in it it will not return that but that's why we need to make sure that our ground tile map takes up all of those cells within our used rectangle to make sure that all these tiles are filled in with something there so again you don't have to use a tile map to build up the grid and in fact you might get better or more accurate results by not doing that we're just going to use it as a baseline because it's easy to do if you didn't want to use a tile map what you could do instead is just generate you know a list of of cells of any variety or any width or height and so you would have you could potentially have a navigation grid that is not the same cell size as your tile map but we'll just do the tile map because it's easier in this case and then we're gonna need two more functions that we're gonna make right now one is gonna be funk um add uh traversable did i spell that right yes tiles and so we're going to say tiles which would be an array we'll do a pass here for now and we'll say funk connect traversable tiles and this will also take in an array again the core id of these two functions are taken from that um that tutorial i showed earlier uh we're going to modify them but the core idea of how this gets built up in that tutorial is still super valid and a good way to do it so fundamentally what we're going to do here is we're going to well let me just type this in first so we'll call add traversable tiles pass in our tiles and then we'll say connect traversable tiles and pass in our tiles so fundamentally what we're going to do here is there's two steps and i'm going to actually go back to our diagram that we had to explain those so when we create our navigation grid and we're using our tile map it's basically going to go through and add a point of vertex in our navigation grid at each tile map so it'll add a vertex right here a whoops a vertex right here and right here and right here but it's not enough to just add those vertices you have to tell the a-star implementation your a-star object how those are actually connected so we need to manually say hey this top left rectangle this vertice is connected to this one we need to tell it to connect it via this edge right here and same for these two and these two we also need to do it vertically and we're also gonna do um we're gonna do it uh oh my gosh the word diagonally thank you um so that we can connect it this way i am using rectangles so i can't really draw a diagonal line but just bear with me so we're going to connect this vertice and this vertice same with this one and this one up here we're also going to do it for this one over here as well so all of these were going to connect uh to their horizontal and vertical neighbors as well as their diagonal neighbors and that's going to give us a grid that has a lot of connections and therefore a lot more ways for our agents that are navigating to reach their destination so now here back in godot now that we've talked and kind of seen that in action this ad function is going to be what we first talked about it's going to go through and add all the vertices to our to our grid and then this connect function is going to actually then go through all those newly added vertices and connect all the vertices that need to be connected and we're going to do these only when we create the map we never have to do them again and so that's going to help this be more efficient because we don't have to continually rebuild our navigation grid we'll have to do some updates to it but it'll the core object will be there and that'll help us cut down on the performance cost of doing navigation like this so the functions that we're actually going to use as part of our a star 2d object to connect points and add them one we're going to use this add point function right here so you just give it a point id in the position and and it adds it to the grid then eventually we're going to need to go through and connect those points here and then you can use this bi-directional to connect it both ways which is what we want to do because if you're at one point and you go to the other point to a point it's connected to you want them to be able to go backwards as well so all points should be connected bidirectionally not just one way there's a bunch of other functions here that are definitely worth checking out and looking at on your own time to get more familiar the let's see where is it get point path this is ultimately the function that once we've constructed our grid we're going to use for our agents that are trying to navigate to get the path from one point to another so we're going to use that and then we're also going to eventually use setpoint disabled to disable all the points that are currently blocked by another unit by a wall etc so those are the main functions we're going to use we're going to use a couple others like get id path i believe or get there's a fair amount of them in here but just as kind of an idea of what points we're getting or what functions here we're going to use this is definitely a good class to become familiar with as you're trying to learn how to implement navigation in your game so one other function that we're going to need to write here now that we are familiar with all that the a star implementation provides is a function that will give us a unique tile id so like i said before under the hood even though godot is storing our navigation grid in a relative an array of relative indices basically it also assigns a unique id to each tile that separates it from all the other or not tile but vertex that separates it from all the other vertices in your grid and you can use this not only to store your grid points in your navigation grid but you can also use it to retrieve those points as well as long as your method of determining determining that tile id is deterministic and it'll always produce the same result so anyway we're going to write a function here and we're going to call it get id for points again this one is also pretty similar to what i think it is actually i don't know if i've changed this from what that tutorial um has it's just a useful way that gives it unique id so there's nothing that we really need to modify but basically we're going to create a x variable and this is going to be point to x minus usedrect.position.x we're going to do the same thing for the y here and what this is doing is it's creating basically a number really like a hash code you can think of based on where this specific point or this vertex is and then it's storing that so it's always unique independent of where it is in the grid or even in your game it could be you know like in a negative quadrant like below or somewhere to the left of 0 0 or it could be positive doesn't matter it will still be a deterministic number that we can use so we'll do x plus y and then multiply that by the used rectangle so remember that's the size of our tile map the x and so this is just a formula that again will produce basically like a hash code that we can use to give each tile a unique id and so we're going to need to do that up here when we actually start adding in our tiles which we'll do right now so if we come up to our add traversable tiles function it's actually going to be pretty simple we're just going to go through each tile in the tiles array that we pass in and we're pretty much just going to get a unique id and then add that point so we'll save our id is going to be gets id for points it will pass in the tile itself because remember these tiles that we have here these used cells is just a list of those relative tile indices so we're going to pass that in and then here we are just going to say a star dot add point simple enough we'll pass in the id and then uh what it requires is that you give it a position in your grid and remember we want our a star grid to line up with our tile map grid in the sense that all the relative indices match up so we are just going to give it um a vector of the ti actually i think we can just do tile right because tile is a vector so that should work we're just going to give it the same x and y relative coordinates that it had in the tile map and now this is going to build up our entire a star grid which is great now what we need to do is actually implement the function that will connect all these points together so we're going to do pretty much the same thing as we did above we're going to go through each tile in our tile set and again remember even though we're doing this twice we're going through all these we're only doing these two operations right when our game starts so not a big performance issue and so we're going to do again similar thing we'll say var id equals get id for point and this time we're not going to be generating a new id to save it we are going to be using it to grab the already existing tile that's there so i'll say tile and then here what we're going to do is a little bit of math to make this easier so remember how i said we needed to connect all the horizontal vertical and diagonal siblings so basically the eight tiles that surround our this tile that we're currently looking at so we need to connect all of those edges all of those lines and in order to do that we're going to use a little bit of a math a math trick to prevent us having to do the same operation over and over so we're going to say for x in range of 3 and then for y in range of 3. and what this is going to do is it's going to generate a set of numbers from 0 1 and 2 in the x direction and in the y direction so we'll get an uh basically a 9 number or a 9 tile grid where we can use these indices to just connect all these points without having to manually write that eight times and so we'll use this double loop here and then we'll say var target and this is going to be tile so we're going to grab the tile we're currently looking at and then add to that a vector 2 of x minus 1 and y minus 1. and the reason we're doing that is because remember using range here we're gonna go from zero one and two but the indices we really want are relative to the current tile we're looking at so we want the indices negative one zero and one in both directions okay so now that we are getting the coordinates of all like eight of our neighboring tiles we need to actually get the id of the current one we're looking at so we're going to say oops let me do a var target whoops target id and this is going to be again using our get id for point function and we're just going to pass in target and so we're going to get the id and then what we need to do is check to make sure that one and this is the thing because we are going to be going through the point zero zero here we're going to be looking at this specific tile that we're already looking at and so what we can do is just say if tile equals target so if our target is the tile we're currently looking at or not a star dot has point so we also want to make sure that we are only connecting edges where there's an actual point which might not be the case here in certain situations so just to be safe we'll do that and we'll just say continue so if either of those are the case move on to the next target tile and then now that we have these we know we can connect them so we can say a star.connect points and we're going to give it the id of our tar or our regular tile or the current tile our center tile and then the current target tile and this last um parameter here bi-directional remember we talked about that we do want it to be true because we want the connection to go both ways so now we should have not only a tile map or a sorry a navigation map a grid but all the points should be connected so now what we need to do is actually call this function when our game starts so i'm going to go back to our main script and i'm going to add two on ready variables one is going to be for our ground because we need to pass in our ground tile map and the other is going to be for our pathfinding so pathfinding and we'll do this and then so when our game starts probably line 25 that i just added here i'm just going to say pathfinding dot create navigation map and we're going to pass in our ground so we are creating a navigation map now we are we are turning our tile map into a grid of points that can or cannot be navigated based on parameters we give it now we just need to tell the rest of the game you know our units to use that navigation map and so we can do that right now and actually make it so our ai units use this navigation map to get around now the tricky thing about that remember is that our unit our ai units are going to live as children of our ally and enemy map ai and those are a couple layers down and we need to get them our pathfinding somehow so again we're going to use some nested dependency injection to get those there so what i'm going to do is come over to our map ai which is the script for our map ai over here and then add to our initialize function here a pathfinding parameter and i'm also going to come into our pathfinding script and add a class name just so that we can get good auto completion for the what we're using here so now we can say that our pathfinding node is of type pathfinding and what we're going to do then is actually pass that into our children so what we can do is just save i'll save our path finding here which will be of type pathfinding and then once we've initialized this what we can do is whenever we spawn a unit down here we can set units instance so these are going to be all of our units we can say unit instance.pathfinding pathfinding pathfinding to be pathfinding so it's a little convoluted the nested dependency injection there just passing it down but it's a lot better than trying to like go up the tree and grab it from each of our units it's a little bit cleaner than that and our unit doesn't have to rely on a beam there and so now if i come into our actor script or excuse me actually let's uh let's actually add this we're already accessing our ai from here so let's actually add this to our ai for our unit instance and then what i can do is come into our ai script here and then we'll have another variable here which i'll just call pathfinding again this will be a pathfinding of type pathfinding and this is going to be where we're actually using this pathfinding node in our units to get a new path okay so now we've added uh our pathfinding node to our ai our unit ai but we don't we haven't actually made a function on our path finding node itself that will generate a new path for that specific unit or for that from a certain starting position to another so if i come back to our pathfinding script we're going to add that function right now and this will probably be the last thing we do in this video and then in the next one we'll handle actually wiring it up and we will handle actually looking at walls and starting to do some collision avoidance so we're going to say function and we'll just say get new path and so we need a start location and an end location so this will be a vector 2 and it will be an n or start vector 2 and end vector 2. and these are going to be world coordinates so i'm just going to add a note here start and end are both in world coordinates so we're going to be converting from world coordinates to our tile map or our grid coordinates our navigation grid because again they're the same relative coordinates and then back so the first thing we need to do is get uh our we'll save our start tile and we're going to get the uh tile coordinates for our start and end position so we need to find for these world positions which tile are they in like which um just like which square are they in and this is why it's important to make sure our ground tile cover or our ground tile map covers our whole map so that we don't get errors here and you could you should definitely do some error checking here to make sure that we're actually in our tile map but we'll we'll ignore that now and assume that we are always going to be in our tile map because our ground tile map should cover our entire game world so we'll say start tile this is going to be tile map again referencing our ground tile map and we're going to say is it's world to map right so this is a function built into a tile map where you give it world coordinates and it returns a vector 2 of the tile coordinates so 3232 would return 1 1 in our tile map coordinates using our example we had earlier so we will say start here and pretty much the same thing here and tile equals tile map world to map and we'll say end so now we're going to have our tile coordinates now that we have those remember this is just our ground tile map we need to actually get these uh these vertices in our navigation grid so we're going to say var start id and this is going to be um oh my gosh why can't i oh yeah so get point for man that blanken today so get id for points and then we're going to say start tile same thing for our end tile so end id equals get id for point and tile okay so now that we have both the tile ids for both of our tiles what we're going to need to do now is make sure that we can actually navigate between these two points so we need to check that these are both valid points so if not a star dot whoops hey start dot has point um i need to indent that so it has to have star id so make sure that a point with that unique id is in it or not a star that has points i did it again a start oh my good good galley all right and this is going to be end id so if either of those are not there we just need to return and we'll return null here because there's no path so then what we can do actually we might want to just return an empty array let's do null for now and then if you get an error you might have to change that to be an array depending on what happens but okay so if we get here we can assume that we can navigate between these two points so we're going to call we're going to say our path map so this is our path relative to our tile map and this is going to be a star dot get point path and then we're going to say start so you'll notice that get point path here takes a from and a to id so we'll say start id to end id and this path map what this get point path function is going to return is going to be an array of all the points relative points again in our tile coordinates from start to end and so now we need to go through this array of points and convert it to world coordinates so that we can actually tell our units to move to those world coordinates so that we're not dealing in tile coordinates anymore so the way we're going to do that is say um var path world so instead of path relative to our tile map we'll say path world this is going to be just an empty array here and we're going to say four points in path map so for each tile coordinate in our path map we're going to say point world is equal to tile map and similar to how our tile map has a world to map it's also got a map to world so we'll do tilemap.map to world and then our map position is just going to be point and we also are going to need to add half cell size so remember this map to world is going to give us the top left corner of our of our square or our grid that area in world coordinates but we want the middle of it so that we're not moving always to the edge of something so we're going to add this half cell size to get the middle of that connection rather than the vertices itself the top left corner and so once we have this we're going to say pathworld.append so then we're going to add this onto our array we'll add point world and then once we've gone through and built up all those we can return pathworld and actually i am going to make this return an array and then this is just going to return an empty array here because there's no valid points so what we've done here just to recap because again i know lots of kind of confusing we're going from world coordinates to tile coordinates to tile ids then back tile coordinates then back to world coordinates there's a lot of stuff going on um again if you really need to if you need to watch this video over again or just mess around with it on your own do whatever you got to do because this is definitely complex so if you're lost it's not just you this is tough stuff especially if you haven't done it before but we're getting we're converting from our world coordinates to our tile coordinates and then we're getting the specific unique ids in our navigation grid making sure that there's a valid path between those two tiles and then we're getting the path the top the tile coordinates the points between those two tiles and then we need to go through again and convert them back to world coordinates so that our units can actually use them to navigate so i think we're going to call it for this video because it's getting kind of long and we've done plenty of stuff next video we'll actually implement this into our unit ai so that they use this path to move and hopefully we'll kind of get into adding collisions and updating our what our grid looks like so that points are disabled when they are blocked by walls or other units so i hope you've enjoyed this video hope you've been able to follow along please feel free to ask any questions in the comments or hop into our discord server is a great place to get some help um if this has been a helpful video to you i'd really appreciate it if you would like or subscribe to the channel that always helps just to gauge interest and helps the channel grow but thanks so much guys i'll see you in the next video you

Channel: jmbiv

Views: 4,387

Keywords: godot, godot engine, godot 3.2, godot tutorial, godot top-down, godot 2d, top-down shooter, how to make a game in godot, game development, game development tutorial, game development for beginners, godot for beginners, how to make a top down game in godot, how to make a top down shooting game in godot, game dev, indie game dev, indie game development, how to make video games, how to godot, hobby game development, gamedev, godot game engine

Id: Z6QopKiRNLE

Length: 37min 17sec (2237 seconds)

Published: Sun Aug 09 2020

Reddit Comments

[u/[deleted]]

Your content is amazing!

[u/mac-gamer]

Looking forward to the next installment!