CISC124 Assignment 2: Writing methods and introduction to using objects

Download and save this eclipse project archive file but do not extract it. Copy or move the file into the assignment directory on your computer.

Next, copy your Assignment 1 solution for ForestFire.java into the A2 project soc package. You will be adding several methods to your ForestFire class in this assignment to produce a runnable Forest-fire simulation.

Submitting your work

DO NOT upload a zip file containing your work. Doing so greatly slows down the processing of assignments, and you will receive a grade of zero on this assignment if you do so.

Your class should both be in the package soc (the same package that they appear in in the project file). DO NOT change the package name or remove the package name from your files.

When marking your work the teaching assistants will be looking for the following:

Review of the Forest-fire model

Students should review the information in Assignment 1 for the details of the Forest-fire model. In particular, students should review the rules that govern the model and the definition of the Moore neighborhood.

Step 1: Generating random numbers

Rules 3 and 4 of the Forest-fire model introduce randomness to the model. Rule 3 says that a tree can randomly be struck by lightning and set on fire. Rule 4 says that a tree can randomly grow in an empty cell. To implement a computer program of the Forest-fire model we require a way to generate random numbers.

The class java.util.Random allows the programmer to create an object of type Random that can generate random boolean, integer, and floating-point values. To use the class, we must first import the class because it is defined in the package java.util.

Open ForestFire.java and add the following import statement after the package declaration:

package soc;

import java.util.Random;        // ADD THIS LINE

Next, create a Random object by adding the following lines of code somewhere inside the class body of ForestFire:

public class ForestFire {

    // SOMEWHERE INSIDE THE CLASS BODY
    // THE MOST LOGICAL LOCATION IS AFTER THE DECLARACTION OF PROB_GROWTH

    /**
     * A random number generator.
     */
    private static Random rng = new Random(1);

}

The added code declares a static variable named rng that stores a reference to a Random object.

The class Random has two methods that are useful in this assignment. The method:

public double nextDouble()

double value = ForestFire.rng.nextDouble();

public int nextInt(int bound)

int value = ForestFire.rng.nextInt(100);

    /**
     * Tests if a tree spontaneously grows during one time step in a Forest-fire
     * simulation.
     * 
     * @return true if a tree spontaneously grows, false otherwise
     */
    public static boolean randomlyGrows() {
        
    }

    /**
     * Tests if a tree burns after being struck by lightning during one time step in
     * a Forest-fire simulation.
     * 
     * @return true if a tree burns after being struck by lightning, false otherwise
     */
    public static boolean randomlyIgnites() {
        
    }

For the method randomlyGrows(), you should generate a random double value between 0.0 and 1.0. If the generated value is less than ForestFire.PROB_GROWTH then the method should return true, otherwise it should return false.

For the method randomlyIgnites(), you should generate a random double value between 0.0 and 1.0. If the generated value is less than ForestFire.PROB_IGNITION then the method should return true, otherwise it should return false.

Step 2: Initializing the cells of a Forest-fire

To run a Forest-fire simulation, we must initialize the cells of a Forest-fire model. There are many ways that we can initialize the cells; for example, we can set the cells so that they:

    /**
     * Sets all of the cells of a Forest-fire model to a specified state.
     * 
     * <p>
     * NOTE: THIS METHOD IS ALREADY IMPLEMENTED.
     * 
     * @param cells the cells of a Forest-fire model
     */
    public static void fill(State[][] cells, State s) {
        int rows = ForestFire.rowsIn(cells);
        int cols = ForestFire.colsIn(cells);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                cells[r][c] = s;
            }
        }
    }

The fill method sets all of the cells of a Forest-fire model to some specified state s.

    /**
     * Sets the cells of a Forest-fire model to a checkerboard pattern of
     * {@code State.EMPTY} and {@code State.OCCUPIED} cells. The state of the
     * upperleft-most cell {@code State.EMPTY}.
     * 
     * @param cells the cells of a Forest-fire model
     */
    public static void checkerBoard(State[][] cells) {
        
    }

After completing the checkerBoard method, you can run the Viewer class to visualize the cells of a Forest-fire model. You should see the following if your method is correct:

Step 3: Updating the forest

