基于Binary Heap的A*算法

核心提示：--代码来源于网络---最近比较空闲，研究了一下手机游戏中的寻路算法小地图中，基于Binary Heap的A*算法，解决的方式就不说了，怎么解决都差不多，紧紧提供给大家一个大体思路，各位兄弟具体使用时肯定还需要修改的，假如地图比较大，就要好好考虑了gameloft的彩虹六号里面的寻路算法就很经典

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

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

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

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