Pathfinding Visualizer Tutorial (software engineering project)

what's up everybody how's it going today is the day this is the video the long waited pathfinding visualizer project tutorial this is by far and away the most requested video that I've had if you haven't seen the video that I made about a month ago on the software engineering projects that got me into Google where I showcased my pathfinding visualizer project be sure to check it out I'll put the link in the description in the comments below but ever since I posted that video I swear I've been getting multiple comments every single day on all my other videos asking me for a tutorial for this pathfinding visualizer project this is it you have asked you have requested you have demanded and as you know I'm a public servant you demand I provide by the way while I would definitely encourage you to watch this entire video I do realize that it's pretty long so I'm gonna put timestamps in the description and in the comments below so if you want to skip to more important parts you can do that before we jump into the coding I have to say a few things first of all I have no idea how to do this project right now I rode the code for this pathfinding visualizer three years ago at the very beginning of my coding career I had only been coding for about two or three months when I did this project and if you go on the github repository for this project which is public by the way it is absolute spaghetti code you'll see that this was written in pure native JavaScript meaning no libraries like angular or react just JavaScript and of course HTML and CSS and just overall it was kind of all over the place which is fine I was a beginner but the point that I'm trying to make here is that I'm not gonna be walking you through that code we will be referencing it to kind of inspire ourselves and see what in the heck I did you know I'll probably take some animations a bit of code here and there but overall I'm gonna be rewriting this from scratch using the programming knowledge that I know today and we're gonna be doing this in react now if you don't know react don't worry about it this is gonna be a very very basic react and I'll even show you how to set up the project which is super trivial I just did it now with the create react app plug-in or whatever command it is and you're gonna be able to learn react along the way and again this is gonna be very basic react really nothing to fear and I'm gonna kind of walk you through it the second thing that I wanted to say before we start coding is what exactly we're gonna be building in this video tutorial because if you look at my current path finding there's a wiser project you'll notice that it's pretty big there's a lot of functionality right here on the home page we've got this little dialog box that explains what the project is it's got like nine pages and a bunch of text and images we're not gonna be doing that then here we've got our main grid with a start node and an end node and you can draw walls on the grid of course you can visualize here's seven or eight algorithms you can also draw mazes and patterns you can add a third node you can do things like clearing the board clearing the path changing the speed of the algorithm and you've got this little legend here so again as you can see there's a lot of stuff we're not gonna be doing most of it we are gonna be doing the fundamentals the stuff that you really need to then be unblocked to add whatever functionality you want to do so what does that mean we're gonna build the grid of course we're gonna build the start node this little arrow and the end node and I guess we'll see as we go along if we build out the ability to move them probably because that's kind of core to the app but maybe we'll leave that as an exercise to the viewer and then we are definitely gonna build building walls and we are gonna do Dijkstra's algorithm Dijkstra's algorithm is sort of the grandfather of path finding algorithms that's the algorithm that we're gonna implement we're gonna implement the animations so this stuff whoops visualize Dijkstra's of course we're gonna do the visualize button and then finally we will do the part that actually draws out the shortest path like this little yellow thing here I don't think we're gonna do this automatic recomputation of the shortest path when you drag the target node that'll probably be an exercise for the viewer but the point is once you have that core functionality of just visualizing Dijkstra's algorithm you can pretty easily add other algorithms add other functionality to clear the board reset it and so on and so forth and you can put your spin on it make this these your own project third thing that I want to say is that the reason I've been sort of pushing off doing this video is because this video takes a little bit more effort and time and concentration than most of my other videos like I said I have no idea how to do this project I'm going to try to do it right now but also I'm extremely busy I've got tons of stuff with algo expert this weekend I'm traveling unfortunately so I won't be able to do much of this at all so all this to say right now I am giving myself the challenge that I have to do this tonight before I go to bed now it is currently 958 p.m. and I have not started coding so I will not stop until I finish the code I won't edit this video tonight but until I finish this entire coding tutorial I will not go to bed so wish me luck I've got a Red Bull with me again Red Bull sponsor me if you haven't seen my previous video I mentioned that already anyway got to do it last thing before we get into coding I am preemptively hoping that you will find this video very informative and enjoyable to watch and the only thing that I ask of you in return for this video is that you be so kind as to smash the like button you really helps with a YouTube algorithm and also if you can comment down below what you think about the video that also helps with the YouTube algorithm the more engagement all those things they really do help oh and also if you're prepping for coding interviews check out audio expert oh use the promo code cleanse elem for a discount on the platform that's the sponsor for this video my company now let us begin and don't worry they're gonna be links to the github repos for this project that I'm doing in this video as well as my original pathfinding visualizer project in the description and in the comments below alright the first thing we're gonna want to do is to get a react app environment setup now fortunately react does this for you it's literally trivial to get your first react app set up and running and to just start coding just Google create a new react app click on I think the first link it'll bring you to react J's org and if you scroll down here it explains to you what you have to do you need to have node and NPM installed make sure that you have the correct versions they literally tell you here and then literally copy-paste this line I just did it npx create react app my app you put it in your terminal I just did it here and it'll take a while to run then you can CD into my app this will be the name of your directory by the way you can name this anything I named it my app you probably want to name it like pathfinding visualizer and then finally do NPM start and you will literally be up and running once you've done these things you should have your directory here with a bunch of files that they've created for you automatically and then if you go back to your browser you should have at localhost port 3000 this page that they've rendered for you and you can make edits to your code so for instance here I'll put C where it says learn to react I'll put learn react fubar save and it'll hot reload it and you can see that it says learn reacts fubar and so now I guess we're ready to start so I think I'm gonna go ahead and start cleaning up some of these files because we don't need everything here [Music] okay so what I went to head and did is I said I'm actually not gonna really touch all their files because I'm not sure if you need them I don't want to waste time with that but I deleted everything that they were rendering in the main app dot J's file and I created my own components my pathfinding visualizer component and I imported it and rendered it here and now I'm never gonna touch their files any more I'm no longer gonna touch to their abs yes I'm no longer gonna touch any of their auto-generated files I am just gonna work out of this pathfinding visualizer component or directory which I created right here in the source directory and any sub directories or whatever that I want to add in there so my path finding visualizer component right now is just the simple react component by the way for those of you who are familiar with hooks and functional components and react I'm not gonna be using that here I'm just gonna be using basic react I think it'll be a slightly more accessible to most people so here this is a simple component right pathfinding visualizer and I'm not doing anything it doesn't have any state it just renders a div that says through a node component and this is another thing that I just created here node and I haven't really put anything yet and I've created a couple of CSS files so this right now looks like this a blank page that says foo at the top so if we go back to our pathfinding visualizer what are we trying to create let me clear the board here we want to create this grid right before we can actually do any of the functionality we need this grid on the table or on the page now I forget what I did to create this grid I actually think that I used HTML table elements but I'm wondering if we can just use lead is that we kind of align one by one I'm gonna play around with the code and get back here in a bit okay so just explain a little bit what I'm doing here I've been trying to see if I can just like have this two-dimensional array of all the nodes and kind of iterate through all of them and render a bunch of this node component which is gonna be right here which is gonna be each little grid or cell but this just seems like it's not working I think I'm gonna try to go with a table component or a table htm' element and go with that I think this is what I did in my previous project so I'm gonna go look at the github repo and see if I can figure it out actually I don't think I need this I think I can go with my original strategy I'm so bad at CSS I can never remember how to put next to each other how do you Center a div again this'll have to do for now so what I have so far just a bunch of nodes that I have kind of like very naively created here with you know like 15 rows and 50 columns each and then I iterate kind of through every row and through every column and I create a node and that's how I get this grid like this but I mean clearly I'm gonna have to clean it up so I guess I've got my grid here now I mean this this code is like kind of bad right now but it does give me what I need so what should I do next maybe I'll start by actually visualizing with CSS the start node and the end node and then I'll jump into Dijkstra's algorithm I guess what I think I'm gonna do is I'm gonna create a sort of structure or interface for what a node looks like and I think a node will have a few things it'll have like a row and a column it'll have maybe an is visited property so we'll see as we go [Music] I'm gonna get rid of this little warrant react warning here by adding this key property if you have this little warning you have to add a unique key to things that are in an iterable [Music] okay so I've just installed a prettier which will autoformat my code because it's so annoying to have like react with huge wines and your JSX not formatted so if you want to do the same thing in vs code just get prettier as an extension you can look for extensions with command shift P you look for extensions install extensions look for prettier install it and then if you go to workspace settings and you look for format on save make sure this is checked off this little thing and so then when you go to your file here you see here if I have this line and I save it it auto formats it okay let's keep coding [Music] [Music] I've added a start node and an end note they look very ugly right now but basically what I did is I in my path my visualizer I set the start node and the finish node here in like I've created this object I'll probably have to move this around soon but I created this object for every node where I say hey is start is only crew if the row is number 10 so we're on the tenth row and we're on the fifth column and is finish is the same thing except if we're on the 45th column and then down here when we render these nodes I passed down as properties is start and is finish based on the node so we're only ever gonna have two one is start one is finished with the way the code is written and so then in my node component I've got this turnery here it's a little bit ugly but whatever that says hey if we have is finished that's true we're gonna have an extra class name called node finish and that's just background color red hence the red node here and if we are a node start then we're gonna have background color green okay so I'm still debating what to do next but I think I'm gonna go and implement Dijkstra's algorithm and then kind of take it from there start marking nodes as visited and so on and so forth so first I have no idea how to do Dijkstra's I forgot how the algorithm works I can like vaguely remember it but what I'm gonna do is I'm gonna look at the code that I had in the previous project so I'm gonna go look at the github repo and I'm gonna copy/paste it clean it up and see if we can work from there here it looks like it is in I think it's in browser and pathfinding algorithms see this is why it's bad to not name files like correctly like what is test algorithm why is there one that's a star but there's no Dijkstra I think Dijkstra is an unweighted search algorithms how am I supposed to find this this is like not comprehensible okay let me go back let's see where I called Dijkstra's algorithm so it's probably bored take a look at this code this is just like incomprehensible by the way this goes to show you I remember I used to be the kind of person who was like no I'll remember my code like in the future it's fine if it's like a little bit crazy like I remember it I wrote it like you know I literally have like zero recollection of ever writing this or no I do remember writing this for like understanding this is another story it looks like it is this unweighted search algorithm and we pass the current algorithm you see here oh no no Dijkstra is weighted Dijkstra is a weighted algorithm cuz let's see if we have here if we add weights if you press W by the way fun facts present W and you drag it you can add weights you use like the path can go through it but they count as like tougher to go through if that makes sense they have a weight oh yeah it is yeah I say right here it is a weighted algorithm yep whereas an unweighted would be something like in breadth first search we said is unweighted which means that I clear the board and I put oh yeah it just can't put weight nodes I just did not put like you you can't press W and put a weight node and now I'm starting to remember thank suppose algorithm is a weighted algorithm meaning that if there are certain parts of a path that you tell the algorithm I do not want to go through that part of the path because it is weighted as an example oh there's heavy traffic in this area on Google Maps right Dijkstra's algorithm can use that information to compute the shortest path this is all starting to like come back to me after like three years it's crazy if Dijkstra's is a weighted algorithm and we say if weighted algorithms so if current algorithm is bi-directional a-star we do some random stuff if weighted algorithms includes current algorithms oh my got this code we do this weighted search algorithm okay so we need a weighted search algorithm mm isn't Dijkstra yeah whoa there's a lot of code for Dijkstra's algorithm wait am I in the correct whoa okay okay let's just copy this entire what is going on here weighted Manhattan this okay we're not gonna do weighted Dijkstra's for now we're gonna do Jesus it's 1054 p.m. already okay so I just created this algorithms folder which is not gonna be like a react components I moved it out I kept it in source well who cares about that for now and in it I created this Dijkstra dot J's file and now I copied this weighted search algorithm that I had and we're gonna try to like cut out all the junk and just like create Dijkstra's algorithm once again I currently don't remember how Dijkstra's algorithm works so I have to like refigure it out and once I have it down I will explain it to you by the way as I'm filming this video right now I'm really hoping that this is gonna turn out a good video and not sound like garbage cuz we're never just feel like it's this camera filming me for like what seems like an eternity struggling to write CSS so let me know if you think this is a good video or this ended up being like really bad so I think I remember how Dijkstra's algorithm works now I just want to verify it on Wikipedia just read out an actual explanation rather than try to three figure it out from my code okay okay okay okay okay I think I remember now how Dijkstra's algorithm works basically you start at your start node and you kind of forget about your target node for a second and you say every other node on the graph in our case in this grid right is gonna have a distance of infinity to our starting node or is gonna have a score of infinity if you will but that score represents the distance from the starting node and then you say okay I'm at my stray node I'm gonna grab all of its direct neighbors so in our case it's gonna be up right down left because we're not going diagonally and in the case of like a real graph like maybe if we're in a city or whatever it might be you know roads that you can go by or we'll go through or something but for us we grab all of our neighbors and we update their distances for our neighbors they're in distance one from our starting node right and you say okay I'm gonna pick this closest of my neighbors pick one neighbor then you update the distances of all the others okay I'm gonna braid the algorithm and then explain explain it in detail once we're there okay so I think I've got a working Dijkstra's algorithm now I'm not really gonna go too far into explaining how Dijkstra's algorithm works I'll walk you through the code very quickly basically we have our grid that we take into the function we've got our start node and our finish node you start by saying hey let's just make sure that we're not in a weird eggs case where there is no start node or finish node or where they overlap but then the idea is this with Dijkstra you set the distance of every single node to infinity because you cannot reach all the nodes they're all sort of super far away except the start node the start node is a distance of zero then you say I'm gonna pick the closest node of all the nodes to visit next now of course if all the nodes have a distance of infinity except the start node that has a distance of zero and you're gonna start at the starting node once you get to your closest node the start node this is what happens here in this while loop you say I'm gonna update or first of all I'm gonna visit this node but then you say I'm gonna update all the neighboring nodes of this node in this case the nodes right above below to the right and to the left and I'm gonna say these nodes now have a distance of whatever my current distance is plus one so you update all of them right so you can imagine again in our grid it's like we had all of our nodes that were at a distance of infinity except for a starting node at a distance of zero and suddenly you update the four neighboring nodes to be at a distance of zero plus one and then you say okay the node that I was just at I've visited it I'm gonna eliminate it now you say I'm gonna grab now the closest node of all the remaining nodes again all of them are at a distance of infinity except four of them that are at a distance of one so you pick one of the four and keep doing this process now the beauty of Dijkstra's algorithm is that if you use correct data structures you can get a very fast algorithm here I'm actually not using the correct data structures typically in this thing of keeping track of whatever the closest unvisited node by distance is you usually use a mini heap a heap that keeps the minimum values right and I don't want to do that here because it's not really an effect you know the JavaScript speed of our project we're dealing with very few nodes so I'm just using an array of unvisited nodes and I'm sorting the array every time so like every time that you're about to explore and you node but you can see that I'm sorting all the unvisited nodes based on their distance and then I'm saying the closest node is the one that's like right below here but overall typically you would use a heap and so finally eventually you will reach a point where the closest node is the finish node at that point you're done with the algorithm so this is sort of the Dijkstra's algorithm that I've got here we're gonna test if it's working with the animations I haven't handled things like the wall or things like the animations we're gonna do that in a little bit so unfortunately my screen recording got messed up for this next part basically all that I did is I added the visualize Dijkstra's algorithm button this is literally just a button with an onclick handler that calls this visualize Dijkstra's method which I coded out of it later and then I also did a bit of refactoring in this file so I added this method to get the initial grid I also renamed the nodes in our state to be grid instead of nodes it's just a little bit more accurate and here I also created this create node method that takes in a column and a row and adds a bunch of property that we might need later on in the algorithm so for instance I added this distance pretty which we needed the Dijkstra's method in the Dijkstra file I realized that I'm sort of merging UI logic with algorithm logic here but I figured for this project whatever I wanted to kind of move fast but so that's what I did oh and I created constants for the rows and columns of the start node and of the finish node and the last thing that I did here in this part is in the Dijkstra's algorithm I made this method return an array of visited nodes in the order that we visited them so basically after every closest node I just append the closest node to this array of visited nodes in order and finally at the very end when we reach the finish node I return this array and this was done because we're gonna want to animate the nodes in the array in the order that we visited them then so that's what this is and that's all that I did in this part I've been spending the last like 10 minutes trying to understand why I had this bug where my closest node was equal to a thousand which was made like no sense it's because I'm doing unvisited nodes dot unshifted unshipped as a value to an array I wanted to shift the value to pop it off from the front of the array ah [Music] yep now it works okay so it looks like we've got our visited nodes in order now from Dijkstra's let's assume that we have no bugs and see if we can animate them this is an array an ordered array of the nodes that we visited in order so I'm just gonna iterate through them and with some sort of a synchronicity or a set timeout in JavaScript I'm gonna change the state you know every leg 0.5 seconds on each node and see if it animates them and of course in the node component we'll have some kind of like if is animated change to the color or something like that okay so basically where I'm at right now is we click on the button we called visualize Dijkstra which calls our Dijkstra's algorithm which gives us the array of visited nodes in order and then we call this animate Dijkstra function that goes through all the nodes that we visited in order and that says hey for every node we are gonna create a new node off of that node and we mark that one as is visited and then we update our state which is our grid with that new node so we literally like do a copy a slicing of the state of the grid I know this is not like very good from a complexity point of view but we update the state and then we say with a set time out of a hundred milliseconds with a delay of a hundred milliseconds we are going to overweight these would all they would all be delay to by a hundred milliseconds the idea is with the delay of 100 milliseconds we update the state with that new node as visited which is gonna rerender everything and we pass for every node the is visited property and then in the nodes we say oh if we're visited then we add another class node visited which is gonna have background blue but again this is actually gonna bug out this if I'm not mistaken is going to cause all of them to appear blue at the same time let's just try it what my computer doesn't crash okay so my computer is crashing but for a reason that's completely different and not sure why okay so what I said would happen did happen they all turn to blue why isn't a computer laggy okay they all turned bloomin this looks like the Dijkstra shape that we should be getting okay we're good we're good so that basically we need to we need to delay the set time out like multiply 100 milliseconds by the index of our current node so we'll do we'll do something like crap I forget closure is this not gonna work with x I here it is with let it is right I think this is to work let's try it nope it did not work right isn't it work again we are we sure it doesn't work it doesn't work why does it work I should probably put everything in the set timeout ah there now it works okay but this is way too slow so we'll do we'll go back to this look will you look at that we've got our Dijkstra's let's make it faster let's put 50 mmm let's put 20 what do we have what do I have for my animations here and whatever I'll just play around with it hey I don't want I don't want to say anything but like we got it working okay it looks like it bugs out if you go too fast let's do like 15 why does it bug out here because of the way we're updating the states maybe 20 makes more sense for now I think the way that we're updating the state is really really bad right now because we are yeah we're oh I'm probably gonna have to refactor this we're doing just like so many state updates that has to rerender so much stuff how could I do this better [Music] now I'm gonna move on to the next thing which is making the walls by clicking and dragging across the grid and then at the end if we really need to we'll refactor but let's move on to the walls so unfortunately there was another bug with my screen recording for this next part it's the last time that it happened I swear the rest of this video is not messed up so here all that I did was implement the functionality to create walls on the grid so when you click on a node you want it to turn into a wall or turn back into a normal node if it was already a wall and then when you click and drag you also want to be able to create walls that's what I did to do that I created three Mouse event listeners an on Mouse down on Mouse enter and on Mouse up which I call here in the node file on the node div and on Mouse down happens when you press your mouse button not when you release it that's on click on click is when you press and release on those down is just when you press which is what we want to create a wall where we want to just press and have it be a wall then on up happens when you release so on quick kind of emerges mouse down and mouse up and mouse enter is kind of just like hovering above an element whenever your mouse sort of enters the elements area this event listener gets called and so this is gonna be useful when we drag our mouse right to create the walls now these event listeners here are these methods these callbacks that were calling on the event are defining our pathfinding visualizer file when they're pretty simple the handle mouse down event gets a new grid where the node at the given row and column we have this helper down here but the node right here the node at the given row and column gets toggled between a wall or not a wall and it also sets this boolean mouse is pressed to true because we're gonna want this boolean because in our mouse enter we only want to make nodes that we enter walls or not walls if we're currently pressed right you can imagine that we don't want to hover all the time and make walls that wouldn't make sense so we only want to click and drag to make walls so that's why we have this boolean and then handle mouse up says hey once you release the mouse is no longer pressed and we're no longer want they're gonna want to create walls so these are the three Mouse event listeners that we have this is what allows us to create walls and the last thing that I think I showed you in the section was that even though we had created the walls we weren't actually handling them so if I look at the grid here which might look a little bit different than it did in the video cuz this is sort of the final project here so if I put walls here and I visualize the Dykstra's it's gonna kind of just go through the walls and ignore them all right back to the normal video now [Music] there we got the walls working it's as simple as adding if closest node is wall continue in our Dijkstra's function now I think we need to handle the case where we cannot get to the last node yeah that is buggy so what we need to do here is we need to do if closest node dot distance equals infinity meaning if we have literally no closest node because we are trapped in wall then we return what we return we return the visited nodes in order there so now we stop okay so we're getting really close to actually being done you definitely need to make this Styles a lot better and I do want to kind of try to make it faster because right now it's still pretty slow I'm wondering if we're not gonna be able to make it faster because of react like if we set States can we can we set state every 10 milliseconds [Music] yeah I'm afraid that we might not be able to do this with the react with said state faster than 20 milliseconds it seems like otherwise it just like freaks out because I think it's trying to rerender the entire Dom kind of think if there's a better way to do this I'm gonna put a pause on that for a second and I'm gonna try to make this a lot prettier by actually adding legitimate styles and animations why is the animation causing a bug the animation is like causing it to be pressed still see that that's so weird why is it doing that I hate when they're like incomprehensible CSS bugs yeah it's like continuing like I'm not clicking right now I think I press up I click and it's like it's still clicked my mouse up are we mousing up okay so look whoa what look it's like look like can you see this like look press and it didn't mess up it didn't bounce up why did it not mess up oh oh no I'm probably not gonna fix this CSS bug tonight cuz like I don't know what this is but that should have messed up that seems like some kind of animation problem with react or something yeah we're gonna keep the walls to this color for now but we're not gonna do any animation on them unfortunately kind of mad about that but whatever [Music] whoa okay we're gonna have performance problems with react sound a little bit upset well first of all okay CSS animations of this type when they're this many can be pretty bad if you are not like on a gaming computer I used to be on a gaming computer with my previous pathfinding project here I'm on a Mac now so even here you can see by the way like it's pretty laggy when I visualize it used to not be laggy at all that being said oh this is like exacerbated because of the react state okay I'm gonna try doing something very hacky okay let me first try to clean up a little bit of the code and then see if we can do something hacky to kind of circumvent react this is so weird why is the grid getting like more okay so the border was what was messing up the grid all right a hacked react everybody lo and behold packed so the reason it's no longer laggy is because instead of updating the states in react in the set timeout every 20 milliseconds which was causing the entire Dom to rerender or rather this entire like react component to re-render which was like the entire grid every 20 milliseconds instead what I'm doing is something that you should never do in react which is I'm grabbing the individual element and to be honest I could be doing this with a ref so that's really this is fine with a react ref it's like fine it's and I'm just updating the class of the element to node visited and it works now let's see with the animation nice not bad not bad there's something missing though like here I have like a yellow dot share of a yellow dot which is like where the algorithm is currently at I'm not really sure how I was doing that I think it's this thing that's like had it somewhere yeah visited start node blue animation I think I don't think I'm gonna get into that that's probably that's like a minor detail but it like if you really want to have this the node that you're currently at have a different animation you can probably put like a different class on it or something for a split second you can probably figure it out I will leave it as an exercise to the viewer oh look I'm happy we got it like this is looking pretty close to this giver cake now look nice oh and we can make it even go faster now she made it go faster it starts to lag a little bit but that's just because in my computer I can't really do anything about it if you want to use CSS animations you have to expect some lag but cool so what are we missing now we've got the walls unfortunately they don't have an animation but who cares there's some weird bug with that like on Mouse up with the animation I'm not gonna get into that if someone knows what that bug is then do let me know in the comments below but otherwise whatever we've got the actual Dijkstra's algorithm working oh we need to have the shortest path I think that's like the last thing that we need okay so how are we gonna do this shortest path thing how do we even know this sort of path from Dijkstra what is this Oh [Music] oh I was keeping track of a previous note okay the people demand I provide smash the like button yes I mean Dijkstra's algorithm you need a pointer to the previous note it's the parent note so it's actually not hacky it's sort of a hacky waking the code and it's certainly in my older repo but basically when you wants to arrive at the destination node with Dijkstra's you have to like work your way back in when your time to find the shortest path [Applause] let's do it okay so my current strategy is I've added I basically renamed the update neighbors method and Dijkstra's to update unvisited neighbors so I'm only getting the unvisited neighbors and ivory added the visited marks here where when we explore a node we mark it as is visited get on a visited neighbors is exactly the same but at the very end it filters the neighbor by the neighbors by those that are unvisited and then when we're updating the neighbors with any distance we mark them with the previous node that is the current node that we're at and this should eventually give us the shortest path even when we update a neighbor from multiple different nodes maybe this should work and so then once we have the visited nodes in order from Dijkstra we can call another node to get nodes in the shortest path order starting at the thinnest node and making our way back right and so I wrote this method this really just like cursing our way backwards through these dot previous node this feels like a linked list basically this is really quite the algorithm that we're writing here now I want a constant log it just to see that it's not broken and then we're gonna try to visualize it so okay let's just confirm that it's not broken okay doesn't look like it's broken otherwise we would have gotten what I make console.log in here okay buddy looks like it's not broken I just redo it one so I should I hope I'm not gonna run out of battery um let me just redo it once okay yeah so 21 nodes this looks sort of correct they're all in the same row perfect that means that that's good because like there are no walls it's normal they're sort of staff is going down the same road row ten perfect I think we are golden okay and that makes up and after me thanks Rob what's all this forty and less network equal less than or equal to visit knows a word length and here we can say SEP time when you say if everything if I is equal to visited nodes in order that length name you're done with all the other set timeouts then you something can return we return here and here will do they just we do such timeout animate so we'll do visit ten times I still is ready and you're gonna meet here told another nation that says there's not any sort is passed right thanks for petrol stack really have this here it has this here and have this here that's why I kept summer with orders and here we are we gonna do something like it already restored in this right that's video there for me before the okay we're doing this to not equals statements don't need to keep any of this hearing or either because we're doing our document get illness only I don't remove this just just go rate there's no way beautiful this go away beautiful this no lakes shortest path and we do that we'll have that be yellow let me hide it in my own my products so let's see [Music] there's a bug with the bug no he's not the fine well that brings you yes compliment that Brittany has got whoa okay ready please please okay okay okay okay okay okay okay okay okay yeah okay let's put walls let's put walls let's put walls let's see if this works if this works I'm probably gonna gonna call it cuz I'm really happy right now it works it works you should probably be a little bit slower let's put this 25 it's a wall again wall some walls walls we did it we did it we got the pathfinding visualizer working we can probably make that again even slower okay but I think I'm gonna do now is try to clean up a tiny bit some of this code because there's still some like nasty stuff and then we're probably gonna I'm gonna read through all of it to really do this sort of like tutorial part of this video probably gonna spend just five minutes cuz I said hopefully you've been sort of following and then we're gonna call it [Music] okay I actually think that this isn't that bad so I'm gonna probably stop the whole refactor thing here and just like go through the example now because this works the algorithm works it looks close enough to the project that I had for something that I did and what when did I started I spent eight or nine I forget when I started but roughly like five six hours ago and yeah so basically we did this very simply and I'm very happy that we did this a lot cleaner than my previous project of course this is much simpler of an app I don't have all the other algorithms yet all the mazes and all of that but still this is a lot simpler we did this with a total of four files basically - all the react app stuff and these files are pretty simple we've got our node component which is really the sort of simplest or dumbest components all that it has is these three like Mouse handlers and these are really just for the walls and these are passed down from the parent component the pathfinding visualizer component we also have a few like boolean that help us determine what class to put to be honest this isn't super pretty here we could do this like another way but I feel like it's flying here - just like compute the class name right here in the component like you there's an argument to be made that we could pass down this string here like instead of is finish is start as well we could pass that like type type finish type start but I don't know one thing to note is we do have to put an ID here if we want to very easily access this node with document dot get element by ID I do think that we could use a react ref here but I didn't really want to spend the time to do that right now you can Google react refs if you're unfamiliar with them they're basically like in the react way of doing document dot get element by ID and that's not another component our CSS is very straightforward the animation is by the way like they look super fancy but they're really nothing that's special like you could just play around with like all these properties that I have here just play around with them google other types of animation timing function and see what looks cool let me know if you manage to make your path finding algorithm project look a lot cooler no idea why the wall animation was messing up the on Mouse up event whatever Dijkstra's algorithm here or this file with Dijkstra's pretty straightforward we run our Dijkstra's algorithm I've added a couple comments for you if to make things a bit clearer but overall Dijkstra's algorithm is all about basically assigning a distance to all of the nodes in your grid and having these distances start infinity except for the starting node at zero and saying at any point in time what is the closest node to me typically this is done with a men heap to be very very performant or optimized from a complexity point of view time complexity point of view here we just do it with an array of unvisited nodes that we keep sorting every time and whenever we visit a new node we mark it as visited and then we say ok well now that we're here let's update all the neighbors to see which one is the new closest and that's that and we also keep track of the previous neighbor the previous node that we were at then we have this get nodes in Christ paths order that backtracks from the finish node back to the starting node to get this sort of path and then finally we have our main file the path finding visualizer file pretty simple again it keeps track of our grid in our state so we initialize it at the very beginning you can read our pure function here that initialize it it's basically just like hard coding the number of rows and columns that we have and creating nodes out of all of them and our nodes are structured here they have like a column they have a row they have your distance is visited the kinds of things they have a pointer to the previous notes they're kind of like a linked list and then we've got we've got our functions that handle the mouse events pretty straightforward you can kind of read them they sort of read kind of like English basically you know when the mouse is down we make sure that the we update them that was pressed to be true and we toggle the nodes is wall status same for the mouse enter but only if the mouse is already pressed meaning that we're dragging you know the walls and then when we click the button to visualize dijkstra we have this animate Dykstra function or first we call the Dykstra method right and passing in the grid and the start node and the finish node and then we animate Dykstra and to animate Dykstra we grab the return value of the I struggle because the visited nodes in order we do this little set timeout thing where we say like every 10 milliseconds animate the node and to animate it we don't use react because typically with react you would just like update the state and that would update all the components but that becomes a really bad performance wise because we have to re-render the entire grid every time by the way there might be a better way to do that with react that I haven't thought of like maybe there's a hack you we're not a hockey wave like oh that our waited just to update one part of the react component but I haven't I don't know I didn't give it much thought so I just went ahead and did this document dot get element by ID where we say hey for every node every 10 milliseconds just change its class name directly in the Dom the very much better from a performance point of view and I think you could do this with react breaths like I said and then once we're done with all that like when I is equal to the end of visited nodes in order right then we do the same thing but we animate the shortest path this time and that's literally like the same kind of logic except here we we update the class to be sorta Spath which is that yellow thing and we do it a bit like slower even this would be 50 and that's it this is our Dykstra our Dijkstra project again very like bare-bones right now and I will leave it to the viewer to to leave it as an exercise to the viewer to do better than this to really expand it and make it your own right you can add so much more functionality but um that's that hopefully hopefully you found this helpful if you're genuinely interested in putting this project on your resume I'd really encourage you to spend a few more days refining it adding more functionality more algorithms putting your own twist on it so that it doesn't necessarily look like an exact clone of mine but so that it looks like your own project oh and also there are a lot of EDS cases in this project that I haven't handled at all in this video like for instance not allowing the user to add walls or to move the nodes when there's an algorithm and progress or an animation in progress so these are the kinds of things that might be worth adding in your own project and it'll be a great way for you to learn react if you don't already know it to flex your front-end skills to flex your algorithm skills so great project overall I really hope that you enjoyed this video I hope that this ended up being a good tutorial I know that it was kind of weird cuz I was just rebuilding this project myself I actually had kind of fun doing it let me know what you thought about it in the comments below like I said before please don't forget to smash the like button and I will see you in the next video

Channel: Clément Mihailescu

Views: 280,844

Rating: 4.9321017 out of 5

Keywords: software engineering projects, software engineering projects for beginners, software engineering projects with source code, coding projects, programming projects, programming projects for beginners, pathfinding visualizer project, pathfinding algorithms visualized, path finding algorithm visualization, programming project tutorial, coding project tutorial, web development project tutorial, dijkstra's algorithm visualization, javascript project tutorial, dijkstra's algorithm

Id: msttfIHHkak

Length: 55min 11sec (3311 seconds)

Published: Sat Oct 05 2019