# Outside Dynamic Evacuation Routes to Escape a Wildfire: A Prototype App for Forest Firefighters
## 3 Materials and Methods
### Wildfire Spread Algorithm  
The propagation model uses an automated cell with geographic information using Google Maps. The algorithm has an accuracy of 99% using as a base the [PERSON] model, as described in [14]. This paper describes a previous work where the feasibility of a tool for predicting forest fires and state change rules in cellular automata is analyzed. The equation to obtain the probability that a cell is burning is given by [35]:  
\[P_{burn}=P_{0}(1+P_{vgg})(1+P_{den})P_{w}P_{ele} \tag{1}\]  
where  
* \(P_{0}\) is an empirical factor with a value of 0.58. * \(P_{vgg}\) (Vegetation) depends on the kind of vegetation in the zone. * \(P_{den}\) (Density) can have the values of limited \(=-0.4\), medium \(=0\), or high \(=0.3\). * \(P_{w}\) (Wind speed) is the angle between the direction of propagation of the fire (the direction in which the neighboring cell has been with respect to the center) and the wind direction. * \(P_{ele}\) indicates fire spreads faster if it goes uphill than downhill. The fire propagation is carried out on an image of the forest obtained from the Google Maps API. It is divided into 25 smaller images called _Tiles_ and where there is a 256 \(\times\) 256 px matrix. The matrix represents the cellular automata (CA) (Figure 2). CA considers a finite number of states that evolve according to a set of rules in discrete time; the possible states are:  
* _State 1_: The cell does not contain vegetation and therefore cannot catch fire. * _State 2_: The cell contains fuel, but it has not yet caught fire. * _State 3_: The cell is on fire. * _State 4_: The cell contained vegetation and burned. Figure 1: External application interaction diagram with algorithms for the creation of evacuation routes. In each discrete step (\(t\)) of the simulation, there are several rules for the transition of the states, given the cell (_i,j_):  
* _Rule 1:_ If the state of (\(i,j,t\)) = 1, then the next state will be (\(i,j,t+1\)) = 1. Therefore, cells that do not contain fuel will remain in the same state, because they cannot catch fire. * _Rule 2:_ If the state of (\(i,j,t\)) = 3, then the next state will be (\(i,j,t+1\)) = 4. Therefore, if the current cell is on fire, in the next step, it will be considered completely burned out. * _Rule 3:_ If the state of (\(i,j,t\)) = 4, then the next state will be (\(i,j,t+1\)) = 4. Therefore, if the cell is completely burned, its state will not change. * _Rule 4:_ If the state of (\(i,j,t\)) = 3, then the state of (\(i\pm\alpha,j\pm\alpha,t+1\)) = 3, \(\alpha\in\{0,1\}\), with certain probability of fire. Therefore, if the current cell is burning, its neighboring cells will burn as well, unless they have already been evaluated by the above rules. Algorithm 1 shows the analysis that is performed for each cell in the CA. This process is repeated for each neighbor of a point. The algorithm only needs a location to evaluate and the points of interest (initial, ignition point of the fire; location, location point of the person at the start of the wildfire). Figure 2: Google Tile creation process for the evaluation of CAs in fire prediction. ```
Result: Propagation (Change of states) Input: Location, Init point, directory. Output: CA with propagation information of each cell:(IDmesh) Cell ID, (degree)  Next step to a neighbor in that direction, (x, y) Position on the Tile, (lat, long)  Latitude and longitude, (ele) Elevation, (Pburn) Probability of the cell catching  fire, (State) Cell Status. Get the Google Tile to start processing. Extracted from directory  Obtain the mesh (matrix) for the cellular automata of the Google Tile chosen. (location)  The initial position is obtained for the fire spread calculation. (init point) whileNeighbors existdo  The probability that a cell changes state is calculated (Pburn)  Depending on Pburn, the state is verified.