后面准备谈谈个人对A*算法的理解，这篇算是很重要的基础知识。

之前说到地图上一般用网格图的方式进行简化和标准化，那么计算两点之间的距离，常用的方法有三：

曼哈顿距离

适用于只可上下左右移动的地图。最典型的可以看回龙观地图：

回龙观地图

如上图，假设你坐一辆出租车，想从A点到B点，只能向上下左右方向移动，图中蓝线这种斜穿小区的移动是不可以的，所以也叫出租车距离、城市街区距离。

网格图

如上图，红色方块仅可向上下左右四个绿色方块移动。

曼哈顿距离就是两个点在标准坐标系上的绝对轴距总和。

曼哈顿距离

如图，设A(1,2)，B(4,4)，设直线移动一单位距离为D，则公式为：

(|A.x-B.x|+|A.y-B.y|)*D。

可得d=(|1-4|+|2-4|)*D=5D。

上图红黄绿三条线路的曼哈顿距离都是5D。

对角线距离

适用于可以斜向移动的图形，如下图。

网格图

设直线移动一单位距离为D，那么斜向移动距离，其实就是根据勾股定理，求腰为D的等腰直角三角形的斜边，即√2D。

对角线距离

设A(1,2)，B(4,4)，根据公式：

dx=|A.x-B.x|

dy=|A.y-B.y|

D*(dx+dy)+(√2D-2D)*min(dx,dy)

可得距离约等于3.8D。

因为涉及到开2的平方根计算，必然出现浮点数，计算机处理起来比较耗费资源，在这里我们可以在损失一定精度的情况下，进行优化。

我们知道√2≈1.4，如果我们假设D=10，则√2D≈14，如此，我们将两个常数代入公式，就将涉及浮点数的开平方根运算转换成了整数的加减乘运算。

得出距离为38。

欧几里得距离

适用于可以随意移动的图形。

欧几里得距离

其实就是根据勾股定理求斜边。

设直线移动一单位距离为D，公式如下：

dx=|A.x-B.x|

dy=|A.y-B.y|

D*sqrt(dx*dx+dy*dy)

如上图，设A(1,1)，B(5,4)，勾三股四弦五，AB的直线距离必为5。

多啰嗦几句，因为地球是个球体，我们有山、高原、平原、盆地、海沟等地形，是个三维的，所以求两个真实地点的距离还要考虑更多的因素，比如两点的弧长，高度差、地球半径等。

但是如果只是估算一个大概的距离，或者只需要求出两点的最短路径，或者两点就在一个不大的区域内，比如回龙观。单纯地使用欧几里得算法也够用了。

代码

public class Distance {    /**     * 直线移动一单位距离代价     */    private static final BigDecimal straightCost = new BigDecimal(10);    /**     * 对角线移动一单位距离代价<br/>     * 如果要求高精度，可以设置为BigDecimal(Math.sqrt(2)).multiply(Distance.straightCost);     */    private static final BigDecimal diagonalCost = new BigDecimal(14);    /**     * 曼哈顿距离<br/>     * (|start.x-end.x|+|start.y-end.y|)*straightCost     *      * @param start     * @param end     * @return     */    public static BigDecimal manhattan(Node start, Node end) {        int dx = Math.abs(start.getX() - end.getX());        int dy = Math.abs(start.getY() - end.getY());        return Distance.straightCost.multiply(new BigDecimal(dx + dy));    }    /**     * 对角线距离<br/>     * 曼哈顿距离+(sqrt(2)-2*straightCost)*min(dx,dy)     *      * @param start     * @param end     * @return     */    public static BigDecimal diagonal(Node start, Node end) {        int dx = Math.abs(start.getX() - end.getX());        int dy = Math.abs(start.getY() - end.getY());        BigDecimal dxy = new BigDecimal(dx + dy);        BigDecimal minDxy = new BigDecimal(Math.min(dx, dy));        BigDecimal result = Distance.straightCost.multiply(dxy).add(Distance.diagonalCost.multiply(minDxy))                .subtract(minDxy.multiply(Distance.straightCost).multiply(new BigDecimal(2)));        return result;    }    /**     * 欧几里得距离<br/>     * 就是根据勾股定理求斜边。straightCost*sqrt(dx*dx+dy*dy)     *      * @param start     * @param end     * @return     */    public static BigDecimal euclidean(Node start, Node end) {        int dx = Math.abs(start.getX() - end.getX());        int dy = Math.abs(start.getY() - end.getY());        return Distance.straightCost.multiply(new BigDecimal(Math.sqrt(dx * dx + dy * dy)));    }    public static void main(String[] args) {        Node start = new Node(1, 1);        Node end = new Node(5, 4);        System.out.println(Distance.manhattan(start, end));        System.out.println(Distance.diagonal(start, end));        System.out.println(Distance.euclidean(start, end));    }}

Node类就x，y两个参数，不再附上。