js版本A*寻路算法- Javascript - 软晨网（RuanChen.com）

当前位置: 首页 > 图文教程 > 网络编程 > Javascript > js版本A*寻路算法

Javascript: 自己开发Dojo的建议框架; js每次Title显示不同的名言; 不用AJAX和IFRAME,说说真正意义上的ASP+JS无刷新技术; 无限级别的菜单（侧拉菜单）; 点选TOP后并不是直接跳到页顶的，而是滚动上去; js下拉菜单中自动信息轮换播放; 英文首字母全大写的js实现脚本; 实例区别onClick和onDBClick两事件方法; 改变文本框字体颜色的js脚本; js星空效果代码; 判断li是否有样式的js代码; 文本框点击时文字消失，失去焦点时文字出现; 如何让一个层关闭之后，就算刷新页面了也不显示。除非关闭页面再次打开; 右下角弹出窗口效果代码; JS控制对象移动效果; 验证用户是否修改过页面的数据的实现方法; Javascript操作select方法大全[新增、修改、删除、选中、清空、判断存在等]; 正则表达式判断是否存在中文和全角字符和判断包含中文字符串长度; EXT富客户端后台管理系统初步代码; 不同浏览器javascript变量作用域的处理方法

No. « ‹ 110 111 112 113 › »

技术文章搜索

关键字

Javascript 中的 js版本A*寻路算法

出处:互联网 整理: 软晨网（RuanChen.com） 发布: 2009-09-12 浏览: 291 ::

收藏到网摘: n/a

在window.setTimeout方法中传送对象用js重建星际争霸

说到做游戏，必不可少的需要用到寻路算法，一般游戏里的寻路算法大多数都以A*算法为主，这里也就实现了js里采用a*寻路的程序，在51js和蓝色都开了帖。
程序是以前写的，后来也没有修正或者精简，有冗余之处大家还见谅一下。
当然，这个寻路算法也不是最优化的，像幻宇开发的“交点寻径法”也是个中精品，两者可谓各有千秋，只是如果地图很大的情况下，我们会惊讶于“交点寻径法”的迅速。

点击运行可以看到效果:

