j2me中的A*算法

import javax.microedition.midlet.*;
import javax.microedition.lcdui.*;
import java.lang.Thread;

public class MainMid extends MIDlet {
	MainPit myScreen;
	boolean first = true;

	public MainMid() {
		myScreen = new MainPit(this);
	}

	protected void destroyApp(boolean unconditional) {
	}

	protected void pauseApp() {
	}

	protected void startApp()// J2ME程序的执行线程，自动执行响应按键。
	{
		Display.getDisplay(this).setCurrent(myScreen);// myScreen获得当前屏幕的显示权
		if (first)// 限定执行线程只执行一次
		{
			try {
				Thread myThread = new Thread(myScreen);// 开启一个线程用来实现游戏的逻辑与绘制
				myThread.start();// 打开线程
			} catch (Error e) {
				destroyApp(false);
				notifyDestroyed();
			}
			first = false;
		}
	}

	// 游戏结束
	public void exit()// 关闭执行线程，整体程序退出
	{
		destroyApp(true);
		notifyDestroyed();
	}

}

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=10, cy=0;

	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++) {
				switch (moveSpace[i][j]) {
				case 1:
					gb.setColor(0x00000000);
					gb.drawRect(j * cw, i * ch, cw, ch);
					break;
				case 2:
					gb.setColor(0x00ffff00);
					gb.fillRect(j * cw, i * ch, cw, ch);
					break;
				case 8:
					gb.setColor(0x00cccccc);
					gb.fillRect(j * cw, i * ch, cw, ch);
					break;
				case 9:
					gb.setColor(0x00000000);
					gb.fillRect(j * cw, i * ch, cw, ch);
					break;
				default:
					break;
				}
			}
		}
	}

	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, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
			{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
			{ 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
			{ 1, 8, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 9, 9, 9, 9, 9, 9, 1, 1 },
			{ 1, 9, 8, 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, 8, 1, 1, 2, 2, 2, 2, 2, 2, 2 },
			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1 },
			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
			{ 1, 1, 9, 9, 9, 9, 9, 9, 1, 2, 1, 1, 9, 9, 9, 9, 9, 9, 1, 1 },
			{ 1, 9, 1, 1, 1, 1, 1, 9, 1, 2, 2, 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, 2, 9, 9, 9, 1, 9, 1, 1, 9, 1, 1 },
			{ 1, 1, 9, 1, 9, 9, 9, 9, 1, 2, 1, 1, 9, 1, 9, 9, 9, 9, 1, 1 },
			{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 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;
		switch (moveSpace[y][x]) {//所有障碍物
		case 8:
		case 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
			/*
			 * 如果某个相邻格已经在开启列表里了， 检查现在的这条路径是否更好。 换句话说，检查如果我们用新的路径到达它的话，
			 * 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, 4);
					getGHF(ttx - 1, tty, tx, ty);
				}
			}
		}

		if (!isBalk(ttx, tty + 1)) {
			if (openList[tty + 1][ttx][0] == 0) {
				addInOpenList(ttx, tty + 1);
				setFather(ttx, tty + 1, 1);
				getGHF(ttx, tty + 1, tx, ty);
			} else
			/*
			 * 如果某个相邻格已经在开启列表里了， 检查现在的这条路径是否更好。 换句话说，检查如果我们用新的路径到达它的话，
			 * G值是否会更低一些。如果不是，那就什么都不做。 另一方面，如果新的G值更低， 那就把相邻方格的父节点改为目前选中的方格
			 */
			if (openList[tty + 1][ttx][0] == 1) {
				if (openList[tty][ttx][1] + moveSpace[tty + 1][ttx] < openList[tty + 1][ttx][1]) {
					setFather(ttx, tty + 1, 1);
					getGHF(ttx, tty + 1, tx, ty);
				}
			}
		}

		if (!isBalk(ttx, tty - 1)) {
			if (openList[tty - 1][ttx][0] == 0) {
				addInOpenList(ttx, tty - 1);
				setFather(ttx, tty - 1, 2);
				getGHF(ttx, tty - 1, tx, ty);
			} else
			/*
			 * 如果某个相邻格已经在开启列表里了， 检查现在的这条路径是否更好。 换句话说，检查如果我们用新的路径到达它的话，
			 * G值是否会更低一些。如果不是，那就什么都不做。 另一方面，如果新的G值更低， 那就把相邻方格的父节点改为目前选中的方格
			 */
			if (openList[tty - 1][ttx][0] == 1) {
				if (openList[tty][ttx][1] + moveSpace[tty - 1][ttx] < openList[tty - 1][ttx][1]) {
					setFather(ttx, tty - 1, 2);
					getGHF(ttx, tty - 1, tx, ty);
				}
			}
		}

		// 从开启列表中选择F值最低的方格。
		int bx = ttx, by = tty, 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];
						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) {
		}
	}

	/**
	 * 核心算法
	 * @param bx
	 * @param by
	 * @param tx
	 * @param ty
	 */
	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);//加入OpenList
			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();
		}
	}

	protected void showfather(int x, int y) {
		if (x == begin_x && y == begin_y) {
			//搜索结束
			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;
		}
	}
}

[翻译]A*寻路初探
http://blog.vckbase.com/panic/archive/2005/03/20/3778.html