基于Binary Heap的A*算法

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

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

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

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