Egret社区
以前看过一点,但一直没自己写过,这次刚好要用到,就顺便写了一个。A*寻路大致算法都是差不多的,不过不同游戏不同需求,我这次写的会有一些细节上的优化,不过暂时还没有比较,是否真的会提高效率也是抛砖引玉,想和大家探讨一下,希望有经验的朋友多多指点
第一步当然是先上Demo:多人离散寻路Demo演示

本贴目录:
1、首先以我的理解大概介绍了A*算法的基本思路
2、介绍了我的代码中的不同的实现方法与优化(也许不是新的东西,不过我之前也没见过,是自己摸索出来的,效率是否比常规的好还有待验证,欢迎讨论指点)
3、部分源码介绍
4、源码献上~。~

一、A*算法基本思路介绍

A*算法有很多,考虑到一些新人朋友,我这里就按照我的认识简单介绍一下,如果讲晕了的话就度娘一下哈~

图片都是网上经典的图,

图1

图1

如图1所示,现在我们要从小绿到小红,那么在不会大跳不会飞的情况下,就必然会首先通过小绿周围八个点中的一个,那么到底我们要选哪个点呢,我想大家一定有一个共识,那就是我们选的点,不光要离小绿近,也要离小红近,也就是这个点到小绿的距离+到小红的距离,应该是最小的一个。如图,这八个点中都有三个数字,这其中左下角的就代表和小绿的距离,右下角的就是和小红的距离,而左上角的数字就是这两个距离求和。

那么这几个数字都是如何得到的呢,我们假设,一个格子的距离是10,那么根据勾股定理可以得到斜角的距离就是根号二*10=1.414.....*10
这里我们就取近似值约等于14.这里我们采用的是曼哈顿式(来源于格子形的曼哈顿街道,也就是横着距离多少,竖着距离多少,再加起来)来求解距离,那么大家应该能轻松明白图一中各个数字的意义了吧,不妨自己推算一下。

我们用一些字母来代替这些大白话,到小绿的距离我们称为移动耗费,用字母G来表示,到小红的距离我们成为预估移动耗费,用字母H来表示,二者的和称为预期总移动耗费,用字母F来表示。(开个小差,有童鞋问为什么用这三个字母呢,Maybe G=Go,代表走了多少,H代表Home,离家还有多远,F代表“Fuck,居然这么麻烦” )

这里有一点需要注意,就是起止点如果已经定好了,那么H值就是不会变的了,但G值会变。为什么呢,因为H值是到终点的耗费,终点不变,H自然不变。但G值则取决于自己的父节点(后面会介绍),也就是实际某点的G值=自己到父节点的G+父节点的G。

A*算法属于启发式算法,整个A*算法的流程先从起点到终点,再从终点到起点回溯的过程,在每一步都找当前认为最近的点。细心的童鞋会注意到周围八个格子中还有一个小箭头,这个箭头呢就是代表“我从哪里来,我滴朋友”,也就是都指向自己的上一个节点(父节点)。我们每次使用一个新节点作为当前点时,都会把他周围没有使用过的点指向自己(那么使用过的点怎么办呢,这就要看这个使用过的点,是从原来的父节点得到的F值小,还是以新节点得到的F值小,如果新的小,果断大义灭亲,可以见得,大义灭亲以后,自己的G值就变了)。

对于A*算法,里面有两个非常重要的东西,就是-开启列表和关闭列表
开启列表:咱们还是来看图1,抛去起点外,我们在它周围选了八个点来比较选取最优点,那么这八个点就是在开启列表里了,简而言之,我们的待比较点,都会放在开启列表里。
关闭列表:还是图1,我们把八个点放到开启列表里后,起点就没用了,因为我们已经使用完了,这时候我们就把起点放到关闭列表,简而言之,我们计算过的点,都会放在关闭列表里

那么怎么来一步步的选取开启列表,存放关闭列表呢,,这也是一个主要部分了。经过上面的介绍再来理解这个就不太难了,下面我们来看图2:

图2

图2

首先选取起点周围八个点放入开启列表,起点放入关闭列表,选取最小F值得点,即右边F值为40的点,这时候我们就以F40为基准点,把他周围点放入开启列表,这时候我们发现,F40右边三个都是墙,所以不管,左边是起点已经放入关闭列表了,不管,那么就还剩下四个点,而这四个点之前都已经放入到开启列表了,前面说过,这时候,我们就看,如果以F40为基准点来计算这四个点的F值会不会更小,很容易看出来不会的,所以把F40放到关闭列表,不管了。然后怎么办呢,当然是继续从开启列表里找F值最小的点,那么现在开启列表里还剩下七个点,显然又上和右下的点F值最小并且相同,这时候我们就随便选一个就行了,图中选了右下点,然后我们把右下点放入关闭列表,选取他周围的点放入开启列表,重复的部分就不说了,主要就是右下点,这个点其实是被障碍物蹩脚了,所以这个点也不会放入开启列表(注:是否蹩脚取决于项目实际需求),依次递归,如果路径是通的的话,我们最终是可以把终点放入开启列表的,这时候,寻路结束。

