--------------代码来源于网络-----------------------

最近比较空闲，研究了一下手机游戏中的寻路算法

小地图中，解决的方式就不说了，怎么解决都差不多，如果地图比较大，就要好好考虑了

gameloft的彩虹六号里面的寻路算法就很经典，但据说他们是发明了一种专利算法，具体的我就不知道了~但我估计应该是在地图里面设置了一些路点之类的标志。。。。。

我今天贴的代码完全是别人的代码，我也没改动，也没有测试过内存占用，紧紧提供给大家一个大体思路，各位兄弟具体使用时肯定还需要修改的。尤其对于内存资源比较紧张的手机来说，a*算法的改进绝对值得各位好好研究

相关资料：

a*寻路算法(for 初学者)

在a*寻路中使用二*堆

enjoy:)

--------------------------source code----------------------------------------------

/**
* astar pathfinding algorithm
*/
public class astar {
private square[][] squares;

public static final byte wall = 0x1, blank = 0x0;

public static final byte wall_mask = (byte) 0xf;

public static final byte open_mask = (byte) 0x80;

public static final byte closed_mask = (byte) 0x40;

private byte[][] map;

private square lstart;

private square lend;

private static final byte orthogonal_cost = 1;

byte height;

byte width;

// binary heap
public square[] heaptree;

public int heapsize;

boolean first = true;

void updatemap(byte[][] mapmatrix) {
  if (map != null) {
   map = null;
   releasefind();
  } else {
   lstart = new square((byte) 0, (byte) 0, (byte) 0, (byte) 0);
   lend = new square((byte) 0, (byte) 0, (byte) 0, (byte) 0);

   heaptree = new square[height * width + 1];
   squares = new square[height][width];
  }
  map = mapmatrix;
}

public void releasefind() {
  int i, j;
  for (i = 0; i < height; i++) {
   for (j = 0; j < width; j++) {
    squares[i][j] = null;
   }
  }

  for (i = 0; i < heaptree.length; i++) {
   heaptree[i] = null;
  }
}

public square findpath(byte sy, byte sx, byte ey, byte ex, boolean canfly) {
  lstart.x = sx;
  lstart.y = sy;
  lend.x = ex;
  lend.y = ey;
  if (canfly) {
   square sqr, last;
   last = lstart;
   int sign;
   if (ex != sx) {
    sign = (ex - sx) / math.abs(ex - sx);
    for (byte i = (byte) (sx + sign); i != ex; i += sign) {
     sqr = new square(sy, i, (byte) 0, (byte) 0);
     sqr.parent = last;
     last = sqr;
    }
   }
   if (ey != sy) {
    sign = (ey - sy) / math.abs(ey - sy);
    for (byte i = (byte) (sy); i != ey; i += sign) {
     sqr = new square(i, ex, (byte) 0, (byte) 0);
     sqr.parent = last;
     last = sqr;
    }
   }
   lend.parent = last;
   return lend;
  }

  byte height = this.height;
  byte width = this.width;

  int i, j;
  for (i = 0; i < height; i++) {
   for (j = 0; j < width; j++) {
    map[i][j] &= wall_mask;
   }
  }
  heapsize = 0;

  openlistinsert(this.lstart.y, this.lstart.x, (byte) 0, null);
  square current = null;

  byte ty = 0, tx = 0, tg = 0, tmpg;

  while (heapsize != 0) {
   // 取出open表中第一个
   current = openlistremove();

   // 到达终点!
   if (current.y == this.lend.y && current.x == this.lend.x) {
    return current;
   }

   byte cy = current.y;
   byte cx = current.x;

   fl: for (i = 0; i < 4; i++) {
    switch (i) {
    case 0: // 上
     ty = (byte) (cy - 1);
     if (ty < 0)
      continue fl;
     tx = cx;
     tg = orthogonal_cost;
     break;
    case 1: // 左
     tx = (byte) (cx - 1);
     if (tx < 0)
      continue fl;
     ty = cy;
     tg = orthogonal_cost;
     break;
    case 2: // 右
     tx = (byte) (cx + 1);
     if (tx >= width)
      continue fl;
     ty = cy;
     tg = orthogonal_cost;
     break;
    case 3: // 下
     ty = (byte) (cy + 1);
     if (ty >= height)
      continue fl;
     tx = cx;
     tg = orthogonal_cost;
     break;
    default:
     break;
    }

    if ((this.map[ty][tx] & wall_mask) != wall
      && (this.map[ty][tx] & closed_mask) == 0) {
     if ((this.map[ty][tx] & open_mask) == 0) {
      openlistinsert(ty, tx, (byte) (current.g + tg), current);
     } else {
      tmpg = (byte) (current.g + tg);
      if (this.squares[ty][tx].g > tmpg) {

       this.squares[ty][tx].setg(tmpg);
       this.squares[ty][tx].parent = current;
       heappercolateup(squares[ty][tx].position);
      }
     }
    }
   }
   this.map[current.y][current.x] |= closed_mask;
  }
  return null;
}

private byte calculateh(byte y, byte x) {
  return (byte) (orthogonal_cost * (math.abs(this.lend.y - y) + math
    .abs(this.lend.x - x)));
}

public void openlistinsert(byte ty, byte tx, byte g, square parent) {
  this.squares[ty][tx] = new square(ty, tx, g, calculateh(ty, tx));
  this.squares[ty][tx].parent = parent;
  heapinsert(this.squares[ty][tx]);
  this.map[ty][tx] |= open_mask;
}

public square openlistremove() {
  square temp = heapdeletemin();
  this.map[temp.y][temp.x] |= open_mask;
  this.squares[temp.y][temp.x] = null;
  return temp;
}

// binary heap
public void heappercolateup(int position) {
  if (position <= this.heapsize) {
   while (position > 1) {
    if (this.heaptree[position].f < this.heaptree[position / 2].f) {
     square temp = this.heaptree[position];
     this.heaptree[position / 2].position = position;
     this.heaptree[position] = this.heaptree[position / 2];
     temp.position = position / 2;
     this.heaptree[position / 2] = temp;
     position = position / 2;
    } else
     return;
   }
  }
}

public boolean heapinsert(square element) {
  if (this.heapsize == heaptree.length - 1 || element == null) {
   return false;
  }

  this.heapsize++;
  int hole = this.heapsize;

  while (hole > 1 && element.f < this.heaptree[hole / 2].f) {
   this.heaptree[hole / 2].position = hole;
   this.heaptree[hole] = this.heaptree[hole / 2];
   hole = hole / 2;
  }

  this.heaptree[hole] = element;
  this.heaptree[hole].position = hole;

  return true;
}

public square heapdeletemin() {
  if (this.heapsize == 0) {
   return null;
  }

  square smallest = this.heaptree[1];
  this.heaptree[this.heapsize].position = 1;
  this.heaptree[1] = this.heaptree[this.heapsize];
  this.heaptree[this.heapsize] = null;
  this.heapsize--;

  int current = 1;
  int child;
  while (2 * current <= this.heapsize) {
   child = 2 * current;

   if (child != this.heapsize
     && this.heaptree[child].f > this.heaptree[child + 1].f) {
    child++;
   }

   if (this.heaptree[current].f > this.heaptree[child].f) {
    square temp = this.heaptree[current];
    this.heaptree[child].position = current;
    this.heaptree[current] = this.heaptree[child];
    temp.position = child;
    this.heaptree[child] = temp;
   } else {
    break;
   }
   current = child;
  }

  return smallest;
}

}

class square {
public byte f;

public byte g;

public byte h;

public int position; // heap position

public byte y;

public byte x;

public square parent;

public square(byte y, byte x, byte g, byte h) {
  this.y = y;
  this.x = x;

  if (!(g == 0 && h == 0)) {
   this.g = g;
   this.h = h;
   this.f = (byte) (this.g + this.h);
  }
}

public void setg(byte g) {
  this.g = g;
  this.f = (byte) (this.g + this.h);
}
}