A* Pathfinding Visualization Tutorial - Python A* Path Finding Tutorial

[Music] hello everybody and welcome back to their python tutorial so in this video what we're going to be doing is learning about the a star path finding algorithm and then actually implementing that into a visualization tool so this is a really cool video because this project is just really fun in my opinion to actually see how a computer kind of goes down the process of finding the shortest path between two points and a visualization tool like this although it is kind of simple this isn't going to be a super complicated program looks really great on a resume and is a really great thing you can point someone to and say hey you know not only do i know how to use algorithms but i also can implement them into this cool visualization tool and you can now watch these you know this computer figure out the shortest path between two points so anyways this has really fascinated me let me give you guys a quick demo of what it is we're going to be creating and then i'll talk more about how this tutorial series is going to look or how this tutorial is going to look and kind of what you can expect from it so you can see here this is the basics we have just the visualization of finding the shortest path now since a star is actually an informed search algorithm which we'll talk more about later this means we can avoid doing a ton of unnecessary searches that we don't need to do so for example in an uninformed search algorithm they may potentially consider some of the nodes over here where i'm kind of drawing and erasing these barriers and the reason they might do that is because it's just somewhat of a brute force approach they're just checking every single possible path they're not actually moving in a direction that kind of makes sense whereas this algorithm here you can see was always kind of moving in the right direction it might have gone off a little bit maybe it goes down some roads that aren't necessarily correct but it always is moving in the correct direction and that is kind of what's guiding the algorithm and making it much more efficient now of course these gains are way bigger when you have a huge map and a much larger network of nodes connected together but in this case on a 50 by 50 grid which i have it happens pretty much instantly and if i omitted actually doing the drawing aspect where we draw the green and red squares then this would happen pretty well instantaneously so with that being said i will quickly say that this is not a beginner tutorial series although it's not going to be super complicated we are going to be using some data structures and algorithms we're going to be talking about this algorithm which is not trivial by any means and well if you're you don't have any experience with python this might be a little bit overwhelming so i just want to warn you right now so that being said let's go ahead and start talking about the a star path finding algorithm after a quick word from our sponsor i need to thank simplylearn for sponsoring this video and introduce you all to their data scientist master program that was co-developed with ibm this program is comprised of six unique courses that implement a unique blended learning experience in a high engagement online classroom environment during this program you will master 30 plus in-demand skills and work with tools and languages like r sas python tableau hadoop and spark you'll master these skills through 15 real life projects and one capstone project during this 12 month comprehensive course you'll also be given 1200 usd worth of ibm cloud credits to use during your 24 7 access to the ibm watson platform after completion of this course you'll be given certificates from ibm and simply learn to testify to your skills as an expert in data science get started by hitting the link in the description all right so now it's time to understand the a-star pathfinding algorithm so before i go into all the kind of explanations and definitions i'm going to quickly define what a few terms mean so when i say node i'm talking about a letter okay i'm talking about a b c d this is a node a node is anything in a graph that you can visit you can think of this as a vertex right say we have a triangle you can think of the nodes of a triangle if you're treating this as a graph as the three vertexes and the edges are going to be all the lines that connect those so we have nodes and we have edges just understand edges connect nodes nodes are usually represented as a circle or something that you could visit if we look at a grid for example and we have like a 2x2 grid then really you can draw this grid in kind of a graph format like this where all of these are the nodes and then the edges are the connections between these nodes which could just mean you know what it means like go from that node to this node that's all i'm saying just hopefully that makes sense and last thing here to explain is when we have an edge we can have a wedge an edge that is a weighted edge or an unweighted edge if it's a weighted edge what that means is that it takes a certain amount or it is a certain length so obviously weight one is a shorter edge than weight two so obviously this is not drawn to scale if you're talking about the weights of these edges but i've drawn them just with different weights so that for this algorithm it makes sense so we can actually do something that's meaningful but in our example we do the a-star path finding and we're using the grid none of the edges are going to be weighted they're all just going to be known as like 1. we'll just give them all weight 1 because we're just assumed they're all the same distance essentially okay hopefully that makes sense now let's get into the algorithm so uh how does this work what is the a-star path finding algorithm well the goal of this algorithm is to find the shortest path from point a to point b in a graph using the edges that are in that graph right and anything can kind of be represented as a graph just like we've been drawing over here and i've been showing you so how do we do that well this is an informed search algorithm which means we don't only just brute force and attempt every single path we actually have what's known as a heuristic function that helps guide us and figure out the correct path to go down essentially as you'll see as we go through this algorithm we only consider paths that we know are optimal we don't consider things that you know have a huge distance to get to them already or that look like they're going to be really far apart we may consider those but that's the least priority and hopefully we don't even have to we end up finding a shortest path before we even consider those nodes so that's kind of the point of this algorithm as you're going to see but i think the best way to explain this to you is really just to go through an example and just kind of slowly go through it as we go so what we need to do to start is we need to take our start node which in this case is going to be a we need to put this inside of our open set so we have this open set this is going to be represented by a priority queue when we actually do this implementation don't worry if you don't know what that is we'll talk about it later and essentially the open set keeps track of the nodes that we want to look at next you can think of it almost just as a queue it's the next things that we want to consider so we always start by putting our start node in the open set and we put it in the open set along with the distance to that node which we're going to say is our our f score now i need to define what this f g and h scores stand for because these are going to be very important as we go through this algorithm so let's do that quickly so h score which is of just simply a function h n so h of n gives us an estimate of the distance from node n to the end node essentially we just pass it a node and it looks at the end node and says okay you know i don't really know how far away you are but like if we're just doing absolute distance so literally from the center of say a to d even if an edge doesn't exist here i'm going to assume your you know x blocks away just based on that absolute distance that's what this function does there's many different distance formulas you can use in here i think euclidean distance is popular some people use manhattan distance that's what we're going to use here lots of different distances anyways this is just some function that gives us the distance from node n to the end node there we go and again this is not like a super correct distance this is just a guess at what that distance is based on some formula that we've implemented in there awesome that's the h score your g score is the um the current shortest distance to get from the start node to this node so we're talking about the g-score of c then whatever the shortest distance from start from point a which is our start node to point c that we've currently taken that we've currently found will be this g-score and the f score is simply the addition of the g score and the h score so if you understand that and i wrote the kind of formula down here so we can remember what makes everything up the f score is pretty much trying to give us an estimate say okay we've already taken two blocks to get to this node and from this node we think it's going to take like five blocks to get to the end node so we have a total score of seven okay should we start looking at this one first or should we consider this next node that has a lower f score right because maybe a lower f score means that this is actually closer and we should take that node over the other node that's the way that we prioritize which nodes we consider is by using the f score and the f score is made up of the g score and the h-score so again g-score is the exact distance the shortest distance that we found currently to get from the start node to whatever node we're talking about if we're talking about node d whatever the distance is whatever shortest path we've currently found to node d that's the distance we're going to have for our g score the age score is the heuristic which is just the guess at how far away we are from the end and the f score is the addition of those two scores to give us an estimate of how far away this node is from the end node uh or like what that finalized path would look like so that is these scores and they're going to be very important as we go through here so let's actually start this we have open set we have zero a so of course a is g score uh f score and h score is going to be zero because well it's itself right at our start node we can't have an f g and h score that's higher than zero because we're just already at our our same note hopefully that makes sense now the rest of these scores though we're going to start them at infinity and you're going to see why but just imagine the age score is not really relevant right now for these ones but just they're all infinity to start okay so we start them off at affinity because currently we have no idea we have not found any path these nodes we haven't considered anything from the start node so we just assume it takes infinity to get there that's just our main assumption and these might actually stay infinity because we may never actually even consider them so we have zero a and we pull zero a out of the open set we've just set everything up we've you know initialized our table we pull it out so we delete it from the open set and we start looking at it so okay we're on node a now we're considering node a i think i'm just gonna underline what node we're currently looking at so i'll just underline it like that we're looking at node a and the first step is to look at the neighbors of node a so in this case the only neighbor of node a is c and there's only two ways to get to node c there's two edges so we have the two edge and the one edge so we start by just looking at any edge there's no order we take in looking at it so we say okay to get to node c we have edge one right so we have this edge here so what we're gonna do is we're going to say okay is this edge that we've currently taken like the current path to node c that we're on how long is this path what is the current path well the current path is distance one so we compare that now to the g-score of node c and we say okay is the current score that we're looking at score one shorter than the current g-score of node c so we compare it to infinity which is right here and we say which is shorter well of course distance one is shorter than infinity or smaller than infinity so we go ahead and we update the g-score and make it one and we say okay now currently the best path we know the best we've found to get to node c is from node a to node c taking edge one right taking the edge with weight one so we update that score then we go ahead and we update the h score so we say okay since we're considering this node c now we found a better path we're not skipping over it this is the correct way to go what is the h score the tentative distance from node c to node d what is our guess for that well our guess for that we can just kind of make that up i'll just say oh we think that's going to take you know one distance point to get there so i'll just write 1 here of course obviously it's 2 but we don't know that we're just taking an absolute distance guess so we take we take a guess of one and then we update our f score and we say okay well the f score now is going to be two because of course the g score and the a score added together is two and once we update the g score we update the h score and then we update the f score accordingly so hopefully this is all making sense but this is the basics of it so 2 1 1 those are our scores and then we go ahead and we update this last which tells us where we came from to get these scores so we came from node a to get to node c there we go that just tells us what node was the last node we came from awesome now i'm actually just going to delete this other edge because for our example we're not going to do anything with multiple edges so i think it'll just make more sense to do this so let's go ahead and do that so now once we've considered this node and we said okay you know this was the shortest path what we do is we take that node and i'm just going to erase some of this stuff now to clean it up and we add it into the open set so we say okay we've considered node a now we just looked at node c as a neighbor so let's throw that into the open set so we're going to say okay what's the f score of node c that's two let's add that to the open set so we say two c say the current choice distance um in the open set is two c now we look in the open set and we say okay give me the node that has the shortest f square well there's only one thing in the open set so we have to use this one so we take it out and i guess i can just move it like this if i really wanted to oops i forgot a bracket let's move that there so we take this and we move it out of the open set and we start considering node c so double underline and now we do the same thing we look at the neighbors of node c so let's start by going to node b let's look at node b and we go okay so what is the current distance that it takes us to get from node c to node b well we got to know go from a to c that's one and then from c to b that's four so our current kind of tentative g score right now is four so we say all right if we're using node c to get to know b we're gonna have a g score of four so we take four right and we compare it to the g score of b and we say okay is that larger or smaller well that is going to be smaller so we update the g score of b and then we go ahead and we update the h score and the f score so what's the h score from node b to node d let's just say that that's a distance of let's give it 2 that's going to be our guess so we'll say okay that's going to be 2. so now our f score is 6. now we've looked at node b we've considered the neighbor so we add node b into the open set with its current f score so we say 6 b and that's now inside of the open set so let me just erase this now to clean this stuff up and then we'll move forward and we'll do the next neighbor so of course the next neighbor is d which so happens to be our node but don't worry we're not done the algorithm yet so we go from c to d and we say okay what is the tentative g-score that we've kind of just calculated here between node c and node d from the start node well that's of course going to be three so we go here to the g-score we say okay well is that less than infinity yes it is so we update that that becomes three what do we do next we update the h score and we update the f score so let's say that our guess from node d to d well that's obviously going to be zero so we'll put zero right there and then what about the f score well that's just going to be 3 right so there we go so now we go into the open set and we put inside of here 3 d like that boom so now we've considered c we're done with c we can erase this right here and let me just fix this this bubble uh we can erase this four and now we go into our open set and we say okay give me the node in here that has the shortest f score or the lowest f score well of course that's 3d so we pop 3d out of here and as soon as we do this as soon as we take the end node out of the open set we immediately finish the algorithm and we know that the shortest path now has to be from a oops it was not supposed to be an eraser from a to c to d now the reason we know that and let me just actually fill some of these things and i forgot to fill in the last column from d that was c from b that was c and from a the last would have just been nothing but anyways this is what our last column would look like so the node that we came from and essentially what we do is okay we found d we know this must be the shortest path because if d was in here anywhere else we would have picked it out and it would have had a shorter f score right because we picked out the smallest f score so we reached d we took out the last node and now the algorithm is complete it's finished and all we have to do is find the path now the way we find the path is we just backtrack we say okay d came from c c came from a so that must be our path right there and that is our path and it so happens to be the shortest path just by following that formula now of course things can get a little bit more complicated and there's more edge cases and things to consider but that is the basics of this algorithm you have this h score and this f score and this g score that help show us where we should be going what direction we need to move in and what nodes we consider next so let's just imagine for a second though that maybe we didn't just immediately consider this this end node right maybe we didn't hit the endnode let's just imagine that actually d maybe isn't necessarily the endnote maybe there's another node here that is the end node and that's our new end then what we would do is we would simply since d was already in here we'd pop it out we'd consider the neighbors of d so we considered c we consider b and we consider e and remember if i'm considering b what i would be thinking about is okay so to get from a to c to d to b what is the distance going to be and of course that distance is going to be larger than whatever the current distance was the current g-score to get to b so actually one two one um is going to be the same but since it's the same we don't bother updating it we just say okay we don't need to update that because obviously the current distance to get from a to c to d to b well that's four the distance that we have as the g score that's four so since that's not smaller we just don't do anything we just skip over b and we say okay we don't need to look at that anymore we're not adding it back in the set we're just moving past it and then we go and we consider d all right we consider c and we consider e so we do e our c we determine that well to get to c is obviously not shorter to go ac dc than it is to just go ac so we don't update that and then we consider e we'd update e in here with whatever the values are we'd add e to the open set the distance for e would almost likely be larger than the distance for b we would take out b we would consider that and and that's how we would keep going so i know i'm kind of just fast forwarding through the rest of the algorithm it does take a long time to walk through but that is the basics and of course as we go through this it's going to start to make a lot more sense but that is how the f g and h score work and hopefully you understand how we're considering nodes that are closer first with that estimate of that h score um that g score that's telling us the actual distance and that f score that's the combination in between so anyways that is going to be my explanation if you don't understand that i'm going to recommend you head to wikipedia maybe re-watch this see if you can do this yourself on it on your own graph maybe do it on a piece of pencil and paper but once you feel comfortable let's move forward and let's actually start coding this out okay so sorry for that long explanation but i really do try and try my best to make sure you guys really can understand everything so that i'm not just blindly going through and showing you that even if you don't understand completely i will be re-explaining as we get to the implementation part but now let's actually start working on this visualization tool and more of the fun stuff so the only real prerequisite for this is to install pygame so pi game is a 2d graphics module in python really easy to use i'll explain all the stuff that we do here but to install that go to your command prompt or terminal and you're gonna type pip install pi game now you might if you're on mac be able to use pip three so just try pip install pi game if that doesn't work for you i'll leave a card to a video that explains how to install pygame and i'll leave a link in the description as well if you're on mac just replace uh pip with pip 3 and that should hopefully be able to install it and then i think you can also try python hyphen m and then pip install and then pie game as well now these are all just different options you can try so i'm just giving you a bunch of commands but in your terminal or in your command prompt pip install pi game pip 3 install pi game python hyphen m pip install pi game or python 3 hyphen m pip install pi game if none of those work or you get like pip is not recognized as an internal external command watch the video it should hopefully help you do that anyways once we've done that i'm going to be working in subline text for this video you guys can work in whatever editor you want we're going to start by doing some imports so we're just going to import pygame i've already made a python file here we're going to import math like that and we're going to say from q import priority queue now we'll be using this later i'll explain how that works it's going to be for the algorithm but you don't need to install this this should be built into the python standard library now next i'm going to define the width of my window so i'm going to make everything square so i'm not going to have a height i'm just going to have a width and i think i'm going to make that 800. so width 800 and then i'm going to say win and then in this case that's going to be equal to pygame.display.set underscore mode and inside of a set of brackets i'm going to go width width so this what this does is just set up why is this not working with i'm hitting enter it's literally canceling what i'm typing okay anyways width like that hopefully that's fine if i could get the right character okay so width sorry about that but regardless what we're doing here is we're just setting up the display so we're essentially saying this is how big the display is going to be this is the dimensions i'm making it width by width just so it's a square and then i don't have to deal with any height variables later which is going to make things a little bit nicer next what we're going to do is we're going to set a caption for the display so not in capitals we're going to say pi game dot display dot set underscore caption and for the caption what we're going to do is just put whatever we want but i'm going to put a star like that and i guess i don't need to say star a star path finding algorithm this mic is really in my face kind of in the way of the keyboard so that's why i'm getting all these typos because i usually look down a little bit just pre-warning there anyways we have that now so widthwindpygame.display.set underscore caption and now if we actually go ahead and run the program we should see that a window pops up and then it just immediately disappears so that's how you can test to make sure that this is working you're not going to see anything right now it's just going to go away pretty much instantly but if that's working good okay so next we're going to define a bunch of colors now i'm actually just going to copy these in you guys can pause the video if you want to copy them out but all this code will be in the description if you want to copy and paste different aspects of it but i want to have all these color codes here because we're going to need to be using them for actually making the path and making the different squares and changing the color of things and all that so we have red this is a red green blue color code green blue yellow white black purple orange gray turquoise feel free to change all of these colors to whatever you want but just define them in all capital letters as constants and have them here so we can use them throughout the program now the next thing that i'm going to do is i'm going to define a class called spot now remember we're building a visualizing tool so i actually have to build kind of the main visualization tool before i can implement the algorithm because the algorithm is going to be dependent on what our tool looks like right so we need to figure out essentially how are we going to keep track of all of these different nodes that are in our grid because remember we're going to do this huge grid this grid is actually going to be a 50 by 50 grid and we can change the dimensions of that if we want and in that grid we're going to have a bunch of spots or a bunch of cubes or whatever you want to call them i like to call them spots but you can call them whatever you want you can even call this a node that might even make more sense but i'm going to go with spot and this spot is going to need to hold a bunch of different values so it's going to need to keep track of where it is so what row column position it is in the grid because this will just be one of those little cubes it's going to need to know what the width of itself is so it knows how to draw itself right if it is wrong itself although i don't think we actually actually we will need to draw these spots because they're going to be different colors and then it's going to need to keep track of all of its neighbors that's something that's important and a few other things as well so it's color will be the main thing because it needs to know okay am i a red node am i a green node am i a barrier am i the start node am i the end node which will all be represented by different colors if you remember the example that i did and so on and in fact let me just run the example so you can kind of see what i mean so we have like all these different spots right so when i click on one of them it changes colors and that's what the job of this spot class is going to be is to keep track of the color of all of these spots and know what location it's in right so then when i press space you can see there's red and there's green and then of course there's purple as well that represents the path so hopefully that makes sense uh i just wanted to show you that's what it is okay so class spot so we're going to define an init in here so we're going to say define a knit we're going to say self we're going to say row call width which is just going to be you know how wide is this spot and then rows now i'm just going to call this total underscore rows now the reason i'm doing that is because we need to keep track of how many total rows there are here you'll see why in just a second but this spot does need to know that and i want to avoid any global variables so i'm just going to throw it right into the instance so i'm going to say self.row equals row i'm going to say self.call equals call i'm going to say self.x equals row times self dot width actually this is just going to be width i'm going to say self.y equals call times width as well now the reason i'm doing this is because i need to keep track of the x y like the actual coordinate position on my screen because when i draw things in pi game i can't just say okay draw it at you know five five i need to draw the actual cube which is going to have some kind of width it's going to be sitting in some position so i need to know what position that is and i can determine that because let's say i have 50 total cubes and the size of my screen is 800 well then i go 800 divided by 50 which i think is like 16 or something like that and that will be the width of each of my cubes so i can figure out where the starting x and y position is by taking the row that i'm at and multiplying that by the width of all of these cubes that's the idea there we're going to say next self.color equals white so to start we're going to have all white cubes this will again change as we go through i'm going to say self. oops if i could type here equals a blank list and then i'm going to say self.width equals width and self dot total underscore rows equals total underscore rows next what i'm going to do is i'm going to make a get underscore pause method and we're actually going to have a bunch of methods in this class and this is just simply going to return self.x or notself.x self.call and self.row and sorry it's going to be the other way around actually self.row then self.call so for this specific program i'm going to be indexing things using row columns so that's just what we're doing for the grid right if you look at grid of course we have a bunch of rows like that and we have a bunch of columns down so you know something like here could be indexed with i don't know like 6 3 or 6 4 or whatever it may be but we start by calling the row out so whatever y coordinate and then i call the x may seem counter counterintuitive or counterproductive but the way we're going to represent the data this this makes sense later okay so we have get pause so now we're going to define is underscore closed so is closed essentially like have we already looked at you have we already considered you those are the red squares so in this case we're going to say okay what makes a spot closed what would mean that this spot is in the closed set so we're not looking at it anymore what makes it red well i pretty much told you that we're just going to return self.color equals equals rep so the idea behind all of these methods here is we're just going to have a bunch of methods that essentially tell us the state of this spot and we're going to have a bunch of methods that allow us to update the state of this spot as well so they're just going to be changing the color and if this color is white well then this is a square that we've not yet looked at we could visit it if it's red we've already looked at it if it's black it's a barrier that's something we have to avoid that the algorithm can't use as a node to visit if it's orange it's the start node if it's purple it's the path right if you get the point so this might not be the best way to do it but this is what i've gone with for this tutorial and i think it makes it pretty easy to understand so we'll say is open so is open is just going to be return self dot color equals equals green so essentially are you in the open set now i don't know if we are even going to use that method but i'm just defining all of the different states just so it's consistent so next we're going to say is barrier so are you an obstacle well what makes this an obstacle that's if the color is equal to black right so if it's black because we're going to punch it in and we're going to draw all the obstacles then this is a barrier so that's what we're doing next we're going to say is underscore oops is underscore start i'm going to say self and we're going to say return self.color equals equals and for the start color we'll just go with orange but you're welcome to change any of these colors of course if you'd like and then finally we go is end actually there should be one more and we'll return self.color equals equals and i think i went with purple for the color finally i'm going to add another method and this one's going to be called reset and this is simply going to change the color back to white so define reset and we'll just say self.color equals equals white like that okay now you thought i was done with all the methods but we actually have more this is like the longest class that's just the most simple thing in the world but i'm going to say make underscore color and what am i saying make color i'm going to say make open make closed and pretty much duplicate all of these methods here with just a make in front of them so when you call this it will make this cube whatever it is that i'm saying here so in this case uh we'll start with closed just so it stays consistent so make closed self and i believe make closed was what color were we going with i think that was red right so we're going to say self.color equals rep so this time instead of just giving them back like are you red are you green are you this is going to actually change the color so make close we'll say make open this is going to be self and we'll say self dot color oops equals green like that we have more oh that's nice of that one away so to make open uh what else do we have make barrier make underscore barrier this is going to be self and then we'll go self dot color equals black okay and define make underscore end this is going to be self let me self dot color equals and what was the end color that was i'm going to go with turquoise actually for the end color and instead of purple i'm going to change this to turquoise my bad on the end color guys i want that want that one to be turquoise and then we'll say define make underscore path self self.color equals purple so purple will be the path turquoise will be the end color and then finally we need to add two more methods so define draw so this is going to be the method we call we actually want to draw this cube on the screen so we're going to say self wind so this is actually going to be this window so essentially where do we want to draw this that's what this argument is saying right here so self win and i think that's all i need and then to draw a cube in pi game go pygame.draw.rectangle so rect like that you put the window you put the color so that's self.color like that and then you put a rectangle that you want to draw so you give it an x y width and height and you can see it's saying surface color rect width that's just telling us how do you want to draw this rectangle where do we want to put it what position that's how pi game works so the way pie game works actually let me just run this example here is you start drawing things from the top left hand side of the screen so 0 0 is actually where i just put this start dot so technically i shouldn't be able to do that but that's fine if that happens see where this orange cube is uh or let's put it there where the orange cube is this is actually the zero zero so this is zero zero not down here like where you would normally think and as you move to the right x increases as you move down y increases so over here in the very corner where the turquoise dot is that would be 800 800 if this was 800 by 800 which it is so that's the idea with the x y when i start drawing something i always start drawing from the top left hand corner so if i say like i'm strong at 50 50 and the width is 16 then you're actually going to extend to like 66 66 so you go from 50 to 66 50 to 66 if you're talking about the lines hopefully that makes sense but i'm just trying to kind of illustrate to you how that works okay so we're going to go pi game.draw.rect we're going to say self and in this case not row and call but self.x because that's the actual coordinate position i want to draw at and then self.width and self dot not height width again so since we're not doing a height everything's square we can just pass in width twice and i'll just make it a rectangle and then finally we're going to say define update underscore neighbors if i could spell neighbors correctly like that this is going to take self and this is going to take a grid and we'll do this one later because this one is kind of a big function and then lastly i'm just going to say define underscore underscore lt underscore underscore just so i don't forget to do this we'll talk about what this does in a second other and we're just going to return false now for any of you that don't know what this lt is it's stands for less than and essentially this is how we handle what happens if we compare two spots together so now what i'm saying is essentially if we compared this spot and some other spot so two spot objects i'm just always going to say that the other spot is greater than this spot or yes i think that's actually maybe it's the other way around but regardless don't worry about this right now we'll talk about it when we use it but i just don't want to forget so i'm putting it there right now okay so the next thing i'm going to do just because this one's really easy is i'm going to define the heuristic function that we're going to use for our for our algorithm right so we need we need that h function we actually need to make that heuristic function so let's code that out we're going to say define i'm just going to call this h actually i'm just going to put p1 p2 here and p1 and p2 are going to be 0.1.2 so i'm expecting point 1 and point 2 to look like x y right or to be like row column or something like that so we have to figure out the distance between point one and point two and return that so the way we do this because we're gonna use manhattan distance which essentially is l distance so i'll show you how that works on the grid right here is we just do a very basic formula but essentially l distance or like manhattan distances say i have like these two cubes the distance i'm going to calculate between them is going to look like this it's just going to be whatever the quickest l is to get here this is going to be my guessing distance because we can't move on diagonals right and even if you could so if we can move on diagonals like that that's still going to be the same distance as just going in an l like that so that's what manhattan distance is it's sometimes called taxi cab distance as well because it's like if you're going in a straight line and you're moving around and all that but hopefully that makes sense that's the distance we're calculating so to do that i'm just going to say x1 y1 equals p1 i'm going to say x2 y2 equals p2 this is because this is going to be a component right so if i have like like p2 is going to be made up of something like you know 1 9 so i can split it into the variable x1 y1 where x1 would be 1 y1 would be 9 by just doing that it's a short cut in python and i'm going to return the absolute distance abs this is a built-in function of x1 minus x2 plus the absolute distance of y1 minus y2 it doesn't matter if you swap x2 and x1 so long as you swap y2 and y1 as well because that's the h function that's our heuristic now what i need to do is i need to actually come up with a way to make a grid so i need some data structure that can hold all of these spots so that i can actually manipulate them i can use them i can traverse the grid right i need this list that's going to hold all of the spots that i have in my grid so what i'm going to do is i'm going to say define make underscore grid like that and inside of here i'm just going to take the rows and the width so i'm essentially saying okay how many rows do you want in your grid because we're just going to have the same amount of rows as we do have columns and what do you want the width of this grid to be so that's what we're doing so i'm going to say grid equals a blank list and i'm going to say gap equals width integer division by rows so width of course be the width of our entire grid and rows will be how many rows we have doing an integer division will just give us what the gap should be between each of these rows or in other words what the width of each of these cubes should be so hopefully that makes sense and now we're just going to go ahead and actually create this i'm going to say 4i in range and i guess it's going to be rows we're going to say 4j in range rows up here we're going to say grid dot append an empty list we're going to make a 2d list that looks something like this with a bunch of different rows in their own list that all have spot objects inside of them so we say grid we have the gap and we have grid dot append for j in row range now we're going to say spot equals a new spot so we're going to use this class that we just defined up here we need to pass it its row its column its width and the total amount of rows in the grid and then there it'll be able to figure out where it should actually be sitting so we're going to say i j for row column because this is going to be our row this is going to be our column so we pass it i j we're going to pass it the gap that's going to be its width and we're going to pass it rows so now we have this spot object that we've created and what we need to do is we need to append it into the grid so we can say grid.append spot like that and that should actually be sorry grid i believe it's grid i dot append spot so what this is going to do is say okay in grid row i which is the row we just created here we're going to append the spot into it so we have a bunch of lists inside of lists that all store spots then at the very end of this we're going to return oops if i could hit the t key we're going to return the grid awesome so now we have the actual grid being able to be created and i'm just going function through function because i think it's easy to just code out these small parts that all do separate things and then kind of combine them together at the end so we have make grid and now we need a way to draw the grit so we have all these cubes but remember all these cubes are just like white cubes or black cubes we don't actually have any grid lines so if you look at this right you can see these gray grid lines and like all my cubes you can really clearly see kind of where they are and you know where they're defined so we need a way to draw these um these grid lines that we have that's what i'm going to do here so i'm going to say define draw underscore grid like that we're going to take inside of here the win the rows and the width so this is not actually going to draw every one of the cubes that are inside of the grid it's just going to draw those grid lines so this is pretty easy to do actually i'm going to say gap equals width integer division rows again that's going to be the exact same thing as up here i could have made this all capitals in fact to stay consistent let's make this lowercase like that and we're going to say 4 i in range rows like that and then here we're going to draw lines so for every row we're going to draw a i believe horizontal line first so pygame.draw.line in this case and what we're going to draw is a yeah horizontal line for each one of these rows so to do that we need to pass the win we need to pass the color which is gray and then we need to pass two positions so two xy positions where we want the start of the line to be where we want the end of the line to be so the start of the line we want to be at x position 0 and we want the y position to be i multiplied by gap like that and then for here we want this one to be width and then i multiplied by gap the reason we want that is because we're going to multiply whatever the current index of the row that we're on by the gap and what that will do is it will essentially tell us where we should be drawing the grid line so if we start at zero width we know we're going to be all the way on the two borders of the screen and we're just going to move those down constantly and draw a bunch of horizontal lines now we'll do the exact same thing i'm really going to copy this for loop and i'm just going to change the variable to be j so for j in range so now we're going to do the vertical lines and what we can do is just leave j times gap but leave that as the x and then as the y we're going to go zero and width like that so tap that in i'll explain this quickly essentially this is the exact same thing as the horizontal lines except i'm flipping the coordinates so now we're always going to be at the top and bottom and we're going to shift along the x-axis and draw all of those vertical lines so i think let me just make sure yeah that's it for doing that and next we're going to actually make the main draw function which is going to draw everything so i'm going to say define draw and inside of draw we're going to take win grid so we need an actual grid that's being passed here we need the amount of rows and we need the width of the screen so we have win grid rows width and then here we're going to say wind.fill so this just fills the entire screen with one color you do this at the beginning of every frame so we're going to run like you know 100 frames per second or 50 frames per second or whatever it is and at the beginning of every frame we're going to paint over everything that was on the canvas and we're going to redraw everything in its current state it's not the most efficient way to go about doing things when you talk about drawing things on the screen but for our purposes totally fine and this is common practice in pie game so we're going to fill everything with white and then what we're going to do is we're going to say 4 in lower cases for row in grid so for all those rows and we're going to say 4 spot in the row because remember this grid is going to be whatever this creates so it's going to be a 2d array or a 2d list and we're going to say spot dot draw and we're going to pass the win so essentially if we go back to spot.draw you can see this just draws its own color on its x y and whatever the width it is so it just draws a cube with whatever color this spot is right that's all it does so now we just need to call that method on all our spots which are going to be stored in our grid which are stored in the rows so we loop through all of it go through all the rows and then draw all of the spots next we draw the grid so we say we're going to draw the grid lines now on top of that because this will be drawn first so we fill the screen we draw all the colors we draw the grid lines on top and then we'll be good and we've drawn everything we need to draw so we do draw grid we need to pass that win rows and width like that and then finally we do pie game dot display dot update now there's nothing that needs to go in here all this is tells us is hey pie game take whatever we've just drawn and update that on the display awesome so next what we need to do is we need to write a few more functions so the next function i'm going to write is a function that can take a mouse position uh position sorry and figure out what grid uh or what i don't even know describe it what cube or what spot we actually clicked on so if you imagine let me just boot this up here for one second i have to be able to figure out which one of these spots to change colors when i click the mouse right now this is pretty easy math but essentially i have to figure out based on where my mouse position is in this screen because right here it's at 0 0. in the bottom right hand corner it's at what do you call it 800 800 i got to figure out based on whatever position it is what cube i'm clicking inside of that's what this function is going to do given a mouse position is going to translate that into a row column position representing the cube that i actually clicked on so i can do things like draw a maze and all that fun stuff so let's figure out how we do that so we're going to say define get underscore clicked underscore position so this is just telling me you know where do we click so get clicked position we're going to take a mouse oops if i could get inside of here we're going to take a pause which will be the mouse position and we're going to take the rows and the width so first thing we need to do is we need to define the gap so we're going to say the gap is equal to the width over over the rows so integer division and then we're going to say i comma j equals position so essentially we're going to say okay you know like the x y we could actually do this maybe this will be easier let's go the y x is going to be equal to position and we can say rho is equal to i over over gap and call is equal to not i sorry this is y oops 2x over over gap so the reason this works is we're figuring out uh we're pretty much just taking whatever the position is in the x and wherever the position is in the y and dividing it by the width of each of the cubes so that'll give us where we are and what cube we've clicked on i i can't really explain that much more and then we'll just return row call like that so we'll be getting the row column that whatever person clicked on and this is just a helper function that is you know nice and easy to use and now we're off to the main function where we're actually going to start setting up some of these events and start drawing some things on the screen and seeing how all this works so we're going to say define main this is going to take a window and a width like that this is going to be our main loop this is kind of the usually you start with this but i just wanted to get all kind of the easy stuff out of the way all these you know basic functions and this class and the more tedious stuff before we did this so we didn't have to keep going back and changing this our main loop and this is going to determine essentially all of the you know checks that we're doing so all the collision checks all of the oh when you press space start the algorithm oh when you press on this cube change the barrier that's what we're doing inside of here so maybe a little bit more complicated but shouldn't be crazy so i'm going to start by defining the amount of rows we want to use so i want 50 rows the way i'm going to do this you can quite easily change this number to whatever you want and it'll just make a grid that has more cubes in fact i have my other example up let me show you what i mean now you know i have a hundred cubes and we can quite easily run the algorithm on this it's just gonna take a little bit longer because there's a lot more cubes so i'm setting it up in a dynamic fashion such that you know everything is completely changeable and that's why this might take a little bit longer but it's nice because you can make it as big or as small as you want so we're going to say rows equals 50 we're going to say grid equals make grid oops if we go like that what we need to pass to make grid is the rows and the width so we have rows like that and we have the width so now make grid which we just defined up here is going to actually generate the grid and give us that 2d array of spots or a 2d list whatever you want to call it next i'm going to define the start position and the end position which to start are going to be none we need to decide those and then i'm going to say run equals true and started equals false so essentially just some variables to keep track of the start and end position if we're running the main loop or not and if we've actually started the algorithm or not so now we're going to say well run so while this run variable is true i'm going to say for event in pygame.event like that and what this essentially is saying okay at the beginning of each of this while loop let's loop through all the events that have happened and let's check what they are so an event could be someone pressed down on the mouse so they press the keyboard button or a timer went off whatever events happen in pi game we're looping through them and now i'm going to check them so i'm going to say if event dot type equals equals pie game dot quit in all capitals this is always the first one you should check and what i'm going to do is i'm going to say run equals false like that and what this is essentially saying is okay if we press that x button at the top right hand corner of the screen then stop running the game and at the very bottom of this while loop i'm going to say pie game dot quit oops so pie game dot quit and what this does is it just exits the pie game window so and whenever we hit this line which will only happen when the while loop stops running do we quit now the next thing i'm going to say is if started continue now the reason i'm putting this here is because once we start the algorithm i don't want the user to be able to press anything other than the quit button so this uh while loop will be running when the algorithm is running right but if the algorithm has started they shouldn't be able to like press anything they shouldn't be able to change the obstacles like that'll mess stuff up if they do that so that's why we're saying if started continue now the next thing to check and this is really some of the only commands we need to do here is if the user pressed down on the mouse so if the user pressed on the mouse we need to potentially draw a barrier we need to do the start position we need to the end position there's a bunch of different things we need to check right because if you see the way that this works uh it's a little bit small now i apologize when i press the first and second time that does the start and end position and then i can do the barriers right and if i right click somewhere i can remove the start position and i can put it back to wherever i want and if i right click on any of this stuff it deletes it so we need to check that and there's a few checks to do here to make sure that like after i right click the start or the end position i can place it kind of wherever i want right so that is what i'm talking about and now you can see that the reason i did if started is so i can't just draw a bunch of barriers like i'm pressing down here and i can't delete the color on these squares it just happens right and actually we'll let this run just because i find it so fascinating to see this thing just go and figure itself out like look at that but hopefully that illustrates to you what we're doing here so now we need to check the mouse position so we're going to say if pygame. dot get underscore position then what we're going to do sorry not get position get pressed get position will be next and then 0 and what this stands for is what mouse button we pressed so essentially we're saying if the pie game mouse was pressed and we pressed on the left mouse button so like your common mouse button you're clicking mouse button then do something otherwise so we're gonna say elif game dot mouse dot get underscore pressed one sorry not one two which is actually the right mouse button i believe then we're going to do something else so if they press the left mouse button do something otherwise if they press the right mouse button do something and if you wanted the middle mouse button you would do it with one right so 0 1 2 left center right if you're thinking about that so that's what this says this is we'll do a comment left and this is right okay so now inside of here if they do that we're going to say position equals pie game dot mouse dot get underscore position so pos like that with a set of brackets this simply gives us the position of the pi game mouse on the screen so what x y coordinate it's at now we're going to say row column equals and guess what we're going to use this helper function that we used that we just made so we're going to say get underscore clicked position we're going to pass the position and then what else do we need the rows and we needed the width like that so there we go so now this is going to give us the row and column that we clicked on so this is what actual spot in our 2d list did we click on so now we can actually access that so we can say spot equals in this case grid and oops i've just butchered that we go grid and we go row call so we can index the row column in the grid and now you know we can do whatever we want with it so the first thing we're going to say is okay if we have not yet placed the start position we're going to need to do that right so we always do start and end position first if the start and end position aren't down when you click you're either you're setting the start or the end position that's just the basic rule if start and end are not there if they're if we haven't pressed them then make them whenever we press next so we're going to say start equals spots that's why i have this start variable up here and then we're going to say start dot make underscore do i not have a make underscore start i thought i did okay well let's go back up to our thing here and let's make make start because i don't think i added that yeah i can't just completely forgot that so define make underscore start i'm gonna go self i'm gonna go self.color equals and i think we were going with orange for start uh yeah i think so so sorry guys add that method make start uh and then we should be good to do this so now we're gonna say start equals make start and then we'll say an l if and we'll say l if not end and we'll do the exact same thing for end we'll say end equals spot and dot make underscore end so hopefully this makes sense we're saying we press the left mouse button and the start or end one is not yet pressed then let's make that the start or make that the end and we'll always start by doing the start and we'll after the start we do the end now otherwise so in another situation where the start was actually defined we've already done it the end we've already defined we've already clicked it if we're clicking and we're not clicking on the start or we're not clicking on the end so l if spot does not equal end and spot does not equal oops does not equal start then whatever spot we clicked on is just some random spot we need to make it a barrier so we'll say spot dot make underscore barrier like that and that's as easy as this left mouse button press is so now let me run this for you so i'm going to call this function down here and let me show you what we've actually done so far so let's run this i'm like confident that i'm probably going to get an error and my thing is lagging so i'll be right back okay so i had a small error here i don't know something crashed something happened but i also just realized that we just got to fill in a pass here just so i can actually test this right now because i haven't i don't have an indented block for this other mouse position and we're probably going to run into a few errors that we have to fix just because i've been coding for a while so we'll go through these together so main is missing two required positional arguments win and width so here let's pass it to it win which i think was in all capitals and then width as well okay so win and width um i don't remember if i made it in all capitals yes i did so win with we're going to pass that to our main function and hopefully now this will work okay uh so we're getting a black screen and the reason we're getting a black screen is guess what because we never called the draw function we never actually called draw which will then draw the grid and draw everything else that we need to do so what we're going to do is right at the top of our while loop we're going to call draw we're going to give it that win we're going to give it the grid we're going to give it the rows which is all capitals and we're going to give it the width so now we'll call draw every loop and this will just keep drawing everything so let's try this and there we go we get a nice solid grid and look i can even go ahead and i can make all this stuff so of course i can't delete anything now because we don't have the right mouse button set but you can see that i can press and i can do it again and let's run this one more time and i can make my start and end position and all is well and all is good so i think um that's about it now what i'm just going to do here is i'm just going to fix this because let's look at this for one second if i press so that's my start position right i can press my end position right on top of that that's no good that means the start and the end are the same and we can't let that happen so we need to handle that case so now before we actually assign the start we need to make sure that spot does not equal end and before we do the end we need to make sure that end does not our i guess spot does not equal start so that we can't override each other so let's just try it now you can see that's the changing code right there and now see it won't actually let me press it on top of each other i was trying to and you just can't actually press the spot on top of each other which is exactly what we wanted and now we can draw our barriers and obstacles and all that fun stuff so now let's do the left mouse button which is a little bit easier so we're going to say position equals and we're actually just going to copy these first three rows kind of counter-intuitive to do it but that's fine we'll just copy all of them we don't really need to worry about that too much and we're just going to say spot.reset now so essentially we have position row call and spot which i've already discussed and if you press on this spot with your right mouse button i'm assuming that you just want to reset it to be white so we'll say spot.reset and we'll say if spot equals equal start then start equals end and if spot equals equals end and equals none and i mean we can make this an l if it doesn't really matter it's going to be the same thing anyways just to make sure that we reset oh not start equals n start equals none sorry so we reset the start and end if you press on those ones because those are the two variables that we're storing so now let's run this and see what we get so i can you know right press and i can left press hey my left click is not working for some reason so i'm going to have to see whoa there's a bunch of stuff going wrong okay give me a sec guys i'm going to have a look here looks like my something's happening with this update where something's kind of working but it's not really working properly so i'm just going to have a look at this bug and see what's going wrong so looks like inside of my reset we had two equal sign instead of one so that would make sense why it wasn't actually updating the color properly so that would be the mistake there so let's rerun this because before it just wasn't actually erasing anything and now uh when i right click beautiful it actually is working properly so it looks like we've got kind of the main obstacle stuff almost out of the way here and now the next thing to do is really actually just start writing the algorithm which of course is the toughest part but the visualization tool itself is kind of ready to go and everything's set up and handled so the last thing we're going to do here is we're just going to add a event we're going to say if pygame dot event dot type actually sorry not pi game just if event dot type equals equals pie game dot key down and now what we're just going to say is if event so this is essentially telling us did we press a key on the keyboard down if event dot key equals equals pie game dot k underscore space and started equals false sorry not started equals false and not started then what we're going to do is we're actually going to go ahead and we're going to start running the algorithm so the first thing we need to do in here is we need to now go back to the spot class and we need to update all of the neighbors of the spot class so remember that what i was saying before when we were talking about how this algorithm works we need to actually have neighbors for all of these spots so these spots we need to set this up as a graph so every single node which are all these great squares need to have a neighbor beside them so they need to have something to left something to the right up down and that needs to be handled so what we need to do is make this update neighbors method inside of spot which we'll add into this list here the neighbors list all of the valid squares that could be its neighbor so let's run this and i just want to show you something's crashing let me just add a pass inside of here for right now and let me show you what i mean so like this orange square for example has this this neighbor this neighbor this neighbor this neighbor let me just move that over there these four neighbors are these orange squares neighbors right but right now they're actually not because these are barriers so we can't use a barrier as an edge which technically means right now there's no way for this orange square to connect with this green square because it's completely covered it has no neighbors so the point is that every single one of these white squares we need to determine all of its actual neighbors uh that aren't these barriers right so we can't add these barriers as its neighbors because really like say i do this these circles here all the white squares inside of these circles are now useless we can no longer use them and we need to make sure that we know the neighbors of like this white square and that we don't add this black square in there so we don't traverse through any of the barriers right that's kind of what we have to do right now it's not very it's not super difficult to do but i just want to illustrate to you what this is so let's go into uh the update neighbors and let's write this code so essentially what we're going to do is just check up down left right and see if those are barriers or not and if they're not barriers we'll add them into the uh the neighbors list so let me just go have my reference code here to make sure i don't mess this up because this is a fair amount of code we're going to start by saying self.neighbors equals a blank list and we're going to say if self dot row because we do have this it's one of the attributes is less than self.total rows minus one and not grid self dot row minus one self dot call dot is underscore barrier then what we'll do is we'll say self dot neighbors dot append and we will append this so we'll append grid self.row minus one uh and self.call now i know this seems like what the heck did you just do tim but this is i'm checking if the row that we're at is less than the total rows minus one the reason i'm checking that i'm sorry this should be a plus one not minus one is because i want to add one to the row i'm on right now to go down a row so this is going down right we're moving down a row because we start zero one two three four so on like that so we're moving down so i need to check if i can move down because if i'm on like square 49 i'm on square 50 and i try to go to square 51 and that doesn't exist i'm going to crash my program so that's the check right here and we say and not grid self.row plus one self.call.isbarrier then self.neighbors.append blah blah blah append the next row down that's what i'm doing i'm saying we'll use the same column but we'll add one to the row if we can add that to the neighbor now let's copy this exact same thing and we'll actually copy it four times we'll just update what these values are oops let's just copy that if statement okay so now we're gonna go down up is gonna be the next one it's good to comment these just so sometimes you can read them pretty quickly so down up left right so for up we're just going to change all the signs so this is going to be negative now that's going to be oops this isn't going to be self.total rows this is actually going to be a 0 and we're going to say if self.row is greater than 0 and not self.row plus one self.uh call is barrier then we'll say self.neighbors.pen grid self.row plus one uh and self.call now i realize i must i mess something up here this is a plus one and this is a minus one sorry guys so let me space these out so we can actually read this okay space like that so this one sorry if self.row is greater than zero so if we're not at row zero and grid self.row minus one because we're going up now not down i was mixing that up and this isn't a barrier then what we'll do is say self.neighbors.append the grid of self.row minus one so the one above us at the same column awesome that's all we need now instead of call we're going to say if self and said row we're going to say if self.call is less than self.total rows minus one then if not self.row so grid self.row self.column plus 1 is barrier then what we add is instead of row plus one we're going to do column plus one so now we're moving to the left this is actually going to be to the right and this one's going to be to the left i'm just butchering these so badly this is why i want to leave it to the end but this is going to the right so if we go to the right we're just checking one square to the right so we need to make sure that that's valid uh if it is append it into the neighbors hopefully i'm making enough sense to you guys and then here we're gonna do the same thing as row so if self.column is greater than zero and self.grid and not grid self.row leave it like that self.call minus1 right then minus1 we'll go there actually it will go right there okay so let me just make this clear make sure i didn't mess anything up i think this is good essentially you just have to make sure if you're greater than zero if you're greater than zero then you can subtract one without going into the negative numbers so that's fine and then we if that one that we're checking is not a barrier we can add that to the neighbors list so we don't need to return anything from this that's fine that's enough for updating the neighbors again i just butchered that so horribly but hopefully that is enough that makes sense we're just adding the neighbors to all of those things and here again is the code if you need to copy it down and pause the video or anything like that okay so now that we have that let me just go down here and we're going to call that for all of our spots so we're essentially going to say for row in grid and then for grid in row or not grid and row for spot in row spot dot update neighbors so this whenever we actually press that space key down so this is saying you know if we press the key down if the key is the space bar and we've not yet started the algorithm then for row and grid for all the spots in that row update all of their neighbors so call that method that we just created after we do that what we need to do is just call the algorithm so we're just going to say algorithm like that i'm going to pass in the arguments that we have already just because we're going to be using them inside of there and then we should be good to go so i'm going to say lambda which i'll explain in a second because this is a confusing thing i'm going to say draw and i'm literally just going to actually copy this right here i'm going to say draw like that i'll again explain why i'm passing this in a second i'm going to pass the grid and pass the start position and the end position so i've not yet made this function we're going to code that out in a second but what i'm saying is that okay once we start we're going to call this algorithm function we're going to pass a function that is equal to a function call so i'll explain lambda and then grid start and end so what lambda is is an anonymous function so if i go lambda x like that if i said like x equals lambda and then i say print inside here and i go print hello calling x will call this print function the way this the way this works essentially is like you can imagine that i'm just saying like function like if i go like def func and then it's like that so i say like x is equal to define function print hello if i call x which is just another name for this function then that's calling hello it's hard to describe this but it's just known as an anonymous function because you don't need to give it a name you can just kind of put it on a line and this is great because this means i can pass this draw function as an actual argument to another function and then inside of there i can just call this directly so again it might be a little bit confusing but just imagine that it's i'm just calling this draw function whatever whenever i call whatever is represented by this lambda lambda okay mouthful let's now go and code out the algorithm and then we're going to be pretty close to done so underneath h i'm going to define algorithm i'm gonna say draw and then i figure out what else i had here i'm gonna have to go look at this to make sure we don't butcher this so this is draw grid start and end awesome so essentially what i'm saying is i'm taking a argument here which is draw this is a function that i'm going to call so i'm going to call draw like that and the reason i can do that is because lambda was like you know lambda let's just say print hello if i said like draw equals lambda print hello this is a function that calls that function so if i call this draw function it will do whatever is here which is print hello so in this case draw as a function so i can just call the function and it will do whatever draw is hopefully that's kind of making sense but anyways that's the best i can do okay so next what i'm going to do is i'm just going to find some variables and this is where we're actually going to start coding the algorithm and there's going to be a lot of explanation so i'm going to say count equals 0 open set equals priority queue which we'll talk about in a second remember we imported that way at the beginning at the very top of our program from cue import priority queue let's move this down by the way say open set equals priority queue we're going to say open underscore set dot put now this is put instead of push or append it's just what the api is for priority queue and this just means add to the priority queue remember what the first step of our algorithm was it's to add the start node with its original f score which is going to be just zero right so we add the start node with its f score into the open set that's the first steps that's what i'm doing right now i'm going to say okay open set.put and we're going to put the f score which is zero we're going to put count which is zero and the reason i'm putting count is just to keep track of when we inserted these items into the queue that is so we can break ties if we have and if i spell count correctly here so we can break ties if we have two values that have the same um what do you want to call it or not values if we have two things inside of the queue that have the same f score we can just go based on which was inserted first on which one to consider so we have a tie breaker essentially so zero count and then start that's what i'm putting here okay so this is the actual node itself or the spot this is some number it's going to be zero to start and that's the f score which is zero so open uh set.put we're gonna say came from which is pretty much keeping track of where we came from right so what node did this node come from remember like i had you know node b came from node c node c came from node d and that's how we keep track of the path that's what this dictionary is going to do and that'll be more clear as we go next we're going to have our g score so we're going to make a table here that's going to store all of the g-scores so i'm going to say spot float in so essentially we're going to have a key for every spot inside of our g-score it's going to start at float infinity right so this just gives us infinity that's how you do infinity in python we're going to say four row in grid for spot oops in row so this is just a list comprehension this is the same as writing like four row in grid for spot in row uh g-score spot equals float imp uh if we just do like a long drawn out way but since we're going to do this twice i'm just doing it in a list comprehension or a dictionary comprehension and then we're going to originally set the g-score of our start node right so g-score of start is going to be equal to zero because of course the g-score of the start node is just zero now we're going to copy this exact same thing and we're just going to replace g with f because we need the same set up for f and same f score is going to be 0 for our start node and actually sorry the f score of our start node will actually just be the heuristics so it's not actually going to be 0. i miss explaining this is going to be the distance which is going to be the heuristic from h of our start dot get position so get underscore pause and our end dot get underscore pause so sorry this was a mistake on my part the g score and the f score are the g score is set to zero the f score will just be the heuristic because we want to estimate approximately how far away this end node is from the start node and just give that h score already so that'll be the f score for our um our end node the reason we do this is to make sure that we don't when we reach the end node uh we don't automatically assume that it's the best path i hope that kind of makes sense but just imagine that like we start the f score of our start node at infinity so sorry i miss explain this but essentially the reason the f score is just equal to the heuristic is because we do actually want to make an estimate of how far away this start node is from the end node when we begin it's not a huge deal it's not going to be super important but the reason we have that is to make sure that if we say circle all the way around back to the start node we don't take that as the shortest path because it was infinity beforehand we just take whatever we think is going to be the shortest distance which is just the heuristic again it's not huge deal if you understand that or don't understand that but just make this equal to our heuristic which is this h function right here we should be good to go next i'm going to make open underscore set underscore hash equal to a set of start now the reason i'm making a set here is because this priority queue doesn't actually have anything to tell us if a node is in the queue or not and we need to check in some sense if there's something in the queue or not so if we have a value in the queue or if we've removed a value from the queue or whatever it is so we need to have open set hash that is just going to keep track of all the items that are in the priority queue and all the items that aren't in the priority queue so i can remove an item from the priority queue but i can't check if something is in the priority queue where here i can check if anything is in it because this will just be a hash that just stores all the same things that this priority queue stores but just doesn't have the same kind of data structure implementation to give us the smallest item if that makes any sense again this is getting a little bit into some complex data structure stuff but don't worry about it too much hopefully this will make sense as we continue so we're going to say while not open underscore set dot empty so essentially the algorithm runs until the open set is empty or not so if the open set is empty then that means that we've considered every single possible node that we're going to and if we've not found the path yet a path doesn't exist that's what that says and we're going to say just here quickly for event in pygame.event.get now since we have a while loop i need to make a way that people can exit this while loop so if i say i need to just have this event thing here to let them hit that x button if they want to quit so i'll say if event.type equals equals pygame.quit in all capitals then what we'll say is pygame.quit so this again is like we already have this down in the lower section but since this algorithm here takes over and has its own loop inside i need a way to exit this loop just in case you know something goes wrong we can quit or if it's taking too long or whatever it may be we need a way to quit now after we do that we're going to say current equals open set dot and i believe i can just say get and i'm going to index at 2. now the reason i'm indexing at 2 is because our open set is going to store the f score the count and the node now i want just the node so i'm going to start at the very beginning of all of these loops by popping the lowest value f score from my open set now if there's two things that have the same f score we'll look at the count and whatever was inserted first will be what i take so that's what current is saying this is the current node we're looking at so remember same example here if we're starting at the very beginning current will start as the start node because that is the only thing that's in the open set to start so then what we're going to say is open underscore set underscore hash dot remove i think it's remove yeah dot remove current so we're going to take whatever node that we just popped out of the priority queue and we're going to synchronize it with the open set hash by just removing it from that to make sure that we don't have any duplicates or anything out of sync and messing us up next we're going to say if the current is equal to the end so if this node that we just pulled out is the end node we found the shortest path so we need to reconstruct the path and we need to draw that path so for now i'm just going to say pass and we'll deal with this after but this is going to be make path like that and we're just going to return the value true and just say okay we've found a path we're going to exit out of there so i actually don't need the pass but we are going to have to continue this after and and we'll do that later okay so if current equals n boom that's it and now next what we need to do is need to consider all of the neighbors of the current node so we're going to say for neighbor in in this case we're going to say current dot neighbors like that so if the neighbor is in our current dot neighbors right so for all of them we're going to say the temp underscore g underscore score is going to be equal to the g score of whatever the current score is plus 1. now the reason for this is because we can assume that all of the edges are one right so if we want to figure out what the temporary g-score of this neighbor would be assuming we go to this neighbor from whatever current node we're at then we take whatever the distance is this current node the the currently known shortest distance and we add one to it because we're going one more node over which is a neighbor of this node we know it only takes one value so that's totally fine and valid to do so we add one to whatever the current score is for the shortest path to this current node then what we say is we say if temp underscore g-score is less than the g-score of the neighbor so essentially in other words if we found a better way to reach this neighbor than what we had found before update this way update this path store it and make sure we keep track of that that's what we're doing right we're trying to determine the best path to get to every single node and from there we can really easily kind of target ourselves towards the end node and find the optimal path and that's what we're doing so we're saying if the g-score that we're getting by using this neighbor is less than the g-score of what we had on the other neighbor so the actual value then go ahead and change things around update the value say this is a better path so we're going to say first came from so the came from for the neighbor needs to be updated to equal whatever node we're on right now so came from neighbor equals current because it's a neighbor of the current we came from that we're going to say g-score of current is going to be equal to the temp g-score that we just have right there and then we're going to say the f-score like that oops f score is going to be equal to so the f square of current oh sorry what am i saying current this is this should be neighbor my bad guys sorry this this is neighbor i don't know why i was typing current so the g score of neighbor equals the temp g score of course that makes sense the f score of neighbor equals the temp g-score plus the h of in this case it's going to be the neighbor like that dot get underscore position because remember we need the row column position not just the spot itself and not neighbors it's going to be neighbor and then this is going to be end dot get underscore position so let me just assure that i typed that correctly yes i think i did essentially get pause remember is that method we wrote all at the beginning right here that gives us the row and gives us the column so we need to pass that in because the method that does the h if you look right here expects two positions not to spot objects so that's how that works we update the f score and now we say if the neighbor is not in the open set hash so this is why we're using the open set hash so that we can check if the neighbor is in the open set or not so it's not in increment the count because now we're adding something in so if it's not in we add it into the set so count plus equals one and we're going to say open set dot push or is it push or is it put sorry it's put and now we're going to put in this new neighbor right because we're now going to consider this neighbor because it has a better path than what we found before so we're going to put in the f score so we're going to say f score of neighbor needs to go in here we're going to put in whatever the count is we just added 1 to it and then we're going to put in the actual spot object itself which is going to be the neighbor so that goes into the open set and then the open set hash gets the same thing so open set hash dot add neighbor just because we're just going to store the spot in there we don't care about the f score and the count and then we're going to say neighbor dot make underscore closed so this is essentially saying okay we're going to make this current neighbor that we just put here closed so that we know we've already considered this neighbor and that's making me look for or sorry not closed this is going to be open my bad because we just put this into the open set of course it's not closed it's going to be open it's green we put it in the open set and then finally after this what we're going to do is we're going to tab out so outside of the for loop we're going to call draw i'm going to say if current does not equal start then we're going to say current dot make underscore closed like that so what this is going to do is essentially say i mean i just went faster but we've pretty much finished this entire algorithm so i can show you how it works in a second if current is not the start node make it closed so that's saying that if the node that we just considered and we just looked at is not the start node we just make it red and just close it off because we've already considered it and it's not going to be added back into the open set if it is it will be made open and we'll see that right so that's the idea behind this now of course we need to reconstruct the path there's a few small things we need to add but this is pretty much it and at the very end here i'm just going to return none or return false to say hey we did not find a path so that is this entire algorithm so let me go through a quick summary and then we'll actually run this and make sure it works so we have a count we have an open set we start by putting the start node in the open set we have came from this keeps track of where we came from so what nodes came from where so we can find the best path at the end g-score keeps track of again the current shortest distance to get from the start node to this node we initialize them all at infinity to start and then we set the g score of start to be zero f score this keeps track of our predicted distance from this node to the um what do you call it to the end node so going through this path so following this path with this node how long do we think it's going to take or what do we think the distance is going to be to get to the endnote and then we set the initial um so these are start at infinity just like g-score and f-score we start the initial f-score of start to just be the heuristic so whatever our guess is from the start note to the endnote which makes sense because right now it's gonna cost us zero to get from start to start so the only distance we need to go is whatever our heuristic distance is right and then open set hash this is just gonna help us see if something's in the open set and then we have our while loop that says okay while the open set's empty make sure that we're not quitting the game if we are let's quit get out of this current equals open set dot get two so what that does essentially and in fact i can actually just return from this if i wanted to uh let's leave it pie game quit so current equals openset.get2 the open set is a priority queue the priority queue is just an efficient way to get the smallest element every time out of it it has uses a keep sort algorithm i believe to do that actually and you don't have to know what that is but essentially it's just a very efficient way to get the minimum element from this queue so it gives us the minimum element whatever the minimum f score is we get the actual node associated with that or the spot object we remove that from current or from the open set hash sorry remove current from the open set hash we say if we're at the end we found the path we finished boom we're done otherwise consider all the neighbors of the current node to calculate their tentative g-score their temp g-score if that's less than whatever their g-score is in the table then update that because we found a better path and then add them into the open set hash if they're not already in there and that is the very very basics of how this works so now what i'm going to do is go ahead and run this and show you the visualization so i won't be surprised if we made a few minor mistakes and we need to rerun some stuff but let's just go ahead and do this and press space and what is the problem we're getting here so let's see what's happening update neighbors missing one required positional argument grid okay so it makes perfect sense we need to go down here to where we're calling update neighbors and just pass grid into there and hopefully we should be good now so self.spot.updatenavers grid let's run this and see what we get okay and there we go this is actually working and we have the visualization going now of course we don't have the path being reconstructed yet that's the last thing to do but we can see it hit that endnote and boom perfect it found it right and it went and we can see that it didn't consider every single node it actually just went you know pretty much right to the node and had a pretty efficient path to find that so now let's reconstruct the path which is actually going to be really easy to do and then we will be done so now inside of here i'm going to say re construct underscore path i'm going to pass came from and i'm going to pass the current node which is actually just going to be the end so we can just pass end and i'm going to pass draw now draw again is that same function they passed in let's make another function up here and let's say reconstruct underscore path let's take came from and and i was just draw okay now inside of here all we're going to do is we're going to say wow current is in came from so while it's in that list what we're going to do is not current actually yeah let's rename this current so instead of end this is going to be called current so while current is in came from which is that table that stores um you know a came from b b came from c c came from d so on so forth then what we're going to do is we're going to say current equals came from of what is this going to be current and then we're going to say current dot make underscore path and we are going to at the end of here draw okay so i'll explain this really quickly but this is pretty basic we're saying okay the current node starts at the end node we're going to traverse from the end node back to the start node the start node is not in came from it's not in there so that's fine right we don't put anything in came from for the start node so once we get to the start node we're done but essentially current will be equal to whatever we came from from the last node so from the end node what do we come from some node that's current make that part of the path draw it and then keep doing that and then once we get to the point where we're at the node that came from the start node and we hit the start node it will stop and it will stop reconstructing the path so that should be it let's run this and i'm just going to actually say end dot make end here just because if you don't do this essentially what will happen is it's going to draw purple on top of the end node and i'd rather just have us be able to see start end and then the path in between so anyways that'll make sense but let's run this and see if this works now so i'm just going to literally press space you can see boom that's the path that we discovered and there we go now one more thing that we should do is first of all let's run this and see if we can get a more complex example that works a little bit better i want to make a way to like reset this and clear the screen and by the way don't feel bad if yours is running a lot slower than this i'm on a very fast computer right now but let's go to a way to reset this so that we can just run this as many times as we want without having to close the program so this is going to be pretty easy i'm just going to make another command inside of here so unders underneath this if statement and say if event dot type equals equals pi game dot and should actually just be indented one more so not event dot type will say if event dot key equals equals pi game dot k underscore lowercase c then we're gonna clear so what this will do is it just clear the entire screen just make everything white so then we'll be good to go and good to start again so i'm just gonna make sure i'm not messing this up but i think we can just say start equals none end equals none and grid equals make grid and we need to pass what for that rows and wait okay so that should be it for clearing the way this works is we'll just reset start endnote just remake the entire grid which means that everything will just get reset automatically and then we should be good to go um and yeah i think that should literally be all we need to do um yeah so i think that's good i'm just going to add one more thing to this case space thing i don't think i need this started thing actually i haven't even used it so i'm going to say if event dot key equals python.counter space and start and end to make sure hey we have an end and a start node before we do this because if we don't that's going to crash so of course we need that first that's a necessary thing here i should have had before if we have a start and end node then we're good to go and i can remove this if started thing because we're not even going to use that so we can get rid of started okay so now we should be good let's run this and let's see what happens if i press c so c clears everything resets it let's run this and let's press c you can see it resets and then we can go as many times as we want so this is the pathfinding algorithm this video has taken a tremendous amount of time to make this is not an easy thing but a lot of you guys asked for it i think it's really cool and i wanted to make something that was just awesome that you guys could really appreciate you can mess with and i just i love these programs they're so cool they're really what got me into programming when i was a kid so i hope you guys enjoyed if you did make sure you leave a like please subscribe to the channel leave a comment let me know what you thought of the video and of course i will see you guys in another youtube video

Channel: Tech With Tim

Views: 196,785

Keywords: tech with tim, a star path finding, a star pathfinding visualizer, path finding a star python, python a star, a* pathfinding, a* pathfinding tutorial, python pathfinding visualizer, a* search algorithm, a* path finding, path finding visualizer, pathfinding, a*, a* algorithm, astar pathfinding, a star, a* search, astar algorithm

Id: JtiK0DOeI4A

Length: 93min 2sec (5582 seconds)

Published: Thu Jul 16 2020