ShareAA.com

註冊 |登錄

ShareAA.com › 討論區 › Javascript 技術討論 › 查看主題

247

查看

0

回復
返回列表
admin

Rank: 9Rank: 9Rank: 9Rank: 9Rank: 9Rank: 9Rank: 9Rank: 9Rank: 9
go

JS中實現A算法尋路

樓主
發表於 2010-6-1 07:18 | 只看該作者 | 倒序看帖 | 打印


Astar.htm
  1. <html><head><title>use A* to find path...</title></head>
  2. <body style="margin:0px">
  3. <script>
  4. var closelist=new Array(),openlist=new Array();
  5. var gw=10,gh=10,gwh=14;
  6. var p_start=new Array(2),p_end=new Array(2);
  7. var s_path,n_path="";
  8. var num,bg,flag=0;
  9. var w=30,h=20;
  10. function GetRound(pos){
  11.         var a=new Array();
  12.         a[0]=(pos[0]+1)+","+(pos[1]-1);
  13.         a[1]=(pos[0]+1)+","+pos[1];
  14.         a[2]=(pos[0]+1)+","+(pos[1]+1);
  15.         a[3]=pos[0]+","+(pos[1]+1);
  16.         a[4]=(pos[0]-1)+","+(pos[1]+1);
  17.         a[5]=(pos[0]-1)+","+pos[1];
  18.         a[6]=(pos[0]-1)+","+(pos[1]-1);
  19.         a[7]=pos[0]+","+(pos[1]-1);
  20.         return a;
  21. }
  22. function GetF(arr){
  23.         var t,G,H,F;
  24.         for(var i=0;i<arr.length;i++){
  25.                 t=arr[i].split(",");
  26.                 t[0]=parseInt(t[0]);t[1]=parseInt(t[1]);
  27.                 if(IsOutScreen([t[0],t[1]])||IsPass(arr[i])||InClose([t[0],t[1]])||IsStart([t[0],t[1]])||!IsInTurn([t[0],t[1]]))
  28.                         continue;
  29.                 if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0)
  30.                         G=s_path[1]+gwh;
  31.                 else
  32.                         G=s_path[1]+gw;
  33.                 if(InOpen([t[0],t[1]])){
  34.                         if(G<openlist[num][1]){
  35.                                 openlist[num][0]=(G+openlist[num][2]);
  36.                                 openlist[num][1]=G;
  37.                                 openlist[num][4]=s_path[3];
  38.                         }
  39.                         else{G=openlist[num][1];}
  40.                 }
  41.                 else{
  42.                         H=(Math.abs(p_end[0]-t[0])+Math.abs(p_end[1]-t[1]))*gw;
  43.                         F=G+H;
  44.                         arr[i]=new Array();
  45.                         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];
  46.                         openlist[openlist.length]=arr[i];
  47.                 }
  48.                 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")
  49.                 {
  50.                         maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#FF00FF";
  51.                         //maptt.rows[t[1]].cells[t[0]].innerHTML="<font color=white>"+G+"</font>";
  52.                 }
  53.         }
  54. }
  55. function IsStart(arr){
  56.         if(arr[0]==p_start[0]&&arr[1]==p_start[1])
  57.                 return true;
  58.         return false;
  59. }
  60. function IsInTurn(arr){
  61.         if(arr[0]>s_path[3][0]){
  62.                 if(arr[1]>s_path[3][1]){
  63.                         if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))
  64.                                 return false;
  65.                 }
  66.                 else if(arr[1]<s_path[3][1]){
  67.                         if(IsPass((arr[0]-1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))
  68.                                 return false;
  69.                 }
  70.         }
  71.         else if(arr[0]<s_path[3][0]){
  72.                 if(arr[1]>s_path[3][1]){
  73.                         if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]-1)))
  74.                                 return false;
  75.                 }
  76.                 else if(arr[1]<s_path[3][1]){
  77.                         if(IsPass((arr[0]+1)+","+arr[1])||IsPass(arr[0]+","+(arr[1]+1)))
  78.                                 return false;
  79.                 }
  80.         }
  81.         return true;
  82. }
  83. function IsOutScreen(arr){
  84.         if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1))
  85.                 return true;
  86.         return false;
  87. }
  88. function InOpen(arr){
  89.         var bool=false;
  90.         for(var i=0;i<openlist.length;i++){
  91.                 if(arr[0]==openlist[i][3][0]&&arr[1]==openlist[i][3][1]){
  92.                         bool=true;num=i;break;}
  93.         }
  94.         return bool;
  95. }
  96. function InClose(arr){
  97.         var bool=false;
  98.         for(var i=0;i<closelist.length;i++){
  99.                 if((arr[0]==closelist[i][3][0])&&(arr[1]==closelist[i][3][1])){
  100.                         bool=true;break;}
  101.         }
  102.         return bool;
  103. }
  104. function IsPass(pos){
  105.         if((";"+n_path+";").indexOf(";"+pos+";")!=-1)
  106.                 return true;
  107.         return false;
  108. }
  109. function Sort(arr){
  110.         var temp;
  111.         for(var i=0;i<arr.length;i++){
  112.                 if(arr.length==1)break;
  113.                 if(arr[i][0]<=arr[i+1][0]){
  114.                         temp=arr[i];
  115.                         arr[i]=arr[i+1];
  116.                         arr[i+1]=temp;
  117.                 }
  118.                 if((i+1)==(arr.length-1))
  119.                         break;
  120.         }
  121. }
  122. function main(){
  123.                 GetF(GetRound(s_path[3]));
  124.                 Sort(openlist);
  125.                 s_path=openlist[openlist.length-1];
  126.                 closelist[closelist.length]=s_path;
  127.                 openlist[openlist.length-1]=null;
  128.                 if(openlist.length==0){alert("找不到路徑");return;}
  129.                 openlist.length=openlist.length-1;
  130.                 if((s_path[3][0]==p_end[0])&&(s_path[3][1]==p_end[1])){
  131.                         getPath();
  132.                 }
  133.                 else{maptt.rows[s_path[3][1]].cells[s_path[3][0]].style.backgroundColor="#00ff00";setTimeout("main()",100);}
  134. }
  135. function getPath(){
  136.         var str="";
  137.         var t=closelist[closelist.length-1][4];
  138.         while(1){
  139.                 str+=t.join(",")+";";
  140.                 maptt.rows[t[1]].cells[t[0]].style.backgroundColor="#ffff00";
  141.                 for(var i=0;i<closelist.length;i++){
  142.                         if(closelist[i][3][0]==t[0]&&closelist[i][3][1]==t[1])
  143.                                 t=closelist[i][4];
  144.                 }
  145.                 if(t[0]==p_start[0]&&t[1]==p_start[1])
  146.                         break;
  147.         }
  148.         alert(str);
  149. }
  150. function setPos(){
  151.         var h=(Math.abs(p_end[0]-p_start[0])+Math.abs(p_end[1]-p_start[1]))*gw;
  152.         s_path=[h,0,h,p_start,p_start];
  153. }
  154. function set(id,arr){
  155.         switch(id){
  156.                 case 1:
  157.                         p_start=arr;
  158.                         maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#ff0000";break;
  159.                 case 2:
  160.                         p_end=arr;maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#0000ff";break;
  161.                 case 3:
  162.                         n_path+=arr.join(",")+";";maptt.rows[arr[1]].cells[arr[0]].style.backgroundColor="#cccccc";break;
  163.                 default:
  164.                         break;
  165.         }
  166. }
  167. function setflag(id){flag=id;}
  168. </script>
  169. <table id="maptt" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000">
  170. <script>
  171. for(var i=0;i<h;i++){
  172.         document.write("<tr>");
  173.         for(var j=0;j<w;j++){
  174.                 document.write('<td bgcolor="#ffffff" width="20" height="20"></td>');
  175.         }
  176.         document.write("</tr>");
  177. }
  178. </script>
  179. </table>
  180. <a href="javascript:setflag(1);">設置起點</a><br>
  181. <a href='javascript:setflag(2);'>設置終點</a><br>
  182. <a href='javascript:setflag(3);'>設置障礙點</a><br>
  183. <input type="button" value="find">
  184. </body>
  185. </html>
複製代碼
附件: 您需要登錄才可以下載或查看附件。沒有帳號？註冊

TOP

‹ 上一主題|下一主題 › 返回列表

ShareAA.com Inc.

GMT+8, 2010-9-5 13:58, Processed in 0.029432 second(s), 13 queries.

Powered by Discuz! X1

© 2001-2010 Comsenz Inc.