Programming Assignment 10

For this assignment, you will create Python source files containing a function(s) implementing each of the problems described below. If you find it useful for any of the problems in this assignment, you may define additional helper functions that your primary function for that problem calls to solve a sub-problem. Definitions for these helper functions should be included in the same Python source file as the primary function they help. You should store a source file for each problem in a folder named pa10.

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)

Overview

In this assignment, you will develop a simple graphical simulation that analyzes how forest fires spread and how forests regrow after fires. Each time step of the simulation represents one day.

On each day, if a tree is on fire, it may turn to ashes. If a tree is ashes, it may turn into a shoot (a baby tree). If a tree is a shoot, it may starting growing. If a tree is growing, it may reach maturity. If a tree is mature and at least one of its neighbors is on fire, it may ignite (i.e., catch on fire itself).

This simulation will show how a small forest, represented by a 17 × 17 matrix of trees, evolves over time.

Here is a sample of what the first eight "days" of the simulation might look like:

Images are ordered horizontally starting from Day 1 to Day 8

Each snapshot above is a time step of the simulation shown in a 340 × 340 window (in pixels). Notice that the window is "divided" up into 17 × 17 squares. Each of these 289 squares represents one tree in the simulated forest.

In addition to the display functionality provided by the Canvas module, you will also need to use random number generation in this simulation. Suppose an event occurs with a chance of 20 percent. We can write a function that returns true if the event occurs and false otherwise given that the chance of the event happening is 20%:

from random import *

def event():
   if (randrange(100) < 20):
      return True
   else:
      return False

Assuming the randrange generator is uniform, then this returns true if randrange(100) is 0 through 19, and false if randrange(100) is 20 through 99. So 20% of the values will cause the function to return true.

More concisely and more generally, for a chance of p percent, where p is between 0 and 100, inclusive:

def event(p):
  return (randrange(100) < p)

0    on fire
1    in ashes
2    a shoot (i.e. baby tree)
3    growing tree
4    mature tree

The function display(forest) goes through the entire matrix and displays each "tree" as a square of size 20 pixels × 20 pixels in one of the following colors:

"red"          on fire
"#202020"      in ashes (this is a dark gray)
"lightgreen"   a shoot
"green"        growing tree
"darkgreen"    mature tree

Sample Usage:

>> load "display.py"
=> true
>> load "test_display.py"
=> true
>> test_display()

Your image may differ.

Complete the problems below to build this forest fire simulation in Python:

Problems

1. [4 points] Next, you will write 3 functions to test a specific tree in the forest to see if it changes its state. Complete all of these functions in the file tests.py, which should probably begin like this:

   from random import randrange
   
   FIRE = 0
   ASHES = 1
   SHOOT = 2
   GROWING = 3
   MATURE = 4
   
   def event(p):
       # return True p percent of the time
       return randrange(100) < p
   

   Add functions to the file as specified below:

   1. burnout(forest, i, j, p): A cell in the forest at position i, j that is currently on fire will turn to ashes (i.e. burn out) with a chance of p percent at each time step. Write a function burnout(forest, i, j, p) that returns false if the cell at row i, column j in the forest is not on fire, but returns true approximately p% of the time (and false the rest of the time) if the cell is currently on fire.

      General algorithm: Test to see if the cell forest[i][j] represents a tree on fire and use the event function above to see if it returns true given the percentage p. If both of these conditions are true, then return true. Otherwise, return false.

   2. grows(forest, i, j, p): A cell in the forest at position i, j grows with a chance of p percent if it is not on fire and it is not yet mature. Write a function grows(forest, i, j, p) that returns true approximately p% of the time if the cell at row i, column j in the forest is not on fire and is not mature. It should return false otherwise.

      General algorithm: Test to see if the cell forest[i][j] represents a tree that is not on fire and is not mature, and then use the event function above to see if it returns true given the percentage p. If both of these conditions are true, then return true. Otherwise, return false.

   3. ignites(forest, i, j, p): A cell in the forest at position i, j ignites (i.e. catches on fire) with a chance of p percent if it is mature and at least one of its neighbors is on fire. A neighbor of a tree is immediately above, below, to the left or to the right of the tree. Write a function ignites(forest, i, j, p) that returns true approximately p% of the time if the cell at row i, column j in the forest is mature and at least one of its neighbors is on fire, or false otherwise.

      General algorithm: Test to see if the cell forest[i][j] represents a tree that is mature, then test to see if at least one of its neighbors is on fire, and then use the event function above to see if it returns true given the percentage p. If both of these conditions are true, then return true. Otherwise, return false.

      NOTE: Be careful when you test the neighbors. You might be on the edge of the forest. If you test for a neighbor and you go off of the matrix, you might cause your program to crash. It will help here to look at each neighbor separately rather than trying to evaluate all four neighbors in one statement.

   Test your burnout function. Add the following code to tests.py:

   def test_burnout():
       forest = [ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 2, 3, 4, 4] ]
       for i in range(len(forest)):
           for j in range(len(forest[i])):
               print(burnout(forest, i, j, 20), end = " ")
           print()
   

   which creates a simple small forest of size 3 × 5 and calls burnout directly on each cell, printing the results.

   Sample usage:

   $ python3 -i tests.py
   >>> test_burnout()
   False True False False False 
   False False False False True 
   False False False False False
   

   The first two rows should each contain, on average, one true value. For the last row, all outputs should be false.

   Write two additional test functions to test grows and ignites.

