很早就听说过A*算法，据说在寻路径时，是一种比较高效的算法。但是一直没有搞清楚原理。

这段时间刚好有个营救公主的例子：

题描述 :
公主被魔王抓走了 ， 王子需要拯救出美丽的公主 。 他进入了魔王的城
堡 ， 魔王的城堡是一座很大的迷宫 。 为了使问题简单化 ， 我们假设这个迷宫是一
个 N*M 的二维方格 。 迷宫里有一些墙 ， 王子不能通过 。 王子只能移动到相邻 （ 上
下左右四个方向 ) 的方格内 ， 并且一秒只能移动一步 ， 就是说 ， 如果王子在 (x,y ）
一步只能移动到 (x-1,y),(x+1,y),(x,y-1),(x,y+1) 其中的一个位置上。地图由
‘S’，‘P’，‘ . ’ ， ‘ *’ 四种符号构成 ， ‘ . ’ 表示王子可以通过 ， ‘ *’ 表示
墙，王子不能通过；'S'表示王子的位置；‘P’表示公主的位置； n表示公主存活的剩余时间，王子必须在 n 秒
内到达公主的位置，才能救活公主。

解题思路：

1、可以通过广度优先的算法进行演进，不停的查找王子的所有下一点的位置，没查找一次时间减1，直到找到了公主或者时间为0时终止。

这个算法能够比较快速的解决上述的迷宫问题；

2、通过A*算法，查找出每次移动可能到达的所有点，并设置了一定的权值规则，每次选取权值最小的一个点找它的下一个点……(当然，这是搞懂原理之后的后话:) )

本着锻炼下自己的原则选择了A*算法解决上面的问题。

代码实现简要说明：

1、定义了一个迷宫类 Maze，迷宫中包含了王子Prince（包含核心算法）和迷宫的地图MazeMap，迷宫（游戏）启动时，会先初始化地图，然后王子开始寻路（具体算法看代码）;

2、定义了一个位置类Position，描述了二维坐标信息，及加权的PositionWeight类，包含了位置信息、距离王子的距离（A*算法中的G）、距离公主的距离（A*算法中的H）、及二者的总开销(F=G+H)；

相信看懂了A*算法的原理的朋友，很快就能写出一个迷宫的实现方案。

下面贴一下我的实现，注释还算比较详尽，欢迎批评指正:)

[java]
/**
* 迷宫中的位置点 创建人：dobuy
*
*/
public class Position
{
/**
* 水平或者垂直移动一格的距离
*/
private final static int STRAIGHT_DISTANCE = 10;

/**
* 对角线移动一格的距离
*/
private final static int DIAGONAL_LINE_DISTANCE = 14;

private int x;
private int y;

public Position(int x, int y)
{
super();
this.x = x;
this.y = y;
}

/**
* 获取从父节点直接偏移至子节点的距离
*/
public int getOffsetOfDistance(Position position)
{
int x = Math.abs(getX() - position.getX());
int y = Math.abs(getY() - position.getY());

Position offset = new Position(x, y);
if (offset.equals(new Position(0, 1))
|| offset.equals(new Position(1, 0)))
{
return STRAIGHT_DISTANCE;
}
return DIAGONAL_LINE_DISTANCE;
}

/**
* 获取到目标节点的平移距离
*/
public int getDistanceOfTarget(Position position)
{
int verticalDistance = Math.abs(getY() - position.getY());
int horizontalDistance = Math.abs(getX() - position.getX());
return (verticalDistance + horizontalDistance) * STRAIGHT_DISTANCE;
}

public Position offset(Position offset)
{
return new Position(getX() + offset.getX(), getY() + offset.getY());
}

public int getX()
{
return x;
}

public void setX(int x)
{
this.x = x;
}

public int getY()
{
return y;
}

public void setY(int y)
{
this.y = y;
}

@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Position other = (Position) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

@Override
public String toString()
{
return "Position [x=" + x + ", y=" + y + "]";
}
}

/**
* 迷宫中的位置点 创建人：dobuy
*
*/
public class Position
{
/**
* 水平或者垂直移动一格的距离
*/
private final static int STRAIGHT_DISTANCE = 10;

/**
* 对角线移动一格的距离
*/
private final static int DIAGONAL_LINE_DISTANCE = 14;