package demo1;

/**
 * 节点
 *
 */
public  class Node {
	//父节点，只是寻找回去的路径
	public Node parent;

	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int x;
	public int y;

	public int F;
	public int G;
	public int H;

	public void calcF() {
		this.F = this.G + this.H;
	}

}

package demo1;

import java.util.ArrayList;
import java.util.List;

public class StarA {
	
    public static final int[][] NODES = { 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 1, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 1, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 1, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
    };
    
    /*{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
    { 0, 0, 0, 1, 0, 0, 0, 0, 0 }, 
    { 0, 0, 0, 1, 0, 0, 0, 0, 0 },
    { 0, 2, 2, 1, 0, 2, 0, 0, 0 }, 
    { 0, 0, 2, 1, 0, 2, 0, 0, 0 }, 
    { 0, 0, 2, 2, 2, 2, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, */

	public static final int STEP = 10;

	private ArrayList<Node> openList = new ArrayList<Node>();
	private ArrayList<Node> closeList = new ArrayList<Node>();

	/**
	 * 查最短F节点在OpenList中
	 * @return
	 */
	public Node findMinFNodeInOpneList() {
		//假设第一个点，F值最小
		Node tempNode = openList.get(0);
		for (Node node : openList) {
			if (node.F <= tempNode.F) {
				tempNode = node;
			}
		}
		return tempNode;
	}

	/**
	 * 查相邻的节点
	 * @param currentNode  当前的节点
	 * @return
	 */
	public ArrayList<Node> findNeighborNodes(Node currentNode) {
		ArrayList<Node> arrayList = new ArrayList<Node>();
		// 只考虑上下左右，不考虑斜对角
		int topX = currentNode.x;
		int topY = currentNode.y - 1;
		//在面板范围内
		if (canReach(topX, topY) && !exists(closeList, topX, topY)) {
			arrayList.add(new Node(topX, topY));
		}
		int bottomX = currentNode.x;
		int bottomY = currentNode.y + 1;
		if (canReach(bottomX, bottomY) && !exists(closeList, bottomX, bottomY)) {
			arrayList.add(new Node(bottomX, bottomY));
		}
		int leftX = currentNode.x - 1;
		int leftY = currentNode.y;
		if (canReach(leftX, leftY) && !exists(closeList, leftX, leftY)) {
			arrayList.add(new Node(leftX, leftY));
		}
		int rightX = currentNode.x + 1;
		int rightY = currentNode.y;
		if (canReach(rightX, rightY) && !exists(closeList, rightX, rightY)) {
			arrayList.add(new Node(rightX, rightY));
		}
		return arrayList;
	}

	/**
	 * 是否能到达
	 * @param x
	 * @param y
	 * @return
	 */
	public boolean canReach(int x, int y) {
		if (x >= 0 && x < NODES.length && y >= 0 && y < NODES[0].length) {
			return NODES[x][y] == 0;
		}
		return false;
	}

	/**
	 * 查到路径
	 * @param startNode  开始位置
	 * @param endNode   结束位置
	 * @return
	 */
	public Node findPath(Node startNode, Node endNode) {

		// 把起点加入 open list
		openList.add(startNode);

		while (openList.size() > 0) {
			// 遍历 open list ，查找 F值最小的节点，把它作为当前要处理的节点
			Node currentNode = findMinFNodeInOpneList();
			// 从open list中移除
			openList.remove(currentNode);
			// 把这个节点移到 close list，路径节点
			closeList.add(currentNode);
			//周围节点
			ArrayList<Node> neighborNodes = findNeighborNodes(currentNode);
			for (Node node : neighborNodes) {
				//存在openlist中，是待考虑的路径
				if (exists(openList, node)) {
					//重新计算g值，重新赋值
					foundPoint(currentNode, node);
				} else {//openlist不存在，添加到openlist中
					notFoundPoint(currentNode, endNode, node);
				}
			}
			//查询节点是否在待考虑的openlist中
			if (find(openList, endNode) != null) {
				return find(openList, endNode);
			}
		}

		return find(openList, endNode);
	}

	/**
	 * 查节点，计算g值，g值小的重新计算F值
	 * @param tempStart
	 * @param node
	 */
	private void foundPoint(Node tempStart, Node node) {
		int G = calcG(tempStart, node);
		if (G < node.G) {
			node.parent = tempStart;
			node.G = G;
			node.calcF();
		}
	}

