Pathfinding Solution: a neighbors

[00:00:00]
>> The first thing that I want you to do here in this find shortest path, you can write another function that does this, or I just do it right here in line. I need to create a, basically a grid that's the same size of this maze, but that I can like add objects to, right?

[00:00:16]
So I'm just gonna write like a really, oops, don't do that. Const this maze's called visited, that's what I'm gonna call it. And I'm just gonna write this in terms of a quick map. But you could totally do this with a for loop or something like that. Actually, maybe let's even just do this in terms of, well, let's just make a whole different function.

[00:00:42]
Okay, here we go, function, Generate (visited). And it's gonna take in the maze, I think, and that's it. In here we're gonna make an array called visited. So const visited equals empty array. And here we're gonna write a for loop, for let i = 0, i is less than maze.length i++.

[00:01:35]
Okay, so this is gonna be looping over the y axis of our particular array. Cuz, remember our array's 2D. And then inside of that, we're gonna do another for loop, for let, i or let j = 0, j is less than maze( i.length), j++. And actually we could probably make this a little bit better, let's make i here.

[00:02:13]
We're gonna make that y. And then instead of j here, we're gonna make this x. Just to make a little bit, so we can keep track of x and y. Okay, and then we're going to say, Yeah, const new, or coordinate, let's call it coordinate, Is a new object that is, Yeah, it's gonna have closed, And that's gonna be if maze( y x is triple equal to 1).

[00:03:26]
Length is 0 because nothing has touched it yet, right? So we haven't actually started traversing our maze yet. And it hasn't been opened by anyone. So I'm gonna make these little variables at the top just help me keep track. So I'm gonna say const, Null_one = 0, const by_A = 1, and const by_B = 2.

[00:03:58]
And then that way I can say open by null_one. And this makes more sense than open by zero, right? This just makes it a little bit easier to read. So I'm gonna have this coordinate. Here we're gonna have this const yaxis is gonna be equal to new array.

[00:04:16]
And what we're just gonna do here is we're going to, Push into the y axis. So we're gonna say yaxis, Dot push(coordinate). And then down here after this for loop, we're gonna say, Visited.push( yaxis). Then down here return visited. So the code that I have here in my notes looks fairly similar.

[00:04:59]
I just did the exact same thing with a map instead of a couple of for loops. So let's just make sure that this actually looks like the way I think it's gonna look. Console.log, Oops, const visited = generate(visited), With maze and console.log(visited). Okay, so let's do this. We don't wanna skip this anymore.

[00:05:44]
And we'll just do that. And then we'll click play and see what comes out. So you can see here I got an array back. That's actually new to this as well with graph test. Get rid of that, okay. Back in pathfinding.test. So you can see here each one of these has length, for this one, closed false, length, open by zero.

[00:06:22]
So this all looks like it's above board. But this is all I did, right? I basically took this and I made it into my own data structure. So I can keep track of what's opened, what's not opened, all that kinda of stuff. And let's actually do this for this one as well, just so I make sure that this, 6 by 6, good news, these are all six.

[00:06:50]
And I just wanna make sure on row 4 here, sorry, row 5, That these are closed. And they are, okay, cool. So this looks like it's generating okay. So now I have a data structure that I can work with. That one should be open, open, and this one should be closed.

[00:07:12]
Close, cool, great. That works great. So now we have this generated visited maze here that we can work with. And the first thing that we're gonna do is we're gonna say, visited[ [ya], [xa])] is assigned, or, sorry, opened by A, right? So we're gonna start with our maze.

[00:07:45]
And we're gonna spiral out from there. And this looks a little weird for people, because we're used to x comma y. But just think about in the sense of that we're opening the y axis first and inside of the y axis is the x axis. That's why it's ya, xa Same thing here visited ybxb.openedby by b.

[00:08:12]
Okay, and now we'll have like on this one, we're opening this one correctly, we're opening like that, right, wherever the twos are. Okay? Then we're gonna do an aq and a bq. So let aq assigned, and we're just gonna queue up our very first note here. So visited, Actually we can just even copy this, right?

[00:08:52]
And let bq equal that. And this is just gonna work exactly like how it worked with our graph, right? We're just going to go through our aq and our bq, we're gonna spiral them out where we're going to read first traverse until they crossover with each other. So, our outer loop, how far do we wanna go?

[00:09:19]
We wanna go until we find that they meet or they don't meet, right? So we're gonna say while aq.length and bq.length. Whereas before on our social graph, we wanted to limit how far out we would traverse, in this case, we wanna go as far as we possibly can until we find the answer.

[00:09:42]
So, if we get through all of this and we don't find anything, then we're gonna say return negative one where negative one means I didn't find the path, right? There's no path between these two particular things, okay? Then up here we're gonna have an iteration number let iteration equals zero.

