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;
}