	/**
	 * 
	 * @param tempStart  父节点
	 * @param end  			最终位置节点
	 * @param node          当前位置的节点
	 */
	private void notFoundPoint(Node tempStart, Node end, Node node) {
		node.parent = tempStart;
		node.G = calcG(tempStart, node);
		node.H = calcH(end, node);
		node.calcF();
		openList.add(node);
	}

	/**
	 * G是从开始点A到达当前方块的移动量
	 * 计算G
	 * @param start  
	 * @param node
	 * @return
	 */
	private int calcG(Node start, Node node) {
		int G = STEP;
		int parentG = node.parent != null ? node.parent.G : 0;
		return G + parentG;
	}

	/**
	 * H值是从当前方块到终点的移动量估算值
	 * @param end  结束节点位置
	 * @param node  当前位置
	 * @return
	 */
	private int calcH(Node end, Node node) {
		int step = Math.abs(node.x - end.x) + Math.abs(node.y - end.y);
		return step * STEP;
	}

	/**
	 * 查询节点在list中
	 * @param nodes
	 * @param point
	 * @return
	 */
	public static Node find(List<Node> nodes, Node point) {
		for (Node n : nodes)
			if ((n.x == point.x) && (n.y == point.y)) {
				return n;
			}
		return null;
	}

	/**
	 * 节点是否在list中
	 * @param nodes
	 * @param node
	 * @return
	 */
	public static boolean exists(List<Node> nodes, Node node) {
		for (Node n : nodes) {
			if ((n.x == node.x) && (n.y == node.y)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 节点是否在list中
	 * @param nodes
	 * @param x
	 * @param y
	 * @return
	 */
	public static boolean exists(List<Node> nodes, int x, int y) {
		for (Node n : nodes) {
			if ((n.x == x) && (n.y == y)) {
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Node startNode = new Node(5, 1);
		Node endNode = new Node(5, 5);
		Node parent = new StarA().findPath(startNode, endNode);

		for (int i = 0; i < NODES.length; i++) {
			for (int j = 0; j < NODES[0].length; j++) {
				System.out.print(NODES[i][j] + ", ");
			}
			System.out.println();
		}
		
		//添加所有的路径
		ArrayList<Node> arrayList = new ArrayList<Node>();
		while (parent != null) {
			// System.out.println(parent.x + ", " + parent.y);
			arrayList.add(new Node(parent.x, parent.y));
			parent = parent.parent;
		}
		System.out.println("\n");

		for (int i = 0; i < NODES.length; i++) {
			for (int j = 0; j < NODES[0].length; j++) {
				if (exists(arrayList, i, j)) {
					System.out.print("2, ");
				} else {
					System.out.print(NODES[i][j] + ", ");
				}

			}
			System.out.println();
		}

	}
}

package demo2;

import java.util.Comparator;

/**
 * 节点类
 *
 */
class Node2 {
	private int x;// X坐标
	private int y;// Y坐标
	private Node2 parentNode;// 父类节点
	private int g;// 当前点到起点的移动耗费
	private int h;// 当前点到终点的移动耗费，即曼哈顿距离|x1-x2|+|y1-y2|(忽略障碍物)
	private int f;// f=g+h

	public Node2(int x, int y, Node2 parentNode) {
		this.x = x;
		this.y = y;
		this.parentNode = parentNode;
	}

	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;
	}

	public Node2 getParentNode() {
		return parentNode;
	}

	public void setParentNode(Node2 parentNode) {
		this.parentNode = parentNode;
	}

	public int getG() {
		return g;
	}

	public void setG(int g) {
		this.g = g;
	}

	public int getH() {
		return h;
	}

	public void setH(int h) {
		this.h = h;
	}

	public int getF() {
		return f;
	}

	public void setF(int f) {
		this.f = f;
	}
}

// 节点比较类
class NodeFComparator implements Comparator<Node2> {

	@Override
	public int compare(Node2 o1, Node2 o2) {
		return o1.getF() - o2.getF();
	}
}

package demo2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 
 * A星算法步骤： 
 * 1.起点先添加到开启列表中 
 * 2.开启列表中有节点的话，取出第一个节点，即最小F值的节点 
 * 	  判断此节点是否是目标点，是则找到了，跳出
 * 	  根据此节点取得八个方向的节点，求出G，H，F值 判断每个节点在地图中是否能通过，不能通过则加入关闭列表中，跳出 判断每个节点是否在关闭列表中，在则跳出
 * 	  判断每个节点是否在开启列表中，在则更新G值，F值，还更新其父节点； 
 * 	  不在则将其添加到开启列表中，计算G值，H值，F值，添加其节点
 * 3.把此节点从开启列表中删除，再添加到关闭列表中 
 * 4.把开启列表中按照F值最小的节点进行排序，最小的F值在第一个 
 * 5.重复2，3，4步骤
 * 	  直到目标点在开启列表中，即找到了；目标点不在开启列表中，开启列表为空，即没找到
 *
 */
public class StarA2 {
	private int[][] map;// 地图(1可通过 0不可通过)
	private List<Node2> openList;// 开启列表
	private List<Node2> closeList;// 关闭列表
	private final int COST_STRAIGHT = 10;// 垂直方向或水平方向移动的路径评分
	private final int COST_DIAGONAL = 14;// 斜方向移动的路径评分
	private int row;// 行
	private int column;// 列

	public StarA2(int[][] map, int row, int column) {
		this.map = map;
		this.row = row;
		this.column = column;
		openList = new ArrayList<Node2>();
		closeList = new ArrayList<Node2>();
	}

	/**
	 * 查找坐标（-1：错误，0：没找到，1：找到）
	 * 
	 * @param x1  起始位置X
	 * @param y1  起始位置Y
	 * @param x2  结束位置X
	 * @param y2  结束位置Y
	 * @return （-1：错误，0：没找到，1：找到）
	 */
	public int search(int x1, int y1, int x2, int y2) {
		if (x1 < 0 || x1 >= row || x2 < 0 || x2 >= row || y1 < 0 || y1 >= column || y2 < 0 || y2 >= column) {
			return -1;
		}
		if (map[x1][y1] == 0 || map[x2][y2] == 0) {
			return -1;
		}
		Node2 sNode = new Node2(x1, y1, null);
		Node2 eNode = new Node2(x2, y2, null);
		openList.add(sNode);
		List<Node2> resultList = search(sNode, eNode);
		// 没有找到
		if (resultList.size() == 0) {
			return 0;
		}

		// 遍历结果，x，y赋值
		for (Node2 node : resultList) {
			map[node.getX()][node.getY()] = -1;
		}
		// 找到
		return 1;
	}

	/**
	 * 查找核心算法
	 * 
	 * @param sNode
	 * @param eNode   目标节点
	 * @return
	 */
	private List<Node2> search(Node2 sNode, Node2 eNode) {
		List<Node2> resultList = new ArrayList<Node2>();
		boolean isFind = false;
		Node2 node = null;
		while (openList.size() > 0) {
			// 取出开启列表中最低F值，即第一个存储的值的F为最低的
			// 有可能是目标节点的上一个节点
			node = openList.get(0);
			// 判断是否找到目标点
			if (node.getX() == eNode.getX() && node.getY() == eNode.getY()) {
				isFind = true;
				break;
			}
			// 上
			if ((node.getY() - 1) >= 0) {
				checkPath(node.getX(), node.getY() - 1, node, eNode, COST_STRAIGHT);
			}
			// 下
			if ((node.getY() + 1) < column) {
				checkPath(node.getX(), node.getY() + 1, node, eNode, COST_STRAIGHT);
			}
			// 左
			if ((node.getX() - 1) >= 0) {
				checkPath(node.getX() - 1, node.getY(), node, eNode, COST_STRAIGHT);
			}
			// 右
			if ((node.getX() + 1) < row) {
				checkPath(node.getX() + 1, node.getY(), node, eNode, COST_STRAIGHT);
			}
			// 左上
			if ((node.getX() - 1) >= 0 && (node.getY() - 1) >= 0) {
				checkPath(node.getX() - 1, node.getY() - 1, node, eNode, COST_DIAGONAL);
			}
			// 左下
			if ((node.getX() - 1) >= 0 && (node.getY() + 1) < column) {
				checkPath(node.getX() - 1, node.getY() + 1, node, eNode, COST_DIAGONAL);
			}
			// 右上
			if ((node.getX() + 1) < row && (node.getY() - 1) >= 0) {
				checkPath(node.getX() + 1, node.getY() - 1, node, eNode, COST_DIAGONAL);
			}
			// 右下
			if ((node.getX() + 1) < row && (node.getY() + 1) < column) {
				checkPath(node.getX() + 1, node.getY() + 1, node, eNode, COST_DIAGONAL);
			}
			// 从开启列表中删除
			// 添加到关闭列表中
			closeList.add(openList.remove(0));
			// 开启列表中排序，把F值最低的放到最底端
			Collections.sort(openList, new NodeFComparator());
		}
		//是否结束
		if (isFind) {
			getPath(resultList, node);
		}
		return resultList;
	}

	/**
	 *  查询此路是否能走通（节点是否可以达到）
	 * @param x
	 * @param y
	 * @param parentNode  父节点
	 * @param eNode    目标节点
	 * @param cost
	 * @return
	 */
	private boolean checkPath(int x, int y, Node2 parentNode, Node2 eNode, int cost) {
		Node2 node = new Node2(x, y, parentNode);
		// 查找地图中是否能通过
		//0：可以到达
		if (map[x][y] == 0) {
			closeList.add(node);
			return false;
		}
		// 查找关闭列表中是否存在
		//在closeList中，则不可达
		if (isListContains(closeList, x, y) != -1) {
			return false;
		}
		// 查找开启列表中是否存在
		int index = -1;
		//在openlist中存在
		if ((index = isListContains(openList, x, y)) != -1) {
			// G值是否更小，即是否更新G，F值
			// 重新设置节点G，F值
			if ((parentNode.getG() + cost) < openList.get(index).getG()) {
				node.setParentNode(parentNode);
				countG(node, eNode, cost);
				countF(node);
				openList.set(index, node);
			}
		} else {//节点不再openlist中
			// 添加到开启列表中
			node.setParentNode(parentNode);
			//计算G,H,F值
			count(node, eNode, cost);
			openList.add(node);
		}
		return true;
	}

	/**
	 * 集合中是否包含某个元素(-1：没有找到，否则返回所在的索引)
	 * @param list
	 * @param x
	 * @param y
	 * @return
	 */
	private int isListContains(List<Node2> list, int x, int y) {
		for (int i = 0; i < list.size(); i++) {
			Node2 node = list.get(i);
			if (node.getX() == x && node.getY() == y) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 从终点往返回到起点（原路返回）
	 * 递归
	 * @param resultList
	 * @param node
	 */
	private void getPath(List<Node2> resultList, Node2 node) {
		if (node.getParentNode() != null) {
			getPath(resultList, node.getParentNode());
		}
		resultList.add(node);
	}

	/**
	 * 计算G,H,F值
	 * @param node
	 * @param eNode
	 * @param cost
	 */
	private void count(Node2 node, Node2 eNode, int cost) {
		countG(node, eNode, cost);
		countH(node, eNode);
		countF(eNode);
	}

	/**
	 * 计算G值（从A点到方块的移动量）
	 * @param node
	 * @param eNode
	 * @param cost
	 */
	private void countG(Node2 node, Node2 eNode, int cost) {
		//父节点是null，直接设置G值
		if (node.getParentNode() == null) {
			node.setG(cost);
		} else {
			node.setG(node.getParentNode().getG() + cost);
		}
	}

	/**
	 * 计算H值（从方块到B点的估算移动量）
	 * @param node
	 * @param eNode
	 */
	private void countH(Node2 node, Node2 eNode) {
		node.setF(Math.abs(node.getX() - eNode.getX()) + Math.abs(node.getY() - eNode.getY()));
	}

	/**
	 * 计算F值
	 * @param node
	 */
	private void countF(Node2 node) {
		node.setF(node.getG() + node.getH());
	}

}

package demo2;

public class TestStarA2 {
	static int[][] map=new int[][]{// 地图数组
             {1,1,1,1,1,1,1,1,1,1},
             {1,1,1,1,0,1,1,1,1,1},
             {1,1,1,1,0,1,1,1,1,1},
             {1,1,1,1,0,1,1,1,1,1},
             {1,1,1,1,0,1,1,1,1,1},
             {1,1,1,1,0,1,1,1,1,1}
     };

	public static void main(String[] args) {

		StarA2 aStar = new StarA2(map, 6, 10);
		int flag = aStar.search(3, 0, 3, 8);
		if (flag == -1) {
			System.out.println("传输数据有误！");
		} else if (flag == 0) {
			System.out.println("没找到！");
		} else {// 找到
			//遍历行
			for (int x = 0; x < 6; x++) {
				for (int y = 0; y < 10; y++) {
					if (map[x][y] == 1) {
						System.out.print("0");
					} else if (map[x][y] == 0) {
						System.out.print("1");
					} else if (map[x][y] == -1) {
						System.out.print("2");
					}
				}
				System.out.println();
			}
		}
	}
}