如何使用AI(人工智能)计算路径

XML.prototype.ignoreWhite = true;
myXML = new XML();
myXML.load("map.xml");
myXML.onLoad = function(success) {
   if (success) {
      myMap = new Array();
      var x = myXML.firstChild.childNodes;
      for (var i = 0; i<x.length; i++) {
         var myString = x[i].firstChild.nodeValue;
         var temp = new Array();
         for(var j=0; j<myString.length; j++) {
            temp.push(int(myString.charAt(j)));    //把XML文件中的記錄轉換成數字
         }
         myMap.push(temp);
      }
      delete myXML;          //取得所有資料後刪除xml, 以減少記憶體佔用
      mapping();       //開始做地圖
   }
};   

function mapping() {
   var width = 28.2;          //每格位置的寬度
   var height = 10.2;       //每格位置的高度
   var dx = 0;
   var dy = 0;
   _global.startPosition = new Array(8,5);          //物件的定位
   for(var i=0; i<myMap.length; i++) {
      for(var j=0; j<myMap[i].length; j++) {
         var mc = _root.attachMovie("box", "box"+i+j, i*myMap.length+j);          //使用attachMovie把上面所做的MC排列
         if (myMap[i][j] == 1) {          //如果數組當中的值是1就代表是阻擋物件
            mc.gotoAndStop(2);
         }
         if (myMap[i][j] == 0) {          //可行走的部份
            mc.onRollOver = function() {       //鼠標移到這個可行走的方塊就取得此方塊的位置
               this.x = this._name.substr(3, 1);
               this.y = this._name.substr(4, 1);
            };
            mc.onRelease = function() {
               validate(this.x, this.y);          //當鼠標點下的時候開始做AI方面的計算
            };
         }
         mc._x = 250+dx;
         mc._y = 50+dy;
         dx = dx+width;
         dy = dy+height;
      }
      dx = -((i+1)*(width-7));
      dy = (i+1)*21;
      j = 0;
   }
   myMap[startPosition[0]][startPosition[1]] = 0;
   _root[("box"+startPosition[0])+startPosition[1]].gotoAndStop(3);       //物件
}   

function validate(r, c) {
   newpath = new PathFinder(myMap);    //使用類來定義
   newpath.finalPosition = [r, c];       //最終位置, 就是鼠標點下的座標位置
   newpath.startPosition = startPosition.slice();       //取得物件一開始的座標
   _global.finalPosition = [r, c];          //定義一個全域變量
   if ((newpath.startPosition[0] != newpath.finalPosition[0]) || (newpath.startPosition[1] != newpath.finalPosition[1])) {          //檢察物件開始的位置是不是就是最終的位置, 不是就開始計算
      newpath.init();       //路徑定義
      newpath.findPath();          //**找出最短路徑的計算...
   }
};

function PathFinder(myArray) {             //定義4組數組來記錄路徑的座標位置
   this.myMap = myArray;
   this.finalPosition = new Array();
   this.startPosition = new Array();
   this.openList = new Array();
   this.closedList = new Array();
};

PathFinder.prototype.init = function() {          //使用node來記錄位置,步數和距離等
   var startNode = new structNode(this.startPosition, 0, 0, 0);
   this.openList.push(startNode);       //把node儲存在數組內
};

PathFinder.prototype.findPath = function() {       //**重要部份
   while (this.openList.length>0) {
      var max = 1000;
      var lastOne = -1;
      var a = 0;
      while (a<this.openList.length) {          //取得最後一組openList數組中的node
         if (this.openList[a].f<max) {
            max = this.openList[a].f;       //步數
            lastOne = a;
         }
         a++;
      }
      var node = this.openList.splice(lastOne, 1);
      node = node[0];
      if (node.pos_str == this.finalPosition.toString()) {       //如果數組的最後一組是最終座標就執行
         this.closedList.push(node);
         var cur = this.closedList[this.closedList.length-1];
         startPosition = cur.pos;
         _root[("box"+this.startPosition[0])+this.startPosition[1]].gotoAndStop(1);    //把原本起點的物件換成普通的地圖
         _root[("box"+this.finalPosition[0])+this.finalPosition[1]].gotoAndStop(3);
         while (cur.parent != undefined) {
            _root[("box"+cur.pos[0])+cur.pos[1]].mask.gotoAndPlay(2);       //我例子中小球
            cur = cur.parent;
         }
         return (undefined);
      }
      var successors = this.getDirection(node.pos);       //取得目前位置可供行走的座標位置
      var a = 0;
      while (a<successors.length) {       //返回的長度最大為4, 即上下左右都沒有阻擋物
         var _skip = false;
         var struct = new structNode(successors[a]);    //同上...   
         struct.parent = node;

       //這裡會依照返回的數組座標判斷出最短的距離(根據步數)
         struct.g = node.g+this.getDistance(struct.pos, node.pos);
         struct.h = this.getDistance(struct.pos, this.finalPosition);
         struct.f = struct.g+struct.h;

         for (var b in this.openList) {         檢察下一步數組的座標是不是和目前相同
            if ((this.openList[b].pos_str == struct.pos_str) && (this.openList[b].f<struct.f)) {
               _skip = true;
               break;
            }
         }
         
         for (var b in this.closedList) {
            if ((this.closedList[b].pos_str == struct.pos_str) && (this.closedList[b].f<struct.f)) {
               _skip = true;
               break;
            }
         }
         
         if (_skip == false) {            
            for (var c in this.openList) {
               if (this.openList[c].pos_str == struct.pos_str) {
                  this.openList.splice(c, 1);
               }
            }
            for (var c in this.closedList) {
               if (this.closedList[c].pos_str == struct.pos_str) {
                  this.closedList.splice(c, 1);
               }
            }
            this.openList.push(struct);       //把下一步最接近終點的座標儲存在openList數組
         }
         a++;
      }
      this.closedList.push(node);
   }
};

PathFinder.prototype.getDirection = function(pos) {
   var r = Number(pos[0]);       //pos是目前座標
   var c = Number(pos[1]);
   var ret = new Array();

    //判斷上下左右方向
   if (this.myMap[r-1][c] == 0) {            
      ret.push([r-1, c]);
   }
   if (this.myMap[r][c+1] == 0) {
      ret.push([r, c+1]);
   }
   if (this.myMap[r+1][c] == 0) {
      ret.push([r+1, c]);
   }
   if (this.myMap[r][c-1] == 0) {
      ret.push([r, c-1]);
   }
   return (ret);
};

PathFinder.prototype.getDistance = function(pos1, pos2) {      
   var d1 = Math.abs(pos2[0]-pos1[0]);
   var d2 = Math.abs(pos2[1]-pos1[1]);
   return (d1+d2);
};

          function structNode(pos, f, g, h, parent) {
                      this.pos = pos.slice();
                      this.f = f;
                      this.g = g;
                      this.h = h;
                      this.parent = parent;
                      this.pos_str = this.pos.toString();
          }

   

                structNode.prototype.toString = function () {
                      return ((((((("[" + this.pos_str) + "], f=") + this.f) + ", g=") + this.g) + ", h=") + this.h);
          };