A星寻路算法 java源程序

package starUtil; import java.util.LinkedList; import java.util.List; /** * @author wenbin_jin * @since aStarAth * @create 2010-3-31 */ public class WayFinder { /** openList存放待考察的节点，closeList存放已经考察过的节点 */ private List<Node> openList; private List<Node> closeList; private int x_limit; private int y_limit; private Node startNode; private Node endNode; public Node getStartNode() { return startNode; } public void setStartNode(Node startNode) { this.startNode = startNode; } public Node getEndNode() { return endNode; } public void setEndNode(Node endNode) { this.endNode = endNode; } public int getX_limit() { return x_limit; } public void setX_limit(int x_limit) { this.x_limit = x_limit; } public int getY_limit() { return y_limit; } public void setY_limit(int y_limit) { this.y_limit = y_limit; } /** * 构造方法，初始化openList和closeList */ public WayFinder(int x_limit, int y_limit, Node snode, Node enode) { openList = new LinkedList<Node>(); closeList = new LinkedList<Node>(); this.x_limit = x_limit; this.y_limit = y_limit; this.startNode = snode; this.endNode = enode; } /** * 把待考察的节点加入openList * * @param node */ public void addToOpenList(Node node) { if (openList.size() == 0) openList.add(node); else { int index = 0; while (node.getAvg() > ((Node) openList.get(index)).getAvg() && index < openList.size() - 1) { index++; } openList.add(index, node); } } /** * 把已经考察过的节点加入closeList * * @param node */ public void addToCloseList(Node node) { closeList.add(node); } /** * 判断一个节点是否在某个链表中 * * @param list * @param node * @return 如果是，返回TRUE 不是返回FALSE */ public boolean isInList(List<Node> list, Node node) { int index = 0; while (index < list.size()) { Node nodeInList = (Node) list.get(index); if (node.getX_coor() == nodeInList.getX_coor() && node.getY_coor() == nodeInList.getY_coor()) return true; else index++; } return false; } /** * * 创建新的节点 * * @param currentNode * @param endNode * @param x_coor * @param y_coor * @param x_limit * @param y_limit * @return */ public Node createNode(List<Node> unpassList, Node currentNode, int x_coor, int y_coor, int x_limit, int y_limit) { if (x_coor > 0 && x_coor <= x_limit && y_coor > 0 && y_coor <= y_limit) { Node newNode = new Node(x_coor, y_coor); if (!(isInList(unpassList, newNode)) && !(isInList(closeList, newNode))) { newNode.setFrom_bgn(currentNode); newNode.setFrom_end(endNode); newNode.setAvg(); newNode.setParentNode(currentNode); return newNode; } } return null; } /** * * 从当前节点currentNode开始，向以他为中心的八个方向扩展更多可以到达的节点 * * @param currentNode */ public void extendMoreNode(List<Node> unpassList, Node currentNode, Node endNode, int x_limit, int y_limit) { Node newNode; int x; int y; x = currentNode.getX_coor() - 10; y = currentNode.getY_coor() - 10; newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor(); y = currentNode.getY_coor() - 10; newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor() + 10; y = currentNode.getY_coor() - 10; newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor() - 10; y = currentNode.getY_coor(); newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor() + 10; y = currentNode.getY_coor(); newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor() - 10; y = currentNode.getY_coor() + 10; newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor(); y = currentNode.getY_coor() + 10; newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } x = currentNode.getX_coor() + 10; y = currentNode.getY_coor() + 10; newNode = createNode(unpassList, currentNode, x, y, x_limit, y_limit); if (newNode != null) { addToOpenList(newNode); } } public void findWay(List<Node> unpassList) { addToOpenList(startNode); Node node = openList.get(0); while (!node.equals(endNode)) { extendMoreNode(unpassList, node, endNode, x_limit, y_limit); addToCloseList(node); openList.remove(node); if (openList.size() <= 0) { System.out.println("没有路径可以从(" + startNode.getX_coor() + "," + startNode.getY_coor() + ")通往 (" + endNode.getX_coor() + "," + endNode.getY_coor() + ")"); return; } else { node = openList.get(0); } } getWayOut(node); } public void getWayOut(Node lastNode) { if (lastNode.getParentNode() != null) { getWayOut(lastNode.getParentNode()); } System.out.println("(" + lastNode.getX_coor() + "," + lastNode.getY_coor() + ")"); } }