Assignment 9: Mushrooms

Due: 8:00am, Thursday, March 11. Value: 30 pts. Submit to Sauron.

Background

Imagine a field in which some mushrooms are growing. We model the field as a grid of squares, where each grid square can potentially hold a mushroom, and each square potentially goes through the following cycle.

Except for a few random squares that start with spores, each grid square starts out empty. The empty square becomes a spore with 50% probability if one or more of its four neighbors are mature. Once it becomes a spore, it remains a spore with 20% probability in each following cycle, until it becomes mature. It spends one simulation cycle in the mature state, then dies for the next cycle, then decays. Finally, after one cycle of decay, the grid square reverts back to being empty.

The following illustrates the first three steps of one simulation.

	Initial state: All squares are empty except for a few random squares with spores. The black border squares are walls; they do not change over time.
	The user clicks the mouse to advance the simulation by one time step. In this case, some of the spores will mature into mushrooms.
	After two steps: Some grid squares become spores due to a mushroom in an adjacent square. The mushrooms die, while some spores from the previous step mature into mushrooms.

Your job

I've written starting code, which sets up the initial grid and random spores. Your job is to modify this to simulate the field of mushrooms as described above. Represent the state of each grid square with the colors shown in the above diagram: green, pink, red, dark red, dark green. The boundaries of the grid, where mushrooms can never grow, are represented with black squares.

The starting program defines two functions get_grid and set_grid that you will find useful for determining and altering the color of a grid square.

get_grid(grid, index)

Returns the color name associated with the square numbered index in grid. The grid squares are numbered in reading order: Square 0 is the upper left corner, 1 is the square to its right, 2 the next square to the right; once we reach the row's end (index 14 if grid_size is 15), the following square (index 15) is the leftmost square of the next row.

set_grid(grid, index, color)

Alters the color for the square numbered index in grid to be as named in the color parameter. The grid squares are numbered as with the get_grid function.

Important notes

• The most obvious approach is to have a loop for each time step, which goes through all grid squares and computes that square's new color for the next time step. But this approach is flawed: With such an implementation, a square that was pink at the time step's beginning could become mature (red); and then later in the same time step, when the computer reaches an empty square just below the now-mature square, that square may then gain a spore. But that's wrong, because the square above was really still a spore at the simulated time step's beginning.

  The solution is to use a two-phase process. In the first phase, you go through all squares to find the empty squares that gain a spore, and you'd temporarily mark them as ones that ought to change to pink. A good way of marking a square is to color it blue. And in the second step, you go through all squares again, coloring the marked (blue) squares pink, deciding whether to color the pink squares red, and so on.

  The program I distribute has already structured things this way, with a do_spore_phase function for performing the first phase and a do_advance_phase for the second.

• This assignment specifies that an empty square becomes a spore with 50% probability whether it has one, two, three, or four mature neighbors. A common misinterpretation is that a mature neighbor drops a spore on each of its empty neighbors with 50% probability. This is not the same: With the latter misinterpretation, an empty square would gain a spore with more than 50% probability if it has multiple mature neighbors.

• Although the program is written for a 15×15 grid of 10×10 squares, your program should work regardless of the grid and square dimensions. That is, you should be able to modify the grid_size and square_size parameters to, say, 60 and 5, and the program will correctly simulate a larger 60×60 field.