|
阅读：2017回复：2
[分享]使用Javascript实现的最短路径A*算法实现。
<html><head><title>use A* to find path...</title></head><br><body style="margin:0px"><br><script><br>/*<br>written by hjjboy<br>email:tianmashuangyi@163.com<br>qq:156809986<br>*/<br>var closelist=new Array(),openlist=new Array();<br>var gw=10,gh=10,gwh=14;<br>var p_start=new Array(2),p_end=new Array(2);<br>var s_path,n_path="";<br>var num,bg,flag=0;<br>var w=30,h=20;<br>function GetRound(pos){<br> var a=new Array();<br> a[0]=(pos[0]+1)+","+(pos[1]-1);<br> a[1]=(pos[0]+1)+","+pos[1];<br> a[2]=(pos[0]+1)+","+(pos[1]+1);<br> a[3]=pos[0]+","+(pos[1]+1);<br> a[4]=(pos[0]-1)+","+(pos[1]+1);<br> a[5]=(pos[0]-1)+","+pos[1];<br> a[6]=(pos[0]-1)+","+(pos[1]-1);<br> a[7]=pos[0]+","+(pos[1]-1);<br> return a;<br>}<br>function GetF(arr){<br> var t,G,H,F;<br> for(var i=0;i<arr.length;i++){<br> t=arr.split(",");<br> t[0]=parseInt(t[0]);t[1]=parseInt(t[1]);<br> if(IsOutScreen([t[0],t[1]])||IsPass(arr)||InClose([t[0],t[1]])||IsStart([t[0],t[1]])||!IsInTurn([t[0],t[1]]))<br> continue;<br> if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0)<br> G=s_path[1]+gwh;<br> else<br> G=s_path[1]+gw;<br> if(InOpen([t[0],t[1]])){<br> if(G<openlist[num][1]){<br> openlist[num][0]=(G+openlist[num][2]);<br> openlist[num][1]=G;<br> openlist[num][4]=s_path[3];<br> }<br> else{G=openlist[num][1];}<br> }<br> else{<br> H=(Math.abs(p_end[0]-t[0])+Math.abs(p_end[1]-t[1]))*gw;<br> F=G+H;<br> arr=new Array();<br> arr[0]=F;arr[1]=G;arr[2]=H;arr[3]=[t[0],t[1]];arr[4]=s_path[3];<br> openlist[openlist.length]=arr;<br> }<br> 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")<br> {<br> maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#FF00FF";<br> //maptt.rows[t[1]].cells[t[0]].innerHTML="<font color=white>"+G+"</font>";<br> }<br> }<br>}<br>function IsStart(arr){<br> if(arr[0]==p_start[0];;arr[1]==p_start[1])<br> return true;<br> return false;<br>}<br>function IsInTurn(arr){<br> if(arr[0]>s_path[3][0]){<br> if(arr[1]>s_path[3][1]){<br> if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))<br> return false;<br> }<br> else if(arr[1]<s_path[3][1]){<br> if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))<br> return false;<br> }<br> }<br> else if(arr[0]<s_path[3][0]){<br> if(arr[1]>s_path[3][1]){<br> if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))<br> return false;<br> }<br> else if(arr[1]<s_path[3][1]){<br> if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))<br> return false;<br> }<br> }<br> return true;<br>}<br>function IsOutScreen(arr){<br> if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1))<br> return true;<br> return false;<br>}<br>function InOpen(arr){<br> var bool=false;<br> for(var i=0;i<openlist.length;i++){<br> if(arr[0]==openlist[3][0];;arr[1]==openlist[3][1]){<br> bool=true;num=i;break;}<br> }<br> return bool;<br>}<br>function InClose(arr){<br> var bool=false;<br> for(var i=0;i<closelist.length;i++){<br> if((arr[0]==closelist[3][0]);;(arr[1]==closelist[3][1])){<br> bool=true;break;}<br> }<br> return bool;<br>}<br>function IsPass(pos){<br> if((";"+n_path+";").indexOf(";"+pos+";")!=-1)<br> return true;<br> return false;<br>}<br>function Sort(arr){<br> var temp;<br> for(var i=0;i<arr.length;i++){<br> if(arr.length==1)break;<br> if(arr[0]<=arr[i+1][0]){<br> temp=arr;<br> arr=arr[i+1];<br> arr[i+1]=temp;<br> }<br> if((i+1)==(arr.length-1))<br> break;<br> }<br>}<br>function main(){<br> GetF(GetRound(s_path[3]));<br> Sort(openlist);<br> s_path=openlist[openlist.length-1];<br> closelist[closelist.length]=s_path;<br> openlist[openlist.length-1]=null;<br> if(openlist.length==0){alert("找不到路径");return;}<br> openlist.length=openlist.length-1;<br> if((s_path[3][0]==p_end[0]);;(s_path[3][1]==p_end[1])){<br> getPath();<br> }<br> else{maptt.rows[s_path[3][1]].cells[s_path[3][0]].style.backgroundColor="#00ff00";setTimeout("main()",100);}<br>}<br>function getPath(){<br> var str="";<br> var t=closelist[closelist.length-1][4];<br> while(1){<br> str+=t.join(",")+";";<br> maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#ffff00";<br> for(var i=0;i<closelist.length;i++){<br> if(closelist[3][0]==t[0];;closelist[3][1]==t[1])<br> t=closelist[4];<br> }<br> if(t[0]==p_start[0];;t[1]==p_start[1])<br> break;<br> }<br> alert(str);<br>}<br>function setPos(){<br> var h=(Math.abs(p_end[0]-p_start[0])+Math.abs(p_end[1]-p_start[1]))*gw;<br> s_path=[h,0,h,p_start,p_start];<br>}<br>function set(id,arr){<br> switch(id){<br> case 1:<br> p_start=arr;<br> maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#ff0000";break;<br> case 2:<br> p_end=arr;maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#0000ff";break;<br> case 3:<br> n_path+=arr.join(",")+";";maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#cccccc";break;<br> default:<br> break;<br> }<br>}<br>function setflag(id){flag=id;}<br></script><br><table id="maptt" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000"><br><script><br>for(var i=0;i<h;i++){<br> document.write("<tr>");<br> for(var j=0;j<w;j++){<br> document.write('<td onclick="set(flag,['+j+','+i+']);" bgcolor="#ffffff" width="20" height="20"></td>');<br> }<br> document.write("</tr>");<br>}<br></script><br></table><br><a href="javascript:setflag(1);">设置起点</a><br><br><a href='javascript:setflag(2);'>设置终点</a><br><br><a href='javascript:setflag(3);'>设置障碍点</a><br><br><input type="button" onclick="setPos();main();this.disabled=true;" value="find"><br></body><br></html><br><br>
|
|
|
1楼#
发布于：2008-03-23 01:43
<P>很好啊，谢谢了</P>
|
|
|
2楼#
发布于：2008-03-23 15:40
<img src="images/post/smile/dvbbs/em01.gif" />
|
|