我早就听说过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*算法来解决上述问题。

原则上我不会教鱼游泳。具体请看牛人的博文：http://www.blueidea.com/tech/multimedia/2005/3121_3.asp,在下面的回复中，另一个牛人已经实现了Flash版的A*算法。就我个人而言，我相当愚蠢。看了几遍才明白。如果你还没接触过，想学，不妨根据图示在纸上或电脑上计算。我相信原则很快就会清楚。

代码实现简要描述：

1.定义了一个迷宫类。迷宫包含Prince(包括核心算法)和MazeMap。当迷宫(游戏)开始时，地图会先被初始化，然后王子会开始找路(具体算法见代码)。

2.定义了描述二维坐标信息的position类Position，以及包含位置信息、与王子的距离(A*算法中的G)、与公主的距离(A*算法中的H)以及两者总成本(F=G H)的加权PositionWeight类。

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

让我们在下面发布我的实现。评论相当详细。欢迎批评指正：)

/**

*迷宫中的定位点，由：dobuy创建

*

*/

公共阶级立场

{

/**

*水平或垂直移动一个网格

*/

私有最终静态int STREET _ DIMENSION=10；

/**

*一个网格的对角线移动距离

*/

私有最终静态int对角线_ LINE _ DISTANCE=14

私有int x；

私有int y；

公共位置(int x，int y)

{

super()；

this.x=x

this.y=y

}

/**

*直接获取父节点到子节点的距离

*/

公共整数偏移位置(位置位置)

{

int x=Math . ABS(GetX()-position . GetX())；

int y=math . ABS(GetY()-position . GetY())；

位置偏移=新位置(x，y)；

if (offset.equals(新位置(0，1))

|| offset.equals(新位置(1，0)))

{

返回直线距离；

}

返回对角线_直线_距离；

}

/**

*获取到目标节点的平移距离

*/

公共整数获取距离目标(位置位置)

{

整数=数学