Coding Challenge 51.1: A* Pathfinding Algorithm - Part 1

What I want to do is have my example demonstrate and animate the process, so I'm going to do something a little different than what's probably found in the Wikipedia pseudocode I'm using. I forgot to mention that I am using a JavaScript framework called P5 and as a whole. P5 asks you to write a configuration function which is kind of a start and I make a canvas and draw is a function that repeats, it's an animation. Repeat what you would normally do with a similar set or request an animation frame or something and with native JavaScript, so what am I going to do?

What I need to do is use the draw loop as a loop, so if I go back to this

part

icular page we can see here where that loop is. There's this loop here while the open set is not empty, so it's doing this. uh solve the problem so ah so this is what's happening open set closed set so this is a concept that is

part

of the

algorithm

that is quite important we have this idea of ​​an open set which is a matrix or a map or a list or whatever data structures you're using, I'm going to just use an array and we have this closed set idea, so the idea is that the closed set stores a list of all the nodes that have finished evaluating, so this is all that is done. that it is not necessary to ever revisit that it will be closed set open set are nodes that still need to be evaluated we need to consider and evaluate them they are not closed yet the

algorithm

ends when the open set is empty there is nothing left to evaluate, well, in actually that is not entirely correct, then the algorithm is finished.

There are two ways the algorithm could end. One is that I'm going to search through nodes and if I ever get to the end, I'm done because I got there. in the end I found the optimal route there, that's how this algorithm works; However, if I have nothing left open to review, there is nothing left to look at, and I haven't reached the end, I have to stop it too. means, um, that means there's no solution, so we might be able to build a, you know, a path, a maze of obstacles with no way to get to the real end, so if there's nothing left to evaluate, you're not there. in the end. so these are important the open set the closed set starts as an empty open set starts with just one node right at the beginning the open set only has uh only the starting node so let's go into my code again and create.

I'm going to make some. of these global variables just so we can see them in the console if necessary or evaluate them in a closed set, so I'm going to create two arrays, an open open list, an open set, an open set and a closed set, and what do. What I'm going to do here in the settings is I'm going to say uh oh, this is a little silly. I'm going to make a start and an end, so the start I'm at is going to be the top left, the start node is grid at 0 0 and the end node is Grid in columns minus one uh rows minus one so you know that They can be chosen randomly or through a variety of other ideas, but the idea is that I want to start here and I want to get there, I want to find the path from the top left to the bottom right of the window.

Okay, so what should I do? I need to say open, configure, press start, so we start with open, open. set, I'm going to look at, uh, that's what I'm going to iterate and check all the possibilities, okay, so let's look at the algorithm that we're going to talk about in a second gcore that we're going to talk about that, uh fscore, these are a lot of things, but this is where I really need to start. I have to say that as long as the open set is not empty, as long as there are places to evaluate, let me start evaluating those places, so the thing is that I don't need a while loop, remember that I am going to use the draw loop, like this which since the draw is already looped, I'll only say if the open set is not empty, so I'll say it the way I'll say it. is uh if the open set is greater than the open set. length is greater than zero great we can continue otherwise there is no solution right I'm going to say there is no solution there is nothing left that doesn't have G there is no solution now which I also want to do just because I want to debug this as we go is I want to write something where I draw all the points on the grid and maybe debug somehow this will be good for debugging so I'm going to write another double.

Loop, this is a long problem. By the way, this is going to be a long type of video. Are you still watching? This could be like multi-part, but I don't know, maybe I should make multi-part videos. Don't know. okay, um grid i j and I'm going to display, so I'm going to write a function, each place will have a function to display uh and what I'm going to do is say uh this. function show equal now ah, so how can the place be displayed? It doesn't know where it is, so I'm going to give each place an This will become important later and then in the show function, I can draw a rectangle on this. x this one I give, but here's the thing, uh, I have a kind of scaling problem which is that if my window is 400 by 400 but I only have 10 columns of 1 in rows, I need to calculate how wide each cell is, like this that I can do that with some global variables, just make a variable W and H and um, what do I do?

What I'll do is say that W is equal to the width divided by columns and the number of columns, right, if it's 400 and I have 10 columns, each point is 40 pixels wide. H is the height divided by rows, okay, this is pretty good, this is pretty good, etc. so I just want to multiply by that W, multiply by that H and then have the width and height. I probably only need one variable to be honest because I'm making everything a square, but whatever, let's say Phil 255 plot zero and let's run this. Again we can see that there is my grid.

