AS3的A寻路代码，了解一下

地形数据不属于A*寻路的范围，这里定义一个 IMapTileModel 接口，由其它（模型）类来实现地图通路的判断。其它比如寻路超时的判断这里也不介绍，具体参考 AStar类及其测试代码。这里只介绍三部分主要内容：

* 数据存储
* 寻路过程
* 列表排序

数据存储
首先看看三个关键变量： 复制内容到剪贴板
代码:
private var m_openList : Array; //开放列表，存放节点ID
private var m_openCount : int; //当前开放列表中节点数量
private var m_openId : int; //节点加入开放列表时分配的唯一ID(从0开始)开放列表 m_openList 是个二叉堆（一维数组），F值最小的节点始终排在最前。为加快排序，开放列表中只存放节点ID ，其它数据放在各自的一维数组中： 复制内容到剪贴板
代码:
private var m_xList : Array; //节点x坐标
private var m_yList : Array; //节点y坐标
private var m_pathScoreList : Array; //节点路径评分F值
private var m_movementCostList : Array; //(从起点移动到)节点的移动耗费G值
private var m_fatherList : Array; //节点的父节点(ID)这些数据列表都以节点ID为索引顺序存储。看看代码如何工作： 复制内容到剪贴板
代码:
//每次取出开放列表最前面的ID
currId = this.m_openList[0];
//读取当前节点坐标
currNoteX = this.m_xList[currId];
currNoteY = this.m_yList[currId];还有一个很关键的变量：
private var m_noteMap : Array; //节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID

