Triplebyte Blog

We help engineers join great companies
Try our coding quiz

Share this article

Modeling How Fire Spreads

By Jen Ciarochi on Jul 27, 2020

Modeling How Fire Spreads

Summary: This article explains how to build and modify a simple fire model, and explores two popular methods to simulate fire spread—cellular automaton and wave propagation models.

It’s Fire Season

 
In July, the Western United States enters the core of the fire season. Many parts of the country are experiencing below-average precipitation and above-average temperatures—creating hot, dry conditions that are ideal for wildfires.

14dayClimateMapscloser.png

NOAA Regional Climate Centers: Generated at HPRCC using provisional data.

Mathematical models of fire behavior, and the calculation systems based on them, are an important part of fire mitigation. Fire models can help determine where a fire is likely to start, how quickly it will spread (and in what direction), and how much heat it will generate; these important clues can save lives and substantially curb financial losses[1].

Modeling Fire Growth: Cellular Automata

 
A simple cellular automaton forest fire model consists of a grid of cells, and each cell can be in one of three states: Fire_Fig1.png

At each time step, the state of each cell on the grid is determined by four rules that the model carries out simultaneously:

Fire_Fig2.png  

A Cellular Automaton Forest Fire Model in Python

 
These four fire model rules are implemented by the iterate function of a cellular automaton model created by Christian Hill1. You can view the full code, with an aggressive amount of explanatory comments, here.

fire_ezgif.gif

# This function iterates the forest fire model according to the 4 fire model rules.
# X is the current state of the forest and X1 is the future state. 
def iterate(X):
    
    # RULE 1 ("A burning cell becomes an empty cell") is handled by 
    # setting X1 to 0 initially and having no rules that update FIRE cells. 
    X1 = np.zeros((ny, nx))
    for ix in range(1,nx-1):
         for iy in range(1,ny-1):
            
            # RULE 4 ("An empty cell becomes a cell with a tree at probability p") 
            if X[iy,ix] == EMPTY and np.random.random() <= p:
                 X1[iy,ix] = TREE
                 
            # RULE 2 ("A cell with a tree becomes a burning cell if at least one 
            # of its neighbors is a burning cell.")
            if X[iy,ix] == TREE:
                 X1[iy,ix] = TREE
                 for dx,dy in neighborhood:
                     if X[iy+dy,ix+dx] == FIRE:
                         X1[iy,ix] = FIRE
                         break
                         
                 # RULE 3 ("A cell with a tree ignites at probability f even if 
                 # none of its neighbors are burning").
                 else:
                     if np.random.random() <= f:
                         X1[iy,ix] = FIRE
         return X1

 

Modifying the Model

 
Some simple modifications to the code can add other features to the model that influence fire spread. For example, to add water bodies—which can block fire spread, I first defined a new cell state (WATER) and expanded the color list and bounds accordingly:

EMPTY, TREE, FIRE, WATER = 0, 1, 2, 3
colors_list = [(0.2,0,0), (0,0.5,0), (1,0,0), 'orange', 'blue']
cmap = colors.ListedColormap(colors_list)
bounds = [0,1,2,3,4]
norm = colors.BoundaryNorm(bounds, cmap.N)

 

Then, I added another rule to the iterate function, which simply ensures that WATER cells remain WATER cells.

def iterate(X):
    X1 = np.zeros((ny, nx))
    for ix in range(1,nx-1):
         for iy in range(1,ny-1):
            if X[iy,ix] == WATER:
                 X1[iy,ix] = WATER
            if X[iy,ix] == EMPTY and np.random.random() <= p:
                 X1[iy,ix] = TREE
            if X[iy,ix] == TREE:
                 X1[iy,ix] = TREE                 
                 for dx,dy in neighborhood:
                     if X[iy+dy,ix+dx] == FIRE:
                         X1[iy,ix] = FIRE
                         break
                 else:
                     if np.random.random() <= f:
                         X1[iy,ix] = FIRE
         return X1

 

