代写Python的小游戏，按照规则来模拟细胞的生死，算法也算是经典算法。
Requirement
The Game of Life is a cellular automaton invented by John Conway, a
mathematician from the University of Cambridge. The game of life is not so
much a game in the traditional sense, but rather a process that transitions
over time according to a few simple rules. The process is set up as a grid of
cells, each of which is alive or dead at a given point in time.
At each time step, the cells live or die according to the following rules:
- A cell that has fewer than two live neighbors dies (because of isolation)
- A cell that has more than 3 live neighbors dies (because of overcrowding)
- A cell that is dead and has exactly 3 live neighbors comes to life
- All other cells maintain their state
Although these rules seem simple, they give rise to complex and interesting
patterns. For more information and a number of interesting patterns see
http://en.wikipedia.org/wiki/Conway’s_Game_of_Life
.
In this assignment, you will implement a Python program to run the Game of
Life.
Thinking about life…
As always, it is important to break the problem down into pieces and develop
the program in stages so that others can understand the code and so that you
can ensure that each piece is correct before building on top of it. We will
break this problem down into the following steps:
- Creating a 2d array of cells
- Displaying the board
- Allowing the user to specify an initial configuration of cells, listing coordinates of the cells that are live at creation.
- Implementing the update rules for the Game of Life
- (Optionally) Running and stopping the simulation.
Before you start, you need to develop a scheme for keeping track of your data.
Basically, the data you need to maintain are the states of all of the cells in
the board. To do this, you should keep track of this data in a 2D array of
integer values, where 0 represents an empty (off) cell and 1 represents a live
(on) cell.
Step 1: Creating an empty 2d board of cells
First, consider a function for creating just one row:
def createOneRow(width):
“”” returns one row of zeros of width “width”…
You might use this in your createBoard(width, height) function “””
row = []
for col in range(width):
row += [0]
return row
—|—
This function offers a starting-point for creating one-dimensional lists— but
the same idea applies for building nested list structures arbitrarily deep.
createBoard(width, height)
—|—
Building on this example, write a function named createBoard(width, height)
that creates and returns a new 2D list of height rows and width columns in
which all of the data elements are 0 (just a Python list!).
Avoid re-implementing the createOneRow function! Rather, use createOneRow
inside your createBoard in the same way that 0 is used to accumulate
individual elements in createOneRow. Here is a template – copy and paste this
and then fill in the parts you’ll need to complete it:
def createBoard(width, height):
“”” returns a 2d array with “height” rows and “width” cols “””
A = []
for row in range(height):
A += SOMETHING # What do you need to add a whole row here?
return A
—|—
That’s all you’ll need! Again, the idea is to follow the example of
createOneRow – but instead of adding a 0 each time, the function would add a
whole row of 0s, namely the output from createOneRow!
Test out your createBoard function! For example,
>>> A = createBoard(5, 3)
>>> A
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
Printing your 2d board of cells
You no doubt noticed that when Python prints a 2d list, it blithely ignores
its 2d structure and flattens it out into one line (perhaps wrapping, if
needed). In order to print your board in 2d using ASCII (we will use graphics
once it’s working…), copy this function into your file:
import sys
def printBoard( A ):
“”” this function prints the 2d list-of-lists
A without spaces (using sys.stdout.write)
“””
for row in A:
for col in row:
sys.stdout.write( str(col) )
sys.stdout.write( ‘\n’ )
—|—
This printBoard function bypasses Python’s behavior of placing a space between
items it prints by using different calls in the library: sys.stdout.write
outputs a character to the screen. This is why it needs to convert the
integers in the array A to strings before writing them. Make sure your
printBoard is working as follows:
>>> A = createBoard(5,3)
>>> printBoard(A)
Adding patterns to 2d arrays…
In order to get used to looping over 2d arrays of data, copy this function
named diagonalize(A) into your file:
def diagonalize(width,height):
“”” creates an empty board and then modifies it
so that it has a diagonal strip of “on” cells.
“””
A = createBoard( width, height )
for row in range(height):
for col in range(width):
if row == col:
A[row][col] = 1
else:
A[row][col] = 0
return A
—|—
This function, diagonalize takes in a desired width and height. It then
creates an array A and sets A’s data so that it is an array whose cells are
empty except for the diagonal where row == col. Try displaying the result with
>>> A = diagonalize(7,6)
>>> A
[[1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0]]
>>> printBoard(A)
Take a moment to note the direction the diagonal is running—that indicates
which way the rows of the board are being displayed: top-to-bottom, in this
case. Also, this example shows that the height and width do not have to be the
same – though it’s certainly ok if they are.
More patterns…
innerCells(w,h) Based on the example of diagonalize, write a variation named
innerCells(w,h) which returns a 2d array of all live cells - with the value of
1 - except for a one-cell-wide border of empty cells (with the value of 0)
around the edge of the 2d array. For example, you might try
>>> A = innerCells(5,5)
>>> printBoard(A)
—|—
Hint: Consider the usual pair of nested loops for this one – except here,
the ranges run from 1 to height-1 and from 1 to width-1 instead of the full
extent of the board!
randomCells(w,h) Next, create a function named randomCells(w,h) which returns
an array of randomly-assigned 1’s and 0’s except that the outer edge of the
array is still completely empty (all 0’s) as in the case of innerCells. Here
is one of our runs – note the safety margin.A = randomCells(10,10)
printBoard(A)
You might recall that random.choice( [0,1] ) will return either a 0 or a 1.
You will need to import random to use it!
copy( A ) Each of updating functions so far creates a new set of cells without
regard to an old generation that it might depend on. Conway’s game of life, on
the other hand, follows a set of cells by changing one generation into the
next.
To see why copy( A ) is a crucial helper function for this process, try the
following commands:
oldA = createBoard(2,2) # create a 2x2 empty board
printBoard(oldA) # show it
newA = oldA # create a false (“shallow”) copy
printBoard(newA) # show it
oldA[0][0] = 1 # set oldA’s upper left corner to 1
printBoard(oldA) # the upper left will be 1
printBoard(newA) # but newA has changed, too!!
Here we have made a copy of oldA, where we have named the copy newA. However,
newA is simply a copy to the reference to the original data in oldA! As a
result, when oldA’s data changes, so does newA’s data, even though we never
touched newA’s data!
The above example shows shallow copying: the copying of a reference to data,
rather than making a full copy of all of the data.
Making a full copy of all of the data is called deep copying. For this part of
the assignment, write a function named copy( A ), which will make a deep copy
of the 2d array A. Thus, copy will take in a 2d array A and it will output a
new 2d array of data that has the same pattern as the input array. To make
sure you output new data, use createBoard to get a brand new array of the data
in the computer’s memory, but it will have a deep copy of that data. Make sure
your copy function is working properly with this example:
oldA = createBoard(2,2)
printBoard(oldA)
newA = copy( oldA )
printBoard(newA)
oldA[0][0] = 1
printBoard(oldA)
printBoard(newA)
This time, newA has not changed just because oldA did!
innerReverse( A ) Copying is a very simple – and not overly interesting – way
that a new generation of array elements might depend on a previous generation
of elements.
Next you’ll write a function that changes one generation of cells into a new
uter edge of cells are always all 0. However, for inner cells - those not on
the edge - where A[row][col] is a 1, the new array’s value will be a 0 - and
vice versa. Try out your innerReverse function by displaying an example. This
one uses randomCells:
A = randomCells(8,8)
printBoard(A)
A2 = innerReverse(A)
printBoard(A2)
Aside: You might point out that it would be possible to simply change the old
input A, rather than create and return new data – this is true for simply
reversing the pattern of array elements, but it is not true when implementing
the rules of Conway’s Game of Life - there, changing cells without copying
would change the number of neighbors of other cells!
Conway’s Game of Life
So, for this step, create a function named next_life_generation( A ). Here is
a starting signature:
def next_life_generation( A ):
“”” makes a copy of A and then advanced one
generation of Conway’s game of life within
the inner cells of that copy.
The outer edge always stays 0.
“””
—|—
This next_life_generation function should take in a 2d array A, representing
the old generation of cells, and it should output the next generation of
cells, each either 0 or 1, based on John Conway’s rules for the Game of Life:
- All edge cells stay zero (0) (but see the extra challenges, below)
- A cell that has fewer than two live neighbors dies (because of loneliness)
- A cell that has more than 3 live neighbors dies (because of over-crowding)
- A cell that is dead and has exactly 3 live neighbors comes to life
- All other cells maintain their state
For concreteness, let’s call the new generation of cells you’re returning newA
in order to contrast it with A.
As suggested in innerReverse, always keep all of the outer-edge cells empty!
This is simply a matter of limiting your loops to an appropriate range.
However, it greatly simplifies the four update rules, above, because it means
that you will only update the interior cells, each of which has a full set of
eight neighbors without going out of bounds. It will help to write a helper
function, countNeighbors( row, col, A ), that returns the number of live
neighbors for a cell in the board A at a particular row and col.
Warnings/hints
There are a few things to keep in mind:
- Only count neighbors within the old generation A.
- Change only the new generation, newA.
- Be sure to set every value of newA (the new data), whether or not it differs from A.
- A cell is NOT a neighbor of itself.
- A 2x2 square of cells is statically stable (if isolated) - you might try it on a small grid for testing purposes.
- A 3x1 line of cells oscillates with period 2 (if isolated) — also a good pattern to test.
Once your Game of Life is working, look for some of the other common patterns,
e.g., other statically stable forms (“rocks”), as well as oscillators
(“plants”) and others that will move across the screen, known as gliders
(“animals/birds”).
An Interactive Game
OK, now that you have all the necessary machinery, make it possible for a
user, that is a game player, to interact with your program to create new
worlds of life and run them.
