## 3 Dynamic Influence Map
### Spread and Attenuation Modes  
#### 3.2.1 Spread Modes  
When the starting point spreads influence to different locations on the map, the spread mode refers to the method used to measure the distance from the starting point to the destination point. The most commonly used methods include the Euclidean distance, Manhattan distance, path length between two points, and adjacent spread. Among these methods, the use of the two-point path length as the spread mode requires all paths to be calculated in advance because the real-time path finding affects the spread efficiency.  
The coordinate system is established with the upper-left corner of the game scene as the coordinate origin.  
1. Euclidean Distance  
When the Euclidean distance is used as the spread mode, the distance between the spread source and each point in the map is expressed as follows:  
\[d_{a,b}=d_{euclidean(a,b)}=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{ 2}\right)^{2}}, \tag{1}\]where \(d_{euclidean(a,b)}\) represents the Euclidean distance between point \(a\) and point \(b\). The coordinates of point \(a\) are \((x_{1},y_{1})\), and the coordinates of point \(b\) are \((x_{2},y_{2})\).  
This spread mode calculates the distance quickly because it only needs two coordinates to obtain a relatively acceptable result. However, if there are obstacles and other information in the path, this spread mode cannot perceive the distance.  
When the Manhattan distance is used as the spread mode, the distance between the spread source and the target point is measured as follows:  
\[d_{(a,b)}=d_{Manhattan(a,b)}=|x_{1}-x_{2}|+|y_{1}-y_{2}|, \tag{2}\]  
where \(d_{Manhattan(a,b)}\) represents the Manhattan distance between point \(a\) and point \(b\). The coordinates of point \(a\) are \((x_{1},y_{1})\), and the coordinates of point \(b\) are \((x_{2},y_{2})\).  
In addition, the path between two points can be used to represent the distance between these points. The measurement method is as follows:  
\[d_{(a,b)}=d_{path(a,b)}, \tag{3}\]  
where \(d_{path(a,b)}\) represents the path length obtained using the pathfinding algorithm. Compared with the Euclidean and Manhattan distance spread modes, this method can take into account the existence of obstacles. Because the pathfinding algorithm usually finds the shortest path, the measurement of distance is often quite accurate. However, in an actual game, especially real-time strategy games such as war games, the response time is an extremely important factor, and the calculation speed of the pathfinding algorithm seriously affects the real-time response ability.  
The adjacent spread method only needs to be executed once to spread the initial influence from the starting point to all points on the map. Using this method, a considerable amount of time can be saved as compared to the use of the pathfinding algorithm. Compared with the use of the Euclidean or Manhattan distance as the spread mode, the adjacent spread mode considers obstacles and other factors. Moreover, when a game unit moves, the influence map can be dynamically calculated and changed accordingly, which is more adaptable to dynamic games.  
Adjacent propagation does not calculate the path length between any two points directly. Instead, it propagates the influence of the adjacent grids of the game object. If the influence values of some of the adjacent grids are changed, then an AI agent propagates the new influence values from these grids with the same method. The influence value can be propagated to four or eight directions in square grids (as shown in Figure 1a,b, respectively) or to six directions in hexagonal grids (as shown in Figure 1c). This process is similar to the flood-fill algorithm.  
Figure 1: Propagation directions. (**a**) Four directions (**b**) Eight directions (**c**) Six directions.