[MUSIC] Welcome to class. In this lecture. We're going to talk about using grids to do Spatial Search. And now when I mean Spatial, we're going to think of our grid as modeling some kind of geometric domain. And then building a search that moves through the cells in the grid to locate some objective. We'll start off by exploring why 1D search is easier than 2D search. So, we'll do, kind of, interesting example of doing a 1D search. Then, I'll show you, kind of, a similar example in 2D and try to help you understand why doing 2D search is hard. Then we'll look at some code I've provided that actually does 2D search on a grid and then we'll finish off the lecture by talking kind of about a fundamental algorithm for moving over grids and talk a little bit about how this extends to graphs, which are the subject of algorithmic thinking. [BLANK_AUDIO] All right, I promised you an example of a one dimensional spacial search and kind of to illustrate why it's easy to do one dimensional searching. So last summer I took my family to Europe and we spent a few days in Paris. And one of the highlights of the trip was to walk down the Champs Elysees. And my daughter, who is a teenager, was very excited because there was an Abercrombie and Fitch on Champs Elysees. So we said here is how we will find it. We will start at the Arc de Triumph and walk down the street and eventually we will have to pass by the Abercrombie and Fitch. So let's just try to do that in Google Maps. [INAUDIBLE] Arc de Triomphe. Let's click, let's click, let's click, and there I am. Oh, good, I'm in Google Street View. And there it is, the Arc De Triomphe. And straight ahead is the the Champs de Elysees. So let's just start walking. We walk down a little bit, and let's stop and look around. And now big bus, excellent. And, let's keep walking, keep walking. See if we see anything interesting. I see a few shops, nothing promising though. Let's walk some more. let's walk some more. Let's walk more time, take a look. Mm, still nothing that looks interesting. Let's walk again, walk again, let's take a look. Excellent, this [INAUDIBLE] bus [INAUDIBLE] Let's walk a few more times, and continue onward. A gravy truck. Let's see what else, look around, see if I find anything interesting. Oh great. McDonald's. We found McDonald's. Well, it turns out that the Abercrombie and Fitch was a fair bit further down the avenue. But this points out that there's really a simple strategy for finding something that's on a one-dimensional path. You just traverse the path, and eventually you have to pass by what you're looking for. What I'll show you next is an example of why 2D Spatial Search is difficult. Okay, I promised you an example of why 2D search is difficult. So let's imagine we're 500 years ago. So the first thing I'm going to go here and do is I'm going to turn off the map. So we're sitting here, this is Paris. If we kind of scroll over here a little bit, here's the English Channel. We've heard the news that, to the west, there's a vast expanse of unexplored land. So we're excited and we're going to pop in our ship and we're going to sail west and find that land. And in fact, we've heard news that there's a colony at Plymouth, which is very close to Boston. And so we want to sail to that colony. So, here we go. We're sailing west, we're sailing west, we're sailing west. We're sailing along. That's a lot of ocean there. We're sailing west. And then, we come to the next land. Hm. That doesn't look familiar to me and which way do we need to go? North or south? I'm going to guess we go South. Let's go south. I'm getting nervous here. Let's get going. Oh, wait a second, wait a second, this looks familiar. Let's turn on the map. And, sure enough, there's Boston, there's New York. We've been successful. This search points out the difficult of searching in two dimensions. Before we just walked on a simple one-dimensional path and we just checked to make sure if we passed what we needed. Here, when we sailed west, kind of the best stretch we could hope for is to kind of aim maybe to the north of where we're hoping to land and then, sail south and look for our target. If we happen, unfortunately to end up landing south of our target and sailing south, we're going to be in bad shape. Okay. So, what we'll look at next is a different method for doing 2D search that's going to avoid this difficulty. I promised you an example of a 2D search that would avoid the difficulties of the 1D strategies that we used previously. So here I've got an interactive demonstration of how this works. This is going to model the way a fire burns. So I can go over the canvas and I can click. And what I've done is I've essentially set a few of the cells on fire. Now, if I click the step button, I can cause the fire to spread. And so you can see here that every time I click step, I take one of the orange cells, it's kind of the boundary of the fire, and I look at the four neighboring cells, and check to see if I can, the fire can spread. So as I click this, you can see that the fire spreads outward. And it spreads outward in an interesting manner, it kind of spreads outward in kind of a uniform speed, it's not fingering outward in one particular direction. This is an example of a search called a Bedford search and that's what we'll talk about for the rest of the lecture. We can actually do ten steps at a time and we can watch and the four fires will actually merge to form a single fire. The way we implement this is we have an underlying grid that actually stores the yellow cells. The orange cells on the boundary of the fire are actually stored in a cube. On each step, every time we click the step button, we dequeue an element off the queue, we check to see for its four neighbors. Which of those neighbours are not yellow? They haven't been burned. Those that are unburned, we add to the queue. And then when we're done, we basically take this cell and turn it yellow. That simple algorithm allows to kind of visit all the cells in the grid in a very nice, kind of outwardly growing manner. So, let's now take a look at the code and see how this works. Let's look at the code that implemented the demo that we just experimented with. Here's the code. We've implement, imported, a grid class. We've imported a provided queue class and we imported the gooi. Empty cells are going to be unburnt cells, full cells are going to be burnt cells. The class wildfire, really just a subclass of our provided grid class. There are a couple things to notice in initializor that are interesting. We're using this particular syntax here to actually call the initializer for the grid class to set up our grid. We have an auxiliary queue which represents the boundary of the fire. Kind of moving on down. We have a few methods that allow us to manipulate that boundary queue. And, really the most important method is down here, update_boundary. This is the method that's called whenever you click the step button in the demo. The way this works is it dequeues an element from the boundary queue. It computes the four neighbors, so it's going to be a list. You can uncomment this and get the eight neighbors if you'd like. You might, might be worth experimenting with the demo with this uncommented. And for each of those neighbors, we check the following. We check to see if it's unburnt, if the cell's empty. If it is unburnt, we set it to be burnt and we added it to the boundary. This is the entirety of how the search works. It's very important that you understand this code. Spend some time experimenting with it, play with it. You're going to use this code in this week's mini project. You really need to understand how this works. Okay, let's finish things off by talking a little bit about kind of mathematically how Breadth-First Search works. Let's finish off lecture and talk a little bit more about Breadth-First Search. So here we have a page in the math notes that talks more about Breadth-First Search. It's going to talk about a little higher level, we're not going to specialize it for the Wildfire demo. But the fundamental idea is the same. We have a grid, it'll have cells that either visited or unvisited, that correspond burnt or unburnt in the wildfire demo. And we'll have a cue that's going to kind of correspond to the boundary of the search. here, we have a high level description of the algorithm for Breadth-First Search, this is basically pseudo code. But you should really see the body of update boundary sitting right here. We take our queue, we dequeue something. We make it to current cell. We look at all the neighbors of the cell that can be either four or eight. We check to see if its not visited. That would be unburnt. If it is, we make sure it's visited, that would correspond to being burnt. And then we add those cells back onto the boundary. If you look at this outer loop here, the, the way the search works is, we just continually pull things off the front of the queue, until, the boundary queue is empty. That means we've searched every cell in the grid. The, the search that we're doing here is actually applicable to a much wider range of mathematical structures. The grids that we're working with this week are actually an instance of a more general mathematical creation called a graph. So a graph is a collection of notes and edges. We can kind of visualize graphs in the following way. We have these circles with numbers. Those are the notes in the graph, and then we have edges that join adjacent notes. This is really what's going on in a grid. We have cells, those correspond to the nodes, and then adjacent cells are basically paired up by edges. The beautiful thing about Breadth-First Search is this also works on graphs. And in fact, there's a whole wide range of graph algorithms. And that'll be a major topic that you're going to look at inside algorithmic thinking.
