我对AStar算法的探索

最近读到一篇关于《HTML5实现炮塔防守》的文章，对其中的路径搜索算法有点兴趣，稍微探索了一下。


基于搜索下载的Micheal Hong的Java版本的AStar算法，并做了一些调整。核心代码如下：

while (open.isEmpty() == false) {
			close.add(open.remove(0));
			getNeighbour(node, neighbour);
			for (int i = 0; i < neighbour.length; i++) {
				if ((index = contain(open, neighbour[i].x, neighbour[i].y)) != -1) {
					if (open.get(index).gn > neighbour[i].gn)
						// 以前掠过这个节点的时候（getNeighbour的形式）的代价比现在掠过这里的代价大，说明现在的掠过更好
						// 所以用现在的掠过代替？也就是说要把原来的那个替换掉，
						open.set(index, neighbour[i]);
					// 反之，就不考虑这个新的掠过
				} else
					open.add(neighbour[i]); // 没有曾经掠过，就作为候选节点加入
			}
			/* 判断是否到达目标 */
			if ((index = contain(open, end.x, end.y)) != -1) {
				int count = 1;
				Node d = open.get(index);
				while (d.father != null) {
					d = d.father;
					count++;
				}

				d = open.get(index);
				int[][] path = new int[count][];
				for (int i = count - 1; i >= 0; i--) {
					path[i] = new int[2];
					path[i][0] = d.x;
					path[i][1] = d.y;
					d = d.father;
				}
				return path;
			}
			/* 对open表进行排序(按fn由小到大) */
			// 我认为可以不用sort，只是取一个值而已，
			// 也可以在加入open队列的时候就已经形成了大值排序
			Collections.sort((open));
		}

我认为AStar算法的思想不错。
对于遍历，我们想到的可能就是深度优先遍历和广度优先遍历，但是那种教科书式的遍历方法的搜索空间太大了。
于是人们想到了缩小范围的方法，技术总是在不断改进的驱动下进步的。
AStar就是这个思想驱动下诞生的，首先基于原有广度优先遍历会随着层级的递增可选的next step会越来越多，我们不难想到如何在可选的next step集合中找到一个最优的next step，所以关键点就在于如何定义这个最优评估的方法的问题了。
AStar的评估方法就是F=H+G,也就是说评估值等于已经走过的路径总长度加上未来可能还需要走的路径总长度。全局排序后选最优的，也就是最短的。
已经走过的路径很容易，只要我们把它记录累加就能得到，所以关键点又落到了如何预估未来需要走的路径总长度。
那未来需要走的路径总长度又怎么评估呢？就像一个人进入一个沙漠，完全不知道剩下的路到底还有多长，只知道自己已经走了三天三夜，呵呵。
AStar给出了一个方案，那就是当前坐标和目的地坐标的X，Y的差值和，外国人叫曼哈顿距离。具体见百度百科
这样通过比较F值也就是说总路程最短的优先作为next step（虽然只是预估出来的）。
这就像迷茫的寻路过程有了一盏灯指引着你走向终点。而这盏灯其实关键点就是那个曼哈顿距离，所以AStar算法是一种启发式的路径搜索算法。

膜拜了一下这个曼哈顿距离，不经让我发问：为什么就曼哈顿距离而不是其他距离？（TB continue..）