我们继续上一篇，上次我们分析到world.init的map.init，接下来我们继续看地图初始化中的这句：
this.pfinder = buildFinder(this);
该方法对应的文件是require('pomelo-pathfinding').buildFinder，这又是一个独立的模块，实际上就是实现了一套A*寻路算法。
如果有不熟悉A*算法的朋友，看这一篇可能会比较困难，建议可以自己先去查一下资料，我这里也推荐一篇；
A*算法重要的公式：
F = G + H
G＝从起点A沿着已生成的路径到一个给定方格的移动开销。 H＝从给定方格到目的方格的估计移动开销。这种方式常叫做试探，有点困惑人吧。其实之所以叫做试探法是因为这只是一个猜测。在找到路径之前我们实际上并不知道实际的距离，因为任何东西都有可能出现在半路上（墙啊，水啊什么的）。A*算法过程要点大概是如下的：
1. 将开始节点放入开放列表(开始节点的F和G值都视为0);
2. 重复一下步骤: i. 在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点; ii. 把当前节点从开放列表删除, 加入到封闭列表; iii. 对当前节点相邻的每一个节点依次执行以下步骤: a. 如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点; b. 如果该相邻节点不在开放列表中,则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和F值; c. 如果该相邻节点在开放列表中, 则判断若经由当前节点当前节点到达该相邻节点的G值是否小于原来保存的G值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值. iv. 循环结束条件: 当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时应终止循环; 或者当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找到,此时也结束循环 3. 从终点节点开始沿父节点遍历, 并保存整个遍历到的节点坐标,遍历所得的节点就是最后得到的路径;在分析代码之前，先了解下tile的构成，之前就有提到过，tile就是构成地图的一个个正方形小切片它的大小是20*20,每一个tile包含6个属性：
1. tile.X和tile.Y : 代表tile在地图上的坐标
2. tile.processed： 标示该tile是否已经被计算过距离
3. tile.prev：记录到达该tile的前一个tile
4. tile.cost：从起点tile到达当前tile的最短距离
5. tile.heursitic : 从起点tile起，经过当前tile，到达终点tile的距离
buildFinder最终返回的是finder对象，finder对应的代码如下:
var finder = function (sx,sy,gx,gy) { if(map.getWeight(gx,gy) >= CAN_NOT_MOVE) { return null; } clearTileInfo(); var cmpHeuristic = function (t1,t2) { return t2.heuristic - t1.heuristic; } var queue = createPriorityQueue(cmpHeuristic); var found = false; var ft = getTileInfo(sx,sy); ft.cost = 0; ft.heuristic = 0; queue.enqueue(ft); while(0 < queue.length()) { var footTile = queue.dequeue(); var x = footTile.x; var y = footTile.y; if(x === gx && y === gy) { found = true; break; } if(footTile.processed) { continue; } footTile.processed = true; var processReachable = function (theX, theY, weight) { if(weight >= CAN_NOT_MOVE) { //??? return; } var neighbourTile = getTileInfo(theX, theY); if(neighbourTile.processed) { return; } var costFromSrc = footTile.cost + weight * distance(theX - x, theY - y); if(!neighbourTile.prev || (costFromSrc < neighbourTile.cost)) { neighbourTile.cost = costFromSrc; neighbourTile.prev = footTile; var distToGoal = distance(theX - gx, theY - gy); neighbourTile.heuristic = costFromSrc + distToGoal; queue.enqueue(neighbourTile); } } map.forAllReachable(x,y,processReachable); } if(!found) { return null; } var paths = new Array(); var goalTile = getTileInfo(gx,gy); var t = goalTile; while(t) { paths.push({x:t.x, y:t.y}); t = t.prev; } paths.reverse(); return {paths: paths, cost:goalTile.cost}; } finder传进来4个参数，起点的x,y坐标，终点的x,y坐标，首先是判断终点是否可以是障碍物，如果是则返回，然后是clearTileInfo();对应的代码如下：
var clearTileInfo = function () { tiles.forEach(function (row) { row.forEach(function(o) { if(!o) { return; } o.processed = false; o.prev = null; o.cost = 0; o.heuristic = 0; }); }) } 这个方法很简单，就是清空地图tile集合，给他们设置初始值，然后继续往下看finder的代码：
var cmpHeuristic = function (t1,t2) { return t2.heuristic - t1.heuristic; } var queue = createPriorityQueue(cmpHeuristic); 这里的createPriorityQueue(cmpHeuristic);就是前面介绍过的顺序队列，cmpHeuristic就是顺序算法。return t2.heuristic - t1.heuristic;即把经由后一个tile点，从起点到终点花费的距离减去前一个tile点的距离，在这个方法的返回值中实现了enqueue、dequeue、length这三个方法，具体的作用在稍后使用到时再说明。继续看finder接下来的代码：
var found = false; var ft = getTileInfo(sx,sy); ft.cost = 0; ft.heuristic = 0; queue.enqueue(ft);
这个就是前面提到的A*寻路的
1. 将开始节点放入开放列表(开始节点的F和G值都视为0);
首先是getTileInfo(sx,sy),作用就是取到起点的tile的信息，它的代码如下：
var getTileInfo = function (x,y) { assert("number" === typeof(x) && "number" === typeof(y)) var row = tiles[y]; if(!row) { row = new Array; tiles[y] = row; } var tileInfo = row[x]; if (!tileInfo) { tileInfo = { x: x, y: y, processed: false, prev: null, cost: 0, heuristic: 0 } row[x] = tileInfo; } return tileInfo; } 这一段代码很简单，就是先取得坐标所在的行,如果不存在，则初始化一行，然后再取得所在的格即tile，如果不存在，在初始化一个tile进行填充. tile包含的集合信息有：
{x: x, y: y, processed: false, prev: null, cost: 0, heuristic: 0}，
继续回到刚才的finder，接下来就是把cost和heuristic初始化为0, 在调用queue.enqueue(ft);这个方法就是前面createPriorityQueue是返回的对象包含的enqueue方法，我们来看代码：
obj.enqueue = function (e) { this.arr.push(e); var idx = this.arr.length - 1; var parentIdx = floor((idx - 1) / 2); while(0 <= parentIdx) { if(cmpPriority(this.arr[idx],this.arr[parentIdx]) <= 0) { break; } var tmp = this.arr[idx] this.arr[idx] = this.arr[parentIdx]; this.arr[parentIdx] = tmp; idx = parentIdx; parentIdx = floor((idx - 1) / 2); } } enqueue是队列入列的算法，目前我看的不是很明白，但是经过我的实际演算，它的作用就是把队列按照距离进行升序排列,哪位大侠看明白了这段算法介绍一下原理吧，谢谢！
接下来继续看finder：
while(0 < queue.length()) { var footTile = queue.dequeue(); var x = footTile.x; var y = footTile.y; if(x === gx && y === gy) { found = true; break; } if(footTile.processed) { continue; } footTile.processed = true; var processReachable = function (theX, theY, weight) { if(weight >= CAN_NOT_MOVE) { //??? return; } var neighbourTile = getTileInfo(theX, theY); if(neighbourTile.processed) { return; } var costFromSrc = footTile.cost + weight * distance(theX - x, theY - y); if(!neighbourTile.prev || (costFromSrc < neighbourTile.cost)) { neighbourTile.cost = costFromSrc; neighbourTile.prev = footTile; var distToGoal = distance(theX - gx, theY - gy); neighbourTile.heuristic = costFromSrc + distToGoal; queue.enqueue(neighbourTile); } } map.forAllReachable(x,y,processReachable); } 首先是把queue里第一个元素取出 footTile = queue.dequeue();
这个的作用就是A*寻路要点中的
i. 在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点;
ii. 把当前节点从开放列表删除, 加入到封闭列表;它的代码如下：
obj.dequeue = function () { if(this.arr.length <= 0) { return null; } var max = this.arr[0]; var b = this.arr[this.arr.length - 1]; var idx = 0; this.arr[idx] = b; while(true) { var leftChildIdx = idx * 2 + 1; var rightChildIdx = idx * 2 + 2; var targetPos = idx; if(leftChildIdx < this.arr.length && cmpPriority(this.arr[targetPos], this.arr[leftChildIdx]) < 0) { targetPos = leftChildIdx; } if(rightChildIdx < this.arr.length && cmpPriority(this.arr[targetPos], this.arr[rightChildIdx]) < 0) { targetPos = rightChildIdx; } if(targetPos === idx) { break; } var tmp = this.arr[idx]; this.arr[idx] = this.arr[targetPos]; this.arr[targetPos] = tmp; idx = targetPos; } this.arr.length -= 1; return max; }
这是队列的出列算法，同样没看懂，但是它能够保证每次把距离最短的点取出,然后是finder的接下来这一段：
if(x === gx && y === gy) { found = true; break; } if(footTile.processed) { continue; } footTile.processed = true; 这个的作用就是A*寻路要点中的
iv. 循环结束条件:
当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时应终止循环; 或者当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找到,此时也结束循环然后是finder的这句map.forAllReachable(x,y,processReachable);
Map.prototype.forAllReachable = function(x, y, processReachable) { var x1 = x - 1, x2 = x + 1; var y1 = y - 1, y2 = y + 1; x1 = x1<0?0:x1; y1 = y1<0?0:y1; x2 = x2>=this.rectW?(this.rectW-1):x2; y2 = y2>=this.rectH?(this.rectH-1):y2; if(y > 0) { processReachable(x, y - 1, this.weightMap[x][y - 1]); } if((y + 1) < this.rectH) { processReachable(x, y + 1, this.weightMap[x][y + 1]); } if(x > 0) { processReachable(x - 1, y, this.weightMap[x - 1][y]); } if((x + 1) < this.rectW) { processReachable(x + 1, y, this.weightMap[x + 1][y]); }}; 实际上它就是取地图上当前点的下上左右四个tile分别依次进行4次processReachable计算，processReachable就是A*算法的核心所在，
这个的作用就是A*寻路要点中的
iii. 对当前节点相邻的每一个节点依次执行以下步骤:
a. 如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点; b. 如果该相邻节点不在开放列表中,则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和F值; c. 如果该相邻节点在开放列表中, 则判断若经由当前节点当前节点到达该相邻节点的G值是否小于原来保存的G值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.代码如下：
var processReachable = function (theX, theY, weight) { if(weight >= CAN_NOT_MOVE) { //??? return; } var neighbourTile = getTileInfo(theX, theY); if(neighbourTile.processed) { return; } var costFromSrc = footTile.cost + weight * distance(theX - x, theY - y); if(!neighbourTile.prev || (costFromSrc < neighbourTile.cost)) { neighbourTile.cost = costFromSrc; neighbourTile.prev = footTile; var distToGoal = distance(theX - gx, theY - gy); neighbourTile.heuristic = costFromSrc + distToGoal; queue.enqueue(neighbourTile); } } 这里传进theX与theY，指的就是上下左右4个点中的某一个tile， 首先判断该tile是否障碍物，如果是则跳过，否则通过getTileInfo(theX, theY);取出该tile的信息，如果该tile是process过的，则也作为排除点跳过，同时接下来计算经过上一个tile到本tile的cost，算法为footTile.cost + weight * distance(theX - x, theY - y);如果结果小于之前已保存的距离，则把当前cost当做这个tile的cost，同时更新heuristic，然后再重新入列.
这一段不知道说清楚了没有，如果看不明白的同学先看下A*算法吧，看完了基本上就懂了，接下来我们看最后一段代码：
if(!found) { return null; } var paths = new Array(); var goalTile = getTileInfo(gx,gy); var t = goalTile; while(t) { paths.push({x:t.x, y:t.y}); t = t.prev; } paths.reverse(); return {paths: paths, cost:goalTile.cost}; 这个很简单，也是标准的A*算法的最后处理.
这个的作用就是A*寻路要点中的
3. 从终点节点开始沿父节点遍历, 并保存整个遍历到的节点坐标,遍历所得的节点就是最后得到的路径;
如果没有发现路径，结束，然后从目的地倒推，得到path的所有坐标，在paths.reverse();倒序，最后返回path点的集合，以及到达目的地的花销。
好了，这一篇就到这里，大家88