js寻路模式
关键词：寻路
** 1.深度优先搜索（Depth-First-Search）：**
沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。
利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
步骤
- 访问顶点v；
- 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
- 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
Paste_Image.png
对上面的图G1进行深度优先遍历，从顶点A开始。
Paste_Image.png
第1步：访问A。
第2步：访问(A的邻接点)C。
在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
第3步：访问(C的邻接点)B。
在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
第4步：访问(C的邻接点)D。
在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
第5步：访问(A的邻接点)F。
前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
第6步：访问(F的邻接点)G。
第7步：访问(G的邻接点)E。
因此访问顺序是：A -> C -> B -> D -> F -> G -> E
下面以"有向图"为例，来对深度优先搜索进行演示。
Paste_Image.png
对上面的图G2进行深度优先遍历，从顶点A开始。
Paste_Image.png
第2步：访问B。
在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。
第3步：访问C。
在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
第4步：访问E。
接下来访问C的出边的另一个顶点，即顶点E。
第5步：访问D。
接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
第6步：访问F。
接下应该回溯"访问A的出边的另一个顶点F"。
第7步：访问G。
因此访问顺序是：A -> B -> C -> E -> D -> F -> G
广度优先搜索（Breadth-First-Search）：
一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。
步骤：
- 首先将根节点放入队列中。
- 从队列中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜寻并回传结果。
否则将它所有尚未检验过的直接子节点加入队列中。 - 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
- 重复步骤2。
Paste_Image.png
下面以"无向图"为例，来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。
Paste_Image.png
第1步：访问A。
第2步：依次访问C,D,F。
在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。
第3步：依次访问B,G。
在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。
第4步：访问E。
在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。
因此访问顺序是：A -> C -> D -> F -> B -> G -> E
下面以"有向图"为例，来对广度优先搜索进行演示。还是以上面的图G2为例进行说明。
Paste_Image.png
第1步：访问A。
第2步：访问B。
第3步：依次访问C,E,F。
在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。
第4步：依次访问D,G。
在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。
因此访问顺序是：A -> B -> C -> E -> F -> D -> G
启发式搜索(Heuristically Search)：
又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。
就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。
这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价（估价函数）是十分重要的
利用启发式搜索自动寻路实例
<style type="text/css">
*{ margin:0; padding:0;}
li{ list-style:none;}
#map{
height:auto;
overflow:hidden;
margin:20px auto;
border:1px #ccc solid;
border-bottom:none;
border-right:none;
}
#map li{
box-sizing: border-box;
border:1px #ccc solid;
border-top:none;
border-left:none;
float:left;
}
#map li.sty1{ background:#e22841;}
#map li.sty2{ background:orange;}
#map li.sty3{ background:#00bcda;}
#btn{
width:160px;
height: 40px;
color: #fff;
text-align: center;
line-height: 40px;
font-size: 16px;
background-color: #00bcda;
border: none;
border-radius: 5px;
position:absolute;
left:0;
right: 0;
margin: auto;
cursor: pointer;
}
</style>
<body>
<ul id="map"></ul>
<span id="btn">快去解救公主!</span>
</body>
<script type="text/javascript">
var map = [
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,3,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,3,3,0,3,3,3,0,3,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,3,3,0,3,3,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
];
var sizeGird = 24; // 设定网格尺寸
var speed = 100; // 设定移动速度
(function road(){
var oUl = document.getElementById('map');
var aLi = oUl.getElementsByTagName('li');
var oBtn = document.getElementById('btn');
var beginLi = oUl.getElementsByClassName('sty1');
var endLi = oUl.getElementsByClassName('sty2');
var cols = Math.sqrt(map.length);
var openArr = []; // 存放可能要走的路线
var closeArr = []; // 存放不允许走的路线
// 点击按钮初始化
init();
function init(){
createMap();
oBtn.onclick = function(){
openFn();
};
}
// 创建网格
function createMap(){
oUl.style.width = cols * (sizeGird) + 'px';
for(var i=0;i<map.length;i++){
var oLi = document.createElement('li');
oLi.style.width = sizeGird + 'px';
oLi.style.height = sizeGird + 'px';
oUl.appendChild(oLi);
if( map[i] == 1 ){
oLi.className = 'sty1';
openArr.push(oLi);
}
else if(map[i] == 2){
oLi.className = 'sty2';
}
else if(map[i] == 3){
oLi.className = 'sty3';
closeArr.push(oLi);
}
}
}
function openFn(){
var nowLi = openArr.shift();
if( nowLi == endLi[0] ){
showLine();
return;
}
closeFn(nowLi);
findLi(nowLi);
//console.log( openArr );
openArr.sort(function(li1,li2){
return li1.num - li2.num;
});
//console.log( openArr );
openFn(); // 递归操作，重复执行函数
}
// 过滤走过的路线
function closeFn(nowLi){
closeArr.push( nowLi );
}
// 找寻所有可能走的网格
function findLi(nowLi){
var result = [];
for(var i=0;i<aLi.length;i++){
if( filter(aLi[i]) ){
result.push( aLi[i] );
}
}
function filter(li){
for(var i=0;i<closeArr.length;i++){
if( closeArr[i] == li ){
return false;
}
}
for(var i=0;i<openArr.length;i++){
if( openArr[i] == li ){
return false;
}
}
return true;
}
// 找到当前网格周围的八个网格
for(var i=0;i<result.length;i++){
if( (Math.abs(nowLi.offsetLeft - result[i].offsetLeft)<= sizeGird) && (Math. abs(nowLi.offsetTop - result[i].offsetTop)<= sizeGird) ){
result[i].num = f(result[i]);
result[i].parent = nowLi;
openArr.push( result[i] );
}
}
}
// 显示路线
function showLine(){
var result = [];
var lastLi = closeArr.pop();
var iNow = 0;
findParent(lastLi);
function findParent(li){
result.unshift(li);
if( li.parent == beginLi[0] ){
return;
}
findParent(li.parent);
}
var timer = setInterval(function(){
result[iNow].style.background = '#e22841';
iNow++;
if(iNow == result.length){
clearInterval(timer);
}
},speed);
}
// 估价函数
function f(nodeLi){
return g(nodeLi) + h(nodeLi);
}
function g(nodeLi){
var a = beginLi[0].offsetLeft - nodeLi.offsetLeft;
var b = beginLi[0].offsetTop - nodeLi.offsetTop;
return Math.sqrt(a*a + b*b); // 利用了勾股定理
}
function h(nodeLi){
var a = endLi[0].offsetLeft - nodeLi.offsetLeft;
var b = endLi[0].offsetTop - nodeLi.offsetTop;
return Math.sqrt(a*a + b*b);
}
})(map,sizeGird,speed)
在线预览实例 ?[请点这里!!!][]
[请点这里!!!]:http://htmlpreview.github.io/?https://github.com/ferrinte/algorithm/blob/master/road.html
