Gamedev In-depth: Pathfinding Part 1

Key Takeaways

hi welcome back to another in-depth game development video series in this next set of videos we're going to be talking about path finding in this first part we're going to explore what path finding is and define some of the concepts we'll need to know to implement them and in subsequent videos we will explore some different path finding algorithms and how you can implement them in your games first let's talk about what we mean by path finding so I have a simple PI game program here that just draws a grid that's gonna represent our game screen and the map that we're gonna be moving around on before we start writing any code we need to talk a little bit about how we're gonna represent the data for our map and path finding algorithms work on something called a graph and a graph looks like this this is a graph is a mathematical construct where you have nodes that's what these circles are and the nodes have connections between them and if you notice these connections have arrows on them which means they are directional from a you can travel to B but from B you can't travel back to a and path finding algorithms work by traversing the connections in the graph and finding the path from your desired starting point to your desired ending point for example if I am starting on E and I want to travel to a then the path is going to be to move to D and to be and to see them to a and so a path finding algorithm the inputs would be the start and the end and it would tell you the list of the connections that you have to travel to get there and so in most 2d games we're representing our map as a grid of squares and so your graph could be a grid that looks like this or each tile on the grid here's a node and the connections are all of the edges all the each node is connected to its adjacent neighbors and this is fine this works fine from here you can travel along this path to whatever other node your destination is and for example if you wanted to have some walls then your graph would look like this right and so the path would have to go around the walls if you wanted to get from one side to the other however something that you need to take into account is that graph algorithms are faster when there are fewer nodes so the more nodes you have the longer it's going to take to calculate all the different paths and find the shortest one so for example let's look at this map so here's a map of tiles this map is 640 tiles 32 by 20 so the if we were using a square grid the path finding algorithm would have to look at each one of these tiles and find and all the connections between them to get from any point to any other point but we could make this a lot more efficient if we thought about the fact that if you're starting in this room over here and you're heading for this target the difference between this tile and this tile the path is going to be almost the same so you might want to represent your path finding graph like this just using nodes where there are doors or in the middle of the room right and then now we only have 22 nodes in our graph instead of 640 so this is gonna be a lot faster to calculate and so if your mob was say over here in this room and your target is over here then you would just say travel towards the nearest node and then follow the path on the grid I mean sorry on the graph and towards the closest node to the target and then your your mob would find from wherever it is what the closest are what the shortest path is towards that target and then it would be close enough to go straight towards it and we'll talk about that a little bit later once we have our algorithm set up and we're starting to do some path finding but to start with just to keep things simple we're gonna stick to the square grid representation so that our graph our path finding graph is going to match our map grid we will talk a little bit later once we have it working about how we can do this kind of optimization okay it's a little bit more abstract so we're gonna stick to this representation where our map is gonna be a grid our walls are gonna be blank grids that you can't travel in and our path finding algorithm will just look at all the tiles individually okay so our task will be to represent this data in our code so our grid is going to be a bunch of squares right and they will just be labeled by their grid position and any tile that's a wall just shouldn't be in the grid at all all right if there is no two comma one then there's no way to connect to it so so we'll just keep a list of the walls and those will be the ones that we ignore every other tile we look at and any tile that we have we just need to be able to calculate what its neighbors are right which in if it's in the middle is gonna be all four but if we're on an edge or in a corner linear a wall we need to make sure that we only connect to the adjacent ones so we'll need to be able to calculate for any given tile what are its neighbors okay so we're going to do that by using by setting up a new object or a new class so we're gonna call this a square grid and it's starting parameters are just going to be we're gonna tell it what width and height we want and we'll store those as properties so that we can access them anytime we want and then the walls are just going to be a list it'll be a list of what tiles have walls in them okay I'm also going to make a list here of what connections are allowed and what I mean by that are which directions from from any given tile which directions can you travel in okay and in the grid that we drew obviously you can move up down left and right and so since our nodes are going to be our handy PI game vectors we're going to make a list of all the directions that you can travel in you can travel to the right you can travel to the left you can travel up I'm sorry down would be positive one or you can travel up those are the four directions now if you were to be on a grid where you allowed diagonal travel you could add those as well right you could add one one and say you could travel down into the right and so forth but we're not going to do that we're only allowing up down left and right and that'll help us calculate what neighbors a given cell has and that's what we need to do next is we need to calculate you define the neighbors of any given node right so if we pass a node what are the neighbors of that node well the neighbors start with the neighbors are going to be taking this node and adding each of these vectors to it all right and we'll get four neighbors so we want to take the node plus connection for for each connection in that list of connections we're going to add it to note and then we're going to have a list of vectors at the end of this that has those in it and that's fine except for the case where you know one or more of these isn't legal because we were on an edge or we were next to a wall so we need to take these four vectors that we have and we need to filter them out and we need to filter out the ones that are in the walls or outside of the bounds and the easiest way to do that in Python is using the filter function so there's a function called filter in Python takes two arguments okay the second argument is what sequence you're filtering right we're gonna filter the neighbors list and the first argument is what function you want to apply to that to filter it out and this function will be a function that can return true or false right so it looks at the list apply some criteria that can result in true or false and then what you get back out of the filter list or the out of the filter function is which ones were true right so we have a couple of things we want to check first we need to just check if that note that we're adding here is in bounce right is is it a inbounds move so let's define a function called in bounce just to check if a node is in the bounds of the grid and what that means is you know if we have a grid that's 10 10 tiles wide then the legal values for X are from 0 to 9 right and for y it's between 0 and height minus 1 all right so so we just need to check if that is the case and we can do that by just saying my cursor is if we just want the X to be between 0 less than or equal to 0 and [Music] less than with but not equal to all right and also the same is true with left all right if both of those things are true then the tile is in bounce that note is in bounds so we'll use that in bounce and we'll just assign that back to neighbors okay so now our neighbors list instead of having the for all for in it will have just the ones that were in bounce okay now we need to do the same thing again to filter out if it's a possible tile meaning there's no ball there all right so let's define possible and this just means tell us if it is not in all right as long as the note is not in the walls and we're good I just noticed I just put X but I need that's supposed to be no dot X and no dot Y ok so now we should have a list let's let's print it out just to test and be sure it's true what we really want to do is return it right but let's print it out so we can see if our make sure our filters are working right and we're finding the neighbors so we can test that out I've actually already gone down here and I've said I've created a square grid that's five by four and I've added two walls and that's actually so that it will match exactly what we have what we had here in our little example all right I have walls at 2 comma 1 and 2 comma 2 so I've created that grid that's 5 by 4 and add those two walls and now let's find the neighbors of 0 0 and the neighbors of 3 2 and hopefully we'll get the right answers let's see what happens ok oh so you see when we print we're printing out and it's printing a filter object ok what that means is when you run the filter command or when you're in the filter function what it returns is a filter object which is which is an iterable I'm just something you can loop over and do things with but you can't just print it out directly so we need to print out that as a list okay so that's our problem there all right there we go so the neighbors of 0 0 R 1 0 and 0 1 so you can see it filtered out negative 1 0 and 0 negative 1 and then the neighbors of 3 2 are everything but 2 - I actually didn't include 2 2 because 2 2 was in the list of walls ok so our neighbor function is our fine neighbors function is working so let's just not write that out ok then the last thing I'm going to add to the square grid here so that we'll be able to see it is it's just a draw method I'm just going to draw the walls where they're supposed to be so we're just going to go through the walls and figure out where their rectangles are supposed to be it's going to be a rectangle at node I'm sorry at wall times tile signs right that's going to give us the location because wall is a vector so that's gonna give us the X and the y and then the width and height are just also tile size by not size and then we just PG draw rect screen and that light gray color that rectangle so that way we'll be able to draw them we can test that out just by doing g-got draw and we should get a couple of walls at tu1 and tu2 okay so let's get rid of this test grid and what we're going to do is we're gonna make it the size that we specified up top grid width by grid height so that's gonna be how big our Gradius and we need to be able to add and remove walls and it's the easiest way to do that is going to be to be able to click on the screen and draw walls and remove them so we want to detect mouse clicks so in our event loop here we're going to say if event if it's a mouse button down so it's a mouse button down event then we need to get the mouse position right and that's going to tell us what screen coordinates are click was at but let's make that a let's make that a vector since we are gonna be working with vectors the other ones now we have the x and y of on the screen of where the person clicked right but we want the tile coordinates so we need to divide by tile size and then we'll get the integer values right because we're doing integer division and so now we can say if you vet button I'm sorry equals one so if we could done if we click the left mouse button then whatever tile we clicked on we want to if there's no wall there we want to add a wall there but there is a wall there we want to delete the wall there so we want to just basically toggle walls so if it's in the walls list and we want to remove it right otherwise we want to add it okay and we're drawing them so we should be able to click and add walls now okay and so you can go along and add however you like okay alright and we are done we have everything we need to create our graph to add and remove walls so that we can test the pathfinding and see how the paths change as we add and remove walls and in the next video we'll start building our path finding algorithms we'll start with simple ones and then we'll improve them as we go and thanks for watching and I'll see you in the next video you