A*算法JS版

2006-09-23 10:40:35

[code]<html><head><title>use A* to find path...</title></head> <body style="margin:0px"> <script> /* written by hjjboy email:tianmashuangyi@163.com qq:156809986 */ 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=30,h=20; 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()",100);} } function getPath(){ var str=""; var t=closelist[closelist.length-1][4]; while(1){ str+=t.jo&#105;n(",")+";"; 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.jo&#105;n(",")+";";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><br> <a href='javascript:setflag(2);'>设置终点</a><br> <a href='javascript:setflag(3);'>设置障碍点</a><br> <input type="button" onclick="setPos();main();this.disabled=true;" value="find"> </body> </html>[/code]