Introduction

Our group designed and implemented a cellular automaton that emulates how forest fires spread in densely popluated forests.

We have developed an interactive, hardware-based forest fire simulator. The purpose of our system is not to model forest fires with high accuracy. More robust forest fire simulators, such as FARSITE, are used by forest service fire scientists to model the spread of real forest fires. Accurate forest fire modeling is clearly an important endeavor. However, accurate forest fire modeling is difficult and computationally intensive. Simulating large forest fires with high accuracy is actually a current area of research in the field of super computing. Our project did not intend on being highly accurate or realistic. Instead, we implemented a highly simplified cellular automaton that emulates a forest fire. Our goal was to design and implement a simple and interactive system that would provide users with a hands-on opportunity to learn about how forest fires spread. Perhaps by providing users with a way to personally interact with forest fires, our project can inspire them to be more vigilant and help prevent forest fires from happening.

High Level Design

The idea for this project came from a blog post by Christian Hill. Found here. We modified his idea to be a little more realistic. Trees did not have a chance to regrow and there was also no chance of trees spontaneously combusting. The unmodified code tests a 100x100 grid of cells. We wanted to see how much bigger and faster we could run the forest fire simulation on an FPGA.

Our forest fire model is relatively simple at a high level. There are 3 types of cells. A cell can be empty, burning, or a tree. If a cell is empty, it stays empty. Initially, the cells along the border of the grid are empty. If a cell is burning, it stays burning for one cycle and then transitions to empty. If a cell is a tree, we check the state of its neighbors. If none of its neighbors are burning, it stays a tree. If one of its neighbors is burning, there is a probability that the tree will transition into a burning cell.

At the highest level the HPS prompts the user for settings like humidity, and temperature, which affect the probability of trees lighting. This is passed to the FPGA where the fire state machine iterates over all the trees. This state machine spits out pixel data which is loaded into vga memory which is then sent over to the vga monitor.

Whether a tree will ignite or not, is not deterministic. It is random. A tree can only ignite if one of its 8 neighbors is on fire. If this is true, then there is a probability that the tree will ignite. We implemented the probablility by using an LFSR for pseduorandom number generation in hardware. This had to be done in hardware or our speed would be limited by the HPS. This random number gets compared to a threshold value. The threshold value is indirectly controlled by the user when they set the temperature and humidity levels.

Program/hardware Design

The hardest part of our design was coming up with a way to display the output on the VGA screen. We originally thought that we could use 640 column modules and do a lot of the work in parallel. This came out with the correct data in modelsim. However, getting 640 column modules to write to the VGA screen one at a time became a challenge. Furthermore, there was no need to be so aggressive with timing because the VGA screen cannot run that quickly anyway. Instead of trying to multiplex the output of 640 column modules, we came up with a new design that could go through all the pixels serially.

The basis of this design is the compute module. The compute module takes in as inputs, the states of the 8 neighbors, the state of the current node, a random value, and a threshold. If a node is dead, it stays dead. If a node is on fire, it dies immediately. If a node if alive, it dies if a neighbor is on fire and if the random value is greater than the threshold. The threshold is decided based on the humidity and temperature the user selects, from HPS. The random value is received from an LFSR. This is a linear-feedback shift register which uses shift registers and an Xor gate to output semi random numbers. The 8 neighbors and current node states are inputted from 3 memories.

Because we are rastering in a 3 by 3 square left to right, we only need to know the three right most values, Northeast, Right, and southeast. The other values we can save in registers to be used again.

This compute module rasters across the entire grid of memory, while outputting next state information and pixel data. This is like the Mandelbrot set lab (with one iterator), this pixel data is loaded into vga memory and sent out to the vga screen.

The design for our LFSR was heavily influenced by some lecture slides we found online here. We adapted the code to suit our needs, but used the lecture slides as a guideline.

Results

Python Simulation Data

Before attempting to implement anything on the FPGA. We modified Python code written by Christian Hill. The unmodified code can be found here. We removed the possibility of trees randomly igniting and regrowing to make the model slightly more realistic. Instead, we had the model always ignite the tree in the top left corner of the grid. We set the probability of igniting to 50%. Below are some of the outputs we received from running our Python script. They are all different, as expected.

Modelsim Simulation Data

