[MUSIC] All right, this week is all about class design. You saw what you're gonna be doing in the project. You're gonna be working with that road data to plan routes on a map. But this week, what you're gonna be focusing on is just some very simple search and route planning algorithms. The focus this week is really on how to take a problem like that, represent it as a graph, and then build some Java classes in order to represent that graph structure. Unlike in previous assignments in our previous courses, we're gonna be giving you very little starter code. So this week's gonna help you with the process of taking a problem, that's well specified but not detailed in Java, and writing it up as some Java classes. So by the end of this video, we're gonna look at how to take a problem and turn it into a graph representation. And the problem we'll be looking at this week isn't exactly the same as you'll be working with in your project, it's a simple little map that a robot's gonna navigate through in order to find some gold. So here it is. Here is the problem we'll be working with this week. We've got a little grid world and in this little grid world, we've got a robot. And this robot's goal is to navigate the grid world in order to find the gold. And you can see that there are some obstacles in this world represented as walls and the robot is not allowed to move through those walls. So it has to find a path through this little maze, to the gold. And, of course, this problem can be represented as a graph. Otherwise, I wouldn't be talking about it right now cuz the focus of this whole course is all about graphs. So we're gonna use this little example for three purposes. Again, this is not the same exact problem you'll be working with on your programming assignment, but it's similar so we'll use it for three purposes the first is that we will use it to look at, how do we take a problem like this and represent it as a graph? It's gonna be similar to how you take your problem of navigating street data and represent that as a graph. Second thing we're gonna focus on is, how do we do some very basic searching? Through this graph, through this world here which we'll represent as a graph. In order to get the robot from its start position to the gold. And then the third reason we're gonna look at this problem is the theme of the week. The overall theme of the week which is how do we take a problem like this, which is a graph problem, and represent it like java classes. So again, the reason we're not using the project directly is that I'm going to take this problem and really walk you through turning it into some Java code. And I don't wanna give away the answers to how we would take the project problem and turn it into Java code. So what we're going to be doing this week or this, yeah this week, is going to be similar too, but not identical to the class structures that you'll be developing for your project. So, just a disclaimer, don't try to use the class structures we develop directly. Use the ideas of how we translate the problem into Java classes. So, let's get started with that first task of taking that problem and representing it as a graph. So as you know from last week, a graph has two fundamental components to it. It has some vertices, or I like to call them nodes. You'll hear me call them nodes a lot. And it also has some edges. So, in order to represent this problem as a graph we need to define both of those pieces. Let's start with the vertices for the nodes. The nodes in this graph are going to represent all of the places that the robot can be. So our robot's goal is to move around in this world until it reaches the gold, and so it makes sense to have the nodes be these individual cells where the robot is allowed to exist. So we'll go ahead and we'll put a node down in each cell in our little maze. So that takes care of our nodes. Next, we have to think about our edges. What should the edges of the graph be? Well, again our focus is on movement. And we want to move this robot through the world from vertex to vertex or node to node. So our edges in this case are going to define the legal hops that our robot can take. So what hops can the robot take? Well in our world, our robot can only move up, down, left and right. And obviously it can't move through walls. In fact, the walls didn't even get nodes, because they're not legal positions that the robot can exist. Those walls are completely blocked. So when we add our edges, we'll just add an edge for every direction the robot's allowed to move. And that graph is going to look like this. So we've just got one edge coming out of each node to an adjacent node that the robot can move to, in one step. So, there's our graph representation for this problem, and then the next thing we're going to focus on is, how do we take this graph representation and have the robot find a path from wherever it is to the gold.