<html><head><title>use A* to find path...</title></head>
<body style="margin:0px">
<script>
/*
written by 百晓生
email:jsrpg@126.com
qq:156809986
msn:jscript_rpg@hotmail.com
*/
var closelist=new Array(),openlist=new Array();
var gw=10,gh=10,gwh=14;
var p_start=new Array(2),p_end=new Array(2);
var s_path,n_path="";
var num,bg,flag=0;
var w=32,h=32;
function GetRound(pos){ var a=new Array(); a[0]=(pos[0]+1)+","+(pos[1]-1); a[1]=(pos[0]+1)+","+pos[1]; a[2]=(pos[0]+1)+","+(pos[1]+1); a[3]=pos[0]+","+(pos[1]+1); a[4]=(pos[0]-1)+","+(pos[1]+1); a[5]=(pos[0]-1)+","+pos[1]; a[6]=(pos[0]-1)+","+(pos[1]-1); a[7]=pos[0]+","+(pos[1]-1); return a;
}
function GetF(arr){ var t,G,H,F; for(var i=0;i<arr.length;i++){ t=arr[i].split(","); t[0]=parseInt(t[0]);t[1]=parseInt(t[1]); if(IsOutScreen([t[0],t[1]])||IsPass(arr[i])||InClose([t[0],t[1]])||IsStart([t[0],t[1]])||!IsInTurn([t[0],t[1]])) continue; if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0) G=s_path[1]+gwh; else G=s_path[1]+gw; if(InOpen([t[0],t[1]])){ if(G<openlist[num][1]){ openlist[num][0]=(G+openlist[num][2]); openlist[num][1]=G; openlist[num][4]=s_path[3]; } else{G=openlist[num][1];} } else{ H=(Math.abs(p_end[0]-t[0])+Math.abs(p_end[1]-t[1]))*gw; F=G+H; arr[i]=new Array(); arr[i][0]=F;arr[i][1]=G;arr[i][2]=H;arr[i][3]=[t[0],t[1]];arr[i][4]=s_path[3]; openlist[openlist.length]=arr[i]; } if(maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#cccccc"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#0000ff"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#ff0000"&&maptt.rows[t[1]].cells[t[0]].style.backgroundColor!="#00ff00") { maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#FF00FF"; //maptt.rows[t[1]].cells[t[0]].innerHTML="<font color=white>"+G+"</font>"; } }
}
function IsStart(arr){ if(arr[0]==p_start[0]&&arr[1]==p_start[1]) return true; return false;
}
function IsInTurn(arr){ if(arr[0]>s_path[3][0]){ if(arr[1]>s_path[3][1]){ if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1))) return false; } else if(arr[1]<s_path[3][1]){ if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1))) return false; } } else if(arr[0]<s_path[3][0]){ if(arr[1]>s_path[3][1]){ if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1))) return false; } else if(arr[1]<s_path[3][1]){ if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1))) return false; } } return true;
}
function IsOutScreen(arr){ if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1)) return true; return false;
}
function InOpen(arr){ var bool=false; for(var i=0;i<openlist.length;i++){ if(arr[0]==openlist[i][3][0]&&arr[1]==openlist[i][3][1]){ bool=true;num=i;break;} } return bool;
}
function InClose(arr){ var bool=false; for(var i=0;i<closelist.length;i++){ if((arr[0]==closelist[i][3][0])&&(arr[1]==closelist[i][3][1])){ bool=true;break;} } return bool;
}
function IsPass(pos){ if((";"+n_path+";").indexOf(";"+pos+";")!=-1) return true; return false;
}
function Sort(arr){ var temp; for(var i=0;i<arr.length;i++){ if(arr.length==1)break; if(arr[i][0]<=arr[i+1][0]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } if((i+1)==(arr.length-1)) break; }
}
function main(){ GetF(GetRound(s_path[3])); Sort(openlist); s_path=openlist[openlist.length-1]; closelist[closelist.length]=s_path; openlist[openlist.length-1]=null; if(openlist.length==0){alert("找不到路径");return;} openlist.length=openlist.length-1; if((s_path[3][0]==p_end[0])&&(s_path[3][1]==p_end[1])){ getPath(); } else{maptt.rows[s_path[3][1]].cells[s_path[3][0]].style.backgroundColor="#00ff00";setTimeout("main()",10);}
}
function getPath(){ var str=""; var t=closelist[closelist.length-1][4]; while(1){ str+=t.join(",")+";"; maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#ffff00"; for(var i=0;i<closelist.length;i++){ if(closelist[i][3][0]==t[0]&&closelist[i][3][1]==t[1]) t=closelist[i][4]; } if(t[0]==p_start[0]&&t[1]==p_start[1]) break; } alert(str);
}
function setPos(){ var h=(Math.abs(p_end[0]-p_start[0])+Math.abs(p_end[1]-p_start[1]))*gw; s_path=[h,0,h,p_start,p_start];
}
function set(id,arr){ switch(id){ case 1: p_start=arr; maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#ff0000";break; case 2: p_end=arr;maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#0000ff";break; case 3: n_path+=arr.join(",")+";";maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#cccccc";break; default: break; }
}
function setflag(id){flag=id;}
</script>
<table id="maptt" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000">
<script>
for(var i=0;i<h;i++){ document.write("<tr>"); for(var j=0;j<w;j++){ document.write('<td onclick="set(flag,['+j+','+i+']);" bgcolor="#ffffff" width="20" height="20"></td>'); } document.write("</tr>");
}
</script>
</table>
<a href="javascript:setflag(1);">设置起点</a>
<a href='javascript:setflag(2);'>设置终点</a>
<a href='javascript:setflag(3);'>设置障碍点</a>
<input type="button" onclick="setPos();main();this.disabled=true;" value="find">
</body>
</html>
<xmp id=xMapData style=display:none>
25,0;25,1;25,3;25,4;25,5;25,6;25,7;0,8;1,8;2,8;3,8;4,8;5,8;6,8;7,8;25,8;7,9;25,9;7,10;25,10;7,11;25,11;6,12;25,12;5,13;6,13;25,13;5,14;21,14;25,14;5,15;18,15;19,15;20,15;21,15;25,15;5,16;11,16;12,16;13,16;14,16;15,16;16,16;17,16;18,16;19,16;22,16;25,16;5,17;11,17;23,17;24,17;25,17;5,18;6,18;7,18;8,18;9,18;10,18;11,18;13,18;23,18;24,18;25,18;6,19;7,19;8,19;13,19;23,19;24,19;25,19;6,20;14,20;23,20;24,20;26,20;7,21;8,21;13,21;14,21;15,21;20,21;21,21;22,21;27,21;0,22;1,22;2,22;4,22;5,22;6,22;7,22;12,22;13,22;14,22;16,22;19,22;20,22;21,22;26,22;27,22;28,22;8,23;9,23;10,23;11,23;12,23;13,23;17,23;18,23;19,23;22,23;13,24;14,24;15,24;18,24;21,24;23,24;20,25;24,25;19,26;25,26;26,26;19,28;19,29;19,30;19,31
</xmp>
</body>
</html>
<script>
a=xMapData.innerHTML.split(";")
setFlag(3)
for(i=0;i<a.length;i++){ ad=a[i].split(",") set(3,[ad[0],ad[1]]); //setPos("tb_"+ad[1]+"_"+ad[0]) //document.getElementById("tb_"+ad[1]+"_"+ad[0]).style.backgroundColor="black"
}
function setFlag(n){ flag=n;
}
</script>

[Ctrl+A 全选提示:你可先修改部分代码,再按运行]

在window.setTimeout方法中传送对象用js重建星际争霸

Javascript 中的 js版本A*寻路算法

评论 (0) All