2. [4 points] Write a function update(forest) (in the file update.py). This function takes a 17 × 17 matrix representing our forest, as described above, for the current time step of the simulation, and returns a new 17 × 17 matrix representing our forest during the next time step (i.e. after one day has passed).

   The basic idea here is that we start with the current forest in the array forest and create a new snapshot of the forest after one time step in an array new_forest. Each cell new_forest[row][column] represents the new status of the cell in the forest from forest[row][column].

   General Algorithm:

   1. Set p_burnout (the chance that a tree on fire will burn out) equal to 10. (The value 10 used here represents 10%.)
      Set p_grow (the chance that a tree will grow one stage) equal to 10.
      Set p_ignite (the chance that a tree will ignite if any of its neighbors is on fire) equal to 20.
      (NOTE: Once you have the simulation working, you can change these values to explore the simulated forest further.)
   2. Create a new 17 × 17 matrix, called new_forest, with each cell initialized to its respective value in forest. (HINT: Look at the test_display function above to see how to create and initialize a matrix.)
   3. For each row and column of the forest, do the following:
      1. If the cell is on fire, then set the respective cell in new_forest to ashes p_burnout percent of the time. Call the function burnout that you wrote earlier to help you perform this step.
      2. If the cell is not on fire and is not mature, then set the respective cell in new_forest one level higher p_grow percent of the time. (That is, set the cell in new_forest to be a shoot if it was ashes in forest, set the cell in new_forest to growing if it was a shoot in forest, and set the cell in new_forest to mature if it was growing in forest.) Call the function grows that you wrote earlier to decide whether to advance the cell on this step.
      3. If the cell is mature and at a least one of its neighbors is on fire, then set the respective cell in new_forest to be on fire p_ignites percent of the time. Call the function ignites that you wrote earlier to help you perform this step.
   4. Return the new_forest as the final result.

   Since your update function will depend on functions in tests.py, you should import these functions by adding this line to update.py:

   from tests import *
   

   Test your update function using the run_simulation function in simulation.py, which creates a random forest and runs the simulation for 100 "days". Sample usage:

   $ python3 -i simulation.py
   >>> run_simulation()
   

   Alternatively, you might call run_simulation(step = True) instead of run_simulation(); this steps through the simulation day by day, waiting for you to hit enter to advance to the next day, rather than sleeping for a set amount of time.

   If you do this part correctly, the first 8 days of your simulation should match the pictures at the beginning of this assignment. You can change the seed for the random number generator later to try out other simulations, and you can change the chances for cool, grow and ignite to see how these effect the simulation once you're done.

3. [2 points] Instead of initializing the forest with random trees on fire, the function call run_simulation(init = 'wall') initializes the forest with all the trees in the top row of the matrix on fire, and the rest of the trees in random non-fire states. You might expect this to result in a wall of flame sweeping south through the forest, but that is not what happens. Since trees have only a 20% chance of igniting when one of their neighbors is on fire, and trees already on fire have a 10% chance of burning out at each step, the evolution of the fire is very irregular. In addition, because it takes a while for the fire to reach more deeply into the forest from the north edge, the more southerly trees will have reached maturity and be more likely to ignite when the fire does arrive. Try it and see.

   The function call run_simulation(init = 'n') is similar to run_simulation(init = 'wall'), except that it calls the function fire_wall_n() to create the initial forest instead of fire_wall_forest() (see the code in simulation.py. Your job is to define fire_all_n within simulation.py to complete the program.

   fire_wall_n() is similar to fire_wall_forest() except that instead of setting the entire top row of trees on fire, it prompts the user for a number n, and then sets the first n trees on fire. So if the user entered the number 8, the initial state of the forest would be random values between 1 and 4, except that forest[0][0] through forest[0][7] would start out at 0 (on fire). If the user enters a value for n that is less than 0 or greater than 17, the function should require entering a value again. (Use a while loop for this.)

   Hint: The input() method returns a string. If you need to convert a string to an integer you can use the int method. For example, the assignment statement

   n = int(input("How many trees initially on fire? "))
   

   assigns to the variable n the integer value of the command line input provided by the user.

   With this approach, your program will stop with an error if the user types in a non-integer, because it is an error to try to convert a non-integer string using int. You can assume users are good typists, but be aware that writing fragile input functions with no error checking is usually a very bad idea.

Submission

You should now have a pa10 directory that contains the required files tests.py, update.py, and simulation.py each—in turn—containing the corresponding function(s). You do not have to hand in the testing functions since we will have copies of these. Zip up your directory and upload it using the handin system. (The handin system will accept submissions until the deadline Tuesday night.