This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Pathfinding & Demonstration" Lesson
[00:00:02]
>> Brian Holt: So, what we're going to do now, I think this is really, really cool. And for the longest time, up until maybe a couple of years ago, I felt like this problem of pathfinding was inaccessible to me. I felt like I didn't have enough theory. I didn't have enough mathematics, logic, whatever you want to say, to approach this problem.
[00:00:24] And sitting down with some of my friends that worked that Netflix, they kind of started talking. I'm like wait, I can do this. I understand how to do this. And I got really excited about it and learned a bunch of stuff about it. And since learning about how to do pathfinding, it's come up in like four interviews.
[00:00:48] It is pretty useful and it comes up very frequently in senior interviews. Let's talk about what pathfinding is. I think its super fun but my definition of fun might not be yours. I sit at home and do it on whiteboards. I'm just kidding that's not really true. Actually that's kinda true but that's okay.
[00:01:11] Pathfinding. We're going to have a 2D Cartesian graph, which is just a fancy way of saying a plane that has x and y coordinates. That's really what I'm trying to say here. I think in these particular examples, we have origins starting at the top left. Cuz we write a lot of CSS and we're probably pretty used to that.
[00:01:36] I'm pretty used to that so I'm gonna make you be used to it too. And the idea is I have two points, in this case a and b. And I wanna get from a to b, right? I wanna path find all my way over there. So just sitting down right now with those particular goals in mind.
[00:01:57] I imagine many of you would be able to write some sort of naive implementation that basically says go towards it until you hit it. Which works in this particular case, right? If there's no obstacles, if there's no bends or anything like that. You could probably just say, if I need to go in a positive direction go positive, if I need to go in a negative direction go negative.
[00:02:16] And that would generally work, you would end up with something like this, right? From A, to B, I would go down until I could go down no more, and then I would go right until I would hit it. And that would be a good path finding algorithm for this particular instance.
[00:02:29] Given those constraints, this will probably be the most efficient path finding algorithm you can get. This is like go until you hit it, right? It follows, so as you imagine, people that write Google Maps don't have such simple constraints, right? You have to take turns, and there's one ways and all sorts of stuff like that.
[00:02:48] So that's what we're gonna teach you how to do today is one way to pathfind in a maze that has walls and constraints and things like that. Right? Cuz if you try and do your strategy here, you're gonna go until you hit this X And you like I can't go through that, now what would I do, right?
[00:03:11] You could probably try and go this way and then that didn't work, and then you try go the other way. Suffice to say, your algorithm goes from very simple to very complicated very quickly, right? So it would be great if there some way that we could solve this a little bit more elegantly.
[00:03:28]
>> Brian Holt: So I'm going to introduce you to some, I can never remember how to say this, Dijkstra's? Am I saying that right? I don't know, I'm sure someone online is like no it's Dijkstra's. It probably is. It's actually, might be Dijkstra's. Shit. Anyway, [LAUGH] it's this guy's algorithm, right?
[00:03:47] It's really cool. I will actually confess to you that this is not actually truly the same algorithm as I think it is Dijkstra's. What we're going to be doing is a variation, a simplification of this. But the two are often conflated, just so you know. It's not actually truly that his algorithm takes into account waitings as well.
[00:04:10] And we're not going to do any waiting or heuristics, which is another term that I will explain to you perhaps later, just not at this moment in time. So let's try this algorithm. What we're going to do in this algorithm is we're going to start at point A here, right?
[00:04:30] Like what you see right here. And then I'm gonna go one in every single direction. I'm gonna go up, I'm gonna go right, I'm gonna go down, and I'm gonna go left, right? And after I do that with point A, I'm also gonna do it from point B, right?
[00:04:48] So I'm gonna go down to point B and I'm going to go left, I'm gonna go up, and I'm gonna go down. And I'm gonna mark all of those as belonging to point A or point B. And I'm going to mark them of how far away they are from the origin, right?
[00:05:02] So in this particular case, this one's one way, this one's one away, and this one's one away, right? Cool. I'm gonna start by doing that. Then I'm gonna go back to point A and I'm going to go to each one of these. I messed up, this should also be a 2 right here.
[00:05:21] And I'm gonna one away from each one of those as well, right? Yeah, in fact you can see down here I fixed it. So, this would be 2. So, each one of those, I'm gonna go one away, right? So, this is two, this is two, this is two, this is two, and this should be two right here, right?
[00:05:39] So, it's one step further. These are two steps away from A. Do we follow? Kinda, just in a spiral fashion here. Same thing with B, I'm going to go down and mark all of these as being two away, two away. And obviously this is a wall, so you can't go through the wall.
[00:05:55] So that one just kinda gets skipped. Okay? At this point we're just gonna keep alternating. So this is three, three, three, and three. And then all of a sudden, they haven't quite crossed her but on the next iteration these two spirals are going to intersect right? At that point you have found the shortest path, right?
[00:06:17] Because that means that I can go from one, two, three, four, five, six, seven, right? So as soon as these two spirals intersect, you're guaranteed that you have found the shortest path possible between the two. It's a mouthful. Does that make sense? Right? And because you're doing these spiral patterns, you're guaranteed as soon as they intersect that it's going to be the shortest path possible.
[00:06:49] Because if it wasn't the shortest path possible, you would have found it in a previous iteration. Now, in this particular case, we technically found like five shortest paths, because you can go left first, you can go down first. It's going to vive you a shortest path. And if you ran it all the way to completion, you would have all of the shortest paths.
[00:07:11] Any questions about that?
>> Brian Holt: Cool. So let's talk about how this actually works, because you actually already know how to write the code for this. I know that because I literally just taught it to you, like half hour ago. [LAUGH] So picture these, rather than being points like a Cartesian graph, picture them as being trees, right?
[00:07:42] So if I go down here, I have A, which is at 1-1. And then it has a left child, a slightly less left child, a slightly less right child, and a right child. So it's like a tree that has four children. And what I'm doing here is I'm just processing one layer at a time for each one of these, right?
[00:08:08]
>> Brian Holt: This, hopefully, starting to go off in your head it's like, this looks a lot like breadth-first traversal, right? I have these trees that have all these children and I'm just processing one layer at a time, right? Because I'm trying to stay as close to the root as possible Because I want to find the shortest path right?
[00:08:25] You could do death first traversal and it would take you to all the crazy ends of the graph. But we're trying to find this actually as soon as possible. Ideally if you look here, when we find the answer, we never processed any of these black dots over here.
[00:08:39] Because we're trying to do this as fast as possible. You don't want to look at everything if we don't have to, right? So that's why we're doing breath-first traversal here. So that's exactly how you're going to solve it, right? You're going to put each of these children into a queue.
[00:08:53] And you're just going to keep solving the queue until eventually you find two things that, I'm gonna go from this node to this node. I'm gonna see that this node is marked by A and say cool, I found the answer, and that's it.
>> Brian Holt: Does that make sense?
[00:09:11]
>> Speaker 2: So there'd be a fourth unmarked iteration, right? And that's when you'd find the-
>> Brian Holt: Exactly.
>> Speaker 2: Okay.
>> Brian Holt: At some point, you're gonna process this node right here. It's actually gonna be processing this node. This node's gonna say this one's been marked by B. This has not been marked by A.
[00:09:30] And therefore, I've found the answer. I'm going to end the iteration.
>> Brian Holt: Now, in this particular case, I'm just going to ask you to find the length. I'm not going to ask you to find the actual path. I don't want you to return to that because there's a lot of different right answers there.
[00:09:48] But if you were trying to find the actual path, you would just be storing the path on nodes as well. Like, how did I get here, just so you know.
>> Brian Holt: Cool, so yeah, you just keep enqueuing all the immediate children until you run out of things to process.
[00:10:05] And that's it.
>> Brian Holt: I will say that you're gonna have two different queues, right? You're gonna have a queue for A and you're gonna have a queue for B. There are clever ways to write this code so that you only are using one loop. Don't do it, just write two different loops.
[00:10:26] It's just a lot simpler and a lot easier to read. So that's what I wanted to tell you. I want to show you this because I think it's really cool. So, this is called breadth-first search. I was trying to be a little coy about what it was called.
[00:10:42] [LAUGH] So that's why these are two different things. Breadth-first, and extras. But if I have two nodes here and I'm going to just put a wall between two of them, and I'm not going to allow diagonals. In this case I'm asking to not do diagonal. But as you might imagine it's relatively similar you just, instead of enqueuing four things you would enqueue eight things.
[00:11:11] And then you can see what it looks like. This is unidirectional.
>> Brian Holt: If you just do one, it's a little less effective. So if I, now I'm gonna say bidirectional, which means look at both of them at the same time.
>> Brian Holt: As soon as these two intersect, then I know I found the answer, right?
[00:11:34] But that's what it looks like. Hopefully, that helps to visualize what's happening there.
>> Brian Holt: Questions about that?
>> Speaker 2: So Dijkstra and Breadth-First are different?
>> Brian Holt: If you do Dijkstra's algorithm with no waiting. So when I say waiting,
>> Brian Holt: I think in this case. Yeah, I mean, there's a little bit of difference there.
[00:12:06] Let's see if I can show you. This is more of what I was thinking of. So you could be a little bit smart about this. Typically the best path is going to be the straightest path, right? So you could put some sort of weight so that it tries to go towards it first.
[00:12:20] Right? And that's what I'm saying is that dykstras can account for that. And breath-first is purely blind like just spiral until they meet. Cuz the problem with this is what happens if I have something like this where it's going to try and go towards it first. It's going to be less efficient when it does it that way.
[00:12:46] Cuz it's going to try to go towards it first before going away. Anyway.
>> Brian Holt: Nonetheless they're all still doing a spiral in some direction, right? They're just kind of being choosy about which ones it's enqueuing. So that's really fun to play with, you should definitely check it out.
[00:13:05] There's a bunch of different path finding algorithms. This is just the simplest to code up which is why we're gonna do that one. And then I definitely would invite you to go do A*, just investigate A*, which is the one that I just showed you.
>> Brian Holt: If you wanna see the difference, I put a Stack Overflow answer to answer your question about what the difference is.
[00:13:27] Because I had that question, too, that's why I Googled it.