This paper introduces a novel algorithm for solving the point-to-point shortest path problem in a static regular 8-neighbor connectivity (G8) grid. This algorithm can be seen as a generalization of Hadlock algorithm to G8 grids, and is shown to be theoretically equivalent to the relaxed $A^*$ ($RA^*$) algorithm in terms of the provided solution's path length, but with substantial time and memory savings, due to a completely different computation strategy, based on defining a set of lookup matrices. Through an experimental study on grid maps of various types and sizes (1290 runs on 43 maps), it is proven to be 2.25 times faster than $RA^*$ and 17 times faster than the original $A^*$, in average. Moreover, it is more memory-efficient, since it does not need to store a G score matrix.

该研究介绍了一种新的算法，用于在静态常规8邻接连通（G8）网格中解决点对点最短路径问题，该算法可以看作是Hadlock算法对G8网格的泛化，并且从计算策略完全不同的角度，通过定义一组查找矩阵，以较少的时间和内存开销实现了在提供的解决方案路径长度方面与松弛型$A^*$（$RA^*$）算法在理论上的等效性，通过对各种类型和大小的网格地图的实验研究（1290次实验对比43张地图），平均比$RA^*$快2.25倍，比原始$A^*$快17倍，而且在内存效率上更优越，因为它不需要存储G分数矩阵。

ERA*: 正规栅格地图中解决最短路径问题的增强松弛A*算法

ERA: 正规栅格地图中解决最短路径问题的增强松弛A算法