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;this.OpenList = new Node;}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 = 7;}for (int i = 0; i < a.map.length; i++) {for (int j = 0; j < a.map.length; j++) {if (a.mapc == 7) {System.out.print("※");} else {if (a.map == 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 = sNode;mapc = Constant.NOTE_OPEN;Node cNode = null;while (olength > 0) {cNode = OpenList;@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 forthis.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 == Constant.NOTE_NOWAY) {// 没门return false;}if (mapc == Constant.NOTE_CLOSED) {return false;}if (mapc == Constant.NOTE_NONE) {this.putOpenTable(x, y, eNode, parentNode, step);mapc = Constant.NOTE_OPEN;return true;} else if (mapc == 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 = OpenList;tNode = OpenList;int i = 1;while ((i * 2 + 1) <= olength) {if (tNode.getF() < OpenList.getF()&& tNode.getF() < OpenList.getF()) {break;} else {if (OpenList.getF() < OpenList.getF()) {// 找一个相对较小的子节点交换OpenList = OpenList;OpenList = tNode;i = i * 2;} else {OpenList = OpenList;OpenList = tNode;i = i * 2 + 1;}}}OpenList = null;olength--;mapc = 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 = node;OpenTable.put(node.getX() + "_" + node.getY(), node);int i = olength / 2;Node mid = OpenList;while (mid.getF() > node.getF()) {Node temp = mid;OpenList = OpenList;OpenList = temp;i = i / 2;if (i < 1) {i = 1;}mid = OpenList;}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 == 1) {nodeList.add(new Node(x1 - k, y1 + i));}} catch (Exception e) {}}for (int i = -k; i <= k; i++) {try {if (map == 1) {nodeList.add(new Node(x1 + k, y1 + i));}} catch (Exception e) {}}for (int i = -(k - 1); i <= k - 1; i++) {try {if (map == 1) {nodeList.add(new Node(x1 + i, y1 - k));}} catch (Exception e) {}}for (int i = -(k - 1); i <= k - 1; i++) {try {if (map == 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;} 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;}
页:
[1]