After our simulating our design in Python, we implemented our design in Verilog and tested its behavior in Modelsim. This was not a straightforward process. We implemented and tested 2 designs that did not work as we expected. This is described in detail in the Program/hardware design section of this webpage. Eventually we did come up with a design that accurately implemented the model. Below are some of the waveforms generated in these simulations. Since our hardware random number generator requires a seed, we tested the hardware using different seed values. This testing was performed using a 16-bit LFSR and a 5 by 5 grid of cells. The border cells were empty while the interior cells were all trees. In our final design, we did swap the 16-bit LFSR out for a 32-bit LFSR.

FPGA Implementation

Once we were satisfied with our module's behavior in modelsim, we integrated our design with the GPU with FAST display from SRAM example on the Quartus 18.1 examples webpage. We started with a 5 cell by 5 cell grid and continued to scale up the grid until we ran out of memory blocks. We were able to simulate a 320 by 320 cell grid on the FPGA. We also implemented a user interface that allowed users to set a temperature level and humidity level. Increasing the temperature increases the probability of a tree igniting. Increasing the humidity decreases the probability of a tree igniting. Additionally, users could also decide where the fire would start.Below are some videos demonstrating how the simulation generates a different output when given different seed values and user input.

In the example shown below, the humidty level was set to 4 and the temperature level was set to 3. The fire is starting in the center of the screen.

In the example shown below, the humidty level was set to 5 and the temperature level was set to 3. The fire is starting in the center of the screen. As expected, the fire does not burn as many of the trees due to the increased humidity levels.

Users are also able to change where the fire will start. In the example below, the fire starts in the upper left corner of the screen. One thing that we noticed is that when a fire starts in the corner of the screen, it is more likely to go out befor spreading out of control. This is because the fire will initially have less neighbors if it starts in a corner cell.

Our state machine requires 7 cycles per pixel. We were able to implement a 320 cell by 320 cell grid. Therefore, it takes 716,800 cycles per frame. Therefore, our animation speed is roughly 70 FPS. This is faster than the VGA screen, so we actually get around 60 FPS.

Conclusions

We successfully got the simulation working. We verified what we expected, higher temperatures and lower humidities, caused faster spread than their opposites. The one thing that eluded us was getting the wind to work as a factor, so if given another opportunity that could be something to focus on. We learned more about effective memory management, vga deadlines, cellular automata, and hardware speed up. At the end of the day, this was a pretty robust visual simulator.

Appendix A: Permissions

The group approves this report for inclusion on the course website.

The group approves the video for inclusion on the course youtube channel.

Appendix B: Verilog Code

Appendix C: C Code

Appendix D: Work Distribution

Both students met 3 times a week to work on the project for 2-4 hours each meeting. Most of the work was completed collaboratively during this time. Zane did do some work in Modelsim at home.

Appendix E: References

[1] National Oceanic and Atmospheric Administration, "Ask the scientist: How can the weather spark and spread wildfires?," 4 September 2018. [Online]. Available: https://www.noaa.gov/stories/ask-scientist-how-can-weather-spark-and-spread-wildfires. [Accessed 23 March 2023].
[2] J. Ciarochi, "Modeling how fire spreads," 27 July 2020. [Online]. Available: https://triplebyte.com/blog/how-fire-spreads-mathematical-models-and-simulators. [Accessed 23 March 2023].
[3] S. Elbein, "What the complex math of fire modeling tells us about the future of California’s forests," 18 January 2021. [Online]. Available: https://www.technologyreview.com/2021/01/18/1016215/complex-math-fire-modeling-future-california-forests/. [Accessed 23 March 2023].
[4] C. Hill, "The Forest-fire model," 12 January 2016. [Online]. Available: https://scipython.com/blog/the-forest-fire-model/. [Accessed 23 March 2023].
[5] P. Schaumont, "Lecture 6: A Random Number Generator in Verilog," 2008. [Online]. Available: http://rdsl.csit-sun.pub.ro/docs/PROIECTARE%20cu%20FPGA%20CURS/lecture6[1].pdf. [Accessed 18 May 2023].
[6] Xilinx, "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators," 07 July 1996. [Online]. Available: https://docs.xilinx.com/v/u/en-US/xapp052. [Accessed 18 May 2023].