0:18

Now, a grid is just a partition of a 2D region into a collection of

Â disjoint cells.

Â That sounds really mathematic, but you have lots of experience with grids.

Â You play games a lot,

Â the games you're going to look at in this class, a lot of them are played on grids.

Â 2048, it's a grid of square tiles.

Â Tic-Tac-Toe, it's played on a three by three grid.

Â 0:40

Your last project, the 15 puzzle, again a four by four grid of squares.

Â We'll even build a simulation for how zombies behave.

Â And it's going to again, work on a square grid.

Â 0:50

In this lecture,

Â I'm going to talk a little bit about the terminology we're going to use to

Â work with grids.

Â And then I'll show you a very simple example of

Â some code that works with grids.

Â This should be helpful when you have to implement the second part of 2048.

Â All right, let's talk more about some of the terminology that we use with grids.

Â So, in this class we're going to work exclusively with rectangular grids that

Â are composed entirely of squares.

Â So we'll talk about a grid of a particular size.

Â We'll say something like a three by four grid.

Â And what that means is it's a grid that's three cells high by four cells wide.

Â 1:27

I built a program that kind of shows an example of a grid of a particular size.

Â In Code Sculpture, you can hit this link here.

Â And I've actually run it and

Â here's an example of a grid that is six cells high by nine cells wide.

Â 1:51

So, what's the numbering scheme we're going to use for our grids?

Â It's going to look very similar to the numbering scheme you

Â might have seen from matrices.

Â If you've ever done linear algebra, it's a rectangular array of numbers.

Â And the way matrices and indices are indexed by rows and by columns.

Â So the first index indicates a row and the second index inditate,

Â indicates a particular column.

Â So for example here, the element 3,2 corresponds to a cell which is on the 0,

Â 1, 2, 3 row, and the 0, 1, 2 column.

Â 2:47

Okay.

Â I've built some code that creates and works with a grid.

Â Now this is going to give you an idea about how we actually,

Â tangibly work with grids inside Python.

Â So spend a few minutes to understand this.

Â This will help you when you're working on your mini projects in this class.

Â To begin with, we've defined, we're defining a grid who's height is 4 and

Â who's width is 6,

Â this is going to be a rectangular grid, it's going to have square cells.

Â 3:11

This statement right here is probably the most important one in the whole program,

Â it's actually creating the grid in a single line and the way

Â we're doing this is we're representing a little grid as a list of lists.

Â And we're building this list of lists using a nested list comprehension.

Â So that's what's going over, going in here on the right-hand side of this statement.

Â 'Kay. In particular,

Â take a look at this expression right here.

Â This is a list comprehension reiterating over the width of the grid and

Â we're building a list who's length is GRID_WIDTH.

Â 3:42

Now, the outer comprehension is taking all, each of

Â those lists of length GRID_WIDTH and spilling a new list of size GRID_HEIGHT.

Â So we're really building a list of

Â lists here when we're actually representing our grid.

Â 3:58

Okay, we've built a grid.

Â Now, let's do something with that grid.

Â So, what I've implemented here is a function called traverse_grid that

Â walks through that grid and picks out a subset of the cells.

Â In fact, it behaves in a way very similar to what you'll need to do for 2048.

Â In 2048, when you hit an arrow key, what you'll need to do is,

Â you need to apply your merge function to a collection of

Â cells that either correspond to a row or a column.

Â Instead of writing a separate piece of code for a row, and another piece of code

Â for a column, what I want to show you is how we can do this with a single function.

Â 4:32

So traverse_grid is going to take a starting cell, so

Â a place where we're going to start walking from.

Â Okay, and that's going to correspond to kind of a component that's a row and

Â a column.

Â And it's going to give me a direction, and that direction is going to have two

Â numbers, it's going to be a two bull, it's going to correspond to how much we

Â should move in the first component, that corresponds to row.

Â And then, how much we should move in the second and

Â that corresponds to how much we should move in a column.

Â 4:55

And notice those numbers can both be non-zeros so

Â we could actually move diagonally and then this last premise should be the number of

Â cells that we need to actually pick off.

Â So the code is really straightforward.

Â It's sitting right down here, it's a loop, it just iterates through the number of

Â steps and we need to compute the row and the column of a particular cell we

Â want to, want to actually look at for a given step.

Â And the way we do it is we take the first component of the starting cell and

Â we add to it the step number times the first component of the direction.

Â 5:26

To get the new column, same thing.

Â We take the second component of the starting cell, this column index and

Â we multiply the step times the second component of the direction.

Â Kind of how we want to stride in the second coordinate.

Â And then I have some print statements down here which actually print out what we've,

Â what we're looking at inside this example grid.

Â And notice here,

Â we're always storing in the example grid just a sum of the indices.

Â So, then, next, let's go out and

Â actually look at some examples of how we can use this to strive through the grid.

Â 5:54

Okay, to finish up,

Â I've written a function here which actually runs some examples.

Â So the first thing I've done here is I

Â have written some code that actually just prints out what the grid looks like.

Â So over here you can see the values that are stored in the grid.

Â Notice it's just the sum of the row and

Â the column index for each particular entry.

Â You might look at this code if you're trying to print out the values in

Â a particular bridge you're working with on one of your mini projects.

Â 6:16

The next four chunks of code here actually just called traverse_grid with

Â various parameters.

Â So, to kind of help you visualize what's going on, I've got a little picture here

Â of a four by six grid that I've made with my code from the previous notes.

Â And what I'd like to do is,

Â I'd like to print out the indices of the first row in this grid.

Â So we're, this first row would be row 0.

Â So it'd be like we had 0,0, 0,1, 0,2, 0,3, 0,4 and 0,5.

Â So the starting cell should be 0,0, and the direction should be

Â that we're going to, essentially, leave the, the first entry alone.

Â So it's going to be 0 and then we should like to stride in the second entry.

Â 'Kay? That means the value of 1 and

Â we're going to go with the GRID_WIDTH here.

Â So if you see that, it's actually printing out over here,

Â 0,0, 0,1, 0,2, 0,3, 0,4, 0,5.

Â Okay, let's try to print out the second column.

Â So that would be 0,1, 1,1, 2,1, 3,1.

Â So the starting entry would be 0,1.

Â And the direction would be, well let's see, we want to

Â increment the first component by one and leave the second component alone.

Â So 1,0.

Â 7:25

What if we wanted to actually do this second row in reversed order?

Â Well, what we want to do is, we would want to print out 3,1, 2,1, 1,1, 0,1.

Â And so to do that, we would start at 3,1.

Â That's this value right here.

Â And then we'd like to decrement the first component each time we stride.

Â So that would give us a direction of minus 1,0.

Â 7:45

And even more importantly, if we'd like to do something where you move diagonally,

Â we could go through and say, start at 0,0.

Â Hit 1,1, 2,2 and 3,3 so start value would be 0,0 and the direction would be 1,1.

Â So notice, with a really small piece of code,

Â I've managed to build something that can kind of iterate through a linear

Â sequence of cells in the grid without much difficulty.

Â So, think about this when you are writing your code for the full version of 2048,

Â try to avoid lot's of code duplication.

Â And try to use an approach similar to what I'm talking about here.

Â