使用 m_noteMap 可以方便的存取任何位置节点的开启关闭状态，并可取其ID进而存取其它数据。m_noteMap 是个三维数组，第一维y坐标（第几行），第二维x坐标（第几列），第三维节点状态和ID。判断点(p_x, p_y)是否在开启列表中： 复制内容到剪贴板
代码:
return this.m_noteMap[p_y][p_x][NOTE_OPEN];寻路过程
AStar类 寻路的方法是 find() : 复制内容到剪贴板
代码:
/**
* 开始寻路
* @param p_startX        起点X坐标
* @param p_startY        起点Y坐标
* @param p_endX        终点X坐标
* @param p_endY        终点Y坐标
* @return                 找到的路径(二维数组 : [p_startX, p_startY], ... , [p_endX, p_endY])
*/   
public function find(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : Array{/* 寻路 */}注意这里返回数据的形式：从起点到终点的节点数组，其中每个节点为一维数组[x, y]的形式。为了加快速度，类里没有使用Object或是Point，节点坐标全部以数组形式存储。如节点note的x坐标为note[0],y坐标为note[1]。
下面开始寻路，第一步将起点添加到开启列表： 复制内容到剪贴板
代码:
this.openNote(p_startX, p_startY, 0, 0, 0);openNote() 方法将节点加入开放列表的同时分配一个唯一的ID、按此ID存储数据、对开启列表排序。接下来是寻路过程： 复制内容到剪贴板
代码:
while (this.m_openCount > 0)
{
//每次取出开放列表最前面的ID
currId = this.m_openList[0];
//将编码为此ID的元素列入关闭列表
this.closeNote(currId);
//如果终点被放入关闭列表寻路结束，返回路径
if (currNoteX == p_endX && currNoteY == p_endY)
       return this.getPath(p_startX, p_startY, currId);
//...每轮寻路过程
}
//开放列表已空，找不到路径
return null;每轮的寻路： 复制内容到剪贴板
代码:
//获取周围节点，排除不可通过和已在关闭列表中的
aroundNotes = this.getArounds(currNoteX, currNoteY);
//对于周围每个节点
for each (var note : Array in aroundNotes)
{
//计算F和G值
cost = this.m_movementCostList[currId] + (note[0] == currNoteX || note[1] == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL;
score = cost + (Math.abs(p_endX - note[0]) + Math.abs(p_endY - note[1])) * COST_STRAIGHT;
if (this.isOpen(note[0], note[1])) //如果节点已在开启列表中
{
       //测试节点的ID
checkingId = this.m_noteMap[note[1]][note[0]][NOTE_ID];
//如果新的G值比节点原来的G值小,修改F,G值，换父节点
if(cost < this.m_movementCostList[checkingId])
{
       this.m_movementCostList[checkingId] = cost;
       this.m_pathScoreList[checkingId] = score;
       this.m_fatherList[checkingId] = currId;
       //对开启列表重新排序
       this.aheadNote(this.getIndex(checkingId));
}
} else //如果节点不在开放列表中
{
//将节点放入开放列表
this.openNote(note[0], note[1], score, cost, currId);
}
}从终点开始依次沿父节点回到到起点，返回找到的路径： 复制内容到剪贴板
代码:
/**
* 获取路径
* @param p_startX 起始点X坐标
* @param p_startY 起始点Y坐标
* @param p_id        终点的ID
* @return          路径坐标数组
*/   
private function getPath(p_startX : int, p_startY : int, p_id: int) : Array
{
var arr : Array = [];
var noteX : int = this.m_xList[p_id];
var noteY : int = this.m_yList[p_id];
while (noteX != p_startX || noteY != p_startY)
{
arr.unshift([noteX, noteY]);
p_id = this.m_fatherList[p_id];
noteX = this.m_xList[p_id];
noteY = this.m_yList[p_id];
}
arr.unshift([p_startX, p_startY]);
this.destroyLists();
return arr;
}列表排序
这部分看代码和注释就可以了，不多说： 复制内容到剪贴板
代码:
/** 将(新加入开放别表或修改了路径评分的)节点向前移动 */
private function aheadNote(p_index : int) : void
{
var father : int;
var change : int;
//如果节点不在列表最前
while(p_index > 1)
{
//父节点的位置
father = Math.floor(p_index ／ 2);
//如果该节点的F值小于父节点的F值则和父节点交换
if (this.getScore(p_index) < this.getScore(father))
{
       change = this.m_openList[p_index - 1];
       this.m_openList[p_index - 1] = this.m_openList[father - 1];
       this.m_openList[father - 1] = change;
       p_index = father;
} else
{
       break;
}
}
}
/** 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动 */
private function backNote() : void
{
//尾部的节点被移到最前面
var checkIndex : int = 1;
var tmp : int;
var change : int;
while(true)
{
tmp = checkIndex;
//如果有子节点
if (2 * tmp <= this.m_openCount)
{
       //如果子节点的F值更小
       if(this.getScore(checkIndex) > this.getScore(2 * tmp))
       {
       //记节点的新位置为子节点位置
       checkIndex = 2 * tmp;
       }
       //如果有两个子节点
       if (2 * tmp + 1 <= this.m_openCount)
       {
       //如果第二个子节点F值更小
       if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
       {
         //更新节点新位置为第二个子节点位置
         checkIndex = 2 * tmp + 1;
       }
       }
}
//如果节点位置没有更新结束排序
if (tmp == checkIndex)
{
       break;
}
//反之和新位置交换，继续和新位置的子节点比较F值
else
{
       change = this.m_openList[tmp - 1];
       this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
       this.m_openList[checkIndex - 1] = change;
}
}
}其中 getScore() 方法： 复制内容到剪贴板
代码:
/**
* 获取某节点的路径评分F值
* @param p_index 节点在开启列表中的索引(从1开始)
*/   
private function getScore(p_index : int) : int
{
//开启列表索引从1开始，ID从0开始，数组索引从0开始
return this.m_pathScoreList[this.m_openList[p_index - 1]];
}

 

 

 

 

 

 

 

//别人写得很细节

//我的简单实现方法

 

 

1.生成地图表

 

2.循环检查角色每一步,并作出每一步的优先级别，再分别检查地图表是否可行.

 

附代码

 

   var direct:String="cc";
   //角色的方向
   if(gx<ox){lcr="l";}else if(gx==ox){lcr="c";}else{lcr="r";}
   if(gy<oy){tcd="t";}else if(gy==oy){tcd="c";}else{tcd="d";}
   direct=lcr+""+tcd
   //trace(direct)
   //移動優先級
   switch(direct){
    case "lt" : rl=[[-1,-1],[-1,0],[0,-1],[-1,1],[1,-1],[1,0],[0,1],[1,1]]; break;
    case "lc" : rl=[[-1,0],[-1,-1],[-1,1],[0,-1],[0,1],[1,-1],[1,1],[1,0]]; break;
    case "ld" : rl=[[-1,1],[-1,0],[0,1],[-1,-1],[1,1],[0,-1],[1,0],[1,-1]]; break;
    case "ct" : rl=[[0,-1],[-1,-1],[1,-1],[-1,0],[1,0],[-1,1],[1,1],[0,1]]; break;
    case "cc" : rl=[]; break;
    case "cd" : rl=[[0,1],[-1,1],[1,1],[-1,0],[1,0],[-1,-1],[1,-1],[0,-1]]; break;
    case "rt" : rl=[[1,-1],[0,-1],[1,0],[-1,-1],[1,1],[-1,0],[0,1],[-1,1]]; break;
    case "rc" : rl=[[1,0],[1,-1],[1,1],[0,-1],[0,1],[-1,-1],[-1,1],[-1,0]]; break;
    case "rd" : rl=[[1,1],[1,0],[0,1],[1,-1],[-1,1],[0,-1],[-1,0],[-1,-1]]; break;
   }

 

   if(trole.direct!=direct){
    trole.direct=direct
    trole.getChildAt(1).gotoAndStop("run_"+direct)
   }
   if(rl.length==0){
    //完成了
    trole.getChildAt(1).gotoAndStop(trole.direct)
    //nowmp.cb(nowmp.tid,nowmp.name)  //<<<<  nowmp.name
    return;
   }
   //計算下一步移動的XY,遇到block就下一个
   for(var i=0;i<rl.length;i++){
    rnx=rox-rl[i][0]
    rny=roy-rl[i][1]
    if(typeof main.m_mapb.block["x"+rnx+"y"+rny]=="undefined"){
     break;
    }
   }
   trole.x=rnx*10
   trole.y=rny*10