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/

  • 支付宝二维码 支付宝
  • 微信二维码 微信
相关文章