Javascript实现寻径算法-逐梦个人博客

之前对寻径算法挺感兴趣，然后查了查，似乎都是在说A＊算法，找了一代对资料看，对于其过程，大致清楚，但是到实现然后我就有点蒙，偶然间在网上看到这个算法，觉得比A＊算法简单多了，而且寻找的路径也还挺准确的。下面是整个算法的实现过程。

其实就我理解，这个算法的主要实现思路是这样的：

首先遍历了整个map（生成map的过程就不说了，说的直白点就是一个数组），然后处理每个点的上下左右四个位置，如果有阻碍物（可以通过为0，不能通过为1）或者已经添加到steps数组就不做处理，剩下的添加到steps数组中，该点的值就是上一个点的位置，当然如果四个点中有一个已经是最终的点了那整个遍历结束这样我们就得到了路径数组，现在我们需要做的就是根据我们的得到的steps数组获取最终路径，过程是这样的，我们将将steps数组按照从后到前的顺序依次寻找父节点，直到到达起始点，这样子得出的一条路径就是最终得路径了。

代码实现如下：

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<title>寻径算法</title>
<meta name="description" content="">
<meta name="keywords" content="">
<link href="" rel="stylesheet">
<style>
.button{
width: 531px;
margin: 10px auto;
}
table{
border-collapse: collapse;
width: 531px;
margin: 0 auto;
}
td{
width: 50px;
height: 50px;
border:1px solid orange;
}
td.start{
background: url(http://1814.img.pp.sohu.com.cn/images/blog/2010/1/28/13/13/127242e5097g215.jpg) no-repeat center center;
background-size: 100% 100%;
}
td.end{
background: url(http://img.sc115.com/uploads/sc/png/140706/fish.png) no-repeat center center;
background-size: 100% 100%;
}
td.current{
background: skyblue;
}
td.path{
background: url(http://cdn-img.easyicon.net/png/5308/530838.gif) no-repeat center center;
background-size: 100% 100%;
}
td.block{
background: url(http://ico.ooopic.com/iconset01/open-icon-library-others-icons/gif/119576.gif) no-repeat center center;
background-size: 80% 80%;
}
</style>
</head>
<body>
<div class="button">
<button onclick="javascript:console.time('t');finder();console.timeEnd('t');">去吃鱼啦</button>
</div>
<script type="text/javascript">
var rows = 10,cols =10;
var map = multiArray(rows,cols),elems = multiArray(rows,cols);
var start = [0,0];
var end = [9,9];
var table = document.createElement("table");
for(var i=0,l=map.length;i<l;i++){
var tr = document.createElement("tr");
for(var j=0,ll=map[i].length;j<ll;j++){
var td = document.createElement("td");
if(i==start[1]&&j==start[0]){
td.className = "start";
}
if(i==end[1]&&j==end[0]){
td.className = "end";
}
elems[j][i] = tr.appendChild(td);
(function(i,j){
td.onclick = function(){
clearPath();
if(elems[j][i].className=="block"){
elems[j][i].className = "";
map[j][i] = 0;
}else if(!elems[j][i].className){
elems[j][i].className = 'block';
map[j][i] = 1;
}
}
})(i,j);
}
table.appendChild(tr);
}
document.body.appendChild(table);
function finder(){
clearPath();
var result = [];
var finded =false;
var steps = multiArray(rows,cols);
(function(list){
var next_list = [];
var next = function(from,to){
var x = to[0],y = to[1];
if(typeof steps[x]!= 'undefined' && typeof steps[x][y]!='undefined' && !map[x][y] && !finded){
if(x==end[0] && y==end[1]){
finded = true;
steps[x][y] = from;
}else if(!steps[x][y]){
next_list.push(to);
steps[x][y] = from;
}
}
}
for(var i=0,l=list.length;i<l;i++){
var current = list[i];
var x = current[0],y = current[1];
(x-1>=0) && next(current,[x-1,y]);
(x+1<cols) && next(current,[x+1,y]);
(y-1>=0) && next(current,[x,y-1]);
(y+1<rows) && next(current,[x,y+1]);
}
if(!finded && next_list.length){
arguments.callee(next_list);
}
})([start]);
if(finded){
var current = end;
while(current[0]!=start[0]||current[1]!=start[1]){
result.unshift(current);
current = steps[current[0]][current[1]];
}
}
for(var i=0,l=result.length;i<l;i++){
if(result[i][0]==end[0]&&result[i][1]==end[1]) continue;
elems[result[i][0]][result[i][1]].className = 'path';
}
}
function multiArray(rows,cols){
var a = new Array(rows);
for(var i=0,l=a.length;i<l;i++){
a[i] = new Array(cols);
for(var j=0;j<cols;j++){
a[i][j] = 0;
}
}
return a;
}
function clearPath(){
for(var i=0,l=map.length;i<l;i++){
for(var j=0,ll=map[i].length;j<ll;j++){
if(elems[j][i].className=="path"){
elems[j][i].className = "";
}
}
}
}
</script>
</body>
</html></span>

在线Demo：http://demo.deanhan.cn/findpath/