js版本A*寻路算法_javascript技巧-JS Tutorial-php.cn

说到做游戏，必不可少的需要用到寻路算法，一般游戏里的寻路算法大多数都以A*算法为主，这里也就实现了js里采用a*寻路的程序，在51js和蓝色都开了帖。

程序是以前写的，后来也没有修正或者精简，有冗余之处大家还见谅一下。

当然，这个寻路算法也不是最优化的，像幻宇开发的“交点寻径法”也是个中精品，两者可谓各有千秋，只是如果地图很大的情况下，我们会惊讶于“交点寻径法”的迅速。

<title>use A* to find path...</title> <script> /* written by 百晓生 email:jsrpg@126.com qq:156809986 msn:jscript_rpg@hotmail.com */ 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=32,h=32; 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+""; } } } 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()",10);} } function getPath(){ var str=""; var t=closelist[closelist.length-1][4]; while(1){ str+=t.join(",")+";"; 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.join(",")+";";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">'); } document.write(""); } </script> </table> <a href="javascript:setflag(1);">设置起点</a> <a href="javascript:setflag(2);">设置终点</a> <a href="javascript:setflag(3);">设置障碍点</a> <input type="button" onclick="setPos();main();this.disabled=true;" value="find"> <xmp id="xMapData" style="display:none"> 25,0;25,1;25,3;25,4;25,5;25,6;25,7;0,8;1,8;2,8;3,8;4,8;5,8;6,8;7,8;25,8;7,9;25,9;7,10;25,10;7,11;25,11;6,12;25,12;5,13;6,13;25,13;5,14;21,14;25,14;5,15;18,15;19,15;20,15;21,15;25,15;5,16;11,16;12,16;13,16;14,16;15,16;16,16;17,16;18,16;19,16;22,16;25,16;5,17;11,17;23,17;24,17;25,17;5,18;6,18;7,18;8,18;9,18;10,18;11,18;13,18;23,18;24,18;25,18;6,19;7,19;8,19;13,19;23,19;24,19;25,19;6,20;14,20;23,20;24,20;26,20;7,21;8,21;13,21;14,21;15,21;20,21;21,21;22,21;27,21;0,22;1,22;2,22;4,22;5,22;6,22;7,22;12,22;13,22;14,22;16,22;19,22;20,22;21,22;26,22;27,22;28,22;8,23;9,23;10,23;11,23;12,23;13,23;17,23;18,23;19,23;22,23;13,24;14,24;15,24;18,24;21,24;23,24;20,25;24,25;19,26;25,26;26,26;19,28;19,29;19,30;19,31 </xmp>

Php8, I'm coming too

Learn website layout in 30 minutes

Shangguan Oracle Beginner to Proficient Video Tutorial

Your first line of UNI-APP code

Flutter from scratch to app launch

Brother Lian New Linux Video Tutorial

AXURE 9 Video Tutorial (Suitable for Product Manager Interactive Product Design UI)

Zero Basic Proficiency PS Video Tutorial

16 day UI video tutorial to get you started

PS Techniques and Slicing Techniques Video Tutorial

Alibaba Cloud Environment Construction and Project Launch Video Tutorial

Overview of Computer Networks - Basic Knowledge that Programmers Must Master

Essential Tutorial for Programmers - HTTP Protocol Explanation

Websocket Video Tutorial

js版本A*寻路算法_javascript技巧