pathfinder.java

a java game code for java

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 + "]";
	}
}