Pathfinding Exercise

[00:00:00]
>> Okay so I'm gonna give you these graphs here. And I want you to find the shortest path between these two different things. So everything that is a two in this is point A or point B, right? It's one of the points I want you to find the shortest path between the twos.

[00:00:21]
And anything that is a one, is a wall right? So you can't go through ones. Okay, and these just get more and more complex. And I also give you if you wanna check the edge cases right? So this one for example they're right next to each other, and in this one it's actually impossible.

[00:00:46]
But again, this is extra credit down here so don't worry about this I'm more concerned about these ones. This one, it's kinda hard to see but this is actually a spiraling graph right? So the two here is, this is possible but you can see here it spirals through this wall.

[00:01:02]
So this one's pretty difficult. I would recommend just taking this one at a time, right? So instead of saying all these all at once, I would just start with the four by four. And then I would just say, start skip this one, .skip this one, and .skip this one down here and just worry about the 4 by 4 one at first and then worry about the 6 by 6, and I would work for it that way.

[00:01:33]
The other thing that I gave you here is I wrote this ridiculously colorful logger. So if you want something that's gonna kind of help you visualize what's happening with your maze, this will help you. You have to give it an array of arrays, sorry an array of objects.

[00:01:58]
And that has to have an opened by and a number, zero means no one owns it. One means it's owned by A and two means it's owned by two. So let's see if I can, there we go. This is what this object has to look like for this logger to work.

[00:02:18]
The close to be true or false where if it's true it's a unpassable wall. And then the length is how far it is away from the node that you're tracking. So let's just pop in here and I can show you what that looks like. Log maze there and log maze there, okay?

[00:02:46]
And then let's run these again so you can kind of see what that looks like. Play. So this is what it ends up logging out is these mazes. So you can see this as the 15 by 15 one, 0 0 is where it starts right? And 0 0 here.

[00:03:09]
The green ones are visited by A, the red ones or pink ones are visited by B. So that's what this logger thing will do for you. It'll show you step by step, you can see the path finding algorithm working here, right? So these double dots represent places that it hasn't visited yet.

[00:03:29]
And the Xs represent the waltz. So use that if you want to you don't have to. I just found it easy for me to kind of visualize how things were pathfinding. Okay, any questions about any of this?
>> Besides being fun, why is it useful?
>> There, I have found, well I guess one is just applying breadth traversal.

[00:04:01]
And I'm actually trying to show you less why pathfinding and mazes is useful, and I'm actually trying to have more show you why breadth first traversal is just used everywhere and you probably don't even realize it. Like the ability to find how near something is to something else is extremely useful.

[00:04:17]
So that's probably the core concept I want you to take away from that. Secondly I have been asked this exact question in interview with large tech company that probably shouldn't tell you which one it was, but one you've heard of we'll go with that. So this will be useful in interviews, to it is fun.

[00:04:38]
[LAUGH] And do I have reason number three? I don't know. If I guess you end up working on the Google Maps team this will probably be something that you might think about. But beyond that, I don't know if I've actually had to find how near two things are on a graph before.

[00:04:57]
I have had to use, graph traversal, but not necessarily pathfinding.