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

    很早就听说过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;	}	@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 + "]";	}}

/** * 位置信息的权值 */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;	}	@Override	public int hashCode()	{		final int prime = 31;		int result = 1;		result = prime * result				+ ((position == null) ? 0 : position.hashCode());		return result;	}	@Override	public 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;		}		else			if (!position.equals(other.position))				return false;		return true;	}	@Override	public 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 log			isInitOK = 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 正常可达情况	 */	@Test	public void testStart01()	{		map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },				{ '.', '.', '.', '.' }, { 'S', '*', '*', 'P' } };		maze = new Maze(5, map);		assertEquals(maze.start(), SUCCESS);	}	/**	 * testStart02 正常不可达情况	 */	@Test	public void testStart02()	{		map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },				{ '.', '.', '.', '.' }, { 'S', '*', '*', 'P' } };		maze = new Maze(2, map);		assertEquals(maze.start(), FAIL);	}	/**	 * testStart03 参数异常	 */	@Test	public 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 临界值	 */	@Test	public 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