cs246 hw6/7

CS 246 Homeworks 6 & 7: Conway's Game of Life

You MUST work with at least one other person on this assignment, and may work with up to two. If you choose to have a three-person team, I expect your project to be suitably more sophisticated than a two-person team.

Homework 6 Due:	Monday, April 22, 2013
Homework 7 Due:	Wednesday, May 1, 2013

Please read the homework guidelines before you proceed.

Project Description

Conway's game of life is a cellular automaton and popular example of Artificial Life. It consists of a set of binary cells that obey specific rules at each timestep and grow, die, or evolve over time. Given an initial configuration of binary cells, the system evolves automatically over time.

In this project, you will implement Conway's game of life in C++. You may use text-based output or 2D graphics to show the state of the simulation.

You are welcome and encouraged to read external material on Conway's game of life and appropriate data structures, but you may not use code from or consult any implementations of the game of life or those data structures.

This assignment will be divided into two parts, one of which will count as homework 6 and the other as homework 7.

Requirements

You may use text-based output or 2D graphics to show the state of the simulator. Your display may be as complex or simple as you like.
You must use an appropriate data structure (red-black trees, KD-trees, or a structure of your own choosing/design) to facilitate rapid lookup of cell state.
Your implementation must support a variety of grid topologies, as described below.

Command Line Arguments

Your implementation must accept the following command line arguments:

"-size <rows>,<columns>" -- initializes the size of the life grid (e.g., "-size 100,200" would create a 100 x 200 grid)
"-size <dimension>" -- same as above, but creates a square grid
"-topology {cylinder | moebius | torus}" -- specifies the topology of the grid (see below) (e.g., "-topology torus" would use a torus topology)
"-initialize '(<x1>,<y1>);(<x2>,<y2>);...' " -- initializes the "on" cells (e.g., "-initialize '(10,10);(10,11);(12,10)' " would turn on cells (10,10), (10,11), and (12,10)). Note that you must use single quotes to surround this list to prevent problems with the semicolon and parenthesis.
"-random" -- create a random initial state; cannot be combined with -initialize

The default (no arguments) functionality should be to use a 100,100 torus initialized randomly.

Grid Topologies

The number of rows and columns in the grid stays fixed throughout the game, as specified by the command line arguments. Your implementation should support three different grid topologies, which determine the neighbor cells along the border of the grid:

Cylinder: The cylinder wraps around horizontally, with the left border being adjacent to the right border. For example, the column of cells on the left side of the grid act as if they were bordered on the left by the column of cells on the right side of the grid, and vice versa. The top and bottom borders act as if they are bordered respectively above and below by always-dead cells.

Moebius strip: Like a cylinder, but with the left column identified with the reverse of the right column. That is, the top left square is the neighbor to the right of the bottom right square. The square below the top left square is neighbor to the right of the square above the bottom right square. And so on until the bottom left square, which is the neighbor to the right of the top right square. Note that these conventions also determine diagonal neighbors of border squares.

Torus: Like a cylinder, but instead of having the top and bottom rows bordered by always-dead cells, the top and bottom rows link together. That is, the grid wraps around both horizontally and vertically.

Speed

You will need to be clever to avoid performance issues. While it is possible to implement the game of life entirely as a 2D array, it will be very expensive to iterate over the entire 2D array each timestep. Instead, you should store cell states in a data structure (red-black tree, KD-tree, or one of your own choosing/design) to facilitate efficient lookup. It may help to name cells by their coordinates, and to store the names or pointers to neighboring cells to facilitate rapid lookup of their state. To keep memory from getting out of hand, you will probably want store only live cells in the structure.

Homework 6 Submission

For your homework 6, you must submit a very clear design document for the full project. This design document will have a strict 4 page limit (1in margins, 11pt font), and must specify:

An brief description of the game of life
A full breakdown of your program design, including the interfaces to all components
A system diagram showing how all of the components interrelate
A description of the data structure(s) you chose for efficient cell lookup and a justification of why it will work and the expected computational complexity
A status report on the current state of your implementation and what still needs to be completed (screenshots may be helpful)

Your design document must convince me that I should let you build this program. I expect the design document to be very concise and packed with detail. I strongly recommend that you write it out as a 7-8 page document initially and then compact it like crazy. (Yes, I really do expect you to compact 7-8 pages of material into a four page report.)

You should also submit an initial version of your implementation, and describe its status in the design document. I recommend that you start with a very basic version of the game of life using a 20 x 20 torus, storing everything in only a 2D array (e.g., don't support command line arguments, efficient data structures for quick lookup, etc.). At this initial stage, don't worry about visualizing the game, just output status information. There are no strict requirements for this initial implementation, but it must convince me that you will be able to finish the entire program.

Homework 7 Submission

For your homework 7, you should submit a completed project as well as a two page report (again, this is a strict limit using 1in margins and 11pt font). Your report should again be very detailed and concise, explaining:

An overview of your program and the data structures you chose
A justification for all your design choices
An overview of your final program design and how it differs from your HW6 design
Details on any aspects of the program that are incomplete and how you could complete them

Submission

Submit one assignment for all partners, following the assignment guidelines and submission instructions. You will do this once for Homework 6 and once for Homework 7.

Be sure to list all partners' names in your README file.

Provide a working Makefile for your assignment. The Makefile should support four commands: make, make run, make run_custom, and make clean. I must be able to:

Uncompress your submission
"cd" into the directory
Type "make" and have your program compile itself.
Type "make run" and have it launch itself with the default arguments
Type "make run_custom" and have it launch itself with arguments of your own choosing (unnecessary for the HW6 version)

Put all source code, the data files, the README, your written report, and Makefile into a single .tar.gz file.

Additionally, each partner should also submit an independent and private brief statement via e-mail to Eric that describes each partner's contribution to the project. Use the subject "CS246 HW6/HW7 Partner Work Distribution".

Hints

This is a much larger project than the others, so you must start small and build up gradually. Begin by implementing the game of life using a 20 x 20 torus and storing everything in only a 2D array (e.g., don't support command line arguments, efficient data structures for quick lookup, etc.). At this initial stage, don't worry about visualizing the game, just output status information. Only once you have this basic implementation working should you move to a more complex one. Add in a text-based or graphical visualization. Add in the efficient cell lookup.
Plan ahead, write modular code, clearly define the interfaces and system structure, and communicate constantly with your partner.