Machine Problem 5, due December 5
Part of
the homework for 22C:60 (CS:2630), Fall 2011
|
Submit the source file mp5.a (or mp5.txt if you must) for your solution using the submit command on or before the indicated date.
Conway's game of life was invented in 1970. Your job in this final assignment is to write SMAL Hawk code to:
The Wikipedia article on Conway's Game of Life includes several illustrations of the game in progress, as well as considerable discussion of the rules.
In detail, the state of the life universe is a 2-dimensional array, where each cell is either dead or alive. Dead cells are represented by blanks, live cells by asterisks. The vertical and horizontal spacing should be about the same, so the on-screen display will have blanks between the cells. The net result is that a screen that is x columns by y rows will hold a life universe of size x/2 by y. A typical (but very unlikely) state of the "game" might like this on screen holding 5 by 5 cells.
* * * * * * * * *(*)* * * * * * * * * * *
Parentheses, the cursor, surround one cell. The cursor can be moved, and the state of the cell marked by the cursor can be toggled from dead to alive or from alive to dead. Initially, all cells are dead (blank) and the cursor is in the center of the screen.
Your software should wait for single keypresses from the input. The following single-character commands should be supported:
- Cursor motion (the keys surrounding the J key)
u -- up
i -- up and right
k -- right
< -- down and right
m -- down
n -- down and left
h -- left
y -- up and left
- Editing (the keys surrounding the J key)
j -- toggle the current location * dead or alive
- Running
s -- advance the universe one step under the life rules
- Other
q -- quit
Each cell has 8 neighbors, the cells above and below, to the right and left, and diagonally adjacent. The current state of a cell and the number of living neighbors of that cell determine the next state of the cell. With each generation:
- Living cells with fewer than 2 or live neighbors die of lonleyness.
- Living cells with more than 3 live neighbors die of overcrowding.
- Dead cells with 3 living neighbors come to life.
- The states of all other cells continue unchanged.
The rules above apply to cells that are not at the edges of the universe. Cells on the edge do not change state except when explicitly edited. This allows you to experiment with the effects of turning edge cells on or off.
Note that you must examine the previous states of all neighbors of a cell in order to compute the state of that cell in the next generation. If each cell is represented by only one bit, this means you need two copies of the entire universe. If each cell is represented by multiple bits (for example, one 8-bit byte per cell), we can use one bit for the current state and a different bit for the previous state.
If we represent cells as ASCII characters, with blank and * as the two states, these are represented as:
blank -- 0010 0000 * -- 0010 1010
This means we can toggle a cell from on to off by exclusive oring the cell with binary 0000 1010.
During the move from one generation to the next, we can use bit 1 to represent the previous state of the cell and bit 3 to represent the next state of the cell. So, we count the number of neighboring cells with bit one set to determine whether to set or reset bit three, and then we copy bit 3 into bit 1 to complete move to the next generation. This means that, during the move from one generation to the next, the life universe could contain the following other characters:
( -- 0010 1000 -- cell to be born " -- 0010 0010 -- cell to be killed
It is highly likely that debugging will be easier if your program operates directly on the Hawk computer's video RAM, bypassing the PUTAT and PUTCHAR mechanisms so that you can directly watch the progress of your game implementation in video RAM instead of having to rely on code to copy the universe from some separate array. The display interface is documented in Chapter 12 of the notes. You will need to solve the 2-dimensional array addressing problem whether you build your universe as a separate array or integrate it with video RAM, whether you fold the current and next generation into one array or use two separate arrays.
There will be questions about the Life problem the second midterm exam. The more thought you put into your solution to Life before the exam, the more likely you are to solve those questions.
The implementation of this program is best thought of as being done in steps: The board editor should be useful as a crude drawing program before you start worrying about updating the game from one generation to the next. Do not put off thinking about the update problem, though, as bits of it may show up on the exam.