package eatbean.util.algorithm;/** * <p>Title: A*算法找最短路徑</p> * <p>Description: </p> * <p>Copyright: Copyright (c) 2002</p> * <p>Company: Raindrop</p> * @author "nothing" * @version 1.0 */import eatbean.Room;public class PathFinder {	private final int MIN = -9999;	private final int MAX = 9999;	private Link open = new Link();	private Link closed = new Link();	private int[][] map = null;	private int validNodeCodeBase = Room.BASE_NUM; //  map[y][x]/此變量==1時 [y][x]即為有效結點	public PathFinder(int[][] map) {	    this.map = map;	}	/** 尋找最短路徑,返回路徑反向鏈表的最后一個節點 */	public Node findPath(Node s, Node e) {		long startTime = System.currentTimeMillis();		if(map == null) return null;		if(!isValid(map, s.x, s.y) || !isValid(map, e.x, e.y)) return null;		int mapWidth = map[0].length;		int mapHeight = map.length;		Node result = null;		initLink();		Link link = new Link(s, 0, judge(s, e));		open.next = link;		link.prev = open;		Link linkParent = null;		Node n = null;		while((linkParent = open.next) != null) {		    open.next = linkParent.next;    //  第一個(最優)節點出隊			if(open.next != null) open.next.prev = open;			n = linkParent.node;			if(n.equals(e)) {   // 成功				result = n;				break;			}			//嘗試四個方向的鄰接節點			int x, y;			//上			x = n.x; y = n.y-1;			if(isValid(map, x, y))				generateChild(linkParent, x, y, e);			//下			x = n.x; y = n.y+1;			if(isValid(map, x, y))				generateChild(linkParent, x, y, e);			//左			x = n.x-1; y = n.y;			if(isValid(map, x, y))				generateChild(linkParent, x, y, e);			//右			x = n.x+1; y = n.y;			if(isValid(map, x, y))				generateChild(linkParent, x, y, e);			insert(closed, linkParent);		}		//System.out.print("lapse time1: " + (System.currentTimeMillis() - startTime));		releaseMem();		//System.out.println("lapse time2: " + (System.currentTimeMillis() - startTime));		return result;	}	private void initLink() {	    open.next = null;		closed.next = null;	}	private boolean isValid(int[][] map, int x, int y) {		int mapWidth = map[0].length;		int mapHeight = map.length;	    return (x >= 0 && x < mapWidth) &&			    (y >= 0 && y < mapHeight) &&				(isValidElement(map[y][x]));	}	/** 若code/validNodeCodeBase==1 code即為有效結點 */	private boolean isValidElement(int code) {		return code/validNodeCodeBase == 1;	}	private void generateChild(Link parentLink, int x, int y, Node e) {		Link oldLink = null;		if((oldLink = inOpen(x, y)) != null) {			if(parentLink.g+1 < oldLink.g) {				//  如果由此條路徑找到的 parentLink				//  比別的路徑找到的 oldLink 的代價(此處為g)小				oldLink.g = parentLink.g+1; //  更新走到此節點的權值				oldLink.f = oldLink.g + oldLink.h;				oldLink.node.parent = parentLink.node;				reSort(open, oldLink);    //  重新排序open表			}			return;		}		if((oldLink = inClosed(x, y)) != null) {			if(parentLink.g+1 < oldLink.g) {				//  如果由此條路徑找到的 parentLink				//  比別的路徑找到的 oldLink 的代價(此處為g)小				oldLink.g = parentLink.g+1; //  更新走到此節點的權值				oldLink.f = oldLink.g + oldLink.h;				oldLink.node.parent = parentLink.node;				//  從 oldLink 更新經過 oldLink 的所有路徑				delete(oldLink);				insert(open, oldLink);			}			return;		}		Node childNode = new Node(x, y);		childNode.parent = parentLink.node;		Link childLink = new Link(childNode, parentLink.g+1, judge(childNode, e));		insert(open, childLink);	}	/** 按f值從小到大的規則,把link插入雙鏈表head */	private void insert(Link head, Link link) {		Link temp = head;		while((temp.next != null) && (link.f > temp.next.f)) {			temp = temp.next;		}		//  temp 和 temp.next 之間為要插入的位置		link.prev = temp;		link.next = temp.next;		temp.next = link;		if(link.next != null) link.next.prev = link;	}	/** 因link的f值有變,重新排序 */	private void reSort(Link head, Link link) {		//  有待改進		delete(link);		insert(head, link);	}	private void delete(Link link) {		if(link.prev != null)			link.prev.next = link.next;		if(link.next != null)	    	link.next.prev = link.prev;		link.prev = link.next = null;	}	private Link inOpen(int x, int y) {	    Link link = open.next;		while(link != null) {			if(link.node.equals(x, y)) break;			link = link.next;		}		return link;	}	private Link inClosed(int x, int y) {	    Link link = closed.next;		while(link != null) {			if(link.node.equals(x, y)) break;			link = link.next;		}		return link;	}	private double judge(Node s, Node e) {		return judge(s.x, s.y, e.x, e.y);	}	/** 估價函數 */	private double judge(int sX, int sY, int eX, int eY) {		//待改進	    return ((sX-eX)*(sX-eX) + (sY-eY)*(sY-eY));	}	private void releaseMem() {		//待改進		//System.gc();		open = null;		closed = null;	}	/*	public static void main(String[] args) {		int[][] map = {							{ 0, 1, 0, 0, 0 },							{ 0, 0, 0, 1, 0 },							{ 0, 1, 0, 1, 1 },							{ 0, 1, 0, 1, 1 },							{ 0, 1, 0, 0, 0 },						};		PathFinder pathFinder = new PathFinder(map, 0);		Node s = new Node(0, 0);		Node e = new Node(map[0].length-1, map.length-1);		Node path = pathFinder.findPath(s, e);		if(path == null)			System.out.println("無可用路徑!");		else			while(path != null) {				System.out.println(path.toString() + "\n");				path = path.parent;			}	}	*/}class Link {	Link() {	}	Link(Node node, int g, double h) {		this.node = node;		this.h = h;		this.g = g;	    this.f = h+g;	}	Node node = null;	Link prev = null;	Link next = null;	double f;	double h;  //   到目的地的估計代價	int g;  //  走過的步數(深度),或路徑權值(默認都為1)的和	public String toString() {	    return "node:[" + node + "][g=" + g + ",h=" + h + ",f=" + f + "]";	}}