手机浏览 RSS 2.0 订阅 膘叔的简单人生 , 腾讯云RDS购买 | 超便宜的Vultr , 注册 | 登陆
浏览模式: 标准 | 列表Tag:a*

A*算法的JS实现

Submitted by gouki on 2009, July 20, 10:48 PM

网上找来的代码，经典的东西哦。做网游的人可能会用到。。

XML/HTML代码
  1. <html><head><title>use A* to find path...</title></head>  
  2. <body style="margin:0px">  
  3. <script>  
  4. /*  
  5. written by hjjboy  
  6. email:tianmashuangyi@163.com  
  7. qq:156809986  
  8. */  
  9. var closelist=new Array(),openlist=new Array();//closelist保存最终结果。openlist保存临时生成的点；  
  10. var gw=10,gh=10,gwh=14;//参数 gh是水平附加参数 gwh是四角的附加参数。  
  11. var p_start=new Array(2),p_end=new Array(2);//p_start为起点，p_end为终点  
  12. var s_path,n_path="";//s_path为当前点 n_path为障碍物数组样式的字符串.  
  13. var num,bg,flag=0;  
  14. var w=30,h=20;  
  15. function GetRound(pos){//返回原点周围的8个点  
  16.     var a=new Array();  
  17.     a[0]=(pos[0]+1)+","+(pos[1]-1);  
  18.     a[1]=(pos[0]+1)+","+pos[1];  
  19.     a[2]=(pos[0]+1)+","+(pos[1]+1);  
  20.     a[3]=pos[0]+","+(pos[1]+1);  
  21.     a[4]=(pos[0]-1)+","+(pos[1]+1);  
  22.     a[5]=(pos[0]-1)+","+pos[1];  
  23.     a[6]=(pos[0]-1)+","+(pos[1]-1);  
  24.     a[7]=pos[0]+","+(pos[1]-1);  
  25.     return a;  
  26. }  
  27. function GetF(arr){ //参数为原点周围的8个点  
  28.     var t,G,H,F;//F,综合的距离值，H,距离值 G,水平\角落附加计算  
  29.     for(var i=0;i<arr.length;i++){  
  30.         t=arr[i].split(",");  
  31.         t[0]=parseInt(t[0]);  
  32.         t[1]=parseInt(t[1]);  
  33.         if(IsOutScreen([t[0],t[1]])||IsPass(arr[i])||InClose([t[0],t[1]])||IsStart([t[0],t[1]])||!IsInTurn([t[0],t[1]]))  
  34.             continue;//如果上面条件有一满足，则跳过本次循环，进行下一次。  
  35.         if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0)//判断该点是否处于起点的垂直或横向位置上  
  36.             G=s_path[1]+gwh;//如果不在G=14;  
  37.         else  
  38.             G=s_path[1]+gw;//如果在G=10;  
  39.         if(InOpen([t[0],t[1]])){//如果当前点已存在openlist数组中  
  40.             if(G<openlist[num][1]){  
  41.             maptt.rows[openlist[num][4][1]].cells[openlist[num][4][0]].style.backgroundColor="blue";//调试  
  42.                 openlist[num][0]=(G+openlist[num][2]);  
  43.                 openlist[num][1]=G;  
  44.                 openlist[num][4]=s_path[3];  
  45.             }  
  46.             else{G=openlist[num][1];}  
  47.         }  
  48.         else{  
  49.             H=(Math.abs(p_end[0]-t[0])+Math.abs(p_end[1]-t[1]))*gw;  
  50.             F=G+H;  
  51.             arr[i]=new Array();  
  52.             arr[i][0]=F;  
  53.             arr[i][1]=G;  
  54.             arr[i][2]=H;  
  55.             arr[i][3]=[t[0],t[1]];  
  56.             arr[i][4]=s_path[3];  
  57.             openlist[openlist.length]=arr[i];//将F等信息保存到openlist  
  58.         }  
  59.         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")  
  60.         {  
  61.             maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#FF00FF";  
  62.             if(F!=undefined)  
  63.             maptt.rows[t[1]].cells[t[0]].innerHTML="<font color='black'>"+F+"</font>";  
  64.         }  
  65.     }  
  66. }  
  67. function IsStart(arr){ //判断该点是不是起点  
  68.     if(arr[0]==p_start[0]&&arr[1]==p_start[1])  
  69.         return true;  
  70.     return false;  
  71. }  
  72. function IsInTurn(arr){ //判断是否是拐角  
  73.     if(arr[0]>s_path[3][0]){  
  74.         if(arr[1]>s_path[3][1]){  
  75.             if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))  
  76.                 return false;  
  77.         }  
  78.         else if(arr[1]<s_path[3][1]){  
  79.             if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))  
  80.                 return false;  
  81.         }  
  82.     }  
  83.     else if(arr[0]<s_path[3][0]){  
  84.         if(arr[1]>s_path[3][1]){  
  85.             if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))  
  86.                 return false;  
  87.         }  
  88.         else if(arr[1]<s_path[3][1]){  
  89.             if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))  
  90.                 return false;  
  91.         }  
  92.     }  
  93.     return true;  
  94. }  
  95. function IsOutScreen(arr){ //是否超出场景范围  
  96.     if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1))  
  97.         return true;  
  98.     return false;  
  99. }  
  100. function InOpen(arr){//获得传入在openlist数组的位置，如不存在返回false，存在为true，位置索引保存全局变量num中。  
  101.     var bool=false;  
  102.     for(var i=0;i<openlist.length;i++){  
  103.         if(arr[0]==openlist[i][3][0]&&arr[1]==openlist[i][3][1]){  
  104.             bool=true;num=i;break;}  
  105.     }  
  106.     return bool;  
  107. }  
  108. function InClose(arr){  
  109.     var bool=false;  
  110.     for(var i=0;i<closelist.length;i++){  
  111.         if((arr[0]==closelist[i][3][0])&&(arr[1]==closelist[i][3][1])){  
  112.             bool=true;break;}  
  113.     }  
  114.     return bool;  
  115. }  
  116. function IsPass(pos){ //pos这个点是否和障碍点重合   
  117.     if((";"+n_path+";").indexOf(";"+pos+";")!=-1)  
  118.         return true;  
  119.     return false;  
  120. }  
  121. function Sort(arr){//整理数组，找出最小的F，放在最后的位置。  
  122.     var temp;  
  123.     for(var i=0;i<arr.length;i++){  
  124.         if(arr.length==1)break;  
  125.         if(arr[i][0]<=arr[i+1][0]){  
  126.             temp=arr[i];  
  127.             arr[i]=arr[i+1];  
  128.             arr[i+1]=temp;  
  129.         }  
  130.         if((i+1)==(arr.length-1))  
  131.             break;  
  132.     }  
  133. }  
  134. function main(){//主函数  
  135.        // alert('');  
  136.         GetF(//把原点周围8点传入GetF进行处理。算A*核心函数了 :)，进行求F，更新openlist数组  
  137.             GetRound(s_path[3]) //求原点周围8点  
  138.         );  
  139.   //  debugdiv.innerHTML+="A："+openlist.join('|')+"<br />";//调试  
  140.         Sort(openlist);//整理数组，找出最小的F，放在最后的位置。  
  141.     //debugdiv.innerHTML+="B："+openlist.join('|')+"<br />";//调试  
  142.         s_path=openlist[openlist.length-1];//设置当前原点为F最小的点  
  143.         closelist[closelist.length]=s_path;//讲当前原点增加进closelist数组中  
  144.         openlist[openlist.length-1]=null;//从openlist中清除F最小的点  
  145.     //debugdiv.innerHTML+="C："+openlist.join('|')+"<br />";//调试  
  146.         if(openlist.length==0){alert("Can't Find the way");return;}//如果openlist数组中没有数据了，则找不到路径  
  147.         openlistopenlist.length=openlist.length-1;//上次删除把数据删了，位置还保留了，这里删除  
  148.         if((s_path[3][0]==p_end[0])&&(s_path[3][1]==p_end[1])){//如果到到终点了，描绘路径  
  149.             getPath();  
  150.         }  
  151.         else{//否则循环执行,标准原点  
  152.             maptt.rows[s_path[3][1]].cells[s_path[3][0]].style.backgroundColor="green";setTimeout("main()",100);  
  153.         }  
  154. }  
  155. function getPath(){//描绘路径  
  156.     var str="";  
  157.     var t=closelist[closelist.length-1][4];  
  158.     while(1){  
  159.         str+=t.join(",")+";";  
  160.         maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#ffff00";  
  161.         for(var i=0;i<closelist.length;i++){  
  162.             if(closelist[i][3][0]==t[0]&&closelist[i][3][1]==t[1])  
  163.                 t=closelist[i][4];  
  164.         }  
  165.         if(t[0]==p_start[0]&&t[1]==p_start[1])  
  166.             break;  
  167.     }  
  168.     alert(str);  
  169. }  
  170. function setPos(){//初始原点为起点  
  171.     var h=(Math.abs(p_end[0]-p_start[0])+Math.abs(p_end[1]-p_start[1]))*gw;  
  172.     s_path=[h,0,h,p_start,p_start];  
  173. }  
  174. function set(id,arr){//设置点的类型  
  175.     switch(id){  
  176.         case 1:  
  177.             p_start=arr;  
  178.             maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#ff0000";break;  
  179.         case 2:  
  180.             p_end=arr;maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#0000ff";break;  
  181.         case 3:  
  182.             n_path+=arr.join(",")+";";maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#cccccc";break;  
  183.         default:  
  184.             break;  
  185.     }  
  186. }  
  187. function setflag(id){flag=id;}  
  188. </script>  
  189. <table id="maptt" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000">  
  190. <script>  
  191. for(var i=0;i<h;i++){  
  192.     document.write("<tr>");  
  193.     for(var j=0;j<w;j++){  
  194.         document.write('<td onclick="set(flag,['+j+','+i+']);" bgcolor="#ffffff" width="20" height="20"></td>');  
  195.     }  
  196.     document.write("</tr>");  
  197. }  
  198. </script>  
  199. </table>  
  200. <a href="javascript:setflag(1);">StarPoint</a><br>  
  201. <a href='javascript:setflag(2);'>EndPoint</a><br>  
  202. <a href='javascript:setflag(3);'>Wall</a><br>  
  203. <input type="button" onclick="setPos();main();this.disabled=true;" value="find">  
  204. <div id="debugdiv"></div>  
  205.   
  206. </body>  
  207. </html>  

原文连接：http://www.gamedev.net/reference/articles/article2003.asp
中文翻译：http://data.gameres.com/message.asp?TopicID=25439

我是从http://www.cnblogs.com/jimtomjim/archive/2009/07/20/1527112.html拷贝来的

Tags: a*

Javascript | 评论:0 | 阅读:16550