CPSC-115 Fall 2008
Lab 12
November 18/19, 2008
Professor Heidi Ellis
Be sure that you hand in the printouts of your work before leaving!!!
Objectives:
- To gain a greater understanding of two-dimensional arrays.
In this lab, you will create an application that models the burning of a brush fire or forest fire over time. The goal is to be able to roughly predict how a fire that is burning over a fairly wide area where the fire is not under control will behave. (Credit to Angela B. Shiflet, Wofford College and Nifty Assignments (nifty.stanford.edu))
Prelab: Show the sample grid below after one time period has passed assuming that the probability of fire is 0.1 and the threshold is 0.3. In other words, write out the grid and change any values to reflect how the fire is expected to burn. You will need to read the entire lab carefully before attempting this.
| |
0 |
1 |
2 |
3 |
4 |
5 |
| 0 |
E |
E |
E |
E |
E |
E |
| 1 |
E |
T |
B |
T |
T |
E |
| 2 |
E |
B |
T |
B |
T |
E |
| 3 |
E |
E |
T |
E |
T |
E |
| 4 |
E |
B |
T |
B |
T |
E |
| 5 |
E |
E |
E |
E |
E |
E |
Pair Programming:
- Locate your partner and introduce yourself:
| Tuesday Lab |
|
Wednesday Lab |
| Kristen Anderson | Nick Dragu |
|
Chelsea Bainbridge-Donner | John Wilsterman |
| Jeff Young | Jake Elder |
|
Greg Vaughan | Catherine Doyle |
| | | |
Jesse Vazquez | Ryan Ersland |
| | | |
Jin Feng Liu | Corazon Irizarry |
- Select one person to start as "driver". This person will type at the keyboard for the first 20 mintues.
- Proceed through the process of completing the lab as described below. Be very careful to ensure that every item for both programs is completed.
- Swap pairs every 20 minutes.
- When you are done, be sure to email a copy of the code to the person whose account you are not working in. In other words, make sure that both partners have a copy of the code.
Problem Description
Predicting the spread of a fire that is burning out of control in a large area (i.e., forest fire) is a difficult task. In this lab, you will create a somewhat rudimentary simulation of how fires burn. We will use a 2D grid to represent the area in which the fire is burning. Note that the size of the cell is not relevant for this simulation. However, depending on the size of the area we want to represent, the cells may range anywhere in size from 100 yards square to a square mile. In order to depict the state of the area (i.e., to tell where we have fire and where there are trees and where there is open ground), each cell in the grid will contain a character value that indicates the status of that cell:
- E: The cell is empty - no fire and no tree.
- T: The cell contains trees - no fire.
- B: The cell is burning (contains fire).
The table below shows a sample grid including the row and column indices (in bold).
| |
0 |
1 |
2 |
3 |
4 |
5 |
| 0 |
E |
E |
E |
E |
E |
E |
| 1 |
E |
T |
B |
T |
T |
E |
| 2 |
E |
B |
T |
B |
T |
E |
| 3 |
E |
E |
T |
E |
T |
E |
| 4 |
E |
B |
T |
B |
T |
E |
| 5 |
E |
E |
E |
E |
E |
E |
Our simulation must show how the grid changes over time. Since we cannot simulate continuous time, we will represent time in discrete units called a clock tick. At each clock tick, the simulation calculates the state of our area (see below). Note that the exact time duration of a clock tick does not impact our simulation. However, a clock tick could be a minute, 10 minutes, or an hour, depending on the circumstances of the situation. For our simulation, we only need to know how the grid changes with every clock tick.
The simulation works by being provided an initial grid and then calculating the new state of the grid once every clock tick. We will use a loop to simulate the clock ticks. The next value to be contained in each cell in the grid is determined by the current values in the cells around the cell of interest. For simplicity, we will bound the area that we are looking at with empty cells (all of the cells at the outside of the grid are set to 'E').
In addition to the grid which represents the state of fire, we also have two other pieces of information:
- The probability (a double between 0 and 1) that an individual burning cell will cause a fire in another individual cell.
- The threshold probability (a double between 0 and 1) over which fire will definitely occur.
The probability and threshold values are used to determine whether a particular cell that contains trees will burn in the next clock cycle. For example, if the probability that an individual burning cell will cause a fire is 0.4 and the threshold probability is 0.5, then any cell that contains trees that is located to the north, south, east or west of the burning cell will change state to burning. The calculation to determine if a cell that contains a tree will burn is based on counting the number of cells (north, south, east and west) that are burning and multiplying this number by the probability of the fire spreading. If this total is greater than the threshold value, then the cell becomes burning. Otherwise the cell remains unchanged.
adding together the total probability based on the number of cells that are currently burning north, south, east, and west. In our example above, the cell in location 1,1 will turn to burning as it is bounded by a burning cell to the east and to the south and (2*0.4) > 0.5. Similarly, the cell at location 2,2 will also burn.
We make several assumptions about our simulation:
- An empty cell remains empty for the duration of the simulation. In other words, no new trees grow during the simulation.
- A cell that is burning takes a single time unit to burn and then becomes empty.
- The state of a cell depends only on the cells to the north, south, east and west of the current cell. We will not worry about diagonal cells.
The determination of the value in a cell is based upon the following rules:
- If the cell is empty ('E'), it remains empty for the next time unit.
- If the cell is burning ('B'), it becomes empty ('E') for the next time unit.
- If the cell contains trees ('T'), the number of cells that are burning ('B') to the north, south, east and west are totaled and multiplied by the probability of fire. If that total is greater than the threshold, then the cell becomes burning ('B'), otherwise it remains as it is ('T');
Part 1: Implementation
In this lab, you are to create a FireSimulation class that is responsible for carrying out the simulation of how fire spreads in an area. I have provided you with a SimulationTest.java class that holds the main method that tests the simulation. The UML class diagram for the FireSimulation class is shown below:
| FireSimulation |
|---|
- fireGrid: char[][]
- probFire: double
- threshold: double
|
+ FireSimulation()
+ FireSimulation(fireGrid: char[][], probFire: double, threshold: double)
+ setGrid(grid: char[][]): void
+ setProbFire(probFire: double): void
+ setThreshold(threshold: double): void
+ getWidth(): int
+ getHeight(): int
+ onFire(): boolean
+ calcState(col: int, row: int): char
+ updateFireStatus(): void
+ simulate(): void
+ toString(): String
|
In order to aid in implementation, I have provided descriptions of each of the methods below:
- FireSimulation() : This constructor does nothing.
- FireSimulation(char[][] fireGrid, double probFire, double threshold) : This constructor takes a grid, a probability that a cell will cause fire to spread and a threshold probability. The constructor sets the attributes in the FireSimulation instance accordingly.
- setGrid : This method assigns a new grid to a FireSimulation instance.
- setProbFire : This method assigns a new probability of fire to a FireSimulation instance.
- setThreshold : This method assigns a new threshold value to a FireSimulation instance.
- getHeight : This method retrieves the height of the fire grid.
- getWidth : This method retrieves the width of the fire grid.
- calcState : This method is passed the X and Y coordinates of a cell in the grid. The method then calculates and returns the value of that cell (e.g., the new state of the cell) based upon the current (existing) value of the cell. If the current value is:
- E : The cell remains empty. (What do you return to indicate that a cell is empty???)
- B : The cell becomes empty.
- T : Count the number of burning (B) cells north, south, east and west of the cell. Multiply this number by the probability of the fire spreading. If this total is greater than the threshold value, then the cell becomes burning. Otherwise the cell remains unchanged.
- updateFireStatus : This method loops through the grid ignoring the outer frame of empty cells. (i.e., loop from the second element to one less than the last element.) Each cell in the inner grid is updated to a new value based on calling the calcState method. Note that the best way to do this is to create a new grid containing entirely empty cells, then place the new state of each cell in the original grid into this new grid. Before leaving the method set the reference to the fire grid to this new grid.
- onFire : This method loops through the grid and returns true if any one of the cells is burning and false if there are not burning cells.
- simulate : This method carries out the actual simulation. It starts by printing the original grid using the toString method. It then loops while there are still cells on fire within the grid. Within each loop this method updates the status of the grid using the updateFireStatus method and prints out the new grid using the toString method.
- toString : This method constructs and returns a string that contains the fire grid including appropriate new lines.
I have provided you with several sample grids within the SimulationTest class. You should use these grids to test your FireSimulation class.
A sample execution of the main method where the probability of fire is 0.3 and the threshold is 0.4 might appear as below:
Original grid:
E E E E E E
E B T B T E
E T B T B E
E E T T T E
E T B T B E
E E E E E E
Updated grid:
E E E E E E
E E B E B E
E B E B E E
E E B T B E
E T E B E E
E E E E E E
Updated grid:
E E E E E E
E E E E E E
E E E E E E
E E E B E E
E T E E E E
E E E E E E
Updated grid:
E E E E E E
E E E E E E
E E E E E E
E E E E E E
E T E E E E
E E E E E E
Test your code carefully to make sure that it operates correctly under a variety of test cases. Your code should have good programming style and follow all Java conventions. Don't forget to use constants where appropriate.
You're done!! Don't forget to log out and hand in your printouts to the professor before you leave!!