A*算法实现

 

        在游戏编程中广泛使用了A*算法。 就比如红警里面你框一辆坦克然后在目的地上点一下鼠标，不管多远坦克都会自动跑到目标点上（前提是目标点是可以到达的畅通路径）。在这个过程中坦克起始位置和终点位置中间的路径已经由程序计算完成。而这个程序的算法我们称之为最优路径算法。

       是下面是最优算法A*原理的实现，当然只是原理算法的实现，只供学习和研究其效率一般，没有实现算法和数据结构的优化，负责的程序员应该进一步的优化它。 好了下面我们还是来看看如何实现吧。

地图中每一块都有3个属性
G = 移动代价。
H = 实际代价，离到终点的实际距离。
F = G+H
A* 就是寻找具有最小F值能到达终点的路径。
 
下面我们开始吧
先定义地图数据 0是可走1是不可行走
  int[][] map = {
      {
      0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, { 
      0, 1, 1, 1, 1, 0, 0, 1, 0, 0}, { 
      0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, { 
      0, 1, 0, 0, 1, 1, 1, 1, 1, 0}, { 
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
  };
 
需要维护两个列表一个是开放列表还有一个封闭列表
 Vector open = new Vector();       // 开放列表 
  Vector close = new Vector();      // 封闭列表
 
定义节点类
  class Node {
    int x;
    int y;
    int g;     // G = 移动代价，沿着到父块而生成路径移动的代价。 
    int h;     // H = 从格子中给定 的方块到最终目标 B点的评估移动代价。          
    int f;     //  估价
    Node father;
    Node(Node node, int sx, int sy, int ex, int ey) {
      if (node != null) {  // 新建子节点
        father = node;    // 设置父节点
        x = sx;            // 当前x
        y = sy;           // 当前y
        h = (getABS(sx - ex) + getABS(sy - ey))*10; // 实际代价 当前块移动到终点块的绝对距离。
        g = node.g + 10;                                         // 代价推算 当前块移动代价=父块移动代价+移动代价
        f = g + h;                                                   // 估价
      }
      else {                 // 根节点
        x = sx;
        y = sy;
        h = 0;
        g = 0;
        f = 9999;
      }
    }
  }
 
private int getABS(int v) {
    if (v < 0) {
      return -v;
    }
    return v;
  }

  // 开始寻路
  public void xunLu(int sx, int sy, int ex, int ey) {
    boolean flag = true;  // 是否存在于open list中
    int minIndex = 0;     // 具有最小F值对象的的open list下标
    int newX = 0;
    int newY = 0;

    /**
     * 1 添加开始方块到开放列表。
     *   初始化根接点,把根节点放入开放列表.
     */
    Node minNode = new Node(null, sx, sy, ex, ey);
    open.add(minNode);

    while (open.size() != 0) {
      /**
       *  2 查找开放列表中具有最小F值的方块。
       */
      minNode = ((Node)open.get(0));
      minIndex = 0;
      for (int i = 1; i < open.size(); i++) {
         if (minNode.f > ( (Node) open.get(i)).f) {
            minNode = ( (Node) open.get(i));
            minIndex = i;
         }
      }

      /**
       * 3 把最小F值的方块从开放列表中取出然后放入封闭列表。
       */
      if (minNode != null) {
          close.add(minNode);
          open.remove(minIndex);
      }
        /**
         *  4 如果目前找到的最小F值块是终点就返回。
         */
        if (minNode.x == ex && minNode.y == ey) {
          do {
            minNode = minNode.father;
          }
          while (get != null);
          return;
        }
        /**
         *  5 对最小F值块(即上面刚刚放入封闭列表里面) 的8个相邻方块的进行判断.
         *    将4或8个方向,可以走的放入开放列表内.
         */
        for (int i = 0; i < 4; i++) {
          flag = true;
          newX = minNode.x + t[i][0];
          newY = minNode.y + t[i][1];
          /**
           *5。1 地图是否越界 如果它不可行走，或者存在于封闭列表，忽略它。
           */
          if(newY < 0 || newY > 4 || newX < 0 || newX > 9) {
            continue;
          }
          if (map[newY][newX] == 0) {    // 判断是否是可以移动
            for (int k = 0; k < close.size(); k++) {  
              if ( (((Node) close.get(k)).x == newX) &&
                   (((Node) close.get(k)).y == newY) ) {
                flag = false;
                break;
              }
            }

            if(flag) {
              for(int ii = 0; ii < open.size(); ii++) {  
                if( ((Node)open.get(ii)).x == newX &&  ((Node)open.get(ii)).y == newY) {
                  open.remove(ii);
                  break;
                }
              }
              open.add(new Node(minNode, newX,newY, ex, ey));
            }
          }
        }
      }
    }