# Near-Optimal Weather Routing by Using Improved A* Algorithm
## 3 Improved A* Algorithm
### Heuristic Function Using Haversine Method
#### 3.2.2 Grid Mapping  
Before the route-finding algorithm is run, a base map, which is a graph including nodes and edges to be used as base terrain information for ship operation, must be defined at a constant latitude and longitude interval. However, the node and edge, which are arc shapes on the surface of a sphere, require complex calculations to find the optimal route, so the base map must be transformed into a two-dimensional(2-D) grid map through the equirectangular projection. This 2-D grid map enables the base map to be represented in rectangular shapes, which can help users to visually understand the real sphere map. However, if any place on the sphere is projected into a plane, distortion of its area, angle, direction, and distance occurs. All projections cause distortion in varying degrees and cannot be performed with preserving the above properties [26]. Therefore, projection needs to be chosen to best suit the user's purpose. In the case of route optimization, preserving the angle of the heading direction is very important because the optimal route is found based on the grid. However, AIS and weather data have the problem of using an equidistant latitude and longitude and therefore cannot preserve angles. Therefore, in this study, a method of converting the base map into a conformal map is proposed.  
To convert the base map into a conformal map, the base map should locally maintain an equivalent scale in the \(x\)- and \(y\)-directions (east and north) based on the prime meridian. In other words, as the latitude changes from \(0^{\circ}\) to \(\varphi\), the radius of the parallel of latitude \(\varphi\) also should be changed from \(R\) to \(Rcos\varphi\), as shown in Figure 3. Thus, each distance along the parallel is increased by \(sec\varphi\), which is a scale factor for the parallel of latitude \(\varphi\). Because of the conformality, the circle of the parallel is expanded by the factor \(sec\varphi\) in all directions.  
When the geographic coordinates of latitude \(\varphi\) are expressed as Cartesian coordinates of \(y(\varphi)\) on the base map with the \(x\)-axis along the equator and origin on the equator, by integrating \(Rsec\varphi\), the corresponding \(y\)-coordinate is calculated as follows.  
\[y(\varphi)=R\int\limits_{0}^{\varphi}sec\varphi d\varphi=Rln\left|\tan\left( \frac{\varphi}{2}+\frac{\pi}{4}\right)\right| \tag{4}\]  
The \(y\)-coordinate calculated using Equation (4) is used to calculate a ship's angle of navigation, COG, on the actual spherical surface of the earth.  
Figure 4 shows how COG is defined through the conformal mapping. For this, the distance between two points in the \(y\)-direction is increased by the following scale factor \(S\) for conversion to the  
Figure 3: Spherical-shaped earth.  
conformal map during the movement of the base grid map from point \(p\) with latitude \(u\) to point \(q\) with latitude \(v\), as shown in the figure.  
\[S=\int\limits_{u}^{v}secpd\varphi \tag{5}\]  
In other words, the spacing between the latitudinal lines of the two points must be increased by \(S\) to maintain the actual distance ratio from the earth. Consequently, the COG can be calculated from any arbitrary points \(p\) to \(q\) and is defined as follows.  
\[COG=\begin{cases}atan2(n_{col},Sn_{row}),&if\ \text{atan2}(n_{col},Sn_{row}) \geq 0\\ 360+\frac{180}{\pi}atan2(n_{col},Sn_{row}),&otherwise\end{cases} \tag{6}\]  
where \(n_{row}\) and \(n_{col}\) are the numbers of rows and columns that change when moving to the next node, respectively. The length of each grid is determined by the resolution of the map data.  
A conformal map with this 2D array format was used to calculate the ETA-based path cost (heuristic cost of the A* algorithm) without additional computation through simple array indexing, as described in the next section.