Flash里的 A* Pathfinding -- 详细代码及说明

在家上网赚钱更容易

//code by 月光 2005.9.22
//地图长宽
var mapx = 40;
var mapy = 40;
var total = mapx * mapy;
//边界距离
var distancex = 30;
var distancey = 30;
//移动速度
var interval = 75;
//初始障碍物比率
var balk = 3;
var val;
var width = 0;
var height = 0;
//移动次数
var moves = 0;
//是否正在忙碌
var busy = false;
//是否正在移动
var moving = false;
//是否搜索成功
var finded = false;
//路径记录
var open = new Array();
//方向数组 => 右, 下, 左, 上
var ori = new Array([1, 0], [0, 1], [-1, 0], [0, -1]);
// ========================================
//重置
var reset = function () {
 clearInterval(val);
 for (var i in _root) {
  if (typeof _root[i] == "movieclip") {
   _root[i].removeMovieClip();
  }
 }
 txt.text = "";
 init();
};
btn_reset.onPress = reset;
// ========================================
//初始化
var init = function () {
 var i = 1;
 // 绘制地图
 while (i <= total) {
  var tmp = attachMovie("mc", "m" + i, i, {id:i, visited:false});
  tmp._x = (i - 1) % mapx * tmp._width + distancex;
  tmp._y = Math.floor((i - 1) / mapy) * tmp._height + distancey;
  if (random(balk) == 0) {
   tmp.gotoAndStop(2);
  }
  i++;
 }
 m1.gotoAndStop(1);
 width = m1._width;
 height = m1._height;
 // 主角初始位置
 attachMovie("player", "player", total + 10000, {_x:distancex, _y:distancey});
 player.onPress = function() {
  busy = true;
  txt.text = "请选择目标";
 };
 moving = false;
};
// ========================================
//点击地图后执行
btn.onPress = function() {
 if (!moving) {
  var i = 1;
  while (i <= total) {
   this._parent["m" + i].visited = false;
   i++;
  }
  var x = Math.ceil((_xmouse - distancex) / width);
  var y = Math.ceil((_ymouse - distancey) / height);
  var id = x + (y - 1) * mapy;
  //当前点击的MC
  var tmp = this._parent["m" + id];
  if (!busy) {
   if (tmp._currentframe == 1) {
    txt.text = "目标转换为障碍物";
    tmp.gotoAndStop(2);
   } else {
    txt.text = "目标转换为通道";
    tmp.gotoAndStop(1);
   }
  } else {
   if (tmp._currentframe == 2) {
    txt.text = "目标为障碍物,无法到达";
    busy = false;
   } else {
    findit(x, y);
   }
  }
 }
};
// ========================================
//寻路
var findit = function (x, y) {
 finded = false;
 open = new Array();
 var playerx = Math.ceil((player._x - distancex) / width) + 1;
 var playery = Math.ceil((player._y - distancey) / height) + 1;
 moves = 1;
 // 数组内元素为: X坐标, Y坐标, 距离原点长度, 上级位置
 open[1] = [x, y, moves, 1];
 for (i = 0; i < 4; i++) {
  // 邻格内移动
  if (x + ori[i][0] == playerx && y + ori[i][1] == playery) {
   movefunc();
   return;
  }
 }
 // 非邻格内移动
 var z = 1;
 var t = 1;
 while (open[z] != null) {
  for (i = 0; i < 4; i++) {
   var tmpx = open[z][0] + ori[i][0];
   var tmpy = open[z][1] + ori[i][1];
   if (tmpx > 0 && tmpy > 0 && tmpx <= 40 && tmpy <= 40) {
    var id = tmpx + (tmpy - 1) * mapy;
    var tmp = this["m" + id];
    // 当对象存在及非障碍物及未访问过时
    if (tmp != null && tmp._currentframe == 1 && !tmp.visited) {
     tmp.visited = true;
     open[++t] = [tmpx, tmpy, open[z][2] + 1, z];
     if (open[t][0] == playerx && open[t][1] == playery) {
      finded = true;
      moves = z;
      break;
     }
    }
   }
  }
  z++;
 }
 if (finded) {
  movefunc();
 } else {
  busy = false;
  moving = false;
  //debug
  trace(open.join(" => "));
  txt.text = "无法到达目标";
 }
};
// ========================================
//角色移动
var movefunc = function () {
 moving = true;
 txt.text = "找到目标,正在移动";
 val = setInterval(moveFunc, interval);
};
var moveFunc = function () {
 updateAfterEvent();
 moves = open[moves][3];
 player._x = (open[moves][0] - 1) * width + distancex;
 player._y = (open[moves][1] - 1) * height + distancey;
 if (moves == 1) {
  busy = moving = finded = false;
  txt.text = "已到达目标";
  clearInterval(val);
 }
};
// ========================================
init();
stop();

本帖参考自OReilly的AI for Game Developers这本书的第七章A* Pathfinding,推荐对游戏开发有兴趣的朋友们可以找来研究下.

 

关于A*算法,也叫A STAR,这里有篇国人翻译的文章:
http://blog.vckbase.com/panic/archive/2005/03/20/3778.html
英文原文地址:
http://www.gamedev.net/reference/articles/article2003.asp

原帖地址:
http://www.blueidea.com/bbs/newsdetail.asp?id=2376491