We’re going to write a fire simulation program. This will involve the use of 2D arrays, as well as the notion of simulation through discrete time steps. The simulation is simplistic, but realistic enough to be of interest. For starters, read more about fire simulation, and the approach we are going to take, here:
http://nifty.stanford.edu/2007/shiflet-fire/
You are reading for background information, so ignore the sections on “Meta-information”, “Detailed Description”, and “Assignments”. Our version of the simulation will use a 12x24 grid — that’s the total size, including boundary rows. This implies that at the top of your program, you’ll define N to be 24 (notice the lack of a semi-colon “;” below at the end of the #define):
#define N 24
This will allow us to change the size of our grid easily if we want to. Since our goal is 12x24, here’s a clean way to declare your matrix in the main() function:
int main()
{
int M[N/2][N];
int ROWS, COLS;
ROWS = sizeof(M) / sizeof(M[0]);
COLS = sizeof(M[0]) / sizeof(M[0][0]);
Notice that I compute ROWS and COLS the way we learned in class, so that it’s correct regardless of how the matrix is declared (or how N is defined).
In short, you assignment is to write a simulation program that inputs the starting location of a burning tree, along with the number of time steps, and then runs the simulation, showing the state of the simulation after each time step. For example, suppose the input is “1 1 2”. This places the initial burning tree at position (1, 1) in the matrix, and runs the simulation for 2 time steps. Here’s what the user should see: See image.
This is time step T=0, i.e. before the simulation starts. The burning tree is denoted by a “*”, and the remaining internal area of the simulation is full of trees (“T”). As discussed in the article, the internal area is surrounded on all sides by an empty boundary — which is why the area to the left of the burning tree is blank, as well as the area above the burning tree. The right and bottom edges are also blank, you just can’t see it. This implies that our 12x24 matrix has 10 rows and 22 columns full of trees: rows 1..10 and columns 1..22.
After drawing the simulation area, the program waits for the user to press a key and hit ENTER. I press “s” for step, in which case my program advances 1 time step and then shows me the updated simulation area: See image.
Notice there are now 3 trees burning, the previous one and two of which are newly burning — i.e. they just started burning in this time step. Unlike the article, our trees keep burning :-) I press “s” again to advance the simulation one last time: See image.
There are now a total of 6 trees burning, 3 of which are newly burning. The simulation is now over, since the input specified 2 time steps.
The assignment is much like the overview presented in http://nifty.stanford.edu/2007/shiflet-fire/, with a few changes. As noted in the previous section, our simulation matrix will be 12x24, and this denotes the entire simulation area: internal area + boundary rows and columns. And as shown earlier, you must #define the value of N as 24, so that we can easily change this value when we test your program. The rest of the program should be written in terms of N, ROWS, and COLS.
In our simulation, the fire will spread with a probability of 1.0. This means that if a tree T is burning, its neighbors to the North, South, East and West will start burning in the next time step. Use the same values for EMPTY, TREE, and BURNING as defined in the article: 0, 1, and 2. This implies that all matrices are of type int.
You will be required to use functions in your program. In particular, your program must consist of at least 3 functions, and you need to add a 4 th function of your own choosing. Here is a skeleton program file for you to start from, showing the 3 functions that are required. This is actual C++ code that you should copy and paste to get started (this code will be available on the course web page along with this handout):
#include
using namespace std;
#define N 24
// print:
//
// Prints the simulation matrix M as spaces, *'s, and T's.
//
void print(int M[][N], int ROWS, int COLS)
{
// YOU MUST IMPLEMENT THIS:
}
//
// fill:
//
// Fills the simulation matrix such that the boundary rows
// and columns are empty, the internal area is all trees,
// and one tree is burning at index position (row, col).
//
void fill(int M[][N], int ROWS, int COLS, int row, int col)
{
// YOU MUST IMPLEMENT THIS:
}
//
// main:
//
int main()
{
int M[N/2][N];
int ROWS, COLS;
ROWS = sizeof(M) / sizeof(M[0]);
COLS = sizeof(M[0]) / sizeof(M[0][0]);
fill(M, ROWS, COLS, 1, 1);
print(M, ROWS, COLS);
return 0;
}
You can add as many functions as you want, but you need to have these 3, and add at least one more.
I cannot stress strongly enough the following advice: “baby steps”. Do not try to write the entire program at once, it’s a recipe for disaster. Instead, work towards a solution one baby step at a time. The first step is to create a new project in your C++ environment, and then enter the code shown above. Run this program, and nothing will be output, but you’ll have the correct starting template.
The second step is to write the fill( ) function and just fill the matrix with EMPTY values — i.e. 0. Then write the print( ) function to output the matrix to the console exactly as is. When this is working, you should see this: See image.
In other words, a 12x24 matrix of 0’s. Once that is working, change fill( ) to perform its correct function: the boundary rows and columns should be EMPTY, the internal area should be all TREE, and there should be one tree BURNING at position (row, col). Since (row, col) are passed in as (1, 1) from main( ), you should see this when fill( ) is working: See image.
Notice the “2” in position (1, 1)… Good! Now what? Change print( ) to properly output the matrix; that means “ “ for EMPTY, “T” for TREE, and “*” for BURNING. Think if-statements… Run, and when print( ) is working, you should see: See image.
At this point you have fill( ) and print( ) working. As your next step, I would suggest performing just one step of the simulation. In other words, what you currently have in the matrix M is the initial state of the simulation, i.e. time step T=0. Now perform one step of the simulation, and output the new state of the simulation, which will denote time step T=1. How do you “perform” the simulation? As discussed in the article, for every cell (r, c) in the internal area of the simulation matrix, look at its 4 neighbors: North, South, East, and West. If (r, c) is a TREE and any of its neighbors are burning, then the fire “spreads” to this cell (r, c) and it starts BURNING. Otherwise the cell (r, c) does not change state. Read on…
Now, one of the subtle issues you need to take into account is that when performing a step of the simulation, you cannot change the current simulation matrix — you should think of M as the “current” state of the simulation, and the result of a simulation step is to produce the “next” state of the simulation M2. Thus, you need two matrices in your program, M and M2. Here’s an updated main( ), with changes in boldface:
//
// main:
//
int main()
{
int M[N/2][N];
int M2[N/2][N];
int ROWS, COLS;
ROWS = sizeof(M) / sizeof(M[0]);
COLS = sizeof(M[0]) / sizeof(M[0][0]);
fill(M, ROWS, COLS, 1, 1);
print(M, ROWS, COLS);
//
// perform one step of the simulation, the result is in M2:
//
copy(M, M2, ROWS, COLS); // copy the current state of M into M2:
simulate(M, M2, ROWS, COLS); // simulate fire in M, producing M2:
cout << endl;
print(M2, ROWS, COLS);
return 0;
}
Notice that I’m using functions here to convey the changes to main( ): copy the current state of the simulation into M2, then run one step of the simulation, which updates M2. Then print M2. You are not required to write these functions, you can instead write the code directly in main( ). But it’s a big hint, since you do need to add at least one function… Once you have this working, here’s what you should see for this code: See image.
Notice the fire has spread to positions (1, 2) and (2, 1). Your output should match this EXACTLY.
At this point, you should have a good handle on the program. What remains is to complete the assignment by inputting the 3 values from the user, and looping the simulation to perform the required number of simulation steps. You also need to output some additional details (the time step and number of newly burning trees), as well as pause the simulation after each step. I’d recommend going back to the section entitled “The Assignment” and reading that again for the remaining details. Be sure to test with different starting positions, such as (10, 5), which looks like this initially: See image.
After 1 step, you should have this: See image.