You know, maybe what I should do is I'm making myself ridiculous. Here I should leave everything as one pixel left so I can see the full grid, but whatever to give you an idea, there's the grid, okay. good job, okay, so what I want to do is also do a little bit of debugging, so what I'm actually going to do is make this display function a color and forget about the stroke. I could keep the line, but no. stroke, then what I'm going to do is every time I call the show function I'm going to use a color, so in my debugging I could say I want everything to be white, but I also want to look at the closed list and I also want to see the open list or the closed list and the open set, the closed set, the open set, whatever, I don't remember what they're called, uh, and I'm going to say, closed set, indexi doow, and I'll put them, you know, in green. or closed will be red I guess someone will come up with more beautiful and interesting colors and nicer design options and the open set will be um uh green for open and now if we do this, oops, no, Stoke is not defined, hey, No, Stoke, man, that.

It doesn't make any sense, there's no trace, we're doing well, so we can see that things are getting better here now. I can see it's my open set. Nothing is closed yet, so I want to have this because I want to be able to debug it as it goes along. I need to draw things to see how the algorithm works and also this will open up a lot of interesting visual possibilities for you guys, okay, okay, so let's move on now, what do we do? We have to start thinking about this algorithm so let's go back to Wikipedia um pseudocode the idea here is okay current should be the node in the open set that has the lowest F so in other words um other words I want to evaluate here I am I want to evaluate everything the open set possibilities and what has the lowest F, what will be the best to get me to the end, so how do we find what is the f of something and what is the lowest F?

So the first thing I can do is say for VAR I. is equal to zero I is less than Oops I is less than the open set. length i++, then I'm going to say that our lowest index is equal to zero, so I'm going to assume that in the open set you know there has to be something in the open set. I'm going to assume the lowest is the first, the winner. The Record Keeper. You know, I could say winning rate or whatever. I don't know what to call it. Lower index. You probably have a variable name in the pseudocode, so what I'm going to do now is what I need. to say if op set. uh uh index if it is less than the lowest index set by op.

The lowest index is so long, let's call it winner, winner. F, if it's lower, then the winner is fine, so we're seeing if we have which one is the lowest, that's good, it's an easy algorithm. Go through everything and find the one that's the winner, okay? What do we do next? The first thing is we have to say that if the winner is the end, we're done, so let's add that right here, if the winner of the set of operations is equal to n, remember that the end is a variable that holds on to that last place, so console.log is fine, so that's where We're done, so we start with the open set, we look at all the POs, all the things in the open set, what is best, if the best is actually the end, then we are great, so we finished well, now the next one. everything is fine, so we want whatever we find current to be the node in the open set that has the lowest F sore, so you know what I need to do.

I should say that current VAR is equal and this is really a winning index. I'm going to say open set winner winter winter is coming, except not for a while, when is the sixth book coming out? Does anyone know, okay, another, another topic for another time, so if it's current and I have a lot of typos here, remember if you want to test if something is. equals in JavaScript you need to use double equals if you really want to test if you really want to be sure use triple equals so if current is the end we are done otherwise what do I want to do?

I want to add a closed set push current and then I want to say open set remove current only, this is not any real code so here is one of the tricky things I want to do is there is a function in JavaScript to add a particular object to a array that is pushed there. There's no function in JavaScript to just arbitrarily say hey, if it's in the array, delete it and this is where I'm not going to do things as optimally, but what I'm going to do is find that object and delete it and just I'm going to write a function remove from current open Set array, so I'm going to write my own function.

I'm going to paste it right at the top here uh function delete from array I need an array of functions uh element and then what I have to do is loop through the array but I want to loop back through it. I'll say And in a second uh I is the length of the array I is greater oh length of the the array minus one would start at the end until it reaches zero and if the index of the array I is equal to elt, then the array splices i1, So what is it? I very quickly wrote a function that loops through the array to see if it has that spliced ​​element. a function to remove a particular element by adding an index of the array and I just want to remove that array, someone in the I'm sure someone can tell me a better way to do it but maybe it will work for now.

