后面准备谈谈个人对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两个参数，不再附上。
,
