最短パスA*アルゴリズム実装(Javascript)

7050 ワード

use A* to find path...

<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[i].split(",");<br> t[0]=parseInt(t[0]);t[1]=parseInt(t[1]);<br> if(IsOutScreen([t[0],t[1]])||IsPass(arr[i])||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[i]=new Array();<br> 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];<br> openlist[openlist.length]=arr[i];<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[i][3][0]&&arr[1]==openlist[i][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[i][3][0])&&(arr[1]==closelist[i][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[i][0]<=arr[i+1][0]){<br> temp=arr[i];<br> arr[i]=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[i][3][0]==t[0]&&closelist[i][3][1]==t[1])<br> t=closelist[i][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>


<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>





を ける