[00:10:08]
And the first thing we're gonna say is iteration plus, plus. This is so we can mark that, like if we're exploring here this will be one, this will be one, this will be two, this will be two, this will be two, right? That's why we're gonna keep track here of the iteration const a neighbors equals aq.

[00:10:44]
So, I wrote all these with reduces, which I don't think is the best way actually to demonstrate this. All right, so let's write a function down here before we get into this called get neighbors. Function get neighbors. So we're gonna give it our visited graph. We're gonna give it x and we're gonna give it y.

[00:11:31]
So, basically what I want to do with this function is I wanna say, if I give you a coordinate x and y, give me back all of the neighbors that exist for that particular item. So I'm gonna give it an empty array. And then basically all we wanna do here is we just wanna check to make sure that we're not going out of bounds and that we haven't already visited that, right?

[00:11:57]
So, if y minus one is greater than or equal to zero, right? So if we're going up and we're not going to negative one, right, we're not going out of bounds of our particular array. And, we haven't already visited it, right? Because we don't wanna revisit the same things over and over again.

[00:12:23]
Y minus 1 x, So this is just going up one bit on the same x-axis. Axis, it's a hard word. And it's not closed. That's y minus 1, so it's actually going left. Yep, then neighbors, oops. Neighbors.push visited y minus 1x. So we're just gonna do the same thing for all of our neighbors, right, we're gonna go left, up, right and down.

[00:13:21]
So, luckily these are all kind of minor variations of each other, right? So this one is gonna be instead of y minus 1 plus 1, okay, and instead of going out of bounds this way, we're just gonna go to visited zero.length. I'm assuming that it's a square, not a square but at least rectangular grid, right?

[00:13:48]
So it's not jagged on the edges, which is why I'm just looking at visited zero, okay? And then here will be plus 1 and that's it, right, plus 1, okay? And we're gonna do this again, but we're gonna do x minus 1 that's greater than or equal to 0 and y, x minus 1 closed.

[00:14:27]
Okay? Same thing here, this is gonna be x minus 1. And this is up. Then one more time for x plus 1. And this is for visited.length And visited x plus 1, x plus 1 and this is down. Okay? And then here, this will return to us neighbors, right?

[00:15:13]
So now we can give it any sort of visited array with x and y and we'll get the valid neighbors for us to nq after this. So, what we're gonna do here is we're gonna get the neighbors for a neighbor so const a neighbors, this is assigned get neighbors.

[00:15:40]
We have to go through axis to it this way. So we're going to say four let I, Equal zero. I is less than aq. .length, i++. And we're gonna say, Let aNeighbors, Equal empty array, aNeighbors.push, For all the neighbors in the aQueue. So we're gonna say aQueue, const neighbor, const coordinate = aQueue that.

[00:16:42]
We could have totally done it this way. In fact, let's just do it this way. Sorry, one more time. While aQueue.length, we're gonna say const coordinate, aQueue.shift, okay? So now we can have a coordinate here, and this is gonna keep going until all of this has been emptied.

[00:17:13]
And we're gonna say aNeighbors.concat, Get neighbors of visited coordinate.x and coordinate.y. There we go. Took me a second, but we got there. But the basic idea here is we're gonna go through everything that's in the queue and we're going to enqueue all of its valid neighbors. So then we're gonna have this aNeighbors, and this is gonna have to be equal.

[00:17:49]
So we have to say a, Like that cuz concat gives you back a new array, right? At the end of this aNeighbors is gonna have all of the valid neighbors on there. So we're gonna have to go and modify all of these to be opened by a with all of their correct lengths.

[00:18:14]
Okay, so let's go ahead and do that. We're gonna say, Let's even just say this, gather a neighbors. And then process a neighbors for let i = 0, i is less than i, or sorry, neighbors.length, i++. Const neighbor = aNeighbors(i). I'm seeing neighbor so many times. It's losing all meaning to me.

[00:19:10]
Have you ever had that happen to you? I think it's called semantization or something like that, where you say something so many times that you don't think you're actually spelling it correctly anymore. That just happened. All right, if neighbor.openedBy === B, BY_B, then guess what, we found the answer, hallelujah, return neighbor.length + iteration, right?

[00:19:42]
So this is just saying if I have spun out and I've encountered the next thing that has been opened by b when I'm doing it on a, it means cool, we found the path. So we add my length that I have of how far away I am from my origin plus the iteration, which is how far away you are from the other one, right?

[00:20:04]
Then you've found the correct one. All right, else if neighbor.openedBy === NO_ONE, so if this hasn't been opened before, Then we're gonna say neighbor.length, we're gonna consider this one visited, right? So neighbor.length = iteration, neighbor.openedBy BY_A, and aQeue.push neighbor. Right, so it means that we've gotten one forward, we're not going to queue this neighbor that we're looking at now for the next iteration so that we can go ahead and process it on the next go around.