/**A*算法研究*/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 
     
       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[i][j][3]){						minf = openList[i][j][3];						bx = j;by = i;					}				}			}		}		AAsterisk_t(bx,by,tx,ty);	}		public void pause(long l)	{		try{Thread.sleep(l);System.gc();Thread.yield();}catch(Exception e){}	}		private	void AAsterisk(int bx,int by, int tx,int ty)	{		closeList = null;		openList = null;		closeList = new boolean[mHeight][mWidth];		openList = new int[mHeight][mWidth][5];		closeListLength = 0;		openListLength = 0;		for(int i = 0; i < mHeight; i++){			for(int j = 0; j < mWidth; j++){				//加入标志				openList[i][j][0] = 0;				//   * G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。				openList[i][j][1] = moveSpace[i][j];				//  * H = 从网格上那个方格移动到终点B的预估移动耗费。				//这经常被称为启发式的，可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。				//H值可以用不同的方法估算。				//我们这里使用的方法被称为曼哈顿方法，				//它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向。				openList[i][j][2] = Math.abs(i - ty) + Math.abs(j - tx);				//F = G+H				openList[i][j][3] = openList[i][j][1] + openList[i][j][2];				//父节点				openList[i][j][4] = 0;			}		}				/*		1，从点A开始，并且把它作为待处理点存入一个“开启列表”。		开启列表就像一张购物清单。		尽管现在列表里只有一个元素，但以后就会多起来。		你的路径可能会通过它包含的方格，也可能不会。		基本上，这是一个待检查方格的列表。*/		addInOpenList(bx,by);		/*		   2，寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格。	   也把他们加入开启列表。	   为所有这些方格保存点A作为“父方格”。	   当我们想描述路径的时候，父方格的资料是十分重要的。	   后面会解释它的具体用途。	  		*/		if(!isBalk(bx+1,by)){			addInOpenList(bx+1,by);			setFather(bx+1,by,3);			getGHF(bx+1,by,tx,ty);		}				if(!isBalk(bx-1,by)){			addInOpenList(bx-1,by);			setFather(bx-1,by,4);			getGHF(bx-1,by,tx,ty);		}				if(!isBalk(bx,by+1)){			addInOpenList(bx,by+1);			setFather(bx,by+1,1);			getGHF(bx,by+1,tx,ty);		}				if(!isBalk(bx,by-1)){			addInOpenList(bx,by-1);			setFather(bx,by-1,2);			getGHF(bx,by-1,tx,ty);		}				// 3，从开启列表中删除点A，把它加入到一个“关闭列表”		removeFromOpenList(bx,by);		addInCloseList(bx,by);		//		从开启列表中选择F值最低的方格。		int ttx = bx,tty=by,minf=255;		for(int i = 0; i < mHeight; i++){			for(int j = 0; j < mWidth; j++){				if(openList[i][j][0] == 1){					if(minf>openList[i][j][3]){						minf = openList[i][j][3];						ttx = j;tty = i;					}				}			}		}				AAsterisk_t(ttx,tty,tx,ty);	}		public void showOpenList()	{		for(int i = 0; i < mHeight; i++){			for(int j = 0; j < mWidth; j++){				System.out.print("("+openList[i][j][0]+","+openList[i][j][1]+","+openList[i][j][2]+","+openList[i][j][3]+","+openList[i][j][4]+")");			}			System.out.println();		}	}		public void showCloseList()	{		for(int i = 0; i < mHeight; i++){			for(int j = 0; j < mWidth; j++){				System.out.print("("+closeList[i][j]+")");			}			System.out.println();		}	}			private	void showfather(int x, int y)	{		if(x == begin_x&&y == begin_y){System.out.println("end");return;}		gb.setColor(0x00ff0000);		gb.fillArc(x * cw, y * ch, cw,ch, 0, 360);		switch(openList[y][x][4])		{			case 1:				showfather(x,y-1);			break;			case 2:				showfather(x,y+1);			break;			case 3:				showfather(x-1,y);			break;			case 4:				showfather(x+1,y);			break;			default:			break;		}	}}