Four Semesters of Computer Science in 5 Hours, Part 2 Pathfinding Exercise
This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Pathfinding Exercise" Lesson
>> Brian Holt: So, I think actually what's something useful for you to see,
>> Brian Holt: Nope.
>> Brian Holt: So, this is a lot longer, this is gonna be about 80 lines of code,
>> Brian Holt: A bit less, maybe like 50.
>> Brian Holt: Yeah, so you're going to have this function called findShortestPath, right, and it's gonna return a number, right?
[00:00:39] It's gonna return the integer of this took seven steps to get from here to there.
>> Brian Holt: I do have a visualization tool. I was wondering why that wasn't working. That's what it is, it's in the console. So,
>> Brian Holt: Let's see if I can make this maybe a little bit smaller, so it gets on one line.
[00:01:08] There we go.
>> Brian Holt: So this is the first exercise. You can use this tool, as well. You'll have to follow the way that I do my data structures, but if you want to, it's available to you. You can see 00 and 00, this is where it's actually the two points are trying to go to and you can see how it spirals until they meet.
[00:01:30] And then once it meets, it finishes, right? So in this one, there's a bit of a wall, it spirals out until eventually they meet there. And then the last one here, you can see is a huge spiral that you have to get from this part all the way around the spiral and out and over there, right?
[00:01:48] And you can see down here that it slowly fills up each one of those.
>> Brian Holt: So if that's what you want to do, if you wanna use that, you have to go over to completed and you have to copy over the log maze function, which will do that for you.
>> Brian Holt: But, nonetheless,
>> Brian Holt: Let's go down and take a look at these data. So this is what I'm going to be passing into you, right?
>> Brian Holt: You want to get from one 2 to the other, right? And you can't go through 1s. So 0s are open space, 2s are origin points, and 1s are things that you cannot pass through.
>> Brian Holt: I gave you,
>> Brian Holt: A 4 by 4, a 6 by 6, an 8 by 8, a 15 by 15. And then if you're feeling brave and wanna see if you do some of the edge cases, like what happens if they're next to each other, right? And what happens if it's an impossible maze cuz at that point, you can't find it, right?
[00:03:07] So if you run one of the queues to completion, right, and then at that point, you know for a fact I'm boxed in. I can't get to the other one so then you would return -1. But you can see here that I've described it so it's not going to run until you actually wanna do it.
[00:03:23] But again, I'd recommend tackling these one at a time.
>> Brian Holt: Any questions about the requirements here? So it's going to be passing into the maze, which is going to be that array of arrays of numbers that I just showed you, right? It's gonna be giving you the first origin, the second origin.
[00:03:44] It doesn't actually really matter which is the first, which is the second. It's one origin and the other origin. And then from there, you should return the shortest path, which I would do iteratively if I were you, but that's up to you how you choose to solve that.
[00:04:00] And the last thing that I wanted to say is that I give you this data structure. You're going to have to make some more complicated data structure than this. Cuz you're gonna have to be able to say, this has been visited by this number, this is this far away.
[00:04:13] So you can see, again, if we go into the completed one,
>> Brian Holt: I have a function in here.
>> Brian Holt: Well, I think it's useful to talk about. So the first thing I do here is I create this visited data structure, right? That's definitely something that you'll wanna do, is have some more complicated data structure.
[00:04:37] This has like, is it closed, right? Is it something that I can't pass through? The length away from the origin opened by, so I keep track of, was it opened by no one? Was it opened by A, or was it opened by B? And then the x and y, so, some sorta data structure like that I would suggest doing.
[00:04:56] And then this is also a very useful function to code up as well, getNeighbors. So if I give you 1,1 this will return to you 1,0, 0,1, all of the different neighbors to do. And they'll also check is that a wall? Can I go there? I would suggest doing something like getNeighbors as well.
[00:05:16] It makes it a lot easier that you kind of contain all that insanity to one function.
>> Brian Holt: This is difficult. I don't expect you to finish this. But I would expect you to eventually finish this at some point in the future. It's good to do, so, cool.