位置距离[置顶] 营救公主(Java实现A*算法解决迷宫问题)

改章节笔者在广东游玩的时候突然想到的...之前就有想写几篇关于位置距离的博客，所以回家到之后就奋笔疾书的写出来发表了

    很早就听说过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、定义了一个迷宫类 Maze，迷宫中包含了王子Prince（包含核心算法）和迷宫的舆图MazeMap，迷宫（游戏）启动时，会先初始化舆图，然后王子开始寻路（详细算法看代码）;

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

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

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

/*** 迷宫中的位置点 创建人：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;}@Overridepublic int hashCode(){final int prime = 31;int result = 1;result = prime * result + x;result = prime * result + y;return result;}@Overridepublic 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;}@Overridepublic String toString(){return "Position [x=" + x + ", y=" + y + "]";}
}

/*** 位置信息的权值*/
public class PositionWeight
{/*** 水平或者垂直挪动一格的距离*/private final static int STRAIGHT_DISTANCE = 10;/*** 以后的位置信息*/private Position position;/*** 肇端点（王子的肇端位置），经过以后点的父节点后，到以后点的距离(仅包含垂直和水平直线上的)*/private int distanceOfPrince;/*** 以后点到目标点（公主位置）的距离*/private int distanceOfPrincess;/*** 父节点的权值*/private PositionWeight father;/*** 总开销：包含肇端点到以后点和以后点到终点的开销之和*/private int cost;public PositionWeight(Position position){this.position = position;}public PositionWeight(Position position, PositionWeight father,PositionWeight target){this(position);countDistanceToTarget(target);updateByFather(father);}/*** 获取父子节点间的距离:对角线为14,水平、垂直为10*/public int getDistanceFromAttemptFather(PositionWeight father){Position fatherPosition = father.getPosition();return fatherPosition.getOffsetOfDistance(getPosition());}/*** 更新父节点，并设置以后点的权值*/public void updateByFather(PositionWeight father){setFather(father);int distanceOfPrince = getDistanceFromAttemptFather(father);setDistanceOfPrince(distanceOfPrince + father.getDistanceOfPrince());setCost(getDistanceOfPrince() + getDistanceOfPrincess());}public Position getPosition(){return position;}public PositionWeight getFather(){return father;}public int getCost(){return cost;}public int getDistanceOfPrince(){return distanceOfPrince;}/*** 获取消费的总开销*/public int getSpendTime(){return getCost() / STRAIGHT_DISTANCE;}@Overridepublic int hashCode(){final int prime = 31;int result = 1;result = prime * result+ ((position == null) ? 0 : position.hashCode());return result;}@Overridepublic boolean equals(Object obj){if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;PositionWeight other = (PositionWeight) obj;if (position == null){if (other.position != null)return false;}elseif (!position.equals(other.position))return false;return true;}@Overridepublic String toString(){return "PositionWeight [position=" + position + ", distanceOfPrince="+ distanceOfPrince + ", distanceOfPrincess="+ distanceOfPrincess + ", father=" + father.getPosition()+ ", cost=" + cost + "]";}/*** 设置到目标节点的距离*/private void countDistanceToTarget(PositionWeight target){Position targetPosition = target.getPosition();int distanceToTarget = getPosition().getDistanceOfTarget(targetPosition);setDistanceOfPrincess(distanceToTarget);}private void setDistanceOfPrince(int distanceOfPrince){this.distanceOfPrince = distanceOfPrince;}private int getDistanceOfPrincess(){return distanceOfPrincess;}private void setDistanceOfPrincess(int distanceOfPrincess){this.distanceOfPrincess = distanceOfPrincess;}private void setFather(PositionWeight father){this.father = father;}private void setCost(int cost){this.cost = cost;}
}

import java.util.ArrayList;
import java.util.List;import javax.lang.model.element.UnknownElementException;/*** 迷宫舆图* * 类名称：Maze 类描述： 创建人：dobuy* */
public class MazeMap
{/*** 迷宫中的原点(0,0)*/private Position originPosition;/*** 迷宫中的最大边界点*/private Position edgePosition;/*** 王子的位置*/private Position princePosition;/*** 公主的位置*/private Position princessPosition;/*** 全部可达的位置集合（非墙壁）*/private List allReachablePositions;public MazeMap(){allReachablePositions = new ArrayList();originPosition = new Position(0, 0);}public boolean isOverEdge(Position position){if (getOriginPosition().getX() > position.getX()|| getOriginPosition().getY() > position.getY()|| getEdgePosition().getX() < position.getX()|| getEdgePosition().getY() < position.getY()){return true;}return false;}/*** 判断是否是墙* */public boolean isWall(Position currentPosition){if (isOverEdge(currentPosition) || isPrincess(currentPosition)|| getPrincePosition().equals(currentPosition)){return false;}return !getAllReachablePositions().contains(currentPosition);}/*** 判断以后位置是否是公主位置* */public boolean isPrincess(Position currentPosition){return getPrincessPosition().equals(currentPosition);}/*** 初始化迷宫地址（坐标转换成点对象），并解析出王子的位置和公主的位置* * @param mazeMap 二维坐标表示的迷宫舆图* */public void initMazeMap(char[][] mazeMap){if (mazeMap == null || mazeMap.length <= 0){throw new UnknownElementException(null, "null error");}for (int column = 0; column < mazeMap[0].length; column++){for (int row = 0; row < mazeMap.length; row++){parseMazePosition(new Position(row, column),mazeMap[row][column]);}}edgePosition = new Position(mazeMap.length, mazeMap[0].length);}public Position getPrincePosition(){return princePosition;}public Position getPrincessPosition(){return princessPosition;}/*** 解析迷宫的位置信息*/private void parseMazePosition(Position currentPosition, char thing){switch (thing){case '.':getAllReachablePositions().add(currentPosition);break;case '*':break;case 'S':setPrincePosition(currentPosition);break;case 'P':setPrincessPosition(currentPosition);break;default:throw new UnknownElementException(null, thing);}}private Position getOriginPosition(){return originPosition;}private Position getEdgePosition(){return edgePosition;}private void setPrincePosition(Position princePosition){this.princePosition = princePosition;}private void setPrincessPosition(Position princessPosition){this.princessPosition = princessPosition;}private List getAllReachablePositions(){return allReachablePositions;}
}

