首先来看看完成后的效果：
其中灰色代表路障，绿色是起点和移动路径，红色代表终点
为了继续学习，需要明白几个概念。
曼哈顿距离的定义是，两个物体南北方向的距离与东西方向的距离之和。看起来就好像是直角三角形的两条边之和。
用代码表示出来就是：
/** * 计算两点间的曼哈顿距离 * @param goalNode {Object} 终点坐标 * @param startNode {Object} 起点坐标 * @returns {number} 两点间的曼哈顿距离 */ function Manhattan(goalNode,startNode) { return Math.abs(goalNode.x - startNode.x) + Math.abs(goalNode.y - startNode.y); }
G：从起点开始，沿着计算出的可能路径，移动到该路径上的移动消耗。
H：计算出的可能路径到终点的移动预估消耗。
F：G与H之和。
以下图来说明：
起点S周围有四个可选路径a、b、c、d(为简单起见，不考虑对角线也可行走的情况)，先来看路径a。
从起点S到达a的移动耗费是1格，故G=1。而从a到达终点G的移动耗费估算是5格，故H=5。F是G与H的值相加，为6。
经过观察，a、b、c三个路径的F值是一样的。而d路径的F值为4。可见F值越小，到达终点的花费越少，因此应该选择d路径作为下一步。
到达d路径后，重复前面的过程，搜索周围的路径，找到F值最小的作为下一步，同时将这个路径作为新的起始点。因为接下来每个路径的F值
都是参照这个新起始点来计算的。
由上图可知，S通往G的最佳路径是d、e、f。
但是还有一种情况，比如下图(灰色表示路障，无法通行)：
e和f的F值是一样的，这时候选择哪个呢？其实都可以，一般选择最后一个被计算出来的路径即可。
上述方法虽然可行，但是如果不加以限制，会造成一些不良后果。当从起点S到达新路径d时，d仍需要对周围的路径进行探索，起点S也将包含其中，很显然这是不必要而且浪费的。对此，我们需要维护两个列表，一个称为路径开启列表，一个称为路径关闭列表。
var open = []; //开启列表 var close = []; //关闭列表
open列表的职责是探索周围路径时，将可通行的路径(无路障的路径)加入列表中；
close列表则负责将各个新起点加入其中(相应的这些新起点也要从open列表中移除)，下一次执行路径探索时，如果该路径存在这个列表中，则忽略它。
当终点G被包含在close列表中时，搜索结束。
需要注意的是，为每个新起点标记它的父结点，即它是从哪里过来的(比如d路径的父结点就是S，e的父结点是d)，这样在到达终点G时，就能够根据它的父结点
一级一级地返回，从而找到这条“通路”的所有坐标，有点像链表这种数据结构。
完整代码：
html部分
<!doctype html> <html lang="en"> <head> <meta charset="UTF-8"> <title>a-star</title> <style> body{ margin: 0; font-size:12px; } table{border-collapse: collapse; width: 100%; table-layout: fixed} table th,table td{border:1px solid #000} #t{ width: 831px; } #t td{ width: 30px; height: 30px; text-align: center; } .start{background-color: #00fc5f} .block{background-color:#cacaca} .goal{background-color: #ff2211} .visited{background-color: #009921;} </style> <script src="../jquery-2.1.3.js"></script> </head> <body> <input id="start" type="button" value="开始寻路"/> <script src="a-star.js"></script> <script> $(‘#start‘).bind(‘click‘,function() { move(start,end); }); </script> </body> </html>
js部分
1 var open = [], //开启列表 2 close = [], //关闭列表 3 start = {}, //起点坐标 4 end = {}; //终点坐标 5 var d = document; 6 7 /** 8 * 检查待测坐标是否在坐标集合内 9 * @param toBeCheckNode {Object} 待检查坐标 {x,y} 10 * @param sourceNode {Array} 坐标集合 11 * @returns {boolean} 待测坐标是否在坐标集合内 12 */ 13 function isNodeExists(toBeCheckNode,sourceNode) { 14 for(var i in sourceNode) { 15 if (sourceNode.hasOwnProperty(i)) { 16 if (parseInt(toBeCheckNode.x) === sourceNode[i].x && parseInt(toBeCheckNode.y) === sourceNode[i].y) return true; 17 } 18 } 19 return false; 20 } 21 22 /** 23 * 计算两点间的曼哈顿距离 24 * @param goalNode {Object} 终点坐标 25 * @param startNode {Object} 起点坐标 26 * @returns {number} 两点间的曼哈顿距离 27 */ 28 function Manhattan(goalNode,startNode) { 29 return Math.abs(goalNode.x - startNode.x) + Math.abs(goalNode.y - startNode.y); 30 } 31 32 /** 33 * 选择最佳路径作为新起始点 34 * @param openArray {Array} 开启列表 35 * @returns {Object} 返回新起始点 36 */ 37 function selectNewStart(openArray) { 38 var minNode = openArray[0],i; 39 for(i = 0,len = openArray.length - 1; i < len; i++) { 40 if(minNode.F >= openArray[i+1].F) { 41 minNode = openArray[i+1]; 42 } 43 } 44 start = minNode; 45 //将新开始点加入关闭列表 46 close.push(start); 47 48 //将新开始点从开启列表中移除 49 for(i = 0; i < openArray.length; i++) { 50 if(minNode.x === openArray[i].x && minNode.y === openArray[i].y) { 51 openArray.splice(i,1); 52 break; 53 } 54 } 55 return start; 56 } 57 58 /** 59 * 遍历周围节点并加入开启列表 60 * @param node {Object} 一个起始点 61 */ 62 function searchAround(node) { 63 for(var i = -1; i <= 1;i++) { 64 for(var j = -1; j <= 1; j++) { 65 var x = node.x + i, 66 y = node.y + j; 67 //判断是否为有效的路径点 68 var nodeExsits = findCurrentPositionInfo(x,y) != null; 69 if(!nodeExsits) continue; 70 var t = parseInt(findCurrentPositionInfo(x,y).getAttribute(‘type‘)); 71 72 if(!(x !== node.x && y !== node.y)) { 73 if(x!== node.x || y !== node.y) { 74 var curNode = {x:x,y:y,type:t}; 75 76 //如果该坐标无法通行，则加入关闭列表中 77 if(curNode.type === 4 || 78 curNode.type === 0 || 79 curNode.type === 44) { 80 if(isNodeExists(curNode,close)) continue; 81 close.push(curNode); 82 } 83 84 //如果该坐标已在关闭列表中，略过 85 if(isNodeExists(curNode,close)) continue; 86 87 88 //设置父节点 89 curNode.parent = {x:node.x,y:node.y}; 90 curNode.G = Manhattan(curNode,node); 91 curNode.H = Manhattan(end,curNode); 92 //估算值 93 curNode.F = curNode.G + curNode.H; 94 //将坐标加入开启列表中 95 open.push(curNode); 96 } 97 } 98 } 99 } 100 } 101 102 103 function findCurrentPositionInfo(x, y) { 104 var tds = $(‘td‘), 105 s = x + "," + y; 106 for(var i = 0; i < tds.length; i++) { 107 if(tds[i].innerHTML === s) return tds[i]; 108 } 109 return null; 110 } 111 112 113 function generateMap() { 114 var t = d.createElement(‘table‘); 115 t.id = ‘t‘; 116 d.body.appendChild(t); 117 118 var html = ‘‘; 119 for(var i = -3; i < 10; i++) { 120 html += ‘<tr>‘; 121 for(var j = -3; j < 15; j++) { 122 if(i === 0 && j === 0) { 123 html += ‘<td class="start" type="1">‘+j+‘,‘+i+‘</td>‘; 124 } else { 125 html += ‘<td type="1">‘+j+‘,‘+i+‘</td>‘; 126 } 127 } 128 html += ‘</tr>‘; 129 } 130 t.innerHTML = html; 131 } 132 133 function addStone() { 134 for(var i = 0; i < 50; i++) { 135 var r = Math.ceil(Math.random() * 233); 136 if(r === 57) continue; 137 var res = tdCollections.eq(r).addClass(‘block‘); 138 res.attr(‘type‘,0); 139 } 140 } 141 142 function setGoal() { 143 var r = Math.ceil(Math.random() * 233); 144 if(r === 57 || tdCollections.eq(r).hasClass(‘block‘)) return setGoal(); 145 var res = tdCollections.eq(r).addClass(‘goal‘); 146 147 //var res = tdCollections.eq(24).addClass(‘goal‘); 148 149 return { 150 x:res.html().split(‘,‘)[0], 151 y:res.html().split(‘,‘)[1] 152 } 153 } 154 155 function setColor(start) { 156 var x = start.x, 157 y = start.y, 158 el = findCurrentPositionInfo(x,y); 159 160 $(el).addClass(‘visited‘); 161 } 162 163 function move(s,e) { 164 searchAround(s); 165 s = selectNewStart(open); 166 setColor(s); 167 if(!isNodeExists(e,close)) { 168 setTimeout(function() { 169 log(); 170 return move(s,e); 171 },100); 172 } 173 } 174 175 function init() { 176 open = []; 177 close = []; 178 start = {}; 179 end = {}; 180 } 181 182 function log() { 183 console.log(‘当前起点：‘,start); 184 console.log(‘开启列表：‘,open); 185 console.log(‘关闭列表：‘,close); 186 } 187 188 generateMap(); 189 var tdCollections = $(‘td‘); 190 addStone(); 191 end = setGoal(); 192 start = {x:0,y:0,type:1}; 193 close.push(start); 194 195 //move(start,end);
原文：http://www.cnblogs.com/undefined000/p/5139959.html
