Machine Problem 5, due December 5

Part of the homework for 22C:60 (CS:2630), Fall 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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.

The Assignment

Conway's game of life was invented in 1970. Your job in this final assignment is to write SMAL Hawk code to:

  1. Initialize an empty life universe that fills the screen.
  2. Display that universe on the screen.
  3. Support editing of the universe.
  4. Run an iteration of the Life rules on that universe.

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.

The Screen

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.

Editing Support and Controls

Your software should wait for single keypresses from the input. The following single-character commands should be supported:

The Life Rules

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:

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.

Thoughts about various Implementations

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.

Timetable

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.