Java游戏中的AStar算法源代码

import javax.microedition.lcdui.Graphics; /** * Task: A* 寻路算法 * @author JAROD * Download by http://www.codefans.net * 这里，我并没有完全采用面向对象的思想， * 因为抽离出一个接口，反而显的有点啰嗦了，具体问题具体分析 * */ public class AStar { private int map[][];//地图 private int map_width;//地图的宽度 private int map_height;//地图的高度 private boolean closeList[][];//关闭列表 private int openList[][][];//打开列表 private int openListLength; /* * 注意，打开列表和关闭列表仅仅是容器， * 我这里我几乎完全COPY了论坛上untosil朋友的思想， * 这是一个不错的解决方法。 */ private static final int EXIST = 1; private static final int NOT_EXIST = 0; private static final int ISEXIST = 0; private static final int EXPENSE = 1; //自身的代价 private static final int DISTANCE = 2; //距离的代价 private static final int COST = 3; //消耗的总代价 private static final int FATHER_DIR = 4;//父节点的方向 public static final int DIR_NULL = 0; public static final int DIR_DOWN = 1; public static final int DIR_UP = 2; public static final int DIR_LEFT = 3; public static final int DIR_RIGHT = 4; private boolean isFound;//是否找到路径 private int beginW;//起点位置 private int beginH; private int endW; //目标点位置 private int endH; private int passCount; private int passSpeed = 100; private int passTotalLength; private int passLengthCount; private void cylcePassCount() { passCount += passSpeed; if(passCount >= 1000) { passTotalLength++; passCount -= 1000; } } public void setPassSpeed(int speed) { passSpeed = speed; } /** * Task:设置地图 * 这个本应该是接口实现的。 * @author JAROD * @param obj */ public void setMap(int obj[][]) { map = obj; map_width = map[0].length; map_height = map.length; closeList = new boolean[map_height][map_width]; openList = new int[map_height][map_width][5]; openListLength = 0; } /** * Task: 判断地图上的一点是否可以通行 * 这个本应该是接口实现的。 * @author JAROD * @param w * @param h * @return */ private boolean isMapCanMove(int w, int h) { if (map[h][w] == 0) { return true; } else { return false; } } /** * Task: 得到地图上这一点的消耗值 * 这个本应该是接口实现的。 * @author JAROD * @param w * @param h * @return */ private int getMapExpense(int w, int h) { return 1; } /** * Task: 得到距离的消耗值 * 这个本应该是接口实现的。 * @author JAROD * @param w * @param h * @param targetW * @param targetH * @return */ private int getDistance(int w, int h, int targetW, int targetH) { return Math.abs(w - targetW) + Math.abs(h - targetH); } /** * Task: 得到给定坐标格子此时的总消耗值 * @author JAROD * @param w * @param h * @return */ private int getCost(int w, int h) { return openList[h][w][COST]; } /** * Task:开始寻路 * @author JAROD * @param beginW * @param beginH * @param targetW * @param targetH */ public void searchPath(int beginW, int beginH, int targetW, int targetH) { this.beginW = beginW; this.beginH = beginH; this.endW = targetW; this.endH = targetH; initOpenList(targetW, targetH); addOpenList(beginW, beginH); aStar(beginW, beginH, targetW, targetH); } /** * Task: 画出路径 * @author JAROD * @param g * @param startX * @param startY * @param eachTileWidth * @param eachTileHeight */ public void drawRoute(Graphics g, int startX, int startY, int eachTileWidth, int eachTileHeight) { int color = g.getColor(); g.setColor(0xffffff); g.fillRect(startX, startY, eachTileWidth * map_width, eachTileHeight * map_height); if (isFound == false) { g.setColor(0x0); g.drawString("没有找到路径", (eachTileWidth * map_width / 2) + startX, (eachTileHeight * map_height) / 2 + startY, g.BASELINE | g.HCENTER); g.setColor(color); return; } for (int i = 0; i < map_width; i++) { for (int j = 0; j < map_height; j++) { if (isMapCanMove(i, j) == false) { g.setColor(0xf); g.fillRect(startX + i * eachTileWidth + 1, startY + j * eachTileHeight + 1, eachTileWidth - 2, eachTileHeight - 2); } else { g.setColor(0xffff); g.fillRect(startX + i * eachTileWidth + 1, startY + j * eachTileHeight + 1, eachTileWidth - 2, eachTileHeight - 2); } } } cylcePassCount(); passLengthCount = 0; drawPassRoute(g, startX, startY, eachTileWidth, eachTileHeight, endW, endH); g.setColor(color); } /** * Task: 画出路径 * @author JAROD * @param g * @param sx * @param sy * @param w * @param h * @param ew * @param eh */ public void drawPassRoute(Graphics g, int sx, int sy, int w, int h, int ew, int eh) { if(passLengthCount>=passTotalLength) { return ; } passLengthCount++; g.setColor(0xff0000); g.fillRect(sx + ew * w + 1, sy + eh * h + 1, w - 2, w - 2); switch (openList[eh][ew][FATHER_DIR]) { case DIR_DOWN: { drawPassRoute(g,sx,sy,w,h,ew,eh-1); } break; case DIR_UP: { drawPassRoute(g,sx,sy,w,h,ew,eh+1); } break; case DIR_LEFT: { drawPassRoute(g,sx,sy,w,h,ew+1,eh); } break; case DIR_RIGHT: { drawPassRoute(g,sx,sy,w,h,ew-1,eh); } break; case DIR_NULL: { passTotalLength = 0; } break; } } /** * Task: 打印出路径的寻找方向 * @author JAROD */ public void showRoute() { for (int i = 0; i < map_height; i++) { for (int j = 0; j < map_width; j++) { System.out.print(" " + openList[i][j][FATHER_DIR]); } System.out.println(); } } /** * Task 寻路 * @author JAROD * @param w * @param h * @param endW * @param endH */ private void aStar(int w, int h, int endW, int endH) { int iX; int iY; int cost; if (((w == endW) && (h == endH))) { isFound = true; return; } else if ((openListLength == 0)) { isFound = false; return; } removeOpenList(w, h); addCloseList(w, h); // Down addNewOpenList(w, h, w, h + 1, DIR_DOWN); // Up addNewOpenList(w, h, w, h - 1, DIR_UP); // Left addNewOpenList(w, h, w - 1, h, DIR_LEFT); // right addNewOpenList(w, h, w + 1, h, DIR_RIGHT); iX = w; iY = h; cost = 0x7fffffff; for (int i = 0; i < map_height; i++) { for (int j = 0; j < map_width; j++) { if (isOpenListExist(j, i)) { if (cost > getCost(j, i)) { cost = getCost(j, i); iX = j; iY = i; } } } } aStar(iX, iY, endW, endH); } /** * Task: 添加一个新的节点 * @author JAROD * @param w * @param h * @param newW * @param newY * @param dir */ private void addNewOpenList(int w, int h, int newW, int newY, int dir) { if (isCanPass(newW, newY) == true) { if (isOpenListExist(newW, newY) == false) { addOpenList(newW, newY); setFatherDir(newW, newY, dir); setCost(newW, newY, w, h); } else { if (openList[h][w][EXPENSE] + getMapExpense(newW, newY) < openList[newY][newW][EXPENSE]) { setFatherDir(newW, newY, dir); setCost(newW, newY, w, h); } } } } /** * Task: 设置消耗值 * @author JAROD * @param w * @param h * @param fw * @param fh */ private void setCost(int w, int h, int fw, int fh) { openList[h][w][EXPENSE] = openList[fh][fw][EXPENSE] + getMapExpense(w, h); openList[h][w][DISTANCE] = getDistance(w, h, fw, fh); openList[h][w][COST] = openList[h][w][EXPENSE] + openList[h][w][DISTAN