The Forest-fire model simulates the evolution of a forest over time. The initial configuration of cells corresponds to the forest at time \(t=0\). The model then updates the state of the forest to produce the forest at time \(t=1\). It repeats the update process producing the state of the forest at times \(t=2, 3, 4, ...\).

When the array of cells updates from time \(t=i\) to time \(t=i+1\), all of the cells in the array are updated at the exact same time. This complicates the computation of the next generation of cells.

Suppose that we have an array of cells for time \(t=i\). There is no way to compute the entire array for the next generation of cells in a single step. Instead, we loop over the array of cells and evolve the cells one by one. Consider what happens if we evolve the first cell cell[0][0] from time \(t=i\) to time \(t=i+1\). When we go to update the next cell cell[0][1] we no longer have the state of its neighbor cell cell[0][0] from time \(t=i\) (because we have already updated cell[0][0]).

There are several ways to solve this problem. Perhaps the easiest solution is to copy the array of cells so that we can remember what the state of cells are at time \(t=i\). When we update the cells, we use the information in the copied array to compute the state of the next generation of cells.

    /**
     * Updates {@code cells} so that it is equal to the next generation of cells.
     * 
     * <p>
     * See the assignment document for details.
     * 
     * @param cells the cells of a Forest-fire model
     */
    public static void update(State[][] cells) {
        State[][] copy = ForestFire.copy(cells);
        
    }

update changes the values in cells by applying the rules of the Forest-fire model. When calling the method, cells represents the state of the cells at time \(t=i\). The method changes the values in cells so that when it finishes, cells represents the state of the cells at time \(t=i+1\).

copy is a copy of the cells at time \(t=i\). You should never change the values in copy. When you need information regarding the state of a cell, you should always get that information from the array copy. For example, you need the Moore neighborhood around a cell to test if the cell is adjacent to a burning tree; when you call ForestFire.nMoore you should do so passing in copy as the cells of the forest instead of passing in cells.

package soc;

public class Demo2 {

    public static void main(String[] args) {
        State[][] cells = {
                {State.OCCUPIED, State.EMPTY,    State.BURNING,  State.EMPTY},
                {State.EMPTY,    State.EMPTY,    State.OCCUPIED, State.EMPTY},
                {State.BURNING,  State.EMPTY,    State.OCCUPIED, State.OCCUPIED},
                {State.EMPTY,    State.EMPTY,    State.EMPTY,    State.EMPTY},
                {State.EMPTY,    State.OCCUPIED, State.EMPTY,    State.EMPTY},
        };
        for (int time = 0; time <= 5; time++) {
            System.out.println("Time t = " + time);
            ForestFire.printForest(cells);
            ForestFire.update(cells);
            System.out.println();
        }
    }

}

To remove the effects of randomness, set PROB_IGNITION and PROB_GROWTH to 0.0 (which should guarantee that no tree grows in an empty cell and no tree catches fire from lightning). When run with the updated probability values, the program should generate:

If you set PROB_IGNITION to 1.0 and PROB_GROWTH to 0.0 (which should guarantee that no tree grows in an empty cell and every tree gets hit by lightning) then the program should output:

If you set PROB_IGNITION to 0.0 and PROB_GROWTH to 1.0 (which should guarantee that every empty cell becomes a tree and no tree gets hit by lightning) then the program should output:

Step 4: Finding occupied cells

Counting the number of empty, occupied, and burning cells in a forest are simple search-based tasks. Slightly more complicated is finding and returning the locations of cells with a specified state.

    /**
     * Returns a two-dimensional array of the row and column indexes corresponding
     * to the cells occupied by a tree in a Forest-fire model.
     * 
     * <p>
     * The returned array has two rows and n columns, where n is the number of cells
     * occupied by a tree in the Forest-fire model. The first row of the array
     * contains the row indexes of the occupied cells and the second row of the
     * array contains the column indexes of the occupied cells.
     * 
     * @param cells the cells of a Forest-fire model
     * @return a 2 x n array of row-column indexes of the cells occupied by a tree
     */
    public static int[][] occupiedIndexes(State[][] cells) {
        
    }

