astar.java

mywork是rcp开发的很好的例子

package net.sf.pim.game.util;

import java.util.LinkedList;
import java.util.List;

import org.eclipse.swt.graphics.Point;

/**
 * A*寻路算法的实现
 * @date 20080825
 * @see  http://blog.csdn.net/cping1982/archive/2008/03/04/2146743.aspx 
 */
public class AStar {
	
    // 路径优先等级list(此示例中为内部方法)
    private LevelList _levelList;

    // 已完成路径的list
    private LinkedList _closedList;

    // 地图描述
    private int[][] _map;

    // 限制的行走区域
    private int[] _limit;

    /** 
     * 以注入地图的2维数组及限制点描述初始化此类
     * 
     * @param _map
     */
    public AStar(int[][] map, int[] limit) {
        _map = map;
        _limit = limit;
        _levelList = new LevelList();
        _closedList = new LinkedList();
    }

    /** 
     * A*方式寻径,注入开始坐标及目标坐标后运算,返回可行路径的List
     * 
     * @param startPos
     * @param objectPos
     * @return
     */
    public List<Point> searchPath(Point startPos, Point objectPos) {
        // 初始化起始节点与目标节点
        Node startNode = new Node(startPos);
        Node objectNode = new Node(objectPos);
        // 设定起始节点参数
        startNode._costFromStart = 0;
        startNode._costToObject = startNode.getCost(objectNode);
        startNode._parentNode = null;
        // 加入运算等级序列
        _levelList.add(startNode);
        // 当运算等级序列中存在数据时，循环处理寻径，直到levelList为空
        while (!_levelList.isEmpty()) {
            // 取出并删除最初的元素
            Node firstNode = (Node) _levelList.removeFirst();
            // 判定是否和目标node坐标相等
            if (firstNode.equals(objectNode)) {
                // 是的话即可构建出整个行走路线图，运算完毕
                return makePath(firstNode);
            } else {
                // 否则
                // 加入已验证List
                _closedList.add(firstNode);
                // 获得firstNode的移动区域
                LinkedList _limit = firstNode.getLimit();
                // 遍历
                for (int i = 0; i < _limit.size(); i++) {
                    //获得相邻节点
                    Node neighborNode = (Node) _limit.get(i);
                    //获得是否满足等级条件
                    boolean isOpen = _levelList.contains(neighborNode);
                    //获得是否已行走
                    boolean isClosed = _closedList.contains(neighborNode);
                    //判断是否无法通行
                    boolean isHit = isHit(neighborNode._pos.x,
                            neighborNode._pos.y);
                    //当三则判定皆非时
                    if (!isOpen && !isClosed && !isHit) {
                        //设定costFromStart
                        neighborNode._costFromStart = firstNode._costFromStart + 1;
                        //设定costToObject  
                        neighborNode._costToObject = neighborNode
                                .getCost(objectNode);
                        //改变neighborNode父节点
                        neighborNode._parentNode = firstNode;
                        //加入level 
                        _levelList.add(neighborNode);
                    }
                }
            }

        }
        //清空数据
        _levelList.clear();
        _closedList.clear();
        //当while无法运行时，将返回null
        return  null;
    }
    
    /** 
     * 判定是否为可通行区域
     * 
     * @param x
     * @param y
     * @return
     */
    private boolean isHit(int x, int y) {
        for (int i = 0; i < _limit.length; i++) {
            if (_map[x][y] == _limit[i]) {
                return true;
            }
        }
        return false;
    }

    /** 
     * 通过Node制造行走路径
     * 
     * @param node
     * @return
     */
    private LinkedList<Point> makePath(Node node) {
        LinkedList<Point> path = new LinkedList<Point>();
        // 当上级节点存在时
        while (node._parentNode != null) {
            // 在第一个元素处添加
            path.addFirst(node._pos);
            // 将node赋值为parent node
            node = node._parentNode;
        }
        // 在第一个元素处添加
        path.addFirst(node._pos);
        return path;
    }

    private class LevelList extends LinkedList {
        /** 
         * 
         */
        private static final long serialVersionUID = 1L;

        /** 
         * 增加一个node
         * 
         * @param node
         */
        public void add(Node node) {
            for (int i = 0; i < size(); i++) {
                if (node.compareTo(get(i)) <= 0) {
                    add(i, node);
                    return;
                }
            }
            addLast(node);
        }
    }	
	
	class Node implements Comparable {
	    // 坐标
	    public Point _pos;

	    // 开始地点数值
	    public int _costFromStart;

	    // 目标地点数值
	    public int _costToObject;

	    // 父节点
	    public Node _parentNode;

	    private Node() {
	    }

	    /** 
	     * 以注入坐标点方式初始化Node
	     * @param _pos
	     */
	    public Node(Point _pos) {
	        this._pos = _pos;
	    }

	    /** 
	     * 返回路径成本
	     * @param node
	     * @return
	     */
	    public int getCost(Node node) {
	        // 获得坐标点间差值 公式：(x1, y1)-(x2, y2)
	        int m = node._pos.x - _pos.x;
	        int n = node._pos.y - _pos.y;
	        // 取两节点间欧几理德距离（直线距离）做为估价值，用以获得成本
            //return (int) Math.sqrt(m * m + n * n);
	        //简化取值
	        return 10*(m+n);
	    }

	    /** 
	     * 检查node对象是否和验证对象一致
	     */
	    public boolean equals(Object node) {
	        // 验证坐标为判断依据
	        if (_pos.x == ((Node) node)._pos.x && _pos.y == ((Node) node)._pos.y) {
	            return true;
	        }
	        return false;
	    }

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

		/** 
	     * 比较两点以获得最小成本对象
	     */
	    public int compareTo(Object node) {
	        int a1 = _costFromStart + _costToObject;
	        int a2 = ((Node) node)._costFromStart + ((Node) node)._costToObject;
	        if (a1 < a2) {
	            return -1;
	        } else if (a1 == a2) {
	            return 0;
	        } else {
	            return 1;
	        }
	    }

	    /** 
	     * 获得上下左右各点间移动限制区域
	     * 
	     * @return
	     */
	    public LinkedList getLimit() {
	        LinkedList limit = new LinkedList();
	        int x = _pos.x;
	        int y = _pos.y;
	        // 上下左右各点间移动区域(对于斜视地图，可以开启注释的偏移部分，此时将评估8个方位)
	        // 上
	        limit.add(new Node(new Point(x, y - 1)));
	        // 右上
	        // limit.add(new Node(new Point(x+1, y-1)));
	        // 右
	        limit.add(new Node(new Point(x + 1, y)));
	        // 右下
	        // limit.add(new Node(new Point(x+1, y+1)));
	        // 下
	        limit.add(new Node(new Point(x, y + 1)));
	        // 左下
	        // limit.add(new Node(new Point(x-1, y+1)));
	        // 左
	        limit.add(new Node(new Point(x - 1, y)));
	        // 左上
	        // limit.add(new Node(new Point(x-1, y-1)));

	        return limit;
	    }
	}

	public static void main(String[] args) {
	    // 地图描述
	     int[][] map = {
	            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
	            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };

	    // 无法移动区域
	    int[] hit = { 1 };
		AStar star=new AStar(map,hit);
		List list=star.searchPath(new Point(1,1), new Point(10,13));
		System.out.println("########:"+list);
	}
}