Pathfinding

[00:00:00]
>> This is going to be very similar to graphs. This is gonna be very similar to breadth first traversal. So keep those kinda things in your brain while we're working on this, okay? Imagine you have a six by six grid looks something like this, right? And you wanna get from point A to point B, okay?

[00:00:19]
So that's a 11 to 26, where 00 is this one, we'll always do 00 on the top left. How would you do that? Like what algorithm would you write right now to get from point A to point B? I imagine most you just say, go towards it, right?

[00:00:41]
So just say like, all right, I'm too far to the left and then too far up, assuming you start from A so just go down until you run out of space to go down or you're on the correct level, and then head right. That would work, right? Cuz there's no obstacles here.

[00:00:58]
They will just go here, here, here, here, or you could do it the opposite saying, go right until I'm on the right thing and say go here, here, here, here and then you'd arrive, right? Seems like it would work, right? Okay, yeah, exactly. This is what we diagram out, you just go down until go there, it's five.

[00:01:21]
That would be the shortest path between point A and point B. Now, what if we add a wall in the middle there? That gets a lot harder, right? Cuz if you try and do this, you're gonna go here and then you're gonna hit a wall. Okay, well, you could try to be exploring the wall and say, okay, I can't go that way, this way, down again and then right again, I'd find it.

[00:01:49]
So we could probably write some really basic, go left and right to try and get around the wall kinda thing. But as you might imagine, this is gonna spiral out of control really quickly. What happens if there's no a wall that you have to go all the way down and then back up and around right, or what happens if there's all sorts of various different walls?

[00:02:09]
Cuz I could really easily trick your algorithm, at which point you'd be writing so many special cases that it would just be an absolute mess of code. Wouldn't it be better/easier if there was just some algorithm that we could write that allowed us to always solve these problems?

[00:02:28]
So let's try something here and it's called Dijkstra's algorithm. And the first thing I'll say is we're actually not gonna do precisely Dijkstra's algorithm. Dijkstra's algorithm actually allows you to be even more clever, but we're gonna be doing like the most basic implementation of something that could be considered compliant with Dijkstra's algorithm.

[00:02:52]
And the idea here is that you spiral outward from your points until you find a place where they meet. So what we're gonna do instead is we're gonna go to A and we're gonna explore one in every direction. Then we're gonna go to B and we're gonna do the exact same thing.

[00:03:10]
We're gonna explore one in every direction. We haven't met yet. So we're gonna go back to A and we're going to go one more in every direction. So this is to a way, to a way, to a way, to a way, to a way, right? Assuming we can't go diagonal, right?

[00:03:30]
The same thing was 0.2, 2222. Eventually, just going kinda that spiraling outward. We're gonna find this point here where this three and this three might meet. And all of sudden now we know a path because we've spelled out where from both of them that if we go 1, 2, 3, 3, 2, 1, we have found the shortest possible path between these two points.

[00:04:05]
So this might look to you kinda like breadth-first traversal and that's because it's actually precisely to what it is. The name of this algorithm is breadth-first pathfinding. And Dijkstra's algorithm is really just that doing breadth-first traversals. Just with adding the ability to add weights onto all those various different points, you can say, go towards it first and then try and go left, or you can add some heuristics to how it works.

[00:04:35]
And ours, we're just doing dumb just spiral out until you find the where it meets. So you can think of all these points like 1, 1, it's basically a graph, right? It's a graph of coordinates that connects to other coordinates in the graph. So all we're doing here is we're just spiraling out of our graph and we're just checking all the children in a breadth-first traversal sorta pattern, okay?

[00:05:05]
This is basically tree traversal all over again. We're just using coordinates instead of using connections on our network or nodes in a tree. There's a really cool visualizer here that I linked too down here in the bottom that, let's see, bidirectional. And let's just draw a line between the two of these.

[00:05:31]
And you can say start search and it'll show you except that's not what we wanted to do. That's you want breadth-first search. Don't allow bidirectional start search. So this is literally what you and I are doing together. And then eventually when it finds somewhere that these meet, it'll take that path as the shortest path.

[00:05:59]
And like this can handle pretty difficult situations that you put it in. So now, if we were trying to go directly to this, we would have a hell of a time getting out of our little box here. But with this, it just spirals outward, until eventually finds the space, until it keeps spiraling, until eventually it's gonna find some way to get there.

[00:06:26]
Now as some of you might be saying like, that looks like it's kind of inefficient, cuz once you start getting to these really deep traversals, yeah, it gets a little weird, right? Which is where some of these other ones, like this is Dijkstra over here. But this just allows you to put some more weight on going towards something instead of going away from it.

[00:06:55]
But there you go. Okay. So I also linked a little Stack Overflow here if you want somebody to decline the difference in depth between breadth-first search and Dijkstra's algorithm. So this is still gonna work the same way, where you're just queuing like, you're going to add something to a queue, and then you're gonna process all the items in the queue.

[00:07:23]
This works just like the graph, this works just like breadth-first traversal. You're just using coordinates instead of using people in a social graph. The other thing that you need to keep track of is what has been visited by what. So I need to keep track of that this point has been visited by A cuz what you need to check as soon as this one is found you to say, okay, I'm point A, this has been visited by A and this one's been visited by B.

[00:07:52]
And then when you find that both of them have been visited by different coordinates, then you know that you found the shortest path there. So you're gonna have to do some strategy of keeping track of this has been visited by A, this has been visited by B and this has not been visited at all.

[00:08:08]
So, again, be really inspired by what you just did with graph, cuz the algorithm works pretty similar.