AStar 搜索(A*) 寻路算法

import java.util.PriorityQueue;import java.util.Scanner;public class AStar {private int stepx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };// 第一个是上，顺时针private int stepy[] = { 1, 1, 0, -1, -1, -1, 0, 1 };// 第一个是上，顺时针private int gvalue[] = { 10, 14, 10, 14, 10, 14, 10, 14 };private int n;private int m;private char map[][];private Node mapNode[][];public AStar(int n, int m, Scanner s) {this.n = n;this.m = m;this.init(s);}public int run() {NodeComparator cmp = new NodeComparator();PriorityQueue<Node> open = new PriorityQueue<Node>(n * m, cmp);int x, y;int nxti, nxtj;Node nxt;mapNode[0][0].setInbox(true);mapNode[0][0].g = 0;mapNode[0][0].f = mapNode[0][0].g + mapNode[0][0].h;open.add(mapNode[0][0]);while (!open.isEmpty()) {Node top = open.poll();// 获取并移除此队列的头，如果此队列为空，则返回 null。top.setSteped(true);// 如果终点在结束列表中，表示表示找到了最优解if (mapNode[n - 1][m - 1].isSteped())break;x = top.i;y = top.j;for (int i = 0; i < 8; i++) {nxti = x + stepx[i];nxtj = y + stepy[i];if (!inRange(nxti, nxtj))continue;if(map[nxti][nxtj]=='x')continue;nxt = mapNode[nxti][nxtj];int gg = top.g + gvalue[i];if (gg < nxt.g) {nxt.g = gg;nxt.f = gg + nxt.h;nxt.parent = top;}if (!nxt.isInbox()){nxt.setInbox(true);open.add(nxt);//System.out.println("--> ("+nxt.i+", "+nxt.j+")");}}}return mapNode[n-1][m-1].f;}public void printRace(){Node cur = mapNode[n-1][m-1];while(!cur.parent.equals(cur)){//System.out.println("[ "+cur.i+", "+cur.j+"]");map[cur.i][cur.j] = 'O';cur = cur.parent;}for( int i = 0 ; i < n; i++){for( int j = 0; j < m; j++){System.out.print(map[i][j]);}System.out.println();}}private boolean inRange(int nxti, int nxtj) {if (nxti >= n || nxtj >= m || nxti < 0 || nxtj < 0)return false;return true;}private void init(Scanner s) {map = new char[n][m];mapNode = new Node[n][m];for (int i = 0; i < n; i++) {String tmp = s.next();for (int j = 0; j < m; j++) {map[i][j] = tmp.charAt(j);mapNode[i][j] = new Node(i, j);mapNode[i][j].h = getH(i + 1, j + 1);}}}/** * 曼哈顿距离 * * @param i * @param j * @return */private int getH(int i, int j) {return (n - i + m - j) * 10;}public int getN() {return n;}public void setN(int n) {this.n = n;}public int getM() {return m;}public void setM(int m) {this.m = m;}public char[][] getMap() {return map;}public void setMap(char[][] map) {this.map = map;}}

?

?

?

/** * 地图中的每个位置 * @author coolgo */public class Node {public int i,j;/** * f = g + h; h为估价函数 */public int f=1<<30;public int g=1<<30;public int h=1<<30;/** * if steped= true;表示已经在close列表中 */private boolean steped = false;/** * if inbox = true;表示已经在open列表中 */private boolean inbox = false;public Node parent = this;public Node(int ii, int jj){i = ii;j = jj;}public void setSteped(boolean steped) {this.steped = steped;}public boolean isSteped() {return steped;}public void setInbox(boolean inbox) {this.inbox = inbox;}public boolean isInbox() {return inbox;}}

?

?

import java.util.Comparator;/** * 比较器 * @author coolgo */public class NodeComparator implements Comparator<Node> {@Overridepublic int compare(Node x, Node y) {return x.f - y.f;}}

?

?

import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.Date;import java.util.Scanner;public class Mainx{public static void main(String [] argv) throws FileNotFoundException {FileInputStream fs = new FileInputStream("D:\\work\\Astar\\src\\c.txt");Scanner s = new Scanner(fs);int n,m;n = s.nextInt();m = s.nextInt();AStar ast = new AStar(n,m,s);Date t = new Date();int res = ast.run();Long x = (new Date()).getTime() - t.getTime();ast.printRace();System.out.println("消耗"+res);System.out.println("运行时间"+x+"毫秒");}}

?

?