A start (A*) 算法的Java实现

一、AStart类，AStart(int[][] map, int width, int height)，用find查找两点间的坐标。

/**
 * @author ChenJianxiang 
 * @deprecated
 */
package com.cjx.path;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
//估值函数:f(n)=g(n)+h(n)
public class AStart {
	private int[][] map;
	private int width;
	private int height;
	/** 开启列表 */
	private Node[] OpenList;
	/** 开启列表长度 */
	private int olength = 0;
	/** 开启hashMap */
	private HashMap<String, Node> OpenTable = new HashMap<String, Node>();
	/** 记录节点状态 */
	private int[][] mapc;
	/** 是否找到 */
	private boolean findFalg = false;
	public AStart(int[][] map, int width, int height) {
		this.width = width;
		this.height = height;
		this.map = map;
		this.mapc = new int[width][height];
		this.OpenList = new Node[width * height / 2];
	}
	public static void main(String[] args) {
		int[][] map = new int[][] {// 地图数组
		// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
		{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, // 0
		{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, // 1
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 }, // 2
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 }, // 3
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 }, // 4
		{ 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0 }, // 5
		{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 }, // 6
		{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 }, // 7
		{ 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 }, // 8
		{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, // 9
		{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; // 10
		// Node sNode = new Node(a.map, 0, 0, null);
		// Node eNode = new Node(a.map, 10, 14, null);
		AStart a = new AStart(map, 11,15);
		System.out.println("====================");
		long t = new java.util.Date().getTime();
		List<Node> list = a.find(0, 0, 9,13);
		if (list.size() > 0) {
			for (int i = 0; i < list.size(); i++) { //
				a.mapc[list.get(i).getX()][list.get(i).getY()] = 7;
			}
			for (int i = 0; i < a.map.length; i++) {
				for (int j = 0; j < a.map[0].length; j++) {
					if (a.mapc[i][j] == 7) {
						System.out.print("※");
					} else {
						if (a.map[i][j] == 0) {
							System.out.print("〓");
						} else {
							System.out.print("　");
						}
					}
				}
				System.out.println();
			}
		} else {
			System.out.println("没有通路。");
		}
		System.out.println("用时:" + (new java.util.Date().getTime() - t));
		System.out.println("====================");

	}
	/**
	 * 查找路径
	 * 
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @return
	 */
	public List<Node> find(int x1, int y1, int x2, int y2) {
		Node sN = this.getNearNode(x1, y1, x2, y2, map, width, height);
		Node eN = this.getNearNode(x2, y2, x1, y1, map, width, height);
		List<Node> result = this.find(sN, eN);
		return result;
	}
	/**
	 * @param map
	 * @param startNode
	 * @param endNode
	 * @return
	 */
	private List<Node> find(Node sNode, Node eNode) {
		List<Node> resultList = new ArrayList<Node>();
		olength++;
		OpenList[olength] = sNode;
		mapc[sNode.getX()][sNode.getY()] = Constant.NOTE_OPEN;

		Node cNode = null;
		while (olength > 0) {
			cNode = OpenList[1];
			@SuppressWarnings("unused")
			boolean f0 = false, f1 = false, f2 = false, f3 = false;// 当前节点四方向可通行标志
			for (int i = 0; i < 8; i++) {
				switch (i) {
				case 0:// 东
					f0 = check(cNode.getX(), cNode.getY() + 1, eNode, cNode,
							Constant.COST_STRAIGHT);
					break;
				case 1:// 南
					f1 = check(cNode.getX() + 1, cNode.getY(), eNode, cNode,
							Constant.COST_STRAIGHT);
					break;
				case 2:// 西
					f2 = check(cNode.getX(), cNode.getY() - 1, eNode, cNode,
							Constant.COST_STRAIGHT);
					break;
				case 3:// 北
					f3 = check(cNode.getX() - 1, cNode.getY(), eNode, cNode,
							Constant.COST_STRAIGHT);
					break;
				case 4:// 东南
					// if (f0 && f1)可以直接跳
					check(cNode.getX() + 1, cNode.getY() + 1, eNode, cNode,
							Constant.COST_DIAGONAL);
					break;
				case 5:// 东北
					// if (f0 && f3)可以直接跳
					check(cNode.getX() - 1, cNode.getY() + 1, eNode, cNode,
							Constant.COST_DIAGONAL);
					break;
				case 6:// 西南
					// if (f2 && f1)可以直接跳
					check(cNode.getX() + 1, cNode.getY() - 1, eNode, cNode,
							Constant.COST_DIAGONAL);
					break;
				case 7:// 西北
					// if (f2 && f3)可以直接跳
					check(cNode.getX() - 1, cNode.getY() - 1, eNode, cNode,
							Constant.COST_DIAGONAL);
					break;
				}// end switch
			}// end for
			this.putClosedTabe(cNode, eNode);
			if (this.findFalg) {
				break;
			}
		}
		if (this.findFalg) {// 有
			read(resultList, cNode);
			return resultList;
		} else {// 无
			/** 清空 */
			return resultList;
		}
	}// end find
	/**
	 * 读取所有节点，从起点开始返
	 * 
	 * @param resultList
	 * @param node
	 */
	private void read(List<Node> resultList, Node node) {
		if (node.getParentNode() != null) {
			read(resultList, node.getParentNode());
		}
		resultList.add(node);
	}
	/**
	 * 检查 当前节点周围的节点，是否可以通行，是否在开启列表中，是否在关闭列表中 如果不在关闭与开启列表中则加入开启列表，如果在开启中则更新节点G值信息
	 * 
	 * @param x
	 *            X值
	 * @param y
	 *            Y值
	 * @param eNode
	 *            终点
	 * @param parentNode
	 *            父节点
	 * @param step
	 *            步长
	 * @return
	 */
	private boolean check(int x, int y, Node eNode, Node parentNode, int step) {
		try {
			if (map[x][y] == Constant.NOTE_NOWAY) {// 没门
				return false;
			}
		
		if (mapc[x][y] == Constant.NOTE_CLOSED) {
			return false;
		}
		if (mapc[x][y] == Constant.NOTE_NONE) {
			this.putOpenTable(x, y, eNode, parentNode, step);
			mapc[x][y] = Constant.NOTE_OPEN;
			return true;
		} else if (mapc[x][y] == Constant.NOTE_OPEN) {
			this.updateOpenTable(x, y, eNode, parentNode, step);
			return true;
		}
		} catch (java.lang.ArrayIndexOutOfBoundsException e) {
			return false;// 下标越界
		}
		return false;
	}// end check
	/**
	 * 放入关闭列表
	 * 
	 * @param node
	 * @return
	 */
	private void putClosedTabe(Node node, Node eNode) {
		if (node.getX() == eNode.getX() && node.getY() == eNode.getY()) {
			this.findFalg = true;// 找到了
			return;
		}
		Node tNode;
		OpenList[1] = OpenList[olength];
		tNode = OpenList[1];
		int i = 1;
		while ((i * 2 + 1) <= olength) {
			if (tNode.getF() < OpenList[i * 2].getF()
					&& tNode.getF() < OpenList[i * 2 + 1].getF()) {
				break;
			} else {
				if (OpenList[i * 2].getF() < OpenList[i * 2 + 1].getF()) {// 找一个相对较小的子节点交换
					OpenList[i] = OpenList[i * 2];
					OpenList[i * 2] = tNode;
					i = i * 2;
				} else {
					OpenList[i] = OpenList[i * 2 + 1];
					OpenList[i * 2 + 1] = tNode;
					i = i * 2 + 1;
				}
			}
		}
		OpenList[olength] = null;
		olength--;
		mapc[node.getX()][node.getY()] = Constant.NOTE_CLOSED;
	}
	/**
	 * 放入开启列表
	 * 
	 * @param x
	 * @param y
	 * @param eNode
	 * @param parentNode
	 * @param step
	 * @return
	 */
	private boolean putOpenTable(int x, int y, Node eNode, Node parentNode,
			int step) {
		Node node = new Node(map, x, y, parentNode);
		this.count(node, eNode, step);
		olength++;
		OpenList[olength] = node;
		OpenTable.put(node.getX() + "_" + node.getY(), node);
		int i = olength / 2;
		Node mid = OpenList[i];
		while (mid.getF() > node.getF()) {
			Node temp = mid;
			OpenList[i] = OpenList[olength];
			OpenList[olength] = temp;
			i = i / 2;
			if (i < 1) {
				i = 1;
			}
			mid = OpenList[i];
		}
		return true;
	}
	/**
	 * 已经存在 更新节点F值
	 * 
	 * @param x
	 * @param y
	 * @param eNode
	 * @param parentNode
	 * @param step
	 * @return
	 */
	private boolean updateOpenTable(int x, int y, Node eNode, Node parentNode,
			int step) {
		Node node = OpenTable.get(x + "_" + y);
		int g = parentNode.getG() + step;
		if (g < node.getG()) {
			node.setParentNode(parentNode);
			this.count(node, eNode, step);
			return true;
		}
		return false;
	}
	/**
	 * GHF
	 * 
	 * @param node
	 * @param eNode
	 * @param parentNode
	 * @param step
	 */
	private void count(Node node, Node eNode, int step) {
		this.countG(node, node.getParentNode(), step);
		this.countH(node, eNode);
		this.countF(node);
	}
	/**
	 * 计算G值
	 * 
	 * @param node
	 * @param parentNode
	 * @param step
	 */
	private void countG(Node node, Node parentNode, int step) {
		if (parentNode == null) {
			node.setG(step);
		} else {
			node.setG(parentNode.getG() + step);
		}
	}
	/**
	 * 计算H值
	 * 
	 * @param node
	 * @param eNode
	 */
	private void countH(Node node, Node eNode) {
		node.setH(Math.abs(eNode.getX() - node.getX())
				+ Math.abs(eNode.getY() - node.getY()));
	}
	/**
	 * 计算F值
	 * 
	 * @param node
	 */
	private void countF(Node node) {
		node.setF(node.getG() + node.getH());
	}
	/**
	 * 在地图线路上没有坐标点时取最后的一个点
	 * 
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @param map
	 * @param width
	 * @param height
	 * @return
	 */
	private Node getNearNode(int x1, int y1, int x2, int y2, int map[][],
			int width, int height) {
		Node node = null;
		List<Node> nodeList = new ArrayList<Node>();
		int length = width > height ? width : height;
		for (int k = 1; k < length; k++) {
			for (int i = -k; i <= k; i++) {
				try {
					if (map[x1 - k][y1 + i] == 1) {
						nodeList.add(new Node(x1 - k, y1 + i));
					}
				} catch (Exception e) {
				}
			}
			for (int i = -k; i <= k; i++) {
				try {
					if (map[x1 + k][y1 + i] == 1) {
						nodeList.add(new Node(x1 + k, y1 + i));
					}
				} catch (Exception e) {
				}
			}
			for (int i = -(k - 1); i <= k - 1; i++) {
				try {
					if (map[x1 + i][y1 - k] == 1) {
						nodeList.add(new Node(x1 + i, y1 - k));
					}
				} catch (Exception e) {
				}
			}
			for (int i = -(k - 1); i <= k - 1; i++) {
				try {
					if (map[x1 + i][y1 + k] == 1) {
						nodeList.add(new Node(x1 + i, y1 + k));
					}
				} catch (Exception e) {
				}
			}
			if (nodeList.size() > 0)
				break;
		}
		if (nodeList.size() < 1) {
			return null;
		} else {
			node = nodeList.get(0);
		}
		for (int i = 1; i < nodeList.size(); i++) {
			Node temp = nodeList.get(i);
			int xc = Math.abs(temp.getX() - x2);
			int yc = Math.abs(temp.getY() - y2);
			if (Math.abs(node.getX() - x2) + Math.abs(node.getY() - y2) > xc
					+ yc) {
				node = temp;
			}
		}
		return node;
	}
}

二、节点类

package com.cjx.path;
public class Node {
	@SuppressWarnings("unused")
	private int value;// 当前节点的值,0不可通过,1可通过.
	private int x;// x坐标
	private int y;// y坐标
	private int g;// g值 起始点到当前点
	private int h;// h值 当前点到目标点
	private int f;// f=g+h;
	private Node parentNode = null;
	/**
	 * @param x
	 * @param y
	 */
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	/**
	 * @param map
	 *            地图
	 * @param x
	 *            x坐标
	 * @param y
	 *            y坐标
	 * @param parentNode
	 *            父节点
	 */
	public Node(int[][] map, int x, int y, Node parentNode) {
		this.x = x;
		this.y = y;
		this.parentNode = parentNode;
		try {
			this.value = map[x][y];
		} catch (java.lang.ArrayIndexOutOfBoundsException e) {
			this.value = 0;
		}
	}
	public int getX() {
		return x;
	}
	public int getY() {
		return y;
	}
	public int getF() {
		return f;
	}
	public void setF(int f) {
		this.f = f;
	}
	/** g值 起始点到当前点 */
	public int getG() {
		return g;
	}
	/** g值 起始点到当前点 */
	public void setG(int g) {
		this.g = g;
	}
	public int getH() {
		return h;
	}
	public void setH(int h) {
		this.h = h;
	}
	public Node getParentNode() {
		return parentNode;
	}
	public void setParentNode(Node parentNode) {
		this.parentNode = parentNode;
	}
}

三、常量类

package com.cjx.path;
public class Constant {
	/**横或竖向移动一格的路径评分*/
	public static int COST_STRAIGHT = 10;
	/**斜向移动一格的路径评分*/
	public static int COST_DIAGONAL = 14;
	/**不能行走*/
	public static int NOTE_NOWAY = 0;
	/**当前节点没使用过*/
	public static int NOTE_NONE = 0;
	/**在开启列表中 */
	public static int NOTE_OPEN = 1;
	/**在关闭列表中 */
	public static int NOTE_CLOSED = 2;
}