AA.rar_Java 迷宫_路径

/** A*算法研究 李波seven */ import java.lang.*; import javax.microedition.lcdui.*; import java.util.Random; import javax.microedition.rms.*; import java.io.*; class MainPit extends Canvas implements Runnable { MainMid myMid; //按键表 private static final byte KEY_NONE = 0; private static final byte KEY_UP = -1; private static final byte KEY_DOWN = -2; private static final byte KEY_LEFT = -3; private static final byte KEY_RIGHT = -4; private static final byte KEY_FIRE = -5; private static final byte KEY_GAM_LEFT = -6; private static final byte KEY_GAM_RIGHT = -7; private static final byte KEY_NUM5 = 53; private int hangfire = 300;//延时大小 Graphics gb; private Image bufImg;//缓存 //屏幕大小 private int nWidth; private int nHeight; public MainPit(MainMid mid) { myMid = mid; nWidth = getWidth();//屏幕大小 nHeight = nWidth;//getHeight(); cw = nWidth / mWidth; ch = nHeight / mHeight; try{ bufImg = Image.createImage(nWidth,nHeight);//申请缓存空间 gb = bufImg.getGraphics(); }catch(Exception e){} } public void paint(Graphics g) { g.setColor(0);g.fillRect(0,0,nWidth,getHeight()); g.drawImage(bufImg, 0,0,0); g.setColor(0xff00); g.drawString(""+ttime,0, getHeight(),36); } private void showBegin() { gb.setColor(0x0000ff00); gb.fillArc(begin_x * cw, begin_y * ch, cw, ch, 0, 360); } int state = 0; public void run() { while(true) { switch(state) { case 0: showMap(); showCursor(); break; case 1: showMap(); showBegin(); showCursor(); break; case 2: showMap(); showBegin(); showfather(end_x, end_y); showCursor(); break; } repaint(); serviceRepaints(); try{ Thread.sleep(hangfire); System.gc(); Thread.yield(); }catch(Exception e){} } } private int cx,cy; private void showCursor() { gb.setColor(0x000000ff); gb.drawRect(cx * cw+2,cy*ch+2,cw-4,ch-4); } private int cw,ch; private void showMap() { clearScreen(0x00ffffff); for(int i =0 ; i < mHeight; i++){ for(int j = 0; j < mWidth; j++){ if(moveSpace[i][j]==1){ gb.setColor(0x00000000); gb.drawRect(j * cw, i * ch, cw, ch); } else{ gb.setColor(0x00000000); gb.fillRect(j * cw, i * ch, cw, ch); } } } } private void clearScreen(int c)//用颜色c刷新屏幕 { gb.setColor(c); gb.fillRect(0,0,nWidth,nHeight); } public void keyPressed(int keyCode) { switch(keyCode) { case KEY_UP: case 50: if(cy>0) cy--; break; case 56: case KEY_DOWN: if(cy <mHeight-1) cy++; break; case 52: case KEY_LEFT: if(cx > 0) cx--; break; case 54: case KEY_RIGHT: if(cx < mWidth -1) cx++; break; case KEY_FIRE: case KEY_GAM_LEFT: case KEY_NUM5: switch(state) { case 0: begin_x = cx; begin_y = cy; state = 1; break; case 1: end_x = cx; end_y = cy; ttime = System.currentTimeMillis(); AAsterisk(begin_x,begin_y,end_x,end_y); ttime = System.currentTimeMillis()-ttime; state = 2; break; case 2: state = 0; break; } break; case KEY_GAM_RIGHT: myMid.exit(); break; } } long ttime; private int begin_x = 0; private int begin_y = 9; private int end_x = 0; private int end_y = 0; public int mWidth=20,mHeight=20; private int moveSpace[][] = { {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,9,9,9,9,9,9,1,1,1,1,9,9,9,9,9,9,1,1}, {1,9,1,1,1,1,1,9,1,1,1,9,1,1,1,1,1,9,1,1}, {1,9,1,1,9,9,1,9,1,1,1,9,1,1,9,9,1,9,1,1}, {9,9,9,1,9,1,1,9,1,1,9,9,9,1,9,1,1,9,1,1}, {1,1,9,1,9,9,9,9,1,1,1,1,9,1,9,9,9,9,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,9,1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,9,9,9,9,9,9,1,1,1,1,9,9,9,9,9,9,1,1}, {1,9,1,1,1,1,1,9,1,1,1,9,1,1,1,1,1,9,1,1}, {1,9,1,1,9,9,1,9,1,1,1,9,1,1,9,9,1,9,1,1}, {9,9,9,1,9,1,1,9,1,1,9,9,9,1,9,1,1,9,1,1}, {1,1,9,1,9,9,9,9,1,1,1,1,9,1,9,9,9,9,1,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,1,9,1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1} }; private int openListLength = 0; private int closeListLength = 0; //“关闭列表”，列表中保存所有不需要再次检查的方格。 private boolean closeList[][]; private void addInCloseList(int x, int y) { closeList[y][x] = true; closeListLength++; } /*开启列表就像一张购物清单。 你的路径可能会通过它包含的方格，也可能不会。 基本上，这是一个待检查方格的列表。*/ private int[][][] openList; private void addInOpenList(int x, int y) { openList[y][x][0] = 1; openListLength++; } private void removeFromOpenList(int x, int y) { openList[y][x][0] = 0; openListLength--; } private boolean isBalk(int x, int y) { if(x < 0||x >=mWidth||y < 0||y >=mHeight){ return true; } if(closeList[y][x])return true; if(moveSpace[y][x] == 9){ return true; } return false; } //设置父节点,f:0本身,1,上,2,下,3 左,4,右 private void setFather(int x, int y, int f) { openList[y][x][4] = f; } private void getGHF(int x, int y, int tx, int ty) { openList[y][x][1] = getG(x,y); openList[y][x][2] = getH(x,y,tx,ty); openList[y][x][3] = openList[y][x][1]+openList[y][x][3]; } // * G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。 //父节点的G+自身耗费 private int getG(int x, int y) { switch(openList[y][x][4]) { default: return moveSpace[y][x]; case 1: return openList[y-1][x][1]+moveSpace[y][x]; case 2: return openList[y+1][x][1]+moveSpace[y][x]; case 3: return openList[y][x-1][1]+moveSpace[y][x]; case 4: return openList[y][x+1][1]+moveSpace[y][x]; } } // * H = 从网格上那个方格移动到终点B的预估移动耗费。 //这经常被称为启发式的，可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。 //H值可以用不同的方法估算。 //我们这里使用的方法被称为曼哈顿方法， //它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。 private int getH(int x, int y, int tx, int ty) { return Math.abs(x - tx) + Math.abs(y - ty); } private void AAsterisk_t(int ttx,int tty, int tx,int ty) { /* * 把目标格添加进了开启列表，这时候路径被找到，或者 * 没有找到目标格，开启列表已经空了。这时候，路径不存在。 */ if((ttx==tx&&tty == ty)||openListLength==0)return; // 4，把它从开启列表中删除，然后添加到关闭列表中。 removeFromOpenList(ttx,tty); addInCloseList(ttx,tty); /*5，检查所有相邻格子。 跳过那些已经在关闭列表中的或者不可通过的 (有墙，水的地形，或者其他无法通过的地形)， 把他们添加进开启列表，如果他们还不在里面的话。 把选中的方格作为新的方格的父节点。 */ if(!isBalk(ttx+1,tty)){ if(openList[tty][ttx+1][0]==0){ addInOpenList(ttx+1,tty); setFather(ttx+1,tty,3); getGHF(ttx+1,tty,tx,ty); }else /* 如果某个相邻格已经在开启列表里了， 检查现在的这条路径是否更好。 换句话说，检查如果我们用新的路径到达它的话， G值是否会更低一些。如果不是，那就什么都不做。 另一方面，如果新的G值更低， 那就把相邻方格的父节点改为目前选中的方格 */ if(openList[tty][ttx+1][0]==1){ if(openList[tty][ttx][1] + moveSpace[tty][ttx+1]<openList[tty][ttx+1][1]){ setFather(ttx+1,tty,3); getGHF(ttx+1,tty,tx,ty); } } } if(!isBalk(ttx-1,tty)){ if(openList[tty][ttx-1][0]==0){ addInOpenList(ttx-1,tty); setFather(ttx-1,tty,4); getGHF(ttx-1,tty,tx,ty); }else /* 如果某个相邻格已经在开启列表里了， 检查现