<html><head><title>use A* to find path...</title></head>
<body style="margin:0px">
<script>
/*
written by hjjboy
email:tianmashuangyi@
qq:156809986
*/
var closelist=new Array(), openlist=new Array();//closelist saves the final result. openlist saves temporary generated points;
var gw=10,gh=10,gwh=14;// Parameter gh is a horizontal additional parameter gwh is an additional parameter of the four corners.
var p_start=new Array(2),p_end=new Array(2);//p_start is the starting point, p_end is the end point
var s_path,n_path="";//s_path is the current point n_path is a string in the style of an obstacle array.
var num,bg,flag=0;
var w=30,h=20;
function GetRound(pos){//Return to 8 points around the origin
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){ //The parameter is 8 points around the origin point
var t,G,H,F;//F, the comprehensive distance value, H, distance value G, horizontal\corner additional calculation
for(var i=0;i<;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 one of the above conditions is met, skip this loop and proceed to the next time.
if((t[0]-s_path[3][0])*(t[1]-s_path[3][1])!=0)//Judge whether the point is in the vertical or horizontal position of the starting point
G=s_path[1]+gwh;//If not in G=14;
else
G=s_path[1]+gw;//If it is G=10;
if(InOpen([t[0],t[1]])){//If the current point already exists in the openlist array
if(G<openlist[num][1]){
[openlist[num][4][1]].cells[openlist[num][4][0]].="blue";//Debug
openlist[num][0]=(G+openlist[num][2]);
openlist[num][1]=G;
openlist[num][4]=s_path[3];
}
else{G=openlist[num][1];}
}
else{
H=((p_end[0]-t[0])+(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[]=arr[i];//Save F and other information to openlist
}
if([t[1]].cells[t[0]].!="#cccccc"&&[t[1]].cells[t[0]].!="#0000ff"&&[t[1]].cells[t[0]].!="#ff0000"&&[t[1]].cells[t[0]].!="#00ff00")
{
[t[1]].cells[t[0]].="#FF00FF";
if(F!=undefined)
[t[1]].cells[t[0]].innerHTML="<font color='black'>"+F+"</font>";
}
}
}
function IsStart(arr){ //Defend whether this point is the starting point
if(arr[0]==p_start[0]&&arr[1]==p_start[1])
return true;
return false;
}
function IsInTurn(arr){ //Judge whether it is a corner
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){ //Is it beyond the scope of the scene
if(arr[0]<0||arr[1]<0||arr[0]>(w-1)||arr[1]>(h-1))
return true;
return false;
}
function InOpen(arr){//Get the position passed in to the openlist array. If it does not exist, it returns false, and exists as true. The position index is saved in the global variable num.
var bool=false;
for(var i=0;i<;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<;i++){
if((arr[0]==closelist[i][3][0])&&(arr[1]==closelist[i][3][1])){
bool=true;break;}
}
return bool;
}
function IsPass(pos){ //Does this point pos coincide with the obstacle point?
if((";"+n_path+";").indexOf(";"+pos+";")!=-1)
return true;
return false;
}
function Sort(arr){//Solve the array, find the smallest F, and place it in the last position.
var temp;
for(var i=0;i<;i++){
if(==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)==(-1))
break;
}
}
function main(){//Main function
alert('');
GetF(//Pause 8 points around the origin into GetF for processing. Calculate the A* core function:), calculate F, and update the openlist array
GetRound(s_path[3]) // Find 8 points around the origin
);
+="A:"+('|')+"<br //Debugging
Sort(openlist);// Organize the array, find the smallest F, and place it in the last position.
+="B:"+('|')+"<br //Debugging
s_path=openlist[-1];//Set the current origin to the smallest point F
closelist[]=s_path;//Ask the current origin is added to the closelist array
openlist[-1]=null;//Clear the smallest point of F from openlist
+="C:"+('|')+"<br //Debugging
if(==0){alert("Can't Find the way");return;}//If there is no data in the openlist array, the path cannot be found
=-1;//The data was deleted last time, but the location was still preserved. Delete here
if((s_path[3][0]==p_end[0])&&(s_path[3][1]==p_end[1])){//If the end point is reached, draw the path
getPath();
}
else{//Otherwise, loop execution, standard origin
[s_path[3][1]].cells[s_path[3][0]].="green";setTimeout("main()",100);
}
}
function getPath(){//Draw the path
var str="";
var t=closelist[-1][4];
while(1){
str+=(",")+";";
[t[1]].cells[t[0]].="#ffff00";
for(var i=0;i<;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(){//The initial origin is the starting point
var h=((p_end[0]-p_start[0])+(p_end[1]-p_start[1]))*gw;
s_path=[h,0,h,p_start,p_start];
}
function set(id,arr){//Set the type of point
switch(id){
case 1:
p_start=arr;
[arr[1]].cells[arr[0]].="#ff0000";break;
case 2:
p_end=arr;[arr[1]].cells[arr[0]].="#0000ff";break;
case 3:
n_path+=(",")+";";[arr[1]].cells[arr[0]].="#cccccc";break;
default:
break;
}
}
function setflag(id){flag=id;}
</script>
<table cellspacing="1" cellpadding="0" border="0" bgcolor="#000000">
<script>
for(var i=0;i<h;i++){
("<tr>");
for(var j=0;j<w;j++){
('<td onclick="set(flag,['+j+','+i+']);" bgcolor="#ffffff" width="20" height="20"></td>');
}
("</tr>");
}
</script>
</table>
<a href="javascript:setflag(1);">StarPoint</a><br>
<a href='javascript:setflag(2);'>EndPoint</a><br>
<a href='javascript:setflag(3);'>Wall</a><br>
<input type="button" onclick="setPos();main();=true;" value="find">
<div ></div>
</body>
</html>