对A-Star寻路算法的粗略研究

首先来看看完成后的效果：

其中灰色代表路障，绿色是起点和移动路径，红色代表终点

为了继续学习，需要明白几个概念。

曼哈顿距离

曼哈顿距离的定义是，两个物体南北方向的距离与东西方向的距离之和。看起来就好像是直角三角形的两条边之和。

用代码表示出来就是：

/**
 * 计算两点间的曼哈顿距离
 * @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);
}

View Code

公式F＝G+H

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>

View Code

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 el 待返回元素
 25  * @param arr 数组
 26  * @returns {Object} 返回该元素
 27  */
 28 function getElementInArray(el,arr) {
 29     for(var i in arr) {
 30         if(arr.hasOwnProperty(i)) {
 31             if(parseInt(el.x) === arr[i].x && parseInt(el.y) === arr[i].y) {
 32                 return arr[i];
 33             }
 34         }
 35     }
 36     return null;
 37 }
 38 
 39 /**
 40  * 计算两点间的曼哈顿距离
 41  * @param goalNode  {Object} 终点坐标
 42  * @param startNode {Object} 起点坐标
 43  * @returns {number} 两点间的曼哈顿距离
 44  */
 45 function Manhattan(goalNode,startNode) {
 46     return Math.abs(goalNode.x - startNode.x) + Math.abs(goalNode.y - startNode.y);
 47 }
 48 
 49 /**
 50  * 选择最佳路径作为新起始点
 51  * @param openArray {Array} 开启列表
 52  * @returns {Object} 返回新起始点
 53  */
 54 function selectNewStart(openArray) {
 55     var minNode = openArray[0],i;
 56     for(i = 0,len = openArray.length - 1; i < len; i++) {
 57         if(minNode.F >= openArray[i+1].F) {
 58             minNode = openArray[i+1];
 59         }
 60     }
 61     start = minNode;
 62     //将新开始点加入关闭列表
 63     close.push(start);
 64 
 65     //将新开始点从开启列表中移除
 66     for(i = 0; i < openArray.length; i++) {
 67         if(minNode.x === openArray[i].x && minNode.y === openArray[i].y) {
 68             openArray.splice(i,1);
 69             break;
 70         }
 71     }
 72     return start;
 73 }
 74 
 75 /**
 76  * 遍历周围节点并加入开启列表
 77  * @param node {Object} 一个起始点
 78  */
 79 function searchAround(node) {
 80     for(var i = -1; i <= 1;i++) {
 81         for(var j = -1; j <= 1; j++) {
 82             var x = node.x + i,
 83                 y = node.y + j;
 84             //判断是否为有效的路径点
 85             var nodeExsits = findCurrentPositionInfo(x,y) != null;
 86             if(!nodeExsits) continue;
 87             var t = parseInt(findCurrentPositionInfo(x,y).getAttribute('type'));
 88 
 89             if(!(x !== node.x && y !== node.y)) {
 90                 if(x!== node.x || y !== node.y) {
 91                     var curNode = {x:x,y:y,type:t};
 92 
 93                     //如果该坐标无法通行，则加入关闭列表中
 94                     if(curNode.type === 4 ||
 95                         curNode.type === 0 ||
 96                         curNode.type === 44) {
 97                         if(isNodeExists(curNode,close)) continue;
 98                         close.push(curNode);
 99                     }
100 
101                     //如果该坐标已在关闭列表中，略过
102                     if(isNodeExists(curNode,close)) continue;
103 
104                     //如果该坐标已在开启列表中，则重新计算它的G值
105                     if(isNodeExists(curNode,open)) {
106                         var new_GValue = Manhattan(curNode,start),
107                             //在开启列表中取出这个元素
108                             inOpenNode = getElementInArray(curNode,open),
109                             //取出旧的G值
110                             old_GValue = inOpenNode.G;
111 
112                         //如果G值更小，则意味着当前到达它的路径比上一次的好，更新它的父结点
113                         //以及G值，并重新计算它的F值
114                         if(new_GValue < old_GValue) {
115                             inOpenNode.parent = start;
116                             inOpenNode.G = new_GValue;
117                             inOpenNode.F = inOpenNode.G + inOpenNode.H;
118                         }
119                         continue;
120                     }
121 
122 
123                     //设置父节点
124                     curNode.parent = {x:node.x,y:node.y};
125                     curNode.G = Manhattan(curNode,node);
126                     curNode.H = Manhattan(end,curNode);
127                     //估算值
128                     curNode.F = curNode.G + curNode.H;
129                     //将坐标加入开启列表中
130                     open.push(curNode);
131                 }
132             }
133         }
134     }
135 }
136 
137 
138 function findCurrentPositionInfo(x, y) {
139     var tds = $('td'),
140         s = x + "," + y;
141     for(var i = 0; i < tds.length; i++) {
142         if(tds[i].innerHTML === s) return tds[i];
143     }
144     return null;
145 }
146 
147 
148 function generateMap() {
149     var t = d.createElement('table');
150     t.id = 't';
151     d.body.appendChild(t);
152 
153     var html = '';
154     for(var i = -3; i < 10; i++) {
155         html += '<tr>';
156         for(var j = -3; j < 15; j++) {
157             if(i === 0 && j === 0) {
158                 html += '<td class="start" type="1">'+j+','+i+'</td>';
159             } else {
160                 html += '<td type="1">'+j+','+i+'</td>';
161             }
162         }
163         html += '</tr>';
164     }
165     t.innerHTML = html;
166 }
167 
168 function addStone() {
169     for(var i = 0; i < 50; i++) {
170         var r = Math.ceil(Math.random() * 233);
171         if(r === 57) continue;
172         var res = tdCollections.eq(r).addClass('block');
173         res.attr('type',0);
174     }
175 }
176 
177 function setGoal() {
178     var r = Math.ceil(Math.random() * 233);
179     if(r === 57 || tdCollections.eq(r).hasClass('block')) return setGoal();
180     var res = tdCollections.eq(r).addClass('goal');
181 
182     //var res = tdCollections.eq(24).addClass('goal');
183 
184     return {
185         x:res.html().split(',')[0],
186         y:res.html().split(',')[1]
187     }
188 }
189 
190 function setColor(start) {
191     var x = start.x,
192         y = start.y,
193         el = findCurrentPositionInfo(x,y);
194 
195     $(el).addClass('visited');
196 }
197 
198 function move(s,e) {
199     searchAround(s);
200     s = selectNewStart(open);
201     setColor(s);
202     if(!isNodeExists(e,close)) {
203         setTimeout(function() {
204             log();
205             return move(s,e);
206         },100);
207     }
208 }
209 
210 function init() {
211     open = [];
212     close = [];
213     start = {};
214     end = {};
215 }
216 
217 function log() {
218     console.log('当前起点：',start);
219     console.log('开启列表：',open);
220     console.log('关闭列表：',close);
221 }
222 
223 generateMap();
224 var tdCollections = $('td');
225 addStone();
226 end = setGoal();
227 start = {x:0,y:0,type:1};
228 close.push(start);
229 
230 //move(start,end);

View Code