The method occupiedIndexes returns the row and column indexes of all of the cells occupied by a (non-burning) tree. The method returns a two-dimensional array of int values. The number of rows in the returned array is equal to \(2\), and the number of columns is equal to the number of tree occupied cells. The first row of the returned array contains the row indexes of the occupied cells, and the second row of the returned array contains the column indexes of the occupied cells. For example:

State[][] cells = {
    { State.EMPTY,    State.EMPTY,    State.OCCUPIED},
    { State.OCCUPIED, State.EMPTY,    State.EMPTY},
    { State.BURNING,  State.OCCUPIED, State.OCCUPIED},
};
int[][] indexes = ForestFire.occupiedIndexes(cells);

In the above example, the forest has \(4\) occupied cells having the following indexes:

	cell	cell	cell	cell
row index	0	1	2	2
column index	2	0	1	2

The first row of the array indexes should contain the values 0, 1, 2, 2 and the second row should contain the values 2, 0, 1, 2.

Step 5: A random initial configuration of cells

    /**
     * Sets the cells of a Forest-fire model to a random pattern of
     * {@code State.EMPTY}, {@code State.OCCUPIED}, and {@code State.BURNING} cells.
     * 
     * <p>
     * See assignment for details.
     * 
     * @param percentNotEmpty the percentage of the total number of cells in the
     *                        model to set to State.OCCUPIED or State.BURNING
     * @param percentBurning  the percentage of the number of non-empty cells in the
     *                        model to set to State.BURNING
     * @param cells           the cells of a Forest-fire model
     * @throws IllegalArgumentException if percentNotEmpty or percentBurning is less
     *                                  than zero or greater than one
     */
    public static void randomize(double percentNotEmpty, double percentBurning, State[][] cells) {
        
    }

randomize uses the following algorithm to randomize the state of the cells in the forest:

\(n_\text{not empty}\) is the number of cells that are either occupied or burning. Its value is given by:

\[ n_\text{not empty} = \text{round}( \text{percentNotEmpty} \times \text{total number of cells}) \]

\(n_\text{burning}\) is the number of cells that are burning. Note that only a non-empty cell set to State.OCCUPIED in Step 2 can be set to State.BURNING in Step 3. Its value is given by:

\[ n_\text{burning} = \text{round}( \text{percentBurning} \times n_\text{not empty}) \]

Step 1 of the algorithm is easy to implement. Simply use the ForestFire.fill method.

Step 2 of the algorithm requires you to randomly choose cells. To choose a random cell, simply generate a random row index r and a random column index c. If cells[r][c] is equal to State.EMPTY then change the state to State.OCCUPIED. If cells[r][c] is equal to State.OCCUPIED then that cell was already randomly chosen. Repeat the process until \(n_\text{not empty}\) cells are set to State.OCCUPIED.

Step 3 of the algorithm requires you to randomly choose cells that are already occupied. First, find the indexes of the occupied cells using ForestFire.occupiedIndexes. Next, randomly pick one of the columns from the array retuend by ForestFire.occupiedIndexes; this column contains the row and column index of an occupied cell. If that cell has the value State.OCCUPIED then set it to State.BURNING. If that cell has the value State.BURNIG then that cell was already randomly chosen. Repeat the process until \(n_\text{burning}\) cells are set to State.BURNING.

Step 6: Run the Forest-fire model (OPTIONAL)

package soc;

public class RunForestFire {

    /**
     * Visualizes 1000 iterations of the Forest-fire model.
     *  
     * @param args not used
     */
    public static void main(String[] args) {
        State c[][] = new State[50][100];
        // ForestFire.fill(c, State.OCCUPIED);
        // ForestFire.checkerBoard(c);
        ForestFire.randomize(0.25, 0.01, c);
        
        Viewer.init(c);
        for (int t = 0; t < 1000; t++) {
            Viewer.draw(c);
            ForestFire.update(c);
        }
    }
}

As shown above, the program will start with a random configuration of cells, but you can easily change the initial configuration by commenting and uncommenting the appropriate lines of code.

Regardless of the initial configuration, the model will eventually end up producing a forest that is partially occupied by trees where clusters of trees form and then burn. The following animated GIF shows the output of the above program when run from a random configuration of cells:

Instructions