TAT.vorshen 与 A-Star 不同的像素级寻路算法下
In Web开发 on 2016年03月04日 by view: 1,142
0

先贴上文地址:http://www.alloyteam.com/2016/03/and-a-star-on-different-pixel-pathfinding-algorithm/

之前说到了起点和终点连线平移方式的不足,那这篇文章就介绍另一个给力的方法

演示地址:

http://westanhui.github.io/navigate/index2.html

注意:点击画障碍物,通过左键单击画多边形最后右键自动闭合图像

 

上文中我们绕过障碍物的核心是起点和终点的连线扫过障碍物,当障碍物为多边形的时候,扫过障碍物一定意味着最后是扫过了障碍物上的某一个点

2

那么这一点也一定能成为必过点,那我们就先尽可能的找到每一个点,把它当成必过点来看

3

然后我们把“ 这些必过点尽可能的相连起来,再与起点和终点相连起来,从里面找出最短的一条路径来”,这是整个寻路的核心,已经用语言描述了出来,下面是用程序表现的一些问题

1、哪些点可能成为我们的必过点,不可能所有的点都是的,比如下图

4

在这里我的判断方法是取起点或终点中的一点,然后找到障碍物上能和其直接相连的点(1 级点,不止一个)

然后遍历这些 1 级点,找到障碍物中可以直接相连的 2 级点们…… 以此内推,一直找到某一个点可以直接与终点相连

对,就是树的思想!

2、哪些点是被算作为可直接相连的

这个对于人眼看来很容易区分,但对于计算机稍微有些麻烦

567

图中红色的连线都算作可以直接相连,而下面这样的则不算做相连

8

程序中的判断一定要考虑周全

3、择优取点

之前说了整个核心是树的思想,不停的找某个点的下级可行直连点,什么是可行直连点,请点击下面 gif 图

gif5新文件

看下图中障碍物上标了数字的点

由起点出发,起点的直连点有三个,1,2,3

然后我们来看 3 点的直连点有哪些,图中轻易可知有四个,起点、1,、4、5 这几个点

哪些被算作可行直连点呢,起点不可以,因为它是 3 点的父级点,1 也不可以,它是 3 点的兄弟节点

所以在这里我们认为 4 点和 5 点是 3 点的可行直连点,同理可以得到 5 点的可行直连点只有终点

再用一个树的结构图来表示一下

14

我们过滤无用的直连点越多,程序的性能就会越快,后面的程序会具体的说下这些择优是如何判断

4、哪条路径是最短路径

10

我们都知道了每条路径的每个点,计算一下就知道最短路径了~

 

再贴演示地址:

http://westanhui.github.io/navigate/index2.html

这里没有开启 debug 了,因为 debug 也没啥好显示的…… 下面是核心程序,完整程序请右键源代码~

起点、终点、每个障碍物的点,格式是这样的

x,y 是坐标,isObstacle 是标示是否是障碍物点

index 是索引,其中 start 为-1,end 为-2,障碍物的从 0 开始递增,不要问我为什么-1 和-2…… 拍脑袋

childs 是一个数组,存着该点的可行直连点,并不是直连点哦

注意:存着的对象是深拷贝的!为了方便下面的 parent 属性唯一!

parent 就是该点的父级点,最后用来确定路径的

 

入口的代码还是很简单的,然后先看①,这里对子节点进行一次过滤,这个过滤就是择优的一种

过滤的机制在于子节点是否可以直接到达终点,比如

11

图中粉色点已经可以直达终点,那么我们就把它加入 globalPath 这个最终的路径数组,也把它加入到 avoid 这个规避对象里面去,见标记③

然后再看②,isEnd 属性为 true,这就是对已经当过父级的点不再进行可行直连点判断

之前说过一个是父级,还有一个同级的点,都会进行择优过滤,看④

findChild 函数的作用是找寻一个点(第一个参数)的可行直连点,第三个参数传入的就是这个点的同级兄弟节点

这是整个程序核心的 findChild 函数,第一个 for 循环是依次找每一个点,来判断是否是可行直连点,第二个 for 循环就是具体的判断流程。先看①

假设第一个 for 循环取了一个点 A,要开始判断是否为直连点,然后第二个 for 循环遍历,isLineCross 是判断两条线是否相交的情况,这在上文中也有说过,注意!这里我们需要避免 A 点本身,因为一定是相交,①这里做的判断就是这事

然后再看②

12

起点和粉色(index 为 0)相连的时候,我们判断粉色点的直连点

1 点和 3 点都是直连点,但是 0-1 线和 0-3 线是相交的,所以我们要考虑到这样的情况,两个点的 index 差为 1,或者为障碍物的首尾

注意函数中有一个 mid 变量还有③这块,这里的作用是判断不相交,因为出现这种情况时

13

粉色线我们可以通过 isLineCross 判断出来相交,但是绿色线不会,被我们自己①那时的处理给规避掉了

所以这里取了两点中点进行二次验证,是否在障碍物的内部

最后就是计算距离和展示部分

这里的代码方便理解,就关注下①,当时我就二了,没有带上 Math.sqrt 自以为可以节省性能,然后就炸了…… 为什么就不用说了吧~不知道的回去问数学老师~~

讲解的都是核心一些的代码,其他的一些请看源代码~如果有疑惑欢迎提出,大家一起交流进步~

总结一下上下两篇文:上文讲解了连线平移的思想,也总结了不好的地方,就是对点和障碍物的位置要求较高,但是对障碍物的形状要求很低,下文要求障碍物的形状为多边形(不过目前来说像素级游戏的障碍物非多边形的很少吧= =,我能想到的也就是圆去做障碍物了……),推荐大家采取下文的方法

 

结语:总算码完了上下文,累死。在最后多说一句,大部分游戏还是推荐用格子做,因为格子的存在能减少能多事情,或者说减少很多计算量,打比方就是真· 随机生成(并不是标死多个出生点那种随机生成),格子就方便很多。

大家如果有什么想法和 idea 欢迎留言讨论~

原创文章转载请注明:

转载自AlloyTeam:http://www.alloyteam.com/2016/03/with-a-star-under-different-pixel-pathfinding-algorithm/

发表评论