import javax.lang.model.element.UnknownElementException;/*** 迷宫类：包含王子和迷宫舆图两个对象* */
public class Maze
{/*** 王子*/private Prince prince;/*** 迷宫舆图*/private MazeMap map;private boolean isInitOK = true;public Maze(int time, char[][] map){this.map = new MazeMap();prince = new Prince(time);initMap(map);}public void initMap(char[][] map){try{getMap().initMazeMap(map);getPrince().setMap(getMap());}catch (UnknownElementException e){// TODO logisInitOK = false;}}/*** 游戏开始:返回结果：-1表示营救失败；0表示营救成功* */public int start(){if (!isInitOK){return -1;}return getPrince().startToSearch();}private MazeMap getMap(){return map;}private Prince getPrince(){return prince;}
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 王子* * 类名称：Prince 类描述： 创建人：dobuy* */
public class Prince
{/*** 营救公主失败*/private final static int FAIL = -1;/*** 营救公主成功*/private final static int SUCCESS = 0;/*** 剩余的时光*/private int time;/*** 迷宫舆图*/private MazeMap map;/*** 正待尝试的位置集合(开启列表)*/private List attemptPositions;/*** 已经经过的位置集合(关闭列表)*/private List passedPositions;/*** 公主位置*/private PositionWeight princessPosition;/*** 王子位置*/private PositionWeight princePosition;/*** 王子挪动一步的全部偏移量*/private List offsets = Arrays.asList(new Position[] {new Position(1, 0), new Position(0, 1), new Position(-1, 0),new Position(0, -1) });public Prince(int time){this.time = time;this.attemptPositions = new ArrayList();this.passedPositions = new ArrayList();}/*** 开始寻找公主*/public int startToSearch(){reset();if (getPrincePosition().getPosition() == null|| getPrincessPosition().getPosition() == null || time < 0){return FAIL;}// 1、添加王子自己的肇端位置getAttemptPositions().add(getPrincePosition());// 2、通过挪动维护待尝试列表和已经尝试的列表attemptMove();// 3、已经营救成功或者时光耗尽或者无法营救时，统计结果返回return getSpendTime();}/*** 设置迷宫舆图*/public void setMap(MazeMap map){this.map = map;}/*** 重置* */private void reset(){// 清空待尝试的列表getAttemptPositions().clear();// 清空已经尝试的列表getPassedPositions().clear();// 初始化王子的位置Position princePosition = getMap().getPrincePosition();setPrincePosition(new PositionWeight(princePosition));// 初始化公主的位置Position princessPosition = getMap().getPrincessPosition();PositionWeight princessPositionWeight = new PositionWeight(princessPosition);setPrincessPosition(princessPositionWeight);}/*** 可预知式挪动* */private void attemptMove(){// 1、在如下2种情况下均结束：1)只要在待尝试列表中发现了公主，表明已经找到； 2)迷宫中全部可达的点都遍历完成，仍然无法找到if (getAttemptPositions().contains(getPrincessPosition())|| getAttemptPositions().isEmpty()){return;}// 2、获取最新加入的开销最小的节点PositionWeight minPositionWeight = getMinPositionWeight();// 3、从待尝试列表中移除开销最小节点getAttemptPositions().remove(minPositionWeight);// 4、把找到的开销最小节点加至已经尝试的列表getPassedPositions().add(minPositionWeight);// 5、对以后的开销最小节点进行尝试，找出其全部子节点List subPositionWeights = getReachableSubPositions(minPositionWeight);// 6、把全部子节点按照必定条件添加至待尝试列表for (PositionWeight subPositionWeight : subPositionWeights){addPositionWeight(minPositionWeight, subPositionWeight);}// 7、重复以上操作attemptMove();}/*** 王子从以后挪动一步，可达的位置(忽略墙)* */private List getReachableSubPositions(PositionWeight father){List subPositionWeights = new ArrayList();Position fatherPosition = father.getPosition();PositionWeight subPositionWeight = null;Position subPosition = null;for (Position offset : offsets){subPosition = fatherPosition.offset(offset);subPositionWeight = new PositionWeight(subPosition, father,getPrincessPosition());// 子节点越界或者是墙壁或者已经在尝试过的列表中时，不做任何处理if (getMap().isOverEdge(subPosition)|| getMap().isWall(subPosition)|| isInPassedTable(subPositionWeight)){continue;}subPositionWeights.add(subPositionWeight);}return subPositionWeights;}/*** 添加一个点* */private void addPositionWeight(PositionWeight father,PositionWeight positionWeight){// 在待尝试列表中已经包含了以后点，则按照必定条件更新其父节点及其权值，否则直接添加if (getAttemptPositions().contains(positionWeight)){updateCostByFather(father, positionWeight);}else{getAttemptPositions().add(positionWeight);}}/*** 计算消费的时光*/private int getSpendTime(){if (getAttemptPositions().contains(getPrincessPosition())){int princessIndex = getAttemptPositions().indexOf(getPrincessPosition());PositionWeight princess = getAttemptPositions().get(princessIndex);return princess.getSpendTime() <= time ? SUCCESS : FAIL;}return FAIL;}/*** 从待尝试列表中查找总开销值最小的点(如果有几个相同开销的最小点，取靠近队尾的)* */private PositionWeight getMinPositionWeight(){PositionWeight minPositionWeight = getAttemptPositions().get(0);for (PositionWeight positionWeight : getAttemptPositions()){if (minPositionWeight.getCost() >= positionWeight.getCost()){minPositionWeight = positionWeight;}}return minPositionWeight;}/*** 如果从父节点挪动至子节点的G值小于子节点之前的G值(前提是子节点已经在开启列表中)，则更新子节点的父节点及G值*/private void updateCostByFather(PositionWeight father,PositionWeight subPosition){int distanceOfAttemptFather = subPosition.getDistanceFromAttemptFather(father);int distanceOfPrince = father.getDistanceOfPrince()+ distanceOfAttemptFather;if (distanceOfPrince < subPosition.getDistanceOfPrince()){subPosition.updateByFather(father);}}private MazeMap getMap(){return map;}private boolean isInPassedTable(PositionWeight positionWeight){return getPassedPositions().contains(positionWeight);}private List getAttemptPositions(){return attemptPositions;}private List getPassedPositions(){return passedPositions;}private PositionWeight getPrincessPosition(){return princessPosition;}private void setPrincessPosition(PositionWeight princessPosition){this.princessPosition = princessPosition;}private PositionWeight getPrincePosition(){return princePosition;}private void setPrincePosition(PositionWeight princePosition){this.princePosition = princePosition;}
}

    单元测试类：

import static org.junit.Assert.assertEquals;import org.junit.Test;/*** * 类名称：MazeTest 类描述： 创建人：dobuy* */
public class MazeTest
{private Maze maze;private char[][] map;/*** 营救公主失败*/private final static int FAIL = -1;/*** 营救公主成功*/private final static int SUCCESS = 0;/*** testStart01 正常可达情况*/@Testpublic void testStart01(){map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },{ '.', '.', '.', '.' }, { 'S', '*', '*', 'P' } };maze = new Maze(5, map);assertEquals(maze.start(), SUCCESS);}/*** testStart02 正常不可达情况*/@Testpublic void testStart02(){map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },{ '.', '.', '.', '.' }, { 'S', '*', '*', 'P' } };maze = new Maze(2, map);assertEquals(maze.start(), FAIL);}/*** testStart03 参数异常*/@Testpublic void testStart03(){map = null;maze = new Maze(2, map);assertEquals(maze.start(), FAIL);map = new char[][] {};maze = new Maze(2, map);assertEquals(maze.start(), FAIL);map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },{ '.', '.', '.', '.' }, { '.', '.', '.', '.' } };maze = new Maze(2, map);assertEquals(maze.start(), FAIL);map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },{ 'S', '.', '.', 'P' }, { '.', '.', '.', '.' } };maze = new Maze(-1, map);assertEquals(maze.start(), FAIL);}/*** testStart04 临界值*/@Testpublic void testStart04(){map = new char[][] { { '*', '*', '*', '*' }, { '*', '*', '*', '*' },{ '*', '*', '*', '.' }, { 'S', '*', '*', 'P' } };maze = new Maze(2, map);assertEquals(maze.start(), FAIL);map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },{ 'S', 'P', '.', '*' }, { '.', '.', '.', '.' } };maze = new Maze(1, map);assertEquals(maze.start(), SUCCESS);}
}

文章结束给大家分享下程序员的一些笑话语录： Google事件并不像国内主流媒体普遍误导的那样，它仅仅是中国Z府和美国公司、中国文化和美国文化甚至中国人和美国人之间的关系，是民族主义和帝国主义之间的关系；更重要的是，它就是Z府和公司之间的关系，是权力管制和市场自由之间的关系。从这个意义上说，过度管制下的受害者，主要是国内的企业。Google可以抽身而去，国内的企业只能祈望特区。www.ishuo.cn

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！