Finally, I defined the boundaries of the water bodies (in this case, four vertical “streams”).

X[10:90, 10:15] = WATER
X[10:90, 40:45] = WATER
X[10:90, 60:65] = WATER
X[10:90, 80:85] = WATER

 
These adjustments produce a model that shows how fire growth is restricted by water:

WithWater_ezgif.gif

Notably, in the real world, fire can sometimes “jump” over barriers—a behavior called spotting that creates trouble for fire modelers and responders alike.  

The original model can also be modified to include wind, which can dramatically affect fire spread. To achieve this, I first modified the original neighborhood (commented out below), such that NY and NX respectively represent the first and second coordinates of the original neighborhood.

# neighborhood = ((-1,-1), (-1,0), (-1,1), (0,-1), (0, 1), (1,-1), (1,0), (1,1))
# NY and NX are now neighborhood
NY=([-1,-1,-1,0,0,1,1,1])
NX=([-1,0,1,-1,1,-1,0,1])

 

Just below NY and NX, I defined NZ, which represents wind. Each value in NZ corresponds to one of the coordinates in neighborhood (NY and NX). If at least one of the index values in a neighbor-specifying pair of NY, NX is negative, the corresponding NZ value is 0.1. Otherwise, NZ is 1. As a concrete example, the first value of both NY and NX is -1, so this first pair of coordinates corresponds to the neighbor at (-1,-1). Thus, the NZ value corresponding to this pair is 0.1. This modification ends up biasing fire spread in the direction that wind is blowing, as I explain shortly.

NZ=([.1,.1,.1,.1,1,.1,1,1])

 

The final step is to modify the iterate function to check all neighboring cells. If a neighbor is on fire AND a randomly generated number is less than the neighbor's NZ value (0.1 or 1), the cell catches on fire. Since the random number is a float >0 and <1, when NZ = 1, the random number will always be smaller and the cell will burn. Similarly, 0.1 is below most random numbers generated. This biases fire spread with wind direction.

def iterate(X):
    X1 = np.zeros((ny, nx))
    for ix in range(1,nx-1):
         for iy in range(1,ny-1):
            if X[iy,ix] == EMPTY and np.random.random() <= p:
                 X1[iy,ix] = TREE
            if X[iy,ix] == TREE:
                 X1[iy,ix] = TREE
                 # Check all neighboring cells.
                 for i in range(0,7):
                    # Bias fire spread in the direction of wind.
                    if X[iy+NY[i],ix+NX[i]] == FIRE and np.random.random()<=NZ[i]:
                        X1[iy,ix] = FIRE                 
                         break
                 else:
                     if np.random.random() <= f:
                         X1[iy,ix] = FIRE
         return X1

 

This example code produces a fire model with wind blowing uniformly from the southeast. withWind_ezgif.gif

 

Modeling Fire Growth: Wave Propagation

 
Cellular models, like the one depicted above, simulate fire spread as a contagion process in which fire spreads between cells. One of the major shortcomings of this method is that the use of a gridded landscape distorts fire geometry, although there are methods to help mitigate this (e.g., increasing the number of neighbor cells).

Today, some of the most widely used fire simulators (e.g., FARSITE, Prometheus) are based on Huygens principle of wave propagation. Huygens principle was originally proposed to describe traveling light waves, and also explains how sound waves can travel around corners. The crux of Huygens principle is that every point on the edge of a wave-front can be an independent source of secondary wavelets that propagate (i.e., spread) the wave.

Although Huygens studied light (not sound) and never married, this is what I imagine: HuygenssHouse.png

Wave propagation models simulate fire as an elliptical wave that spreads via smaller secondary elliptical fire wavelets on the fire front. At each time step, the model uses information about the fire environment to define the shape, direction, and size (spread rate) of each wavelet. Shape and direction are determined by the wind-slope vector, while size is determined by fuel conditions.

The new wave-front is the surface tangential to all the secondary wavelets. In other words, the small ellipses form a kind of envelope around the original fire perimeter, and the outer edge of this envelope is the new fire front.

