A*寻道（J2ME实现）
这是很久前另一个BLOG上的，现在不用了。转过来吧，方便查看...
找工作未果， 闲来无事，先学学一些感兴趣的算法和弄些小东西~~
参考文章：
http://blog.vckbase.com/panic/archive/2005/03/20/3778.html
写得真的非常棒，翻译得也很好，整个实现就是跟着他来的。
直接上代码，效率问题没有仔细研究过，我是每次寻路完毕都进行一次资源释放，进一步的优化可以继续参考以上连接作者BLOG的其他关于A*的文章。
/***
* A*寻路
* @author univasity
* 2008-10-01 0:19
* QQ:595920004
*/
public class PF_A_Start {
/**构造函数*/
public PF_A_Start(byte[][] map, byte[] blocks) {
this.map = map;
this.blocks = blocks;
}
/**
* 根据指定的起始位置和目标寻路
* @param sx 起始点X坐标
* @param sy 起始点Y坐标
* @param tx 目标点X坐标
* @param ty 目标点Y坐标
* @return 可行的路径，如果没有则返回空
*/
public int[][] findPath(int sx, int sy, int tx, int ty){
init();
setFatherNode(sx, sy, sx, sy); // 起始点的父节点设置为自身
value_G[sy][sx] = 0;
value_H[sy][sx] = CalculationValueH(sx, sy, tx, ty);
addToOpenList(sx, sy); // 把起始点加入开放列表
while(num_open>0 && !(sucess = isInCloseList(tx, ty))){
// 获取具有最小F值的节点，作为下一个移动目标
int node1 = openList[0];
int nx = node1%10;
int ny = node1/10;
for(int i=1; i<num_open-1; i++){
int node2 = openList[i+1];
int x2 = node2%10;
int y2 = node2/10;
if(ValueF(x2, y2)<ValueF(nx, ny)){
nx = x2;
ny = y2;
}
}
// 把四周可到的节点加入开放列表，以待检测
for(int i=0; i<8; i++){
if(isBlock(nx+px[i], ny+py[i])) // 如果是障碍，跳过
continue;
if(isInCloseList(nx+px[i], ny+py[i])) // 如果已存在关闭列表中，跳过
continue;
if(isInOpenList(nx+px[i], ny+py[i])){ // 如果已存在开放列表中
int fatherNode = FatherNode(nx+px[i], ny+py[i]);
// 判断以当前节点为父节点，G值是否比原来小
setFatherNode(nx+px[i], ny+py[i], nx, ny);
if(CalculationValueG(nx+px[i], ny+py[i])<value_G[ny+py[i]][nx+px[i]]){ // 如果只是
value_G[ny+py[i]][nx+px[i]] = CalculationValueG(nx+px[i], ny+py[i]); // 更新G值，令父节点为当前节点
}else{ // 否则
setFatherNode(nx+px[i], ny+py[i], fatherNode%10, fatherNode/10); // 恢复父节点为初始值
}
}else{ // 未被添加到开放列表
// 设置父节点为当前节点，计算G值和H值，并添加到开放列表中
setFatherNode(nx+px[i], ny+py[i], nx, ny);
value_G[ny+py[i]][nx+px[i]] = CalculationValueG(nx+px[i], ny+py[i]);
value_H[ny+py[i]][nx+px[i]] = CalculationValueH(nx+px[i], ny+py[i], tx, ty);
addToOpenList(nx+px[i], ny+py[i]);
}
}
// 从开放列表删除该节点
deleteFromOpenList(nx, ny);
// 添加到关闭列表
addToCloseList(nx, ny);
} // 搜索结束
// 读取路径
int[][] path = null;
if(sucess){
int[][] temp = new int[num_open][2];
int index = num_open-1;
int nx = tx;
int ny = ty;
while(nx!=sx || ny!=sy){
int node = FatherNode(nx, ny);
nx = node%10;
ny = node/10;
temp[index][0] = nx;
temp[index][1] = ny;
index--;
}
path = new int[num_open-index-1][2];
System.arraycopy(temp, index+1, path, 0, path.length);
}
release();
return path;
}
/**资源初始化*/
private void init() {
num_open = num_close = 0;
openList = new int[map.length*map[0].length]; // 开放列表
closeList = new int[map.length*map[0].length]; // 关闭列表
fatherNode = new int[map.length][map[0].length]; // 父节点列表
value_G = new int[map.length][map[0].length]; // G值表
value_H = new int[map.length][map[0].length]; // H值表
}
/**释放资源*/
private void release() {
openList = null;
closeList = null;
for(int i=0; i<fatherNode.length; i++){
fatherNode[i] = null;
}
fatherNode = null;
for(int i=0; i<value_G.length; i++){
value_G[i] = null;
}
value_G = null;
for(int i=0; i<value_H.length; i++){
value_H[i] = null;
}
value_H = null;
System.gc();
}
/**添加到开放列表*/
private int addToOpenList(int x, int y){
return (openList[num_open++] = y*10+x);
}
/**添加到关闭列表*/
private int addToCloseList(int x, int y){
return (closeList[num_close++] = y*10+x);
}
/**从开放列表中删除*/
private void deleteFromOpenList(int x, int y){
if(num_open<=0)
return;
int i;
for(i=0; i<num_open; i++){
if(openList[i]==y*10+x){
openList[i] = 0;
break;
}
}
for(; i<num_open-1; i++){
openList[i] = openList[i+1];
}
num_open--;
}
/**获取F值*/
private int ValueF(int x, int y){
return value_G[y][x]+value_H[y][x];
}
/**获取父节点*/
private int FatherNode(int x, int y){
return fatherNode[y][x];
}
private void setFatherNode(int x, int y, int fx, int fy){
fatherNode[y][x] = fy*10+fx;
}
/**是否已存在于开放列表*/
private boolean isInOpenList(int x, int y){
for(int i=0; i<num_open; i++){
if(openList[i]==y*10+x)
return true;
}
return false;
}
/**是否已存在于关闭列表*/
private boolean isInCloseList(int x, int y){
for(int i=0; i<num_close; i++){
if(closeList[i]==y*10+x)
return true;
}
return false;
}
/**计算G值*/
private int CalculationValueG(int x, int y){
int node = FatherNode(x, y);
int fx = node%10;
int fy = node/10;
for(int i=0; i<4; i++){
if(fx+px[4+i]==x && fy+py[4+i]==y)
return value_G[fy][fx] + 14;
}
return value_G[fy][fx] + 10;
}
/**计算H值*/
private int CalculationValueH(int x, int y, int tx, int ty){
return (Math.abs(y-ty)+Math.abs(x-tx))*10;
}
/**判断是否是障碍*/
private boolean isBlock(int x, int y){
if(x<0 || x>=map[0].length || y<0 || y>=map.length)
return true;
if(blocks==null)
return false;
for(int i=0; i<blocks.length; i++){
if(map[y][x]==blocks[i])
return true;
}
return false;
}
// 四周8个方位的位置偏移量
private static final byte[] px = {-1,1,0,0,-1,-1,1,1};
private static final byte[] py = {0,0,-1,1,-1,1,-1,1};
private byte[][] map; // 地图数据
private byte[] blocks; // 障碍ID
private int[] openList;// 开放列表
private int[] closeList; // 关闭列表
private int num_open, num_close; // 数量标记
private int[][] fatherNode; // 父节点列表
private int[][] value_G; // G值表
private int[][] value_H; // H值表
private boolean sucess;
}