大概半年前在写蜂窝网格的A*寻路算法时，遇到了如何选择启发式的问题。传统的曼哈顿距离虽然可以正常运行找到正确的最短路径，但是在蜂窝网格地图中，两点间的最短路径不止一条，曼哈顿距离会使路径的选择总是偏向某一方向。根本原因是启发式中的曼哈顿距离并不是两点间真正的最短距离。
在网上搜索了很多，但是一直没有搜到合适的方法，于是在炎热的某一天，自己动笔寻找这种方法。没想到的是答案竟然十分简单。
下图采用二维坐标表示了一个蜂窝网格地图，关于二维坐标系的选择，可以参考这一篇文章《蜂窝拓扑结构在SLG地图布局中的应用》。
在二维坐标系中，横坐标为x，纵坐标为y，可以得出结论，p1(x1,y1)和p2(x2,y2)之间的最短距离为：
注: 公式中的除法是求整数商，比如 3/2=1.
用这个公式可以计算出(1,1)到(4,4)的最短距离为
(|1/2-4/2+1-4|+|1-4x|+|(1-4)+(4/2-1/2)+4-1|)/2=5
看上去是有一些复杂，所以之前在用二维坐标寻找这个规律时费了很多工夫都没有找到，但是改成使用3个坐标来确定一个点的位置就会方便很多，如下图所示。坐标表示为(x,y,z)，出于对称的美观原因，我将Z轴按照负方向增长。在平面上，只需2个坐标即可表示一个点，所以第三个坐标必然可以通过前两个坐标推导出来，在这幅图中，z=y-x。这其中的数学原因不去深究，总之通过一些计算肯定可以得出其中的关系。
三维坐标中最引人注目的一个性质是，从任意一个点向相邻方向移动1格距离，一定会恰好使两个坐标都发生一次改变，改变的数值均为1。通过这个性质，可以得出两点之间的最短距离为：
最后，将三维坐标改为(x,y,y-x)代入上式，可得出二维坐标的最短距离公式，同时需要对二维坐标进行一些变换以适应蜂窝网格，最终就是第二张图中的公式。
