Run update21 in a terminal window to create cs21/labs/11 directory. Then cd into your cs21/labs/11 directory and create the python program for lab 11 in this directory. The program handin21 will only submit files in this directory.

There are some optional components that allow you to further practice your skills in Python. These optional components will not be graded, but may be interesting for those wanting some extra challenges.

Fighting fires is a very risky job, and proper training is essential. In the United States, the National Fire Academy offers classes that are intended to enhance the ability of fire fighters to deal more effectively with forest fires. The Academy has worked with the U.S. Forest Service to develop a three-dimensional fire fighting training simulator. This simulator allows fire fighters to test out strategies under a variety of topographic settings and weather conditions, and to learn which approaches tend to be more successful. Using simulations to model real-world problems where it may be too difficult, time-consuming, costly or dangerous to perform experiments is a growing application of computer science. For this lab you will create your own two-dimensional fire simulator. The idea for this lab came from a 2007 SIGCSE Nifty Assignment suggested by Angela B. Shiflet of Wofford College.

We are providing you with a basic Terrain class. You will be using an instance of this class inside the fire simulation class that you will be writing. You do not need to modify the Terrain class, but you do need to know how to use it.

The Terrain class models a forest as a rectangular grid of rows and columns. Each cell in the grid is in one of three possible states:

1. Forest (not-burning)
2. Burning Forest
3. Empty (previously burnt or cleared)

The colors green, red, and black represent forest, burning forest, and empty space, respectively.

Examine the methods in the Terrain class by opening a Python shell, importing the Terrain module using from terrain import * and running help(Terrain). The sample code below shows how the methods might be used.

from terrain import *

t = Terrain(10, 12)
t.setEmpty(3,3)
t.setBurning(1,2)
t.update()
t.close()

The resulting Terrain is shown below. Note that cell in location (0,0) is in the lower left corner.

Be sure you understand how to use the Terrain class before going on. In particular, note that the terrain does not immediately update after a call to setEmpty or setBurning. Instead, you must call update which will update all cells with their new status.

Create the file fireSim.py to implement the class FireSim that models the spread of fire across a terrain. We will use a simple probabilistic model to simulate the spread of fire. The simulation will proceed in a number of steps. In each step, we look at each cell in the terrain and update its status based on the cell's current status and the status of its neighbors. For this simulation, the neighbors of a cell are cells that are to the immediate North, South, East, or West of the given cell. If the cell is located at position (i,j), the location and names of the neighbors are depicted below.

The basic rules for updating the status each cell is as follows:

• If the cell is currently Empty, it will stay Empty
• If the cell is currently Burning, it will be set to Empty in the next time step
• If the cell is currently a Forest, and none of the cells neighbors are burning, the cell will stay as a Forest
• If a cell is currently a Forest, and one or more neighboring cells are burning, then the cell will be set to Burning in the next time step with probability p

The probability of burning is a parameter that can be set by the user depending on conditions, such as forest coverage type, or wet/dry weather conditions.

The image below shows the status of a fire after 10 steps:

Your simulator must have the following features:

• A constructor that accepts the number of rows and columns for the Terrain as well as a probability (between 0 and 1) of a fire spreading to a neighbor.
• A method that can start a fire in a random location.
• A method to simulate one step of the spreading fire by updating the status of every cell based on the rules described in the previous section.
• A method to simulate a sequence of steps of a spreading fire until no more cells are burning.
• At the end of a simulation, your program should report the percentage of cells burned and the number of steps it took for the fire to burn out. It should wait for a mouse click before ending the program.

You are free to create any additional methods you need to make your class clear and easy to use.

A sample main function may look like this:

def main():
  f = FireSim(10, 12, .55)
  f.startFire()
  f.spread()
  print "This fire burned %0.2f%% of the Terrain in %d steps" \
       % (f.percentBurned(), f.numSteps())
  f.close()

A sample run of this function might print: This fire burned 69.17% of the Terrain in 18 steps.

You may have different method names with different parameters. Remember, the design is up to you as long as you implement all the requirements.

Be sure to test your class by creating some terrains with different sizes, changing the probability of burning, or starting fires in different locations.

Here are a few suggestions that might help you avoid potential problems:

• Use the sleep function (from time import sleep) to pause between steps of the simulation so you can watch the spread of the fire. Otherwise, you might just see the end of the simulation.
• To make an event happen with probability prob use the random() function from the random module. For example the following code will print the word "yes" with probability prob, where prob is between 0.00 and 1.00.

  if random() < prob:
     print "yes"
  

• Note that the methods setBurning and setEmpty will only update the status of a Terrain object on the next call to update. Thus, you can set the status of cells in the next step using setBurning and setEmpty and make one call to update after all the cells of the terrain have been set. If your graphical display seems to update too fast or not at all, it may be a problem related to not using the update method of the Terrain class properly.
• The isBurning method in the Terrain class returns False if the row or col parameter is outside the terrain's boundaries. This can make checking if a neighbor is on fire a bit easier for cells that are on the edge of the terrain.
• The isEmpty method in the Terrain class returns True if the row or col parameter is outside the terrain's boundaries.

As noted above, these questions are NOT required to receive full credit. Furthermore, do not attempt to solve these problems until the required portion of the assignment is complete.

There are many extensions you could add to this program. You could modify how the fire spreads by adding additional rules or parameters. For example, perhaps the probability of catching on fire depends on the number of neighboring trees that are on fire. Perhaps you can add a wind direction and modify the probabilities such that trees down-wind of an active fire are more likely to burn. Perhaps you can create an initial grid with a few "fire lines" of empty cells to prevent fires from spreading. Add a feature where cells could randomly start burning even if no neighbors are burning (as happens with lightning). Allow fire to spread to cells that are more than one cell away. If you allow this feature, can you get a fire to jump a fire line? More complex models could factor in topography, soil moisture, smoldering fires, etc., and are actually used in some geographical information system (GIS) applications for predicting and modeling forest fire risk.

Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.