# Near-Optimal Weather Routing by Using Improved A* Algorithm
## 3 Improved A* Algorithm
### Adaptive Grid System  
In general, map data is collected in the form of a square grid. Thus, it is easy for typical rectangular projection methods such as equirectangular projection method to perform map projection because they can utilize the given form of map data as it is. The equirectangular projection is a very simple map projection used for the base map as meridional intervals of constant spacing and constant intervals of parallels. However, this projection is neither equal area nor conformal and it is distorted along the latitude. This distortion causes the problem of formation of disparate grids when the base map is decomposed in grid format. Even though the grid is defined at equal angle spacing, because the area of interest is close to the polar region, the distance between meridians becomes narrower, which means that the resolution is coarse near the equator and fine in the polar region. However, these irregular resolutions result in an unnecessarily large number of search nodes.  
Therefore, in this study, an adaptive grid system was used for efficient space search of route finding, facilitating multiple steps of grids in the transverse direction according to the latitude values, which enables the grid map to be conformal. Although the shape of the grid map cannot accurately reflect the continuously changing latitudes because of its discrete nature, the adaptive grid system can be applied on the basis of the critical points at which the distance size of the grid changes in an integer ratio.  
As explained in Section 3.2.2, the closer the latitude is to the polar region, the more distortion of the grid geometry, so the grid close to an equator with little distortion needs to be explored for  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Count**} & \multirow{2}{*}{**Mean**} & \multirow{2}{*}{**Std** **(knots)**} & \multirow{2}{*}{**Min** **(knots)**} & **25\%** & **50\%** & **75\%** & **99\%** & **Max** \\  & & & **(knots)** & **(knots)** & **(knots)** & **(knots)** & **(knots)** & **(knots)** \\ \hline
44,405 & 13.5815 & 1.3941 & 8.8 & 12.8 & 13.9 & 14.6 & 16.1 & 18.2 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Statistical characteristics of SOG.  
Figure 5: Histogram and boxplot of SOG data.  
each grid in the transverse direction. On the other hand, the closer the latitude is to the polar regions, the closer the distance between the grids on the sphere is by the ratio of \(\cos(\varphi)\), as shown in Figure 3; the map grids need to be grouped together to avoid unnecessary routing process that explores all grids.  
Therefore, it is necessary to increase the efficiency of the routing process by efficiently grouping grids by reflecting the degree of distortion of grids as latitude increases. The grid search needs to determine a step size considering the distortion ratio of the grid shape. As shown in the right side of Figure 6 if the step size increases by 1 from 1 to 2 and 3 according to the latitude increases, an imbalance between the sectors classified according to the step size occurs, and thus, inefficient grid search is performed at high latitudes with severe grid distortion. On the other hand, as shown in the left side of Figure 6, if the step size increases more smoothly from 1 to 1.5 and 2.5, it can mitigate the imbalance between the sectors, enabling more efficient grid search. As a result, this adaptive grid system facilitates the generation of continuous shape paths by smoothly reflecting the distortion of the grid in accordance with continuous latitude changes. Thus, the route can be navigated efficiently, especially when performing route optimization at high latitudes; this thereby improves the ease of route optimization calculation in conjunction with the COG, which calibrates the direction of ship's navigation on a real spherical surface as explained in Section 3.1.