最短路径A*算法实现(Javascript)

cjx186

浏览: 271939 次
性别:
来自: 杭州

最近访客更多访客>>

wzqiang

agustins

uestcbutcher

zlf3865072

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

js、nodejs

算法 JavaScript J#F#

<html><head><title>use A* to find path...</title></head>
<body style="margin:0px">
<script>
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.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"></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>

分享到：

开发实用插件工具网址 | attachEvent和addEventListener 使用方法 ...

2009-11-14 00:00
浏览 1666
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

最短路径A*算法实现(Javascript)

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

最短路径A*算法实现(Javascript)

评论

发表评论

相关推荐

nodejs http请求

HashMap

nodejs 文件系统(fs) 之读写文件

让破ie6支持png

Nodejs Note

nodejs中使用velocity

Windows和CentOS下安装node和NPM和express

jQuery的小知识

JavaScript动态添加CSS

js中escape,encodeURI,encodeURIComponent三个函数的区别

JsDoc Toolkit制作 javascript 文档用

JavaScript点在多边内

贪吃蛇游戏

Ajax不用XMLRequest的Ajax使用方法

JavaScript跨域问题

学习JavaScript闭包

JavaScript中function

全面理解javascript的caller,callee,call,apply概念

用VML画图(一些基本的矢量图)

最近访客更多访客>>