FF.png Huygen’s principle in the context of fire spread2. Wind is uniform and traveling from the southwest. A) Fire spread across a landscape with homogeneous fuel sources. B) Fire spread across a mosaic landscape with four different fuel types and wind speeds, which change the size and shape of the wavelets.

 

Yes, Fire Modeling Is Considerably More Complicated Than This

 
While cellular automaton and wave propagation models are an essential part of many fire growth simulators, in real-world applications, they become a relatively minor component of a complex simulation process that also incorporates many other models.

These additional models capture factors related to weather, fuel type (fuel is anything that can burn), and topography, which greatly influence fire growth. Additionally, “fires create their own weather,” altering humidity and other aspects of their surrounding environment; this poses a formidable challenge for fire modelers.

Fire_Fig3.png

Select examples of weather- and topography-related factors that influence fire growth. These variables are often incorporated in fire growth simulators.

Consider FARSITE (now part of the FlamMap fire mapping and analysis system)—a prominent fire simulator used by the U.S. Forest Service, the National Park Service, and other state and federal agencies.

FARSITE implements Huygens principle using a set of differential equations developed by G.D. Richards in 1990. However, as the table below illustrates, FARSITE also incorporates many other models—as well as several geospatial data layers—to simulate fire growth. Richards’s equations are only used for a single step of the surface fire calculations and a single step of the crown fire calculations.

Models and Geospatial Data Layers Used by FlamMap/FARSITE

Model Geospatial data layers for landscape
Surface fire spread (Rothermel, 1972) Topographic (elevation, slope, aspect)
Crown fire initiation (Van Wagner, 1977) Fire behavior fuel models
Crown fire spread (Rothermel, 1991) Forest canopy cover
Spotting (Albini, 1979) Forest canopy height
Crown fire calculation (Finney, 1998; Scott and Reinhardt, 2001) Forest canopy base height
Dead fuel moisture (Nelson, 2000) Forest canopy bulk density

 

Fire Modeling Is a Balancing Act

 
Fire modeling requires tradeoffs among accuracy, data availability, and speed. For real-time responses to fire, speed is critical—yet the most physically complex models are impossible to solve faster than real time. As University of Denver researcher Jan Mandel articulated3:

“The cost of added physical complexity is a corresponding increase in computational cost, so much so that a full three-dimensional explicit treatment of combustion in wildland fuels by direct numerical simulation (DNS) at scales relevant for atmospheric modeling does not exist, is beyond current supercomputers, and does not currently make sense to do because of the limited skill of weather models at spatial resolution under 1 km.”

Notably, there are many types of fire behavior models, and these models can be classified based on the types of equations they use, the variables they study, and the physical systems they represent. For the interested reader, the appendix includes a breakdown of the different model classifications.

 

→ Coding Challenge

Can you build your own model (e.g., a cellular automaton) to simulate fire spread?

  • What additional factors can you add to your model?
  • How do you implement them?

Let us know your thoughts in the comments section!


Appendix

Classification of fire models based on equation type used, variables studied, and physical systems modeled. Most models currently used in the United States—including FARSITE—are semi-empirical. Many chemical and thermodynamic questions about fire behavior remain unanswered.

EQUATIONS VARIABLES PHYSICAL SYSTEMS
Theoretical models Based on laws of fluid dynamics, combustion, heat transfer Wildland fire spread models Rate of spread, fire intensity, fuel consumption Surface fire models Model surface fuel l<2 meters high
Empirical models Based on statistical correlations from experiments or historical fires Fire front properties models Geometric flame properties (e.g., height, length, depth, angle of inclination) Crown fire models Model surface and aerial vegetation
Semiempirical models Proposed based on simple, general theoretical expressions. Completed through experiments Spotting models Model burning material (firebrands) transported beyond the main fire perimeter
Ground fire models Model organic forest horizons below litter

References

