# Outside Dynamic Evacuation Routes to Escape a Wildfire: A Prototype App for Forest Firefighters
## 3 Materials and Methods
### Evacuation Routes Algorithm  
A study area can be composed of multiple routes; however, to determine if a path is suitable to be part of an evacuation route, the algorithm evaluates the modified states of the CA cells after executing the fire spread algorithm and classifies them into new states according to the following rules:  
* _State 1_: The cell does not contain vegetation. It can be part of a safe evacuation route. * _State 2_: The cell contains fuel. It can be part of a safe evacuation route. * _State 3_: The cell is on fire. It will not be part of a safe route. * _State 4_: The cell contained vegetation and burned. It will not be part of a safe route. When the cellular automata has been created and an ignition point \(P_{i}=(X_{i},Y_{i})\) is specified in the matrix, it begins with the calculation of evacuation routes using a directed graph; G = (node, edge), where an edge \((e)\) is considered directed if it goes from a path (\(x\),\(y\)). The model currently calculates the evacuation routes considering the slope of the terrain using geo-referential positioning (latitude, longitude, and elevation), assuming that the area affected by the fire is a forest [15]. The \(CA\) analyzes the vegetation density by \(P_{i}\) to know if a cell can burn or not, i.e., evaluates if the cell is empty terrain, asphalt, or vegetable fuel. However, due to the precision of eight digits at each point in the matrix (CA), the distance between \(P_{i}=(X_{i},Y_{i})\) and \(P_{j}=(X_{j},Y_{j})\) is minimal (approximately one step). For this reason, the graph creates several branches in different directions of the Cartesian plane, considering that the neighborhood of a point \(P_{i}\) is evaluated. The route calculation starts from a position \((X_{i},Y_{i})\) adding a new node N to the graph; depending on whether the user moves uphill or downhill, assuming that you have two positions \((X_{i},Y_{i})\), these positions are composed of \(X_{i}=(lat_{i},lng_{i},ele_{i})\) and \(Y_{i}=(lat_{i},lng_{i},ele_{i})\). These points allow generating a route between the entire graph. The algorithm is described in detail in [15]. Figure 3 shows a schematic model of the evacuation route applying the _Dijkstra_ algorithm. The study area is converted into a graph, and the _Dijkstra_ search method is used to find the shortest route to a defined endpoint. The final states of the CA will serve to  
assign a cost to each node in the area. In the cells free or without fire, the probability of the cost will be minimal, while, for the burning or burned cells, the cost will be infinite. At each jump (discrete), each edge's costs are added to find the smallest, discarding repeated or unusable paths to optimize processing. The graph shown in the figure is referential. Each Google Tile processes a graph separately and is joined with another at the perimeter of the GTI. Finally, Algorithm 2 shows the calculation of evacuation routes after having created the CA. The result of this process is three positional arrays that allow creating a dynamic graph to find the route each time there is an event. ``` Result: Evacuation routes Input: Location, Init point,Tile, index, image name. Output: x : List with points of the path in the x-axis. y : List with points of the path in the y-axis. z : List with points of the path in the z-axis. Route Graph Algorithm: The automated cell where the person is initially is obtained while Not being in a safe area do ifThe next step is safe zonethen  The cell is added to the graph  Changing states in the cell else  The neighborhood of the following cell is obtained  The mesh (change) is obtained if the cell leaves the initial matrix. Positions are added to other graphs to verify possible evacuation routes  end if  end while The best evacuation route is obtained and shown in a figure (position: x, y, and z). Figure 3: Dijkstra algorithm for the creation of the evacuation route.