This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.
Grid Class
Loading...
来自 Rice University 的课程
Principles of Computing (Part 2)
206 个评分
从本节课中
Searching and Data Structures
This week, we will explain the importance of searching. We will also explore various data structures and learn about inheritance.
与讲师见面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[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.
