打印

[原创]JS中实现A*算法寻路

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

1^# 大中小发表于 2006-8-6 17:58

程序说明:程序中的障碍点设置后本次寻路中不可修改!
本程序完全采用A*寻路的理念,仅供学习之用!
由于积分不够，还不可以上传压缩包，因此粘贴所以程序代码如下：

<html><head><title>use A* to find path...</title></head>
<body style="margin:0px">
<script>
/*
written by hjjboy
email:tianmashuangyi@163.com
qq:156809986
*/
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>

提示：您可以先修改部分代码再运行

;)

[ 本帖最后由 hjjboy 于 2006-8-6 18:05 编辑 ]

本帖最近评分记录

hutia 威望 +4 原创内容 2006-8-6 19:47

开发JSRPG

TOP

做西部数码代理.Cn1元国际45元 | 将虚拟化进行到底

hutia

诘屈聱牙

荣誉管理团队

帖子: 4718
体力: 14636
威望: 383
当前: 江苏苏州

专长 JS,PHP,ASP

2^# 大中小发表于 2006-8-6 19:49

有关算法的原创文章还是一定要支持的.....

俺是外行....能不能麻烦解释一下 A* 算法？也算给俺扫盲......

hutia归来...
老婆的小店
hutia的个人站点 - 有问题去这里问我

TOP

美橙vps独立IP月付189元

BlueMiracle

中级会员

帖子: 127
体力: 436
威望: 8
当前: 北京海淀区
离线: 62 天

专长 JS,PHP,AS

3^# 大中小发表于 2006-8-6 22:01

不错，上次也有一个蚁群算法js版，现在很多人喜欢搞人工智能了，呵呵

收藏。

http://www.never-online.net

TOP

请大家尊重和保护奥运知识产权。

bound0

老饕

版主

帖子: 3383
体力: 8402
威望: 273
当前: 北京海淀区

专长 JS,Perl,产品设计

4^# 大中小发表于 2006-8-7 22:07

很好呀，做游戏时经常用到的算法（鼠标点某个位置，人物自己找路走过去）。可以参考51js那边的几个JS游戏。

不过，好像还不完善呢，明明可以走过去的，却说“找不到路径”。

[ 本帖最后由 bound0 于 2006-8-7 22:11 编辑 ]

[Bound0 专题列表]QUE SAIS-JE?
生物信息技术支持动漫论坛动漫分享群：45274013

TOP

还在为头像烦恼?还在为不能关注好友动态烦忧?快来蓝色理想家园吧!

powerzl

清风听雨

中级会员

帖子: 212
体力: 487
威望: 0
离线: 3 天

5^# 大中小发表于 2006-8-8 09:18

是啊，楼主能不能解释一下 A* 算法呢？

高雅清香的春兰秋桂，不慕求虚荣，不阿谀权贵；芳香出于自然，不是为了博取别人欣赏。

TOP

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

6^# 大中小发表于 2006-8-8 19:08

引用:

原帖由 bound0 于 2006-8-7 22:07 发表
很好呀，做游戏时经常用到的算法（鼠标点某个位置，人物自己找路走过去）。可以参考51js那边的几个JS游戏。

不过，好像还不完善呢，明明可以走过去的，却说“找不到路径”。

不会吧？
我已经试过了，是肯定能够寻找到路径的。
这个算法，我把穿越拐角的情况设定为不允许，因此在走拐角的时候必须走一个直角。

该算法也是我在自己做的JS游戏《新剑侠情缘》中运用的寻路算法，测试发现没有出现问题。

如果出现了问题，麻烦贴张图上来好吗？谢谢！

[ 本帖最后由 hjjboy 于 2006-8-8 19:22 编辑 ]

开发JSRPG

TOP

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

7^# 大中小发表于 2006-8-8 19:21

引用:

原帖由 powerzl 于 2006-8-8 09:18 发表
是啊，楼主能不能解释一下 A* 算法呢？

其实要说A*算法，网上已经有了许多的教程了，我也就不多说。

A*算法主要用到的是一个公式：F=G+H；
G，是指起始点到当前点的距离。
H，是指当前点到目的点的距离。
F，是两者之和。

为了方便起见，两点之间的距离直接取两者之间X方向的距离差+Y方向上的距离差。