Badger, Stephen, and Matthew Foley. “NFPA Journal - Fire Loss Report, November/December 2019“. National Fire Protection Association (NFPA), September 1, 2019. https://www.nfpa.org/News-and-Research/Publications-and-media/NFPA-Journal/2019/November-December-2019/Features/Large-Loss.

Hill, Christian. “Scipython-Maths: the Forest-Fire Model.” GitHub, March 13, 2018. https://github.com/scipython/scipython-maths/blob/master/forest_fire/forest_fire.py.

Mandel, Jan, Jonathan D Beezley, Janice L Coen, and Minjeong Kim. “Data Assimilation for Wildland Fires: Ensemble Kalman Filters in Coupled Atmosphere-Surface Models.” IEEE Control Systems 29, no. 3 (June 2009): 47–65. https://doi.org/10.1109/mcs.2009.932224.

“Modeling Fire Growth (FARSITE Technical Documentation).” http://fire.org/downloads/farsite/WebHelp/technicalreferences/tech_modeling_fire_growth.htm.

“National Significant Wildland Fire Potential Outlook: Outlook Period – July, August, September, and October 2020.” National Interagency Coordination Center (NICC). Predictive Services National Interagency Fire Center, July 1, 2020. https://www.predictiveservices.nifc.gov/outlooks/monthly_seasonal_outlook.pdf.

Pais, Cristobal, Jaime Carrasco, David L. Martell, Andres Weintraub, and David L. Woodruff. “Cell2Fire: A Cell Based Forest Fire Growth Model,” May 22, 2019. https://arxiv.org/abs/1905.09317.

Pastor, E. “Mathematical Models and Calculation Systems for the Study of Wildland Fire Behaviour.” Progress in Energy and Combustion Science 29, no. 2 (2003): 139–53. https://doi.org/10.1016/s0360-1285(03)00017-0.

Richards, Gwynfor D. “An Elliptical Growth Model of Forest Fire Fronts and Its Numerical Solution.” International Journal for Numerical Methods in Engineering 30, no. 6 (1990): 1163–79. https://doi.org/10.1002/nme.1620300606.

Footnote

[1] Fires cause thousands of civilian deaths and billions of dollars in property loss each year. In 2018 alone, the six costliest fires (Camp Fire, Woolsey Fire, Carr Fire, Ranch Fire, West Fire, and Cranston Fire—all in California) caused $12.4 billion in property losses. In fact, 2018 was the most expensive fire season since 2001—which included 9/11 losses—and the second costliest since records began in 1975.

Get offers from top tech companies

Take our coding quiz

Discussion

Liked what you read? Here are some of our other popular posts…

Triplebyte’s Way-Too-Long Technical Interview Prep Guide

By Triplebyte on Apr 29, 2020

A running collection of technical interview preparation resources that we've collected at Triplebyte.

Read More

How to Pass a Programming Interview

By Ammon Bartram on Apr 29, 2020

Being a good programmer has a surprisingly small role in passing programming interviews. To be a productive programmer, you need to be able to solve large, sprawling problems over weeks and months. Each question in an interview, in contrast, lasts less than one hour. To do well in an interview, then, you need to be able to solve small problems quickly, under duress, while explaining your thoughts clearly. This is a different skill. On top of this, interviewers are often poorly trained and inattentive (they would rather be programming), and ask questions far removed from actual work. They bring bias, pattern matching, and a lack of standardization.

Read More

How to Interview Engineers

By Ammon Bartram on Jun 26, 2017

We do a lot of interviewing at Triplebyte. Indeed, over the last 2 years, I've interviewed just over 900 engineers. Whether this was a good use of my time can be debated! (I sometimes wake up in a cold sweat and doubt it.) But regardless, our goal is to improve how engineers are hired. To that end, we run background-blind interviews, looking at coding skills, not credentials or resumes. After an engineer passes our process, they go straight to the final interview at companies we work with (including Apple, Facebook, Dropbox and Stripe). We interview engineers without knowing their backgrounds, and then get to see how they do across multiple top tech companies. This gives us, I think, some of the best available data on interviewing.

Read More