[MUSIC] Welcome to class. In this lecture, we're going to talk about grids. So a grid is a partition of a 2D domain into a rectangular collection of cells. You've already used grids, used a grid in 2048, you used a grid in tic tac toe. This week we'll use a grid to simulate zombies chasing humans. The basic idea is by splitting up 2D domain into a smaller collection of cells we can do very simple computations to understand what's going on inside a single cell and then we just have to figure out how various cells interact with each other. In this lecture we'll look at three things. We'll talk about an example where we're trying to simulate lots of balls bouncing against each other in a 2D domain. Then I'll just walk you through an implementation of a 2D grid class, and then finally we'll use that 2D grid class in to a very simple but interesting simulation. Let's go to it. Okay, to motivate our, discussion of grids,. I've got a class page here that we're going to talk about how to simulate a collection of balls bouncing around inside a closed rectangular domain. It's basically ball physics. So what I've done is, I've built a program, and we can pop it up here. And what this program does is, it creates a frame. And if we click in the frame,. We spawn balls of fixed radius. And these balls move around at some random velocity. And when they collide, they bounce off of each other. And so you can see this nice simulation of all these balls moving around. Now, how does my code actually do this? Every time we update this diagram, what I do is I go for each ball and I check to see- If it's collided with any of the other balls. So if we have N balls, you can do a little counting and see that the number of collision checks that we're going to do is roughly N squared. To kind of point out the effect of this, what I've done on the class page is I've gone through and I've plotted some graphs here. And this graph kind of shows you the time to do kind of all the ball,ball collisions for one update. And the actual numbers here are as important as to notice as the shape of the graph. This graph actually has a quadratic shape. It reflects the fact that if you double the number of balls, the time it takes to do all the ball, ball collisions goes up by a factor of four. In fact you can kind of see this more tangibly if you divide this by N square, you can see that this graph is essentially going towards the constant. So the running time of algorithm can do ball, ball collision is quadratic. Okay what does this have to do with grids? In the second part of the math notes I've gone through and I've re-implemented my algorithm for computing the ball,ball collisions through part of our ball physics code. Just pop it up here and I'll run it. The idea is we're going to take the domain and we're going to basically partition it into a grid of cells. Each of these cell's size is equal to the diameter of a ball. So, let's add some balls. [SOUND]. Okay, and we'll stop the code. So, what's going on inside this code using a grid? The idea is, for example, that this ball's center lies inside this cell. Okay, this ball's center lies inside this cell. This ball's center lies inside this cell. When I'm trying to find all the balls that could possibly collide with this ball, the only balls that I need to consider are those whose centers lie either in this cell. Or it's eight neighbors. So that allows us to bound very easily the number of balls that we have to test for collision. If you look at this and do a little computation, you can easily show that the maximum number of balls is 36 that could actually kind of be assigned to these nine cells, and in fact, it's probably more like 16. So, this allows us, when we're doing the collision computations, you don't have to look at all N of the balls. We can just simply look at a small fixed number. So, if we go back and we look at our diagram, over here, what we see is that, if we plot the time it takes to do one update for all the balls. The time grows linearly as a function of the number of balls. 'Kay, in fact you can see over here, I've divided by N. 'Kay? So this is nice, because now if we double the number of balls, we simply double the running time. For this particular application where we have maybe 40 or 60 balls, it's not a big deal. But imagine if you're playing a game where you have 1,000 objects or 10,000 objects. You're doing these kinds of collisions. Having doubling versus quadrupling is actually a very important factor. All right, let's talk a little bit about the mathematical representations for grids. So, here we have a class page on grid representations. You may have seen it before when you looked at 2048. A grid is a partition of this 2D region into a disjoint collection of cells. For this lecture the cells are just going to be rectangles and we're going to have a rectangular grid of these cells. The grid will have a height that's kind of the number of cells that we need to stack vertically. And it'll have a width, the number of cells that we need to stack horizontally. But index then starting at 0 to height minus 1 and 0 to width minus 1. We're going to follow Pythons condition, conventions here. So I wrote a program that lets you kind of visualize the indexing scheme that we're going to use. So we're going to have two indices here. The first index is going to correspond to the vertical position of the cell. We'll go from top to bottom. The second index is going to kind of index to the horizontal position, we'll go from 0 to 9. So this grid is a 6 x 9 grid. Now you might ask, well. Why do we reverse these? I mean, when we do Cartesian coordinates, we always have the first coordinate corresponding to the kind of the horizontal position and the second coordinate corresponds to a vertical position. We're being consistent with the ordering that is used when you do matrices in linear algebra. The rows of the matrix, are numbered in ascending order as we go from top to bottom. The columns of the matrix are numbered in ascending order as we go from left to right. So we're going to do is we're going to essentially index our grids in the same way that matrices are indexed. [SOUND] Okay. We're going to be working with grids a lot during this week so what we've done is we've actually built you an implementation of a grid class that we'll use in all of our provided code and that you should use. So, let's walk through it for just a second. We have two constants. Empty and full. Those correspond to the con, possible contents of the cell in the grid. We have an initializer. It takes the height and the width of the grid. And creates a 2D list, who's values are empty to start. We have a string method. It provides basically a human readable string version of the grid. Notice that we use \n to introduce new lines. We have. Two getters, they give us the height and width of the grid. The [UNKNOWN] used those to actually, help draw the grid. We have a collection of getters, and setters. The only thing interesting to know here is, we always refer to a cell in terms of its' row, and column. The two most interesting methods that we've built, is a method called four neighbors, and a method called eight neighbors. Four neighbors returns the neighbors of the cell that are to the left, to the right, and the top and the bottom. You can kind of look at how we manipulate the indices here. Now you'll notice there are some conditionals here. We don't always return exactly four cells as the four neighbors. That's because a cell can be on the boundary. If the cell, lies next to the next boundary. Left boundary of the grid, there is no neighbor to the left. So we might only return three neighboring cells, in that particular case. Eight cells, takes the four neighbors, and actually adds in the four, extra neighbors that are adjacent diagonally. On the final method that we have here, is get index. This is the only method that actually, refers to, where the grid is actually embedded. If we take a point, in where the grid is embedded, say, on a canvas, and we give the size of the cell of the good. We actually get back, the indices, of the particular cell, that contains the point. Alright, let's look at a simple example of using a grid to simulate something interesting. So, here, we're looking at Conway's Game of Life. This is not Milton Bradley's Game of Life with the spinner that you play with your five year old. This is a simulation. It's technically called a cellular automaton in which we have a grid. And the cells in the grid are either alive, those are the black cells, or dead, those are the white cells. And, in the simulation, we update from generation to generation. We change the state of the grid, here in each step of the simulation. And, the rules for computing one generation from the previous generation are actually quite simple. So we take a cell and we look at its eight neighbors. If the cell is live, and it has fewer than two live neighbors, it dies due to under population. If we have a live cell and it has four more cells that are alive, out of the eight neighbors, then that cell dies due to over population. That has if a live cell has exactly two or three neighbors, it's all good. You stay alive. Most interesting rule is if we have a dead cell in exactly three of its eight neighbors are alive, then that becomes a live cell due to reproduction. So when you run this simulation, what comes out are actually quite interesting kind of. Examples of how this grid is updated as the simulation proceeds. Here's an example of a configuration that produces a collection of cells, these are called gliders, that kind of crawl across the grid. People have studied the Game of Life quite extensively. What we're going to do is we're going to look and how we can use our grid class to implement the \Game of Life very easily. [SOUND] Okay lets finish off lecture and look at an implementation of the game of life that uses our good class. So here's the code. We import a module that corresponds to our provided grid class. We also import a gui. We have two constants empty and full. Those correspond to dead and alive cells. We have one class called the GameOfLife. It's a subclass of our grid class. it has all the methods that our grid class has plus two new methods. The first method update Game of Life computes one generation from a previous generation. The only thing to note here is that it computes all the new cell values. Assigns them to a temporary grid then takes that temporary grid and assigns it back into the original grid. We can't go through and update the cells one at a time because there might be interactions between successive updates. Update cell, here, updates a single cell. Here's the critical rule down here. This simply implements the rules for the Game of Life. A cell is going to be alive if it has three living neighbors. Remember we're going to use the eight neighbors here. Or it has two living neighbors and it itself is alive. We can run the code [SOUND] so we can click and drag and create some living cells. And now we can step, and we can watch what happens. So the interesting about this is it's very hard to predict one generation from the next and so in fact the reason this is called the Game of Life is because the cells kind of, [UNKNOWN] it looks like some kind of small maybe single-cell organisms moving or reproducing. This is been kind of an interesting mathematical problem that people have studied for a long time. For us, the critical aspect of this was to know that it was very easy to build the Game of Life using our base grid class. And so we're going to do that in the next lecture, we talk about grid search.