那么路径怎么得到呢,刚只是从头到尾走了一遍,具体我们选的路径是哪些还没有存出来呢呀,这时候就要用到父节点这个东西了。我们从终点开始,依次找自己的父节点,并把该点存到路径数组中,寻到头的时候,我们就得到了一条,从起点到终点的路径。

=============好了,A*寻路的基本逻辑到这里就说完了,下面我来说一下我的代码===========
二、摸索部分,有待验证
我在写这个寻路算法的时候,就感觉每次在把周围点加入开启列表时,都要在关闭列表里搜一遍,再从开启列表里搜一遍,如果数量大的话,这个计算量是指数增加的,那么可不可以避免每次都在一个大数组中进行搜索操作呢,于是我采用了以空间代价换时间的方法。


那就是在每个节点记录一个状态,这个状态显示了当前节点是在关闭列表还是在开启列表中。但是如果在每个节点加这样一个状态就意味着每寻路一次就要进行一遍状态清理,这也是得不偿失的。于是我在寻路算法中加入了一个寻路版本号的东西。这样就既可以避免每次寻路中耗费在开启/关闭数组中搜索的耗费,也可以避免每次进行状态清理了。

三、部分源码介绍
使用起来非常方便,只需要new一个寻路对象,把地图数据赋值进去,然后就可以获取寻路路径了,使用 代码片段如下:
[mw_shl_code=applescript,true]var szmap: Array<any> = [
            [0, 0, 0, 0],
            [0, 0, 0, 0],
            [0, 0, 0, 0],
            [0, 0, 0, 0]
        ];
        var maze:Astar.Maze = new Astar.Maze();
        maze.initMaze(szmap);
        var szpath: Array<egret.Point> = maze.findPath(0, 0, 5, 5);[/mw_shl_code]


//额,刚帖子字数超出上线了,剩下几部分源码大家就下载了看吧,Orz...

好了,感谢您的浏览,下面献上源码VS工程包,欢迎大家多多讨论指点~.~



Astar.zip

399.02 KB, 下载次数: 505, 下载积分: 银子 -1

A*寻路-egret版-vs工程文件包

参与人数 1贡献 +1 收起 理由
A闪 + 1 赞一个!

查看全部评分

分享到 :
16 人收藏

51 个回复

倒序浏览
f111fei  官方团队 | 2014-12-23 16:48:08
感谢分享,挺不错的教程
yicaoyimu  初窥堂奥 | 2014-12-23 16:54:14
那就是在每个节点记录一个状态,这个状态显示了当前节点是在关闭列表还是在开启列表中。但是如果在每个节点加这样一个状态就意味着每寻路一次就要进行一遍状态清理,这也是得不偿失的。于是我在寻路算法中加入了一个寻路版本号的东西。这样就既可以避免每次寻路中耗费在开启/关闭数组中搜索的耗费,也可以避免每次进行状态清理了。

支持一下,赞~~~,之前as的时候也基本是这样做的
lzdmimo  登堂入室 | 2014-12-23 16:54:20
NB了。膜拜中。算法什么的还真不会
7yue  官方团队 | 2014-12-23 16:56:12
哇塞!这个帖子真心是大大地好啊!!!
csujin  圆转纯熟 | 2014-12-23 17:03:09
yicaoyimu 发表于 2014-12-23 16:54
那就是在每个节点记录一个状态,这个状态显示了当前节点是在关闭列表还是在开启列表中。但是如果在每个节点 ...

哦,多谢指点,现在效率还不是很理想,我还要多看看成熟的都是怎么写的
csujin  圆转纯熟 | 2014-12-23 17:09:29
7yue 发表于 2014-12-23 16:56
哇塞!这个帖子真心是大大地好啊!!!

感谢7yue大神来访,持续努力中~
csujin  圆转纯熟 | 2014-12-23 17:22:14
eperfect 发表于 2014-12-23 17:15
学习了,寻路算法的消耗在cpu运算,搭配分帧运算效果更佳

您能大概说说分帧运算是什么意思么,有相关文档可以看看么~感谢您的宝贵意见,谢啦
xsstomy  渐入佳境 | 2014-12-23 17:49:57
顶帖
csujin  圆转纯熟 | 2014-12-23 18:00:50
eperfect 发表于 2014-12-23 17:45
分帧运算就是把原本一帧运算的逻辑拆分为多个帧去运算
你的demo是多人寻路,有一个思路就是把人分开,比 ...

哦,酱紫啊,学习了~后面尝试一下
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|京网文[2014]0791-191号|京ICP证150115号|Egret社区 ( 京ICP备14025619号 )

Powered by Discuz! X3.4 © 2001-2019 Comsenz Inc.

返回顶部