Billows's weblog

    在之前的广度优先算法上加了对每个节点的估价函数变成了A*,有兴趣的可以看看代码,没写注释,有不懂的联系我,呵呵。

    不知道怎么回事,5d居然不能显示上传的swf了,演示地址http://blog.5d.cn/user10/Billows/upload/2006-010/20061027162236094.swf这样吧

/**
 * @author Billow
 */
class AStar {
 private var pathTime:Number;
 private var path:Object;
 private var root:MovieClip;
 private var openA:Array;
 private var closeA:Array;
 private var mapArray:Array;
 private var pathArray:Array;
 private var colID:Number = 50;
 private var rowID:Number = 50;
 private var startColID:Number;
 private var startRowID:Number;
 private var isPathFind:Boolean = false;
 private var endRowID, endColID:Number;
 //private var nodeArray:Array;
 private var indexNum:Number = 0;
 private var preNum:Number = 0;
 //private var blockArray:Array;
 public function AStar(root:MovieClip) {
  //trace(root);
  init(root);
  attachTile();
  //attachBlock();
 }
 private function init(root:MovieClip):Void {
  this.root = root;
  startRowID = 5;
  startColID = 5;
  this.mapArray = new Array();
  //this.pathArray = new Array();
 }
 public function attachTile():Void {
  //trace("attachTile");
  var self = this;
  for (var i:Number = 0; i<rowID; i++) {
   mapArray[i] = new Array();
   for (var j:Number = 0; j<colID; j++) {
    var depth:Number = i*colID+j;
    var tile_mc = root.attachMovie("mc_tile", "mc_tile"+depth, depth);
    tile_mc._x = j*tile_mc._width;
    tile_mc._y = i*tile_mc._height;
    //trace(tile_mc);
    var type:String;
    var randomNum = Math.floor(Math.random()*3);
    if (randomNum == 0) {
     //mapArray[i][j].graphic.gotoAndStop(4);
     type = "block";
    } else if (randomNum>0) {
     type = "common";
     //mapArray[i][j].graphic.gotoAndStop(3);
    }
    if (i == startColID && j == startRowID) {
     //mapArray[i][j].graphic.gotoAndStop(2);
     type = "start";
    }
    mapArray[i][j] = new Tile(this, tile_mc, i, j, false, type);
   }
  }
 }
 public function onPressHandle(pressRowID:Number, pressColID:Number):Void {
  //trace("the start point is:"+startRowID+","+startColID);
  //trace("the end point is:"+pressRowID+","+pressColID);
  //trace("mapArray[pressRowID][pressRowID].type="+mapArray[pressRowID][pressColID].type);
  if (mapArray[pressRowID][pressColID].type != "common") {
   //trace("can't press");
   return;
  } else {
   //this.endRowID = pressRowID;
   //this.endColID = pressColID;
   initMapData();
   //searchPath(startRowID, startColID, pressRowID, pressColID);
   findPath(startRowID, startColID, pressRowID, pressColID);
   //pushPathArray(pressRowID, pressColID);
   attachPath();
  }
 }
 private function initMapData():Void {
  resetAllIsChecked();
  preNum = 0;
  indexNum = 0;
  closeA.splice(0);
  pathArray.splice(0);
 }
 private function attachPath():Void {
  for (var i:Number = 0; i<pathArray.length; i++) {
   var rowNum = pathArray[i].x;
   var colNum = pathArray[i].y;
   //trace("x,y="+rowNum+","+colNum);
   mapArray[rowNum][colNum].graphic.gotoAndStop("move");
  }
 }
 private function resetAllIsChecked():Void {
  for (var i:Number = 0; i<rowID; i++) {
   for (var j:Number = 0; j<colID; j++) {
    mapArray[i][j].setIsChecked(false);
    mapArray[i][j].graphic.gotoAndStop(mapArray[i][j].type);
   }
  }
 }
 private function pushPathArray(ex, ey:Number) {
  pathArray.push({x:ex, y:ey});
  var curIndexNum:Number = closeA[closeA.length-1].preNum;
  while (curIndexNum>0) {
   pathArray.push({x:closeA[curIndexNum-1].sx, y:closeA[curIndexNum-1].sy});
   curIndexNum = closeA[curIndexNum-1].preNum;
  }
 }
 function make_path(ob) {
  // create path array
  pathArray = new Array();
  // loop until no more parents
  while (ob.parentx != null) {
   // add the x and y
   //pathArray[pathArray.length] = ob.x;
   //pathArray[pathArray.length] = ob.y;
   pathArray.push({x:ob.x, y:ob.y});
   // mark the tile
   //game.clip["t_"+ob.y+"_"+ob.x].mark.gotoAndStop(2);
   // make its parent new object
   ob = path["node_"+ob.parenty+"_"+ob.parentx];
  }
  // show time it took to find path
  trace(getTimer()-pathTime+" ms");
 }
 function findPath(startx, starty, targetx, targety:Number) {
  // start timer
  pathTime = getTimer();
  // make new path object
  path = {};
  // make new array for unchecked tiles
  path.Unchecked_Neighbours = [];
  // not done yet
  path.done = false;
  // initialize
  path.name = "node_"+starty+"_"+startx;
  // create first node
  var cost = Math.abs(startx-targetx)+Math.abs(starty-targety);
  path[path.name] = {x:startx, y:starty, visited:true, parentx:null, parenty:null, cost:cost};
  // add node to array
  path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
  // loop
  while (path.Unchecked_Neighbours.length>0) {
   // get the next node
   var N = path.Unchecked_Neighbours.shift();
   // we've finished
   if (N.x == targetx and N.y == targety) {
    // done
    make_path(N);
    path.done = true;
    break;
   } else {
    N.visited = true;
    // right neighbour
    addNode(N, N.x+1, N.y, targetx, targety);
    // left neighbour
    addNode(N, N.x-1, N.y, targetx, targety);
    // up neighbour
    addNode(N, N.x, N.y+1, targetx, targety);
    // down neighbour
    addNode(N, N.x, N.y-1, targetx, targety);
    // rightUp neighbour
    addNode(N, N.x+1, N.y-1, targetx, targety);
    // leftUp neighbour
    addNode(N, N.x-1, N.y-1, targetx, targety);
    // rightDown neighbour
    addNode(N, N.x+1, N.y+1, targetx, targety);
    // leftDown neighbour
    addNode(N, N.x-1, N.y+1, targetx, targety);
    
   }
  }
  // remove path object
  delete path;
  // check if path was found
  if (path.done) {
   // we reached the goal
   return true;
  } else {
   // we couldn't get there;
   return false;
  }
 }
 function addNode(ob, x, y, targetx, targety) {
  // name of the new node
  path.name = "node_"+y+"_"+x;
  // add to the unchecked neighbours, if its walkable
  //if (game["t_"+y+"_"+x].walkable) {
  if (mapArray[x][y].type == "common") {
   // find estimated cost to the target
   var cost = Math.abs(x-targetx)+Math.abs(y-targety);
   // and if its not visited yet
   if (path[path.name].cost>cost || path[path.name].cost == undefined) {
    // make new node
    path[path.name] = {x:x, y:y, visited:false, parentx:ob.x, parenty:ob.y, cost:cost};
    // add to the array
    for (var i = 0; i<path.Unchecked_Neighbours.length; i++) {
     if (cost<path.Unchecked_Neighbours[i].cost) {
      path.Unchecked_Neighbours.splice(i, 0, path[path.name]);
      break;
     }
    }
    // didnt add it yet, too much cost, add to the end
    if (i>=path.Unchecked_Neighbours.length) {
     path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
    }
   }
  }
 }
 public static function main(root:MovieClip) {
  new AStar(root);
 }
}