Easy pathfinding in python [almost without math]

hello there in this tutorial we are going to create this basic pathfinding project where we can move around a roomba in a room and well the roomba always finds the shortest path between the two points it's ultimately a fairly simple project that is quite useful for basically any kind of game now pathfinding does involve quite a bit of math and it can get fairly complicated however you don't actually have to do it yourself because python has a module dedicated entirely to path binding so we are going to use that and essentially we are going to create two projects the first one will introduce the pathfinding module itself and this one will be fairly short because it's a pretty simple module and for the second part we will use the pathfinding module to create an actual useful project now before we get into the code i think it is going to be useful to cover some basic pathfinding theory and don't worry it's going to be short whenever we talk about pathfinding we basically talk about two things number one we have a grid of points and some of these points can be walked over and some cannot for example a grid could look like this where a one is a movable field and the zero is a wall and inside of this grid we also define a start and the target cell and between those two points we are trying to find the shortest path now finding that shortest path is the second part and this is also the actually difficult part because finding this shortest path requires quite a bit of math as a matter of fact there are quite a few different mathematical approaches to figure this path out the most famous mathematical model to achieve this is called a star but there are quite a few more and if you want to get into the math it can really get quite complex but with that we can get started with the pathfinding module and first of all we have to install it and this is going to happen in the usual way so either in the terminal or on the powershell type pip install pathfinding and you should be good to go and with that we can create a really simple pathfinding project and just for reference i have taken this project from the official tutorial of the module i'll put a link to it in the description and here i have a completely empty sheet of code and first of all i have to import a couple of things so let's start by import path find ding and if i run the code now i can see finished and we are not getting an error message so i know that this module here is installed and everything is good if you get an error message here something did go wrong so do check that however for this module we don't actually want to import everything so let's change this a tiny bit for now from pathfinding i want to import a very specific thing and what i want to import is pathfinding dot core dot grid and from this i want to import the class called grid and do make sure here that the first letter has to be capitalized that is quite important and this class is going to be well creating our grid so let's use this right away and for this grid we actually need some kind of map and in my case i have created one already that i called a matrix it looks like this now every time we have a one in this field we can move over the cell but we cannot move over a zero and later on we are going to have a much more complex map for now this is just for illustration and now that we have that we have to actually create a grid and let me actually create a comment here to illustrate this so create a grid and this grid is going to be stored in a variable that i'm going to call grid and for this we are going to use the grid class so the one we have literally just imported this one here and this grid is going to need one named argument and this is called the matrix parameter and in our case we already have a matrix i just called it matrix so literally all we're doing is we're importing this one here as a named argument for the parameter that is also called matrix now that we have that we have to define a start and an end cell so number two create is start and end cell and this also is going to be stored in a variable so i want a start cell and i want an end cell and in here we have to make a choice because essentially we have to pick one of these cells and well define a start point and we can literally pick any cell that we can walk on so we couldn't pick this one here but we could pick literally any other cell and how you create this is we first have to get our grid again so the one we have just created and on this we have to create a node and in this node we have to define an x and a y cell and in my case let's just go with 0 and 0. so right now this 0 and 0 here would be the top left cell in our grid and then for the n cell let's do the same thing except now i want to get a different cell let's say in my case i want five and two and i guess just to be clear here this five is going to be 0 1 2 3 4 and 5. so we are on this column here and then this 2 is going to be 0 1 and two so we're essentially targeting the bottom right cell and that is literally all we need for now now that we have that we can go to the next step that's going to be number three and this is going to be to create a finder with a movement style now a finder basically is the mathematical model that gets us from here all the way to here and this is another thing we have to import so all the way at the top from pathfinding dot finder dot in my case a star i want to import the a star binder and for this class here be really careful with the naming and the capital letters it can be quite finicky but this finder is going to use the specific mathematical model that is called a star so this is one kind of math to get us from point a to point b and there are quite a few more if you check the documentation you can find all the relevant ones and now that we have that we can create what is called a finder and this one also has to be stored in a variable and this is then going to be an instance of the class and that is all we needed we are almost there next up let's call this number four we have to use the finder to find the path all we have to do is getting our finder and then calling the method find underscore path and in here we have to pass in three different arguments the start cell the end cell and the grid so that is all information we already have defined early on it really isn't all that bad once you get the hang of it so i hope that makes sense and now this method here is going to return two things and let's stop both in the variable first of all it's going to return the path and second up is going to return what is called the runs and runs basically means how many cycles or how many cells we have to go through to get to the end of the path can be sometimes useful but in most cases you don't really need it and well with that we have our path so what we can do now is to print the result so let's print our path and if we run the code now we can see a couple of two builds and let's actually go through and see what happens here in our grid we start in cell zero and zero that is this point here then we go one further to the right so we get to this point here that is this one covered then we go to two and zero so that's this one then we go to three and zero that's this one then we go to four and zero this one then five and zero that's this one and then we go downwards so five and one and then five and two and that's the last two cells and that is well the shortest path we could possibly take or i guess at least one of the shortest paths there are couple possible shortest ones in here so let me minimize this again and i guess just for completion what we could also print is runs and this would get us 17. so this finder ran through this matrix 17 times to find this path here it's well not the most relevant information it really doesn't concern us too much although it does tell you one relevant thing and that is that pathfinding is really hardware intensive so what you want to be aware of is that you should be using pathfinding as little as possible because if you use it too much it is going to tank the performance of your game quite substantially so keep that in mind i will talk about it more in the actual project with that we have some very basic pathfinding now there's one more thing that we could be adding because right now we don't have diagonal movement so all we can do in this a-star finder is move right left up and down which in the game sometimes isn't particularly realistic because you might also be able to move to the top right or bottom left and so on so how could we add these different directions and well adding this is kind of cumbersome although not too difficult it is mostly a writing thing essentially in this asta finder class we have to add one argument and that is called diagonal underscore movement now the problem is the argument we have to pass into here has to be another class that we also have to import from the pathfinding module it is called from pathfinding dot core dot diagonal movement from this we want to import diagonal movement and now what we want to do we can pass in this class in here so diagonal movement and then dot all ways so we always want to allow diagonal movement and well that is now all we needed although this part here i do find a little bit cumbersome but it's not too bad i suppose but now i've run all of this again we are getting a slightly different path so we start with zero and zero one and zero two and zero three and zero but now we go to four and one and five and two so this is essentially our path and i guess this one is slightly faster than the one we had before and well now we have diagonal movement it wasn't actually all that bad so that's a pretty good sign and well with that we have our basic project so now all you have to do is to implement all of this in some kind of project wherever you want to have it in my case it's going to be pie game but it could literally be anything else so i guess with that let's start talking about the actual project that is going to look much more interesting now for this project i try to make it as simple as possible so we can focus on the pathfinding part and this is most notable in how the level is set up or the room you can see right now essentially this entire room is just one picture and this picture is composed of individual tiles with each tile being 32 by 32 pixels wide and high and then for the grid i essentially played around and placed zero wherever we have a tile with a wall and one wherever we have a tile with a floor but by themselves the grid and the background art are completely separate they just happen to look the same now this makes the project quite inflexible although in a real project you could set this up significantly better if you want to understand how to set something like this up check out my tileset video it explains all of this in much more detail but in this case i try to keep this project as simple as possible but all the other parts are perfectly functional path finding so you could use them in essentially any kind of game now one more thing before we get into the actual code and that is our folder setup right now i have one folder with the code and all of the artwork which essentially means i have one python file then the background image then a roomba image and then one more image for the selection box thing i'm not really sure how to call it but with that we have all we need so let's jump straight into our actual project and it is going to look like this i already have a very basic setup so essentially what i have in here is a basic input of pygame then the basic pie game setup then our game loop and i'm simply drawing and updating all the stuff that we have if you have no idea what any of this means check out my introduction to pygame it is going to go over all of this in a great amount of detail and well besides that i have also already imported all the stuff we need for the path finding so this is the stuff you have just seen a couple of minutes ago so all right with that we can add a couple of things towards this and let me add another section here let's call it the game setup and then here we need two things first of all we need the background and i call this bg underscore surface and literally all we need for this one is pygame dot image dot load and i call this one map.png and as always don't forget to convert this thing so our game runs a little bit better and now all we have to do in our game loop i want to get my screen and bleed this background image so bg underscore serve and the top left should be in position 0 and 0. so if i run all of this we can see our basic background image and this is literally just an image nothing fancy whatsoever so all right let's close this and with that we can start creating our grid for the pathfinding and for this grid again we are going to need a matrix this one is going to look quite a bit larger in fact it looks like this and well this thing is a little bit larger but if you look at this a tiny bit more closely for example here you can see the wall for the bathroom on the left side and here you can see the wall on the right side of the bathroom or if you look on top here you can see the kitchen table area that we can't move through here you can see one wall of the kitchen and i guess if you actually draw it out it does become a bit easier to see so here we have a pillar here we have another pillar and here we have another wall so this is essentially how the entire project is going to work i have a background art and on top of the background art i have an actual pathfinding grid and those two happen to have the same coordinates but that's the only connection they have i could totally change any of these points to get a different kind of pathfinding setup so i hope that makes sense but also this thing is getting quite wieldy so let me minimize it and then we don't have to worry about it and now with that we can actually start creating our basic pathfinding and i'm going to organize this in two classes and let's start with the first one that i have called path finder there's no inheritance but we are going to need an init method and for the unit method we need dunder init as always we need self and for this one i want to have a matrix and then inside of this let me add a comment for the basic setup and in here first of all i want to have myself dot matrix and just store the matrix by itself and that in a second is going to be just this matrix here that we are going to pass in there it is not going to be a grid yet so we are not creating the grid class and you're going to see in a second why this information is useful by itself it's essentially there to place the mouse cursor but don't worry too much about it for now now besides that i do also want to create the actual grid so self.grid is going to be the grid class and in here matrix is going to be the matrix now on top of that i also want to import another image for this class and let's call this one select surface and for this one all i want is pygame.image.load and this one is called selection.png and for this one we need convert alpha because it has some alpha values and this is literally just the selection image we need to display where the mouse cursor is and let's actually start by creating an instance of this class right in our game setup so in here i'm going to create a path finder and this is just pathfinder and the one argument we are going to pass in here is the matrix so this matrix up here that we just pass in there and nothing else so when we are going to run this code um everything runs but we can't see anything from the pathfinder yet because we are not using this class in any meaningful way but this is going to change now because i'm going to give this class an update method that needs self and nothing else and the first thing i want to do in here is to display where the mouse is so the player actually knows what cell is going to be selected and this let's call it self dot draw active cell so we have to create this method now so draw active cell we need self as usual but nothing else and now in here we have a problem that right now we have a mouse position so we can tell the x and the y coordinates of our mouse but this is not the information that we are going to need because the information we do want is the index for the row and for the column in which of these cells our mouse is going to be so for example if we are in the cell all the way up here i want to have the coordinates 0 and zero or if we are in the one right next to it this one should be zero and one so row zero and column one and this information we would have to get from a mouse position that could for example be 10 and 35 and i guess a better way to illustrate this let me actually do this straight in the game that might make more sense so for now i have my mouse position and i get my mouseposition with pygame.mouse.get underscore position and let's just print our mouse position and don't forget to actually call this update method in our game loop so path finder dot draw active cell for now and if i run this so now in the game you can see my mouse and if i move around you can see the position of the mouse cursor in our game and if i move all the way to the top left you can see at some point 0 and 0 if i hit exactly the right pixel there we go now this position is useful but i do have to convert it because this top cell right now is going to be 0 and 0. but my mouse position is going to be something like 16 and 19 for example you can see it in the bottom left and this number i would have to convert to 0 and 0 because this is going to be one cell and then if a mouse is one field to the right it's going to be right now 50 and 14 this would need to be 1 and 0. so we are in column 1 and row 0. and this has to be applicable to the entire field so we convert our mouse position to a position inside of a coordinate system specifically one field inside of this coordinate system and this fortunately isn't all that difficult so really all we have to do is we need to get a row and a column and this could be a really interesting exercise so try to figure this problem out yourself that you want to convert your mouse position with x and y that could be any number into a coordinate system with a tile size of 32 and 32 so that for example 16 and 16 for x and y becomes 0 and 0 for the row and the column but something like 50 and 10 is going to be 1 and 0 for the row in the column and this really is the sort of thing that is really easy to overthink but solution is actually surprisingly easy so essentially this most position here is going to return an x and a y so for now i just want to get the row which is going to be 1 or our y position and what i want to do is to get the floor division and divide it by 32 with 32 being our tile size and let's actually do an example let's say for our mouse position we have the position 50 and then we're going to apply the floor division and divide this by 32. now if we were to just divide this by 32 we would get something like 1.56 but since we are doing a floor division all our result is going to be is a 1. so all of this information is going to disappear and we are left with a one and then this one is actually all we are going to need so this is going to be our row then and if we use a different number let's say if we used 16 and applied and at the floor division by 32 again this would get us to 0.5 but again since we're doing a floor division anything after the period is going to disappear so this 0.5 is going to disappear and we are left with a zero so we know that at the position 16 we are going to be on the row of zero so this is going to give us exactly the right coordinate point that we are going to need but now we can just copy all of this and apply the same thing to the column except now we need the x and not the y position and with that we have our row and our column so now we can use that information to create a rectangle with an x and a y position this is going to be pygame dot rect and in here we are going to need one tuple with the left and the top and then another tuple with the width and the height and the width and the height are both going to be very simple because they're both 32 now the left and the top are slightly more complex well not that much to be honest so for the left i want to get my column and multiply this by 32 and then for my top i want to get my row and multiply this by 32 and that way we are turning our coordinate system into a specific position on our map except this one is now going to be always in a specific position so it looks like we're following a grid and now what we can do we can get our screen surface and blit and we have our self dot select surface and we have our rectangle and now let's try to run all of this and now we have our selection thing so this green rectangle here is whatever cell we have selected and this right now is following the grid really nicely but there's one downside right now that this green cell is even displayed over a wall or one of these tiles that we are not supposed to move over and this i want to change i only want to run this code here if this information is on top of a cell that we can move over and i guess this could also be a pretty good exercise so try to figure out how to change all of this here to only display this code if we are in our matrix over a one the first thing we are going to need is the information in the matrix what cell we are on so if we are on a one or on a 0. and for that i'm going to create another variable that i call current cell value and this information we can get from the matrix we already have in our class and well literally all we need is self.matrix and in here we first need the index of the row and inside of that we need the index of the column so if i open the matrix again the row here is literally going to select by indexing which of these rows or well lists we are going to look at and then the column is going to look inside of each of those and see which number we're going to pick inside of this list so quite simple actually and well now all we have to do is if our current cell value is equal to one [Music] then we want to run those two lines and if that is not the case well we don't want to do anything and now if i run all of this i still can see my green rectangle but now if i go over wall it disappears and if i go again on the floor now it reappears so this way we have a selection box thing so the player can tell where we are supposed to move so this part wasn't actually so bad cool so now i can minimize this method here and not worry about it again and now with that we can actually start talking about the pathfinding itself and this is going to involve a couple more steps but in the most basic sense here's what we are going to do in our pathfinder class we are going to add some functionality with the pathfinding module to find the start position and an end position and then we are going to have one attribute where we are going to store that information now on top of that we are going to create a whole other class called roomba and this room bar essentially is going to look at the pathfinder class and see if there's any path information and as soon as there's a path information it is going to follow that path now how that pathfinding is going to work specifically we are going to look at in a second let's do this step by step so for now let's work the pathfinding into this actual project and then we can work on the actual movement of the character or well the roomba so here we are back in the code and the first thing i want to do is in our init method i want to add another section for the path finding and in here i'm going to create another attribute that is just going to be path and this is going to be an empty list and now inside of this class i'm going to define another method that i'm going to call create path and this needs self and nothing else and in here we need to get three major things we first need start cell then we are going to need an n cell and then we need to get our path from all of this and i guess let's go for them one by one now first of all i want to get a start x and a start y cell and in a bit once we have our roomba we are going to give the roomba a method to do all of this but for now i'm just going to go with one and one so the top left of our movable cells but later on this one is going to become much more flexible and once we have that i want to get my actual start node so this is going to be self dot grid dot node and in here i want to pass in my start x and my start y so this is the exact same thing we have done earlier to get the start position and now for the end position we want to find our mouse position again and to achieve that i can just copy these lines of code again and minimize this part and now we have the cell we are currently selecting with our mouse and i guess for consistency let's call this and underscore y and and underscore x and let's move them after each other and this way it's going to be a little bit clearer to read although one part annoys me a little bit right now that i just want to move them around so that end x comes first and end y comes second and all right with that we have an end x and an end y so now we have that we can create a proper endnote so self dot grid dot node again and this time again and x and and y and now we have start and we have an end so now with that we can create the actual path and this part i would really recommend for you to try yourself so open the previous project again and try to implement this kind of thing yourself that you create a finder and from this finder you create a path that you are just going to print for now all right so first of all we have to create a finder and this finder is going to be an a star finder and in here i want to get my diagonal movement to be a diagonal movement dot always so this way our roomba can move in the diagonal direction now once we have that information i want to run finder dot find underscore path and in here i have my start i have my end and i have my grid and grid is self dot grid and all of this is essentially what we have done in the first simplified project except now we are actually using it in a real project now this finder here is going to return the path and the runs and in my case i only really care about the path and i want to set this path as self dot path and then for the runs i'm just going to use an underscore to indicate that i don't really care what happens to this information but essentially whatever is going to be returned by this method here is going to be stored in this self.path and now what we can do is print our self dot path except now we kind of have a problem because we have a method but we don't really know when to run it and there's a massive thing you absolutely have to avoid because technically you could run self.create path in here and if we were to do that we would get a new path on every frame of our game and right now we have 60 frames in our game the problem is this kind of pathfinding is really hardware intensive so if we actually tried this our frame rate would drop down really really hard basically no computer can run pathfinding this often so instead let's not do that and a much better idea is that every time we click a mouse button we are going to run this method and to do that we are going to look at this for loop here and really what i want to do is if the event dot type is equal to pygame dot mouse button down then i want to get my path finder and run my create path so this way we are only going to create a path whenever the player clicks a button which is much more reasonable and much more efficient and i guess with that we are not going to use this for loop anymore so i can minimize it and now in this code let's try it and if i click anywhere we are getting a path so we know the pathfinding is working just fine the problem now if i click again we just get well an empty list essentially once we are running all of this our start node is going to be in the same position as our endnote so by default pathfinding doesn't really care what we define in here once we have run this line we always set the end and the start position and this way we can run this path finding once however if we try to run it a second time it's going to return an empty list because our start node and our endnote are in the same position so that's not helpful but fortunately we can change that behavior all we have to do is self dot grid dot clean up and that way all of this is going to be reset at the end of the path and once we have that we're going to recalculate this position and this position here so now let me print self.path again and now let's run all of this so now if i click right next to our start position we go from 1 1 to 1 and then 3 2. so this is our path right now but if i click all the way down here we are getting a very very long path but well we always get a new path no matter where we click so this is working really well however i guess just printing the path looks kind of boring so let's draw the entire thing and for this i'm going to create another method that i'm going to call draw path it needs self add nothing else and now in here i first want to check if self.path has anything in there so if self.path is empty this if statement is not going to run but if it is going to run i want to create another list with points and essentially what we have to do is call pygame.draw.lines and in here we have to pass in a couple of arguments first of all we need to display surface then we need a color and in my case the color i have chosen as the code of this although you could literally choose whatever color you want in here it well doesn't really matter now next up we want to tell if all of the lines we are drawing are going to be closed or open so this is a boolean statement in my case i want this to be open so we don't connect the first and the last point now next up we are going to need points so all the points we are going to create in just a second and then finally we are going to need a line width which in my case is 5 but well choose whatever number you want it really doesn't matter and all that this method here is going to do it is going to draw a couple of lines between all the points we are going to pass in here and these points have to be in here and now we kind of have a problem again because all the points in the path so this path here are going to be something like 0 and 0 or 1 and 1 or something like 20 and 10 but for these points we want actual x and y positions so we kind of have to do the opposite of what we did earlier but we converted the mouse position into a grid now we have to convert a grid to actual positions and this is going to be a for loop so four point in self dot path so i want to go through all the points in this path and inside of this i want to create an x and a y position and first of all i want to get point zero so in our self.path this would be the column and to convert this from a grid back to an actual position i just want to multiply this by 32 and then i could do the very same thing for y except now this has to be a one and this is going to work for now although we do want to make a change in just a second but now literally all i want to do is to get my points variable and append x and y and this has to be appended as a tuple and now once we have that i can call this method so self.draw path and let's see what happens we can see that nothing is working so let's check in our loop ah and the mistake i made here is that draw active cell it should be update instead so we're calling all of this not just the active cell so now let's try this again so now if i click now we're getting a path and if i click again we are getting a different path and all the way in the bottom right now we keep on getting working paths so this is kind of working not all that bad the problem we have now is that our path always goes to the top left of our cell which looks a bit strange so instead i want to move the points of this path to the center of each of the tiles and not to the top left and this is also quite easily done so back in my draw path all i really have to do is to put both of these into brackets and then add plus 16. so plus half the size of each of the tiles another one is again this is going to look much better so i hope you can see the difference this is now our path always ends in the center of the tile not in the top left but everything else works just fine and this way we also don't overlap with the walls so this is looking pretty good so this is then already some pretty good working path finding that works very reliable and there's one additional thing i have been drawing and it is right now whenever we have a corner it looks a little bit ugly because the draw lines feature in pie game just doesn't look very good so i essentially just drew a circle on top of each of the corner to make it look a bit more rounded and this happens with pygame dot draw dot circle and make sure it's inside of this for loop and in here we are going to need the screen again so our display surface besides that i want to have the same color and then besides that i need an x and a y position and fortunately those two i already have so they are very easy to get and now finally i need a radius which in my case is two and let me get rid of this comma here and now let's run this it's going to be very difficult to see but maybe you can tell very slightly that now the corners look a bit more rounded i guess let me exaggerate this a touch so now now you can see what's going to happen and essentially if we turn the circle radius a bit down okay that might even be too large two i think is just enough so this way it looks a bit let's say a tiny bit more rounded it's very very hard to see so with that we basically have our basic pathfinder module so this one is working really well now obviously this still doesn't help us all that much because we need the actual roomba and let's start working on this one now and for this we have to talk about how the movement is going to work and the core logic is essentially going to be this we are going to have a room bar and whatever we click we are going to give this roomba a path and once this roomba has a path it is going to go for every single point inside of this path and essentially what's going to happen is the roomba looks at its current position and at the first point in the path and then the roomba is going to move towards that path and once the roomba is hitting that point it is going to recalculate the direction and this way it's going to move through all of the possible points and eventually ends at the final one and once we are running out of points it is going to stop moving and by the way this is the very same logic i have used for the overworld in a mario game in an earlier tutorial so check this one out if you want to apply this kind of logic in a different context it's basically working in the same way but i guess let's implement all of this straight in the code that's usually going to be the best way here we are back in the code and i want to create another class and let's call this one class roomba it's going to be pygame.sprite.sprite for the inheritance because we are going to create a sprite quite obviously and now in here we are going to need an init method that for now needs self and let's say nothing else for now although it will need something else later on and in here i want to create a basic setup first and the first we need is super dots under init as always and then we are going to need self.image and and self.rect and well for the image all we are going to do is import an image so pygame.image.load and we have a file called roomba.png i am terrible at spelling png and this as always we need to convert alpha to use it a bit more efficiently and now for the rectangle i want self dot image dot get underscore act and for the center i have put this thing at 60 and 60. so it's roughly in the top left of the screen although the specific position really doesn't matter all that much now next up i'm going to add another section that i called movement in a comment and in here i'm going to set self.position for now it's going to be self.rect.center why this one is important you're going to see in just a second but besides that i want to set self.speed at 0.6 and this is literally just going to be how fast the roomba is going to move now finally i want one more section and i call this one the path and in here we're also going to have self.path and this again is just going to be an empty list and in just a bit we're going to pass the path that we created in our pathfinder inside this path here and then finally we need to get this thing it direction which is going to be a pygame.math.vector2 which i can set to 0 and 0. so by default this isn't going to do anything and i guess the direction could be in the movement i think it makes a bit more sense there all right so now we have our basic roomba and let's start by drawing this thing so back in my pathfinder i'm going to add another section here and let's call this one roomba and in here self.character is going to be pygame.sprite.group single and inside of this group single i am going to create this roomba actually let's call it not character but rumor that makes a bit more sense so we're going to create inside of this group single an instance of the roomba class and for now it doesn't have any arguments so we can just leave it at that so now i can minimize this init method and in the update method i can roomba updating and drawing and really what i want to do in here is self.rumba and self.roomba.draw on the screen so this is going to be very simple updating with sprites again if you have no idea how any of this works check out my introduction to pygame it's going to help you enormously but all right now i can minimize this one as well and if i run the code might work yep now we can see in the top left we have our roomba so all the way up here it doesn't really do anything right now but that we are going to work on well now and the first thing we have to work on is when we create our path right now we always start in this position but i want to get this position from the current center of our roomba so ideally what i would like to do is self dot roomba dot sprite so this actual sprite inside of this bright single class and this one should have a method called get coordinate to give us the position of what cell it's currently on and well that is what we have to create now so in here define get underscore coordinate in itself and nothing else and in here again we have to convert an actual position into a tile coordinate and i think we haven't done an exercise in a while so try to do this yourself and this should be fairly similar compared to what we have done with the mouse so try to figure this one out yourself all right so essentially i want to get a column i want to get a row and once i have those two bits of information i want to return the column and the row so how can i get them well first of all i need the center of this roomba and this i can get with self.rect.center x for the column and for the row it is going to be center y so this is going to give me the actual position on the screen and this i have to floor divide by 32 again and well that's literally all we needed so this is pretty much the same thing we have done for the mouse so same logic here essentially so this now we can minimize and not worry about it again and i guess now let's try all of this so now when i run this now we can see that our roomba starts in this position very hard to see because it's well the same cell so it doesn't really count but you're going to see later on this is going to work better but for now we don't get an error message that's usually a good sign but next up we have to create another method and this i have called set path it is going to need self and then the path we want to set and really all that's going to happen here is self.path is going to be the path we pass in it and now for this path i want to call this once we have an actual path in our pathfinder so in here self dot roomba dot sprite dot set path i think i called it yeah and in here self dot path so literally all that's going to happen is once we are running all of this and we have an actual path we want to run this path i am then going to pass inside of this roomba so then we can work with this path inside of this sprite individually so as a matter of fact we don't have to worry about this class at all anymore it's all going to work inside of this roomba and that's going to make our life a fair bit easier and now inside of set path we have to do two more things first of all we have to self and i call this one create underscore collision underscore rex i'm gonna explain in a second what this one does and then after that self dot get underscore direction so what are these two methods doing well get direction i think is well fairly obvious it gets the direction and let me actually draw this right now we have our roomba here and let's say we have a point here we have a point here we have a point here and what get direction does is it looks at the current position of our room bar and then calculates the direction to the next point and then the room bar is going to move in that direction and then we are going to check if this roomba is going to collide with this point and once that does happen we're going to recalculate the direction so this one here and then our roomba is going to move this way and that way our roomba is going to follow this path all the way to the end the problem we have now though is how do we check the collision and for this in my case i have created a rectangle at each of these points and this is what create collision rect does it essentially goes through every single point in our self.path and places a rectangle at every single one of these points and this we can then use to change the direction of our roomba and well now we have to create these two methods so let me actually create them so define this one for now let me add pass in here and neither of them need any argument so that's going to make things a fair bit easier and let's start by create collision rectangles that one actually isn't all that difficult and then here first of all we want to check if self.path even exists because if it doesn't there's no point running any of this and i guess in here what could happen is if the player clicks on the roomba and we are running all of the pathfinding in here but since we click on the roomba itself the path is going to be empty because the start and the end cell are the same position so this way we do want to check if even if the player clicks on something in the field we are checking for errors and now inside of here i want to create self dot collision underscore rex and for now this is just going to be an empty list as a matter of fact i want to create this list right when we are initiating this roomba class and this again is just to make sure that we always have this attribute available even if we don't call this method just in case it's not strictly necessary now we are going to do kind of the same logic we have done earlier in our pathfinder for drawing the path so very similar to what we have done here because in here we looked at all the points inside of the path converted each point to position in our field and then in here just draw a point through them but what we want to do for our roomba or the collision rectangles in here is we don't want to draw a point instead we want to create a rectangle but well the basic logic is the same so for point in self.path i again want to create an x and a y coordinate and well here the same logic applies so i want point for x it's going to be 0 multiplied by 32 and on top of that we're going to add 16. so half the size to make sure that we are in the center of this tile and now i can copy all of this change this to a 1 and then we have the x and the y position so this is actually not that hard now next up we want to use that information to create a rectangle and this is just going to be pygame.rect and in here again we are going to the tubal with the left and the top and then another tuple with the width and the height now the width and the height are going to be quite simple in my case the rectangle is just going to be a dimension of 4 and 4. so it's 4 pixels wide and 4 pixels high and since our speed is 0.6 this should very easily be enough and now for the left i essentially want to get the x and y although right now this would not work and let me explain why essentially if this is one of the tiles in our game so this is 32 by 32 pixels and our x and y right now would be exactly in the middle of that but if we just place these points in here we always place the top left so our rectangle would look something like this which well would be kind of a problem because there is a chance that the rumor might move something like this and miss the rectangle entirely so we have to give this thing an offset to actually place the center of it and that is well very simple all we have to do is to subtract half of the width and half of the height of it and that way we move this rectangle exactly in the center of each of these points and well once we have that all we have to do is get self dot collision rect and append the rectangle and with that we are creating a bunch of rectangles along the path and now we can minimize this and we should never need to open it again unless i made a mistake always a chance for that now next up we have to work on our get direction and in here we need if self dot collision rex so if there's any point inside of our collision rectangles because if there's no point left we know we have reached the end of the path and if that's the case we shouldn't be moving anymore but once there are collision rectangles i want to get a start position and end position and then i want to set the self.direction and minus the start and i want to normalize all of that so this is going to be very simple vector math because the start and the end are both going to be a vector and if you subtract the n from the start of a vector you get the direction between the two vectors um if you don't know vector math this might seem weird but i guess check out the vector math it's super useful but essentially now what we have to get is the vector for our start and the vector for our end and the start is the really simple one all we need here is pygame.math.vector2 and in here i want to set myself.position so this is the position we created further up here and then for the end i also want to get pygame.math.vector2 and for the end i want to get the first collision rectangle so self dot collision rex and zero and this is going to be a rectangle not a position so from this we have to get the center and that is kind of all we needed now i also want to add an else statement that if we are running out of collision rectangles i want to set self.direction back to pygame.math.vector2 and this should just be 0 and 0. so essentially we're not moving at all and then self.pair should also be an empty list so that once we got through all of the collisions we get rid of the path again so we are definitely not going to move anymore and all right with that we can finally create an update method for this roomba and in here all i want to do is self.position is going to be plus equal self.direction multiplied by self.speed so essentially what we're going to do right now is we have this point here and this point starts at the center of our roomba and this point we are going to move in this direction at this speed here and the direction we are going to get from the position of the first point in our path and then self.rect.center is going to be self dot position so this way we make sure we actually place the roomba at the position that we have set here now why is this important why couldn't we just go straight with self.req.center here why do we need position at all and the reason is that vectors and pygame are not exactly perfectly compatible so when we place a rectangle so a rectangle like here we always place integers whereas vectors like self.direction is always going to be a float and pygame converts a float to an integer automatically so that's not the problem the problem is when these two numbers are converted we are losing some information so if you always edit the direction here you might get a slight offset that's not intended because a float here might be 0.78 completely random number but when pygame places this rectangle this 0.78 is just going to be zero and if you keep on adding these tiny offsets eventually this center is going to be in a completely different position because every movement is going to add a tiny additional offset and this well obviously isn't going to be great and the way around that is to store all of this information inside of this position and this position is always going to be a floating point number and then when we place this rectangle we always place this in the same position so that way we avoid adding the error and again check out my overworld tutorial it's going to explain all of this in much more detail but alright i guess let's actually run all of this finally to see what's going to happen so the game still runs now if i click on something we are moving in completely the wrong direction good to know although it's not entirely wrong and i guess let me explain why so right now the origin point of our roomba is here and the first point that we are going to create for our path is going to be here and then the second point is going to be here the third point is here then here and so on essentially our path is going to be this this and then i assume something like this and the reason why our roomba is going to the top left is because this initial first bit here let me overemphasize it a tiny bit so the direction is actually working the problem is now that once we are colliding with any of these collision rectangles we don't actually change the direction so this is something we have to add but everything else seems to work so let's add a collision mechanic and this is just going to be another method and let's call this one check collisions it needs self and nothing else and in here first of all as always i want to check if self dot collision reacts even exists because if it doesn't there's no point running any of the stuff inside of it and now inside of this i want to check for rect in self dot collision rectangles so i want to look at all of the rectangles inside of this list and what i want to do is if rect.collide point self.position so essentially i am looking at this self.position so the position we are moving down here and if this point is in any of the rectangles i want to run some code and what i want to run is self dot get underscore direction again except now i don't want to get the point i'm currently on let me actually explain this so let's say right now this is our roomba and right now we have a point here and a point here and our roomba has moved to this point and now happens to be right on top of it and now we're running get direction so this one here the problem we have now is that getdirection always picks the first point from this path which in our case would still be this point here so the point our roomba is already on top of so if we were to run the code like this we would get a weird result essentially the rumor wouldn't work at all but this is a problem we can work around quite easily literally all we have to do once we are colliding with this point we want to delete that point so delete self dot collision rects and the first item so once we are colliding with the point we are going to delete that point and then get a new direction and that way our roomba is always going to move towards the next point once it reaches the current point and now all we have to do is to actually call this method and i have called this right after the first line so self dot check collisions and now let's run this again so now we are actually moving this roomba and this is looking really good but now at the end oh it's actually working okay so problem now is that this is kind of slow so let's increase the speed a tiny bit so the speed right now 0.6 let's put this to a 2. and now this is looking significantly nicer and i'm just realizing drawing the points here looks kind of bad when i run it often enough but well by itself this is actually working really well and you can even click it whenever you want and this is going quite well and well it's working super well already and okay so with that we are nearly done there's one more thing i would like to add and let me minimize all of these methods because they're kind of hard to read right now okay so here we have our two classes they have gotten quite a bit complex over time but the one thing i would like to add now is that once the roomba is reaching the end point i want to empty this self.path it's not strictly necessary but from the game logic point of view once the roomba is reaching the end of this path the path isn't necessary anymore and if you have a more complex project it might interfere with something else and well all we need for that is another method that i'm going to call empty underscore path it needs self and nothing else and literally all we are doing in here is self dot path is going to be an empty list and then when we create this roomba i'm going to pass this empty path into it and now inside of the roomba class we can create an instance of empty path and now in here let's put it down here next to path so self dot empty path is going to be empty path and now what i want to check is in my collisions that i already check if collision racks exist at all but once we reach the end of this collision rex should be empty and if it's empty an else statement should be running and what i can do in here is run self dot empty the path and this should then empty the path so that in our pathfinder we don't have anything in here anymore which feels a bit cleaner and now let's run all of this again we are getting an error all right it should be self dot empty path so now let's try this again and there we go so now you don't really see a difference except now the path disappears because we are deleting it which i think is a bit better and all right this is feeling quite nice i guess it's still a bit slow and i hate the points let me get rid of those so drop half um let's get rid of this drawing here looks a bit ugly now that look at it and then for the speed let's set this to a free this should definitely be fast enough and now let's run off this again and now with our roomba so this is working really well and well now you have all you need to create pathfinding in basically any kind of game so this sort of system you can pretty much create wherever you want it's pretty flexible when it comes down to it so well with that i hope you enjoyed this tutorial and i will see you around

Channel: Clear Code

Views: 4,983

Rating: 4.985507 out of 5

Keywords:

Id: 8SigT_jhz4I

Length: 71min 12sec (4272 seconds)

Published: Sat Nov 13 2021