在A*算法中，主要就是搜索一个点的周围八个方块（去掉不可走的），然后计算各个方块的F值，取F值最小的作为下一步需要走的方格，而把当前方格作为下一步的父方格。然后另下一步作为当前访格。依此轮回，直到找到目的方格为止。

我只是把我自己制作该算法时候的一些思路写出来，言辞难免粗糙，各位可到网上搜索A*算法教程自行参考。

开发JSRPG

TOP

bound0

老饕

版主

帖子: 3383
体力: 8402
威望: 273
当前: 北京海淀区

专长 JS,Perl,产品设计

8^# 大中小发表于 2006-8-8 20:06

没能再现当时的异常，可能是当时设置不当吧。程序没有问题。:)

[Bound0 专题列表]QUE SAIS-JE?
生物信息技术支持动漫论坛动漫分享群：45274013

TOP

cnbruce

布鲁斯狼

荣誉管理团队

帖子: 7686
体力: 13075
威望: 143
当前: 江苏扬州

专长 ASP,SEO,市场

9^# 大中小发表于 2006-8-9 09:30

这个要加分,去年摆渡程序比赛ACRush就使用的Astar算法

http://astar.baidu.com/data/demo/ACRush.txt

经典可以来场经典算法大演练啊

[ 本帖最后由 cnbruce 于 2006-8-9 09:36 编辑 ]

2008 · 布鲁斯狼的BLOG
-------------------------------------------------------------
艾生活·i0514·小艾生活网

TOP

蓝色

蓝蓝的闪客

管理员

帖子: 18205
体力: 19102
威望: 184
当前: 湖南长沙

专长 产品设计,网站运营,社区

10^# 大中小发表于 2006-8-9 10:35

看看 flash里的研究。这个在游戏中用的也很多。
先点红色块确定起点，再点击任意终点，开始寻路
点击白色框，制造黑色障碍。
RESET，重置随机地图。
感觉速度比JS的快一点。

另外文章的四个分页，做了算法的说明。

http://www.blueidea.com/tech/multimedia/2005/3121.asp

只要集中精力，五年成专家，十年成权威，十五年成世界顶尖。

TOP

renaski

洛林

钻石会员

帖子: 2140
体力: 6562
威望: 6

11^# 大中小发表于 2006-8-9 10:42

看的我头晕

msn:renaski@hotmail.com

TOP

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

12^# 大中小发表于 2006-8-9 21:09

回复 #9 cnbruce 的帖子

稍微看了下你个的那个代码，应该是采用的C写的吧？
应该说C与JS这种解释型的语言速度上是不可比拟的，如果在很大的范围内的话

大虾觉得如何？

开发JSRPG

TOP

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

13^# 大中小发表于 2006-8-9 21:20

回复 #10 蓝色的帖子

看了那个FLASH的寻路算法，真的很不错！
但要是说到速度的快慢，应该JS不会输给AS的吧？

我修改了程序，把延时改成了0，应该很快就能找到终点了！

PS：用JS和AS的字符串累加做了一个速度测试，发现如果执行90000次循环的话，那么JS会死一段时间，然后时间超长。而AS才31ms左右，郁闷！

开发JSRPG

TOP

forfor

钻石会员

帖子: 1472
体力: 5560
威望: 0
离线: 434 天

14^# 大中小发表于 2006-8-9 23:17

不错!
我对于算法还真没研究过,很有启发啊!
我原来用过的寻路算法没用到H计算这一块,可能对迷宫这样复杂的地形帮助不是很大吧,没事儿加上试试看.

自己动手丰衣足食
-------------------------
猫了好长时间了,出来透透气~

TOP

leobluewing

初级会员

帖子: 32
体力: 69
威望: 1
离线: 14 天

15^# 大中小发表于 2006-8-10 10:14

这个不错当时看那个用JS写的SC的时候研究过寻路算法了..

不过楼主这个很直接明了,收了谢谢楼主 ~~

TOP

蓝色

蓝蓝的闪客

管理员

帖子: 18205
体力: 19102
威望: 184
当前: 湖南长沙

专长 产品设计,网站运营,社区

16^# 大中小发表于 2006-8-11 10:12

如果楼主有兴趣，可以看一下这个帖，
我估计性质是一样的。

http://bbs.blueidea.com/viewthread.php?tid=1640729

另外NCS还有这些个帖。
http://bbs.blueidea.com/viewthread.php?tid=2402659

