You should save your program for this assignment in cs21/homework/10. A skeleton version of the program will appear in this directory when you run update21 in a terminal window. The program handin21 will only submit files in this directory. You may work with a partner on this assignment.
Some of the problems will have optional components that allow you to further practice your skills in Python. Optional portions will not be graded, but may be interesting for those wanting some extra challenges.
This assignment asks you to use object oriented design to simulate the spread of a forest fire. Your simulation will use the terrain class which we wrote for this assignment. The terrain class models a forest as a rectangular grid of r rows and c columns. Each cell in the grid is in one of three possible states:
- Forest (not-burning)
- Burning Forest
- 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 an IDLE shell, importing the terrain module using import terrain and running help(terrain). The sample code below shows how the methods might be used.
from terrain import *
t = terrain(10, 12)
The resulting terrain is shown below. Note that cell in location (0,0) in in the lower left corner.
Modeling the spread of fire
Modify the file fireSim.py
in your cs21/homework/10
folder to implement a 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 simulation class should create a new fire simulator given the initial dimensions of the terrain and a probability of catching fire. Your simulator must have the following features:
- Use an instance variable to store a terrain object that will show the status of the current fire.
- Your constructor should accept 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.
- Add a method that can start a fire in one or more locations. You can pick a cell to start the fire at random or use parameters specified by the user.
- Simulate one step of the spreading fire by updating the status of every cell based on the rules above.
- Simulate a sequence of steps of a spreading fire until no more cells are burning.
- Report the percentage of cells burned or burning at any given time.
- Report the total number of steps for a fire to burn out.
A sample main function may look like this:
f = fireSim(10, 12, .55)
print "This fire burned %0.2f%% of the terrain in %d steps" \
% (f.percentBurned(), f.numSteps())
A sample run of this function would print: This fire burned 69.17% of the terrain in 18 steps.
You may have different method names with different parameters. 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.
Hints and Tips
Here are a few Hints and Tips that might help avoid potential problems.
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.
The idea for this assignment came from a 2007 SIGCSE Nifty Assignment
presented by Angela B. Shiflet of Wofford College.