--------------代碼來(lái)源于網(wǎng)絡(luò)-----------------------

最近比較空閑，研究了一下手機(jī)游戲中的尋路算法

小地圖中，解決的方式就不說(shuō)了，怎么解決都差不多，假如地圖比較大，就要好好考慮了

gameloft的彩虹六號(hào)里面的尋路算法就很經(jīng)典，但據(jù)說(shuō)他們是發(fā)明了一種專利算法，具體的我就不知道了~但我估計(jì)應(yīng)該是在地圖里面設(shè)置了一些路點(diǎn)之類的標(biāo)志。。。。。

我今天貼的代碼完全是別人的代碼，我也沒改動(dòng)，也沒有測(cè)試過(guò)內(nèi)存占用，緊緊提供給大家一個(gè)大體思路，各位兄弟具體使用時(shí)肯定還需要修改的。尤其對(duì)于內(nèi)存資源比較緊張的手機(jī)來(lái)說(shuō)，A*算法的改進(jìn)絕對(duì)值得各位好好研究

相關(guān)資料：

A*尋路算法(For 初學(xué)者)

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