<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title> new document </title> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> </head> <body> <script type="text/javascript"> <!-- function search() { var o=new Date; map.search() alert(new Date-o); } //--> </script> <table id="mapInstance" cellspacing="1" cellpadding="0" border="0" bgcolor="#000000"> <script type="text/javascript"> <!-- //定义常量 var balkStr="*"; //障碍字符 var enptyStr=" "; //空闲字符 var startStr="S"; //开始字符 var endStr="E"; //结束字符 var mapArr = [ "************************************", "* * *", "* E *", "* *********", "* * *", "* * *", "* * *", "* *********** * *", "* * * * *", "* *** * * *", "* * * * *", "* * * *", "* ** * *", "**** **************** **************", "* *", "* * *", "**** ***************************** *", "* *", "* *", "* ******************** ********", "* *", "* *", "* S *", "* *", "************************************" ]; var backupMap=[]; //备份地图 for(var i=0,len=mapArr.length;i<len;i++) { mapArr[i]=mapArr[i].split(""); backupMap[i]=Array.apply(backupMap[i],mapArr[i]); } var startPoint,endPoint; //定义起点,终点对象 //表示坐标 function point(ax,ay) { this.x=ax; this.y=ay; this.parent=null; //父坐标(即通过某坐标才找到此坐标,此坐标就是某坐标的近邻(东西南北)) this.equal=function(p) { if(this.x==p.x && this.y==p.y) return true; else return false; } this.toString=function() { return this.x+":"+this.y; } } (function() { var arrHtml=[]; for(var i=0,rowsLen=mapArr.length;i<rowsLen;i++) { arrHtml.push("<tr>"); var rowStr=mapArr[i]; for(var j=0,cellsLen=rowStr.length;j<cellsLen;j++) { var cellStr=rowStr[j]; var color; switch(cellStr) { case " ": color="#ffffff"; break; case "*": color="#cccccc"; break; case "E": //终结点 color="#ff0000"; endPoint=new point(j,i); break; case "S": //起始点 color="#0000ff"; startPoint=new point(j,i); break; } arrHtml.push("<td style='width:20px;height:20px;background:"); arrHtml.push(color); arrHtml.push("'></td>"); } } document.write(arrHtml.join("")); })(); //--> </script> </table> <input type="button" value="开始寻路" onclick="search()" /> <script type="text/javascript"> <!-- //定义地图对象 //注意:坐标是从0开始的 var map=new Object(); map.ins=document.getElementById("mapInstance"); map.yLen=map.ins.rows.length; //Y轴的最大坐标(-1) map.xLen=map.ins.cells.length/map.yLen; //X轴的最大坐标(-1) map.atom=[startPoint]; //可供搜索的原子,默认为起始坐标 map.isEnpty=function(p) //测试坐标是否是没有障碍物 { var x=p.x; var y=p.y; if(x>=0 && x<map.xLen && y>=0 && y<map.yLen) return backupMap[y][x]!=balkStr; else return false; } map.search=function() //寻路 { var tmpPoints=[]; for(var i=0,len=map.atom.length;i<len;i++) { for(var j=0,wayLen=way.length;j<wayLen;j++) //尝试向东南西北各个方向搜索 { var p=way[j](map.atom[i]); if(p!=null) { backupMap[p.y][p.x]=balkStr; //做标记,表示该坐标已经搜索了 p.parent=map.atom[i]; tmpPoints[tmpPoints.length]=p; //作为新的原子 if(endPoint.equal(p)) { map.searchSucceed(map.atom[i]); //寻路成功 return; } } } } //map.setTrack(tmpPoints); map.atom=tmpPoints; //更新原子 if(map.atom.length>0) map.search(); //if(map.atom.length>0) setTimeout("map.search()",2); } //寻路成功 map.searchSucceed=function(p) { while(p.parent) { map.ins.rows[p.y].cells[p.x].style.backgroundColor="#006600"; p=p.parent; } } map.setTrack=function(ps) { for(var i=0,len=ps.length;i<len;i++) { map.ins.rows[ps[i].y].cells[ps[i].x].style.backgroundColor='#004080'; } } var way= [ //东方(左方:返回左边的坐标,如果左边是边沿或是障碍物则回返null,下面的函数雷同)east: function(p) { p=new point(p.x-1,p.y); if(map.isEnpty(p)) return p; else return null; }, //西方(右方)west: function(p) { p=new point(p.x+1,p.y); if(map.isEnpty(p)) return p; else return null; }, //北方(上方)north: function(p) { p=new point(p.x,p.y-1); if(map.isEnpty(p)) return p; else return null; }, //南方(下方)south: function(p) { p=new point(p.x,p.y+1); if(map.isEnpty(p)) return p; else return null; } ] //--> </script> </body> </html> 运行代码复制代码另存代码
<html><head> <meta http-equiv="Content-Type" content="text/html; charset=gb2312"> <title>魔王</title> <style> .main{font:16px} .ww0{width:20;height:20;background-color:#cccccc} .wws{width:20;height:20;background-color:#006600} .wwe{width:20;height:20;background-color:#FF0000} .ww1{width:20;height:20;background-color:#000000} .wwX{width:20;height:20;background-color:#FF9900} </style> <body> <input type=button onclick="findpath()" value="寻路"> <input type=button onclick="refreshpath()" value="刷新"> <input type=button onclick="set(1)" value="设置起点"> <input type=button onclick="set(2)" value="设置终点"> <input type=button onclick="set(0)" value="设置地图"> <TT><div id=main class=main nowrap></div></TT> </body> <script language="javascript"> main.write=function anonymous(string) { this.innerHTML+=string; } var w=100; var h=100; var arr=new Array(w*h); var map=new Array(w*h); var path=new Array(); var s=w*1+1,e=w*(h-2)+w-2; var stri=""; var status=0;var status2=0; for(i=0;i<w*h;i++) { if(i<w||i>=w*h-w|| i% w==0||i% w==w-1) { arr[i]=1; stri+="<a id=a"+i+" class=ww"+arr[i]+"></a>"; } else { arr[i]=0; stri+="<a id=a"+i+" onclick=\"change("+i+")\" class=ww"+arr[i]+"></a>"; } //document.write(arr[i]); if((i+1)% w==0)stri+="<br>"; } main.write(stri); var status=0; function change(k) { if(status==0) { arr[k]=1-arr[k]; refresh(k); status2=0; } else if(status==1) { refresh(s); s=k; mark(s,"S"); Init(s,w,arr); status2=1; } else if(status==2) { refresh(e); e=k; mark(e,"E"); } } function refreshpath() { for(i=1;i<path.length;i++) { refresh(path[i]); } } function refresh(k) { eval("a"+k+".className='ww'+arr[k]"); } function mark(k,c) { eval("a"+k+".className='ww'+\""+c+"\""); } function set(k) { status=k; } function findpath() { for(i=1;i<path.length;i++) { refresh(path[i]); } if(status2==0) { Init(s,w,arr); status2=1; } path=Path(s,e); for(i=1;i<path.length;i++) { mark(path[i],"X"); } } //StartPos起始位置,EndPos目标位置,size每行长度,map一维数组地图 function Init(StartPos,size,omap) { for(i=1;i<omap.length;i++)map[i]=omap[i]; var dat1=new Date();//寻路算法开始时间！！！！！！！！！！！！！！！！！！！！！！！！ var pointer=new Array(map.length) var oldnodes=new Array(); oldnodes[0]=StartPos; map[StartPos]=" S"; var newnodes=new Array(); while(1) { for(i=0;i<oldnodes.length;i++) { var node; var x1=0; var x2=0; var x3=0; var x4=0; node=oldnodes[i]+1; if(map[node]==0) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } if(map[node]!=1){x2=1;x4=1; } node=oldnodes[i]-1; if(map[node]==0) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } if(map[node]!=1){x1=1;x3=1;} node=oldnodes[i]-size; if(map[node]==0) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } if(map[node]!=1){x1=1;x2=1;} node=oldnodes[i]+size; if(map[node]==0) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } if(map[node]!=1){x3=1;x4=1;} node=oldnodes[i]-size+1; if(map[node]==0&&x2) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } node=oldnodes[i]+size+1; if(map[node]==0&&x4) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } node=oldnodes[i]-size-1; if(map[node]==0&&x1) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } node=oldnodes[i]+size-1; if(map[node]==0&&x3) { newnodes[newnodes.length]=node; map[node]=oldnodes[i]; } //if(oldnodes[i]==202)alert(newnodes); } if(newnodes.length==0)break; oldnodes.length=0; for(i=0;i<newnodes.length;i++) { oldnodes[i]=newnodes[i]; } newnodes.length=0; } var dat2=new Date();//寻路算法完成时间！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ alert(dat2.getTime()-dat1.getTime()); } function Path(StartPos,EndPos) { var j; if(map[EndPos]==0) { alert("No path!"); return 0; } var resault=new Array(); while(EndPos!=StartPos) { resault[resault.length]=EndPos EndPos=map[EndPos]; } return resault; } </script> 运行代码复制代码另存代码