寻路算法中，我最佩服的还是微软帝国时代二的算法。
8个种族。上限200，1600个点在寻路，而且还有队列模式。还有地图起伏。
在电脑上玩起来。还算好。
特别觉得难的地方是两个人走同样的路卡住后，又选择同样的方向让路，结果两个人始终卡在那里。
怎么保证不卡死在那儿。真是不容易哈。

只要集中精力，五年成专家，十年成权威，十五年成世界顶尖。

TOP

bound0

老饕

版主

帖子: 3383
体力: 8402
威望: 273
当前: 北京海淀区

专长 JS,Perl,产品设计

17^# 大中小发表于 2006-8-11 13:18

引用:

原帖由蓝色于 2006-8-11 10:12 发表
特别觉得难的地方是两个人走同样的路卡住后，又选择同样的方向让路，结果两个人始终卡在那里。
怎么保证不卡死在那儿。真是不容易哈

这个貌似好办呢：一个节点将要有人走的时候，对其他人来说，节点的G值增加就可以了（其他人就会不太愿意走同一点了）。

[Bound0 专题列表]QUE SAIS-JE?
生物信息技术支持动漫论坛动漫分享群：45274013

TOP

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

18^# 大中小发表于 2006-8-11 17:49

引用:

原帖由蓝色于 2006-8-11 10:12 发表
如果楼主有兴趣，可以看一下这个帖，
我估计性质是一样的。

http://bbs.blueidea.com/viewthread.php?tid=1640729

另外NCS还有这些个帖。
http://bbs.blueidea.com/viewthread.php?tid=2402659

寻路算 ...

那些帖子都是很不错的教程呢，说得比我清楚。

还有，你说的那个微软的帝国时代二的算法在哪里可以参考到？？
要没有，又这个游戏的地址吗？

谢谢蓝色了

开发JSRPG

TOP

hutia

诘屈聱牙

荣誉管理团队

帖子: 4718
体力: 14636
威望: 383
当前: 江苏苏州

专长 JS,PHP,ASP

19^# 大中小发表于 2006-8-11 17:53

引用:

原帖由蓝色于 2006-8-11 10:12 发表
如果楼主有兴趣，可以看一下这个帖，
我估计性质是一样的。

http://bbs.blueidea.com/viewthread.php?tid=1640729

另外NCS还有这些个帖。
http://bbs.blueidea.com/viewthread.php?tid=2402659

寻路算 ...

...........汗.....星际的算法比帝国的优秀的多的多.......

hutia归来...
老婆的小店
hutia的个人站点 - 有问题去这里问我

TOP

hjjboy [楼主]

初级会员

帖子: 19
体力: 47
威望: 4
离线: 25 天

20^# 大中小发表于 2006-8-11 18:14

引用:

原帖由 hutia 于 2006-8-11 17:53 发表

...........汗.....星际的算法比帝国的优秀的多的多.......

原来帝国时代是个PC游戏啊？郁闷，我以为是JS游戏呢

开发JSRPG

TOP

xbstu2006

白骷争宝髅气

银牌会员

帖子: 1282
体力: 2113
威望: 73
当前: 浙江杭州
离线: 2 天

专长 PHP,AS

21^# 大中小发表于 2006-12-6 18:03

引用:

原帖由 hjjboy 于 2006-8-11 18:14 发表

原来帝国时代是个PC游戏啊？郁闷，我以为是JS游戏呢

大汗........

AS3调试器!

TOP

moonsun

银牌会员

帖子: 5650
体力: 1721
威望: 19

22^# 大中小发表于 2006-12-23 13:16

起点和重点重叠的时候出现BUG

69.4.239.126/bbs

TOP

yanyangtian

新手上路

帖子: 8
体力: 21
威望: 0
当前: 安徽合肥
离线: 43 天

23^# 大中小发表于 2007-11-1 13:27

我还是没弄明白!

TOP

imGoL

海盗先生

初级会员

帖子: 134
体力: 156
威望: 0
当前: 广东湛江
离线: 195 天

24^# 大中小发表于 2007-11-1 14:29

我做了个比较变态的测试.

附件: 您所在的用户组无法下载或查看附件，您需要注册/登录后才能查看！

.com

TOP

[原创]JS中实现A*算法寻路

引用:

引用:

回复 #9 cnbruce 的帖子

回复 #10 蓝色 的帖子

引用:

引用:

引用:

引用:

引用:

回复 #10 蓝色的帖子