Ship path planning method based on hexagonal grid and A^* algorithm

To address the limitations of the conventional square grid in ship path planning-such as insufficient safety margins, low search efficiency, and poor adaptability to ship maneuvering characteristics-this study proposes a ship path planning method based on a regular hexagonal grid and an improved A^* algorithm. A hexagonal grid neighborhood model is constructed according to the geometric properties of the regular hexagonal grid and the required ship-obstacle safety clearance, together with an encoding scheme suitable for hexagonal cells. A ship motion cost model is developed by incorporating ship inertia and turning constraints. Based on this model, the traditional A^* algorithm is improved by optimizing the heuristic function and introducing a turning-penalty mechanism, thereby forming a hexagonal-grid-based search algorithm for ship path planning. Comparative experiments show that, compared with the square-grid 8-neighborhood method, the proposed method shortens the path by 5.51% and reduces the number of search nodes by 30.7%; compared with the 4-neighborhood method, the path length is reduced by 17.0% and the number of turning points decreases by 38.6%. The paths generated on the hexagonal grid are smoother and more consistent with ship maneuvering characteristics.