I'll go back and optimize that later, but why am I reviewing it backwards? The reason I check it backwards is that if I check the array forward and delete something, then all the elements come back and I'm going forward, I might skip an array, so I skip an element, so I want to check it backwards, so that we want to eliminate it. uh, open, set, wait, where are we?, uh, remove from array, current, from open, Set current, add to close, set, great, so now. What do we do if I go back to the algorithm? I need to find out.

I need to find out. I need to find out what it will be. What should I add? What should I add to the open set? What do the new nodes do? I need to evaluate and if we think about this correctly if I just went if I started here correctly if this is the grid we try to fill a little bit more of this so it doesn't look so empty if this is the grid What I want to do I just evaluated this is my best node because it only had one option that just entered the closed set and exited the open set.

Now I need to figure out what are some of the nodes I need to check next, it's anything. that is neighbor of that particular node this this or this as long as they are not nodes that we have already checked or finished before, okay, so how do I get the neighbors? I need some way, I'm on the wrong keyboard. I need some way to find out what all the neighbors of the stream are, well, I guess I think a good way to do this would be to add a function on uh, let's add, uh, let's add an array, so let's have each one. keep track of your name neighbors and let's add a function called add neighbors and what I'm going to do is do things like okay, so add neighbors from a particular grid, I'm just going to pass it uh and then what am I going to do?The way I'm going to do it is I'm going to make this a global variable again so I can evaluate this. things, I'm going to say the path, uh, path, path, and what I want to do when I find the PATH, where there's so much code here, it would be nice to organize this better.

I'm going to say that the path is a new array and while I'm going to say VAR, I don't think I can mess anything up by playing with the current, but I'm just saying that the temperature is equal to the current because or the end and as long as the temperature has a previous right as long as there is a prior of what I must do and then I must also say path. push the temperature that should follow. push previous temperature and then temperature equals temperature. previous So this is an algorithm that does this in my head here a little bit.

I think I need to explain this properly. What I'm doing is starting with an empty list and I'm going to put the end in the list and then the end is connected to the previous one so that it goes in the list and that one is connected to the previous one so that one goes in the list, as long as there is one before put the previous one in and now what I'm checking is the one that was before so this is a nice little algorithm to go back down that path and then what I should be able to do is when I'm done I should be able to say if um I don't know where do I want to draw this.

I'm going to do this down here, uh, four and it'll be better, um, sorry, I'm scrolling like crazy, I'm just going to initialize the path as an empty array up here, so I want to say whenever, oh no, I can say that I want to traverse the route and I want to say the index of route i. show with a color uh 0255 so again I'm not thinking about the colors the Clos set is red the open set is green and the path is blue so let's see what happens here uh oh you know what I should Always evaluate that path, why.

It is not correct to see what the current route is. He will only do it when he reaches the end. Makes sense. It makes sense as a route. I think I have to check. I feel there is a bug in the code. So one thing it is. I'm realizing that I can terminate and I can say "no Loop" to stop the loop, but there's no reason why I shouldn't just evaluate what the current path is at each frame and in fact I can do that right here, so let's go. Do that, what am I doing? Okay, so I think things are really working and maybe we'll see some improvements if I want to add a few more things to the code and also add some roadblocks, so let's move on. with this, so what I'm going to do is a couple of things that I want to do first of all, this is not really an act, a good heuristic, where is my heuristic function here?, is to use the Ukian distance, which in It's really just a kind of measurement. that distance isn't really accurate when I can only take non-diagonal steps like this, so there's actually a distance called Manhattan distance or taxi distance that simply measures the difference in x and the difference in y, like so let's say Let me put that legal in which I think is going to give us some results that are going to look a little bit more like what we might expect um, so I'm going to put that in so that that's the absolute value of I um minus G the difference between the I values ​​or the covers all this space is because in some way, the top and the bottom are equivalent, so it ends up checking everywhere, but we will be able to see here that if I were to just change the endpoint, for example, in uh, where do I set the final? the final point to like the third to the fourth row, then actually what you're doing is optimally finding that path very quickly, you don't have to check all the possibilities because what are we? we're using the AAR algorithm so there's a couple of things I want to add to this number one let's add some hurdles so the hurdles really help us understand how this works and number two um let's think about adding diagonals like well and How does that work if we add diagonals?