《Unity3D高级编程之进阶主程》第十章,地图与寻路(二) 寻路网格的构建

寻路网格构建

上一节我们了解了A星寻路的算法及其优化,A星寻路只是算法,需要配套的模块和工具链支撑,单独的一个A星无法运作因为它只是一个算法。

需要什么样的模块和工具链呢,我们这节就来讲一讲,最重要的配套模块‘寻路网格构建’。除了网格构建外,还有动态障碍物,以及地图和地形的构建,最后再配上A星寻路,才形成最终的地图和寻路。

===

1.用二维数组构建虚拟的方形网格

最最简单的也是最最易于理解的网格构建方式要属二维数组网格,它是一个二维数组,每个元素就代表一个方格,方格中数字0代表无障碍,1代表有障碍,或者也可以是数字1代表障碍难度为1,比1大的数字代表更高的障碍难度,数字越大障碍难度越大,到达某个数字比如999,则认为该障碍难度完全无法跨越。

举个二维网格的例子:

    [0][0][0][0][0][0]
    [1][1][0][0][1][1]
    [1][1][0][1][1][1]
    [0][1][0][0][1][1]
    [0][0][0][1][1][1]

这是一个 5 * 6 的二维数组,0代表无障碍,1代表有障碍。我们很清晰的看到这张地图中有哪些是障碍点,在这张地图中,我们从任意一个无障碍点出发都能到达任意一个无障碍点,因为所有的0都是联通的。

用二维数组代表地图是比较抽象的,那么怎么和地图匹配,怎么与地图真正的关联起来呢?

我们在脑海中需要把地图也切成 5 * 6 这样30块地,比如这个张地图总共大小为 50米 * 60米 的大小,假如左下角为[0,0]位置,我们从0,0点开始,10,10点到0,0点为一个方块与[0,0]这个点关联,坐标10,10到坐标20,20为一个方块与[1,1]这个点关联,0,10点开始,10,20点到0,10点的方块与[0,1]这个点关联,依次类推。

每个在地图上的10 * 10大小的一个块正方形的区域,都与数组关联。这样我们在用A星寻路在数组中寻路后的结果都可以一一对应到地图上。

比如,我们寻路到从[0,0]点开始,到[1,4]点的路径为,[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4],反应到地图上时,是0,0点开始移动,先移动到第一个方块也就是(0,0)到(10,10)这个方块的中点,也就是坐标(5,5)的点位上,再移动到(10,0)与(20,10)这个方块区域的中点上,即(15,5)坐标点位上,再移动到(20,0)与(30,10)这个方块区域的中点上,即(25,5)坐标点位上,依次类推,直到移动到最后一个点位,即(10,40)与(20,50)这个方块区域的中点上,即(15,45)这个坐标上,到达终点。

因此A星寻路结束后,给出了[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4],即数组上的坐标路径,在实际地图中则移动的路径为(5,5)->(15,5)->(25,5)->(25,15)->(25,25)->(25,35)->(25,45)->(15,45)的坐标点位顺序。

相当于把整个地图想象成一个矩形,把矩形横切N刀,竖切N刀,成了一个与二维数组匹配的方块地图,每个方块与数组中的一个元素相关联,当我们使用A星算法从数组中算出一个具体的路径时,可以根据这个数组中的路径,来匹配地图上的点位,即方块的中点。

如果这个地图很大,但数组的大小很小,就无法实现细腻的碰撞体,所以我们需要在内存占用量与地图寻路细节之间权衡,即多大的数组与当前的地图才能匹配的更好,数组不能过大,因为过大的数组会造成内存的浪费,又不能过小,因为过小的数组使得地图的障碍细节无法得到完美的体现。所以我们在决定数组多少的时候,需要考虑的是整个地图的大小,以及最小障碍物为多大,来决策究竟需要用多大的数组。

这些切割与关联都是由我们的脑袋想象出来的,过于抽象,毕竟我们在做游戏项目的时候,抽象的东西如果无法可视化的话,就会变得难以运用,至少是难以灵活的编辑和扩展。

那么如何将这个抽象的方块可视化呢,最简单的方法就是用Excel方式,建立一个Excel,在Excel表中填入一个与数组相等大小的矩形方格块,在方格内填入颜色与数字,绿色代表可行区域,并填入0,红色代表不可行区域,并填入1。这样在Excel内就可以设置地图的障碍物,以及障碍物的大小,一眼就能知道,因为那些标记为红色的方格是障碍物,那里是不可通行的,那些标记绿色的地方为空地,那地方是可通行的,整个地图下来哪些地方不可通行,哪些地方可通行,一目了然。最后我们把这个Excel里的数据导出到文件,再在游戏开始时读取文件中的数据,得到地图的二维数组的障碍数据。

除了Excel,我们还可以使用UnityEditor UI编写的地图编辑窗口,把地图大小,方格大小,障碍物等以可视化的形式放在 UnityEditor UI编辑窗口中,并编写保存数据到文件,和从文件读取地图数据的功能和按钮,这样一个地图编辑窗口就能更形象的体现地图的元素。

如果这种可视化还不够,就得在具体的3D场景中的地图上做文章,把具体的整个地图加载并渲染在画面上,然后在地图上用颜色方块的方式画出不同颜色的块状,以具体地图为背景,来编辑地图障碍还是可通行块。当然这也带来更加多的编写和维护工作,但也同时是非常值得的可视化网格编辑器。

如果嫌做一个地图编辑器作为可视化太麻烦,也可以用类似地形贴图的形式来做为可行走点的依据。用一整张1024 * 1024图代表一整个地形的大小,或者也可以为 2048 * 256等不同需求规格的大小,每个像素点代表二维数组的一个元素,比如白色为可行走区域,黑色为不可行走区域,那么这张图就可以压缩成只有R通道的8比特的图,图片像素中0就是黑色,1就是白色,或者加入更多元素2就是泥潭,3就是沼泽等等,这样就可以用图片代替了Excel的数据。当需要加载二维数组作为可行走数据时,则加载该图片读取像素中的每个元素录入到内存中,然后就可以依据内存中的二维数组来判定是否是可行走区域,以及相邻的格子是否是障碍物的判断。

由于一维数组在分配内存块时的紧凑度往往比二维数组要来的好,用一维数组来读取索引中的数值会更加的快,因此我们常常使用一维数组来代替二维数组,在调用索引时也只是多了一个简单的乘法和加法的操作,即 二维数组 [a, b] 等于 一维数组 [a * width + b],这样一来只是消耗很小的CPU就能在一维数组中索引到数值,而不再需要内存地址的跳转。

2.用路点系统构建寻路路线图

用二维数组的方式来构建寻路的基础数据有一定的局限性。当场景特别大,我们就要存储特别大的一个数组,编辑场景的工作量也有所提高,如果一个2048 * 2048 的数组的场景,我们要把所有的障碍点都设置一遍工作量比较大。

除了数组太大和需要编辑的工作量扩大外,二维数组下的寻路路径最多是8方向的,上,下,左,右,左上,左下,右上,右下,寻路后的行走时会比较不真实,感觉是直来直去行走方向,要么90度方向行走,要么180度方向行走,要么45度方向行走,没有其他角度的行走姿势,让人感觉不真实,在像素游戏上还感觉不出什么来,但在3D地形中则会感觉明显的怪异。

路点系统弥补了一些二维数组形式的缺点。路点系统也是一个易于理解的系统,它由很多个点构成,这些点我们称它们为路点,即路上的点,这些路点需要我们手动在地图上放进去,每个路点中都存储了坐标,ID,以及与哪些路点相连的数据。

我们在地图中,放入了很多个路点,并且为这些路点配置了连线,于是就有了这幅画面:

    图片暂时脑补

地图中每个路点都会有与其他某些路点相连接的线,我们可以称它们为路线,由路点与路点之间连线而成。

如果把地图里的路点和路线铺设的更加复杂一点时,所有的点和线都拼成了一张网:

    图片暂时脑补

这张网中,只要我们得到某个点,就能根据这些路点和路线,用A星的算法来寻路到目的地。即,起点为,与起点最近的路点,寻路到,与终点最近的路点,的一条路径。如图:

    图片暂时脑补

路点系统很容易理解,但也需要一些可视化的编辑器的支撑,因为所有的路点都需要在既有的地图上编辑,所以编写一个专门的地图编辑器是必不可少的,没有地图编辑器至少也需要路点编辑器,可保存路点数据到文件,和从文件加载路点数据,以及增加路点,减少路点,添加和减少路点连接信息。

路点系统的缺点也是比较严重的,它任然需要大量的工作量来编辑可寻路的路点信息与连线。另外,它的寻路方式无法识别碰撞而只能用路点的形式来绕过障碍。

当在大块空地上做寻路时,需要在这个大块空地上手动添加很多的路点,才能平滑的适应各种寻路,虽然没什么难度,但对人来说重复的工作量比较大。

3.平面三角形网格的构建 -- Navigation Mesh

路点系统虽然直观,门槛低,上手简单,而且一般情况下路点的数量相对比其他方式的网格少很多,因此内存消耗和CPU消耗都比较少。但是人工手动的重复工作量比较大,更糟糕的是它无法识别障碍区域,行走的路线也依赖路点之间的连线。

三角形网格就很好的解决了路点系统的缺陷,三角形网格是用生成算法自动生成的网格,无需手动编辑,而且还能识别障碍区域。

Navmesh(即 Navigation mesh)是最耳熟能详的寻路解决方案,其实质是三角形网格生成算法 + 多边形之间的合并与裁切算法 + 寻路算法(A星算法 或 射线算法),这个解决方案在2D和3D游戏上的都得到了普遍使用。

尽管Unity3D提供了内置的Navmesh寻路插件,以及Unity3D的Asset Store里也提供了众多的类似的不同种类的插件,但如果我们只是停留在插件使用的表层上,无法更深入理解到原理与底层的算法,那么我们在决策和定制寻路解决方案时仍然将始终无法得心应手,当遇到难题或瓶颈时也无法得到彻底有效的解决。

三角形网格是怎么生成的呢,这个问题在计算机图形学里叫做 “平面多边形的三角剖分问题”,意思是说“怎么将一个平面多边形分解为由许多三角形组成的多边形”。

平面多边形的三角形剖分问题是计算几何研究的一个基本问题,它广泛应用于模式识别、图像处理、计算机图形学以及机器人领域。一方面,三角形作为最简单的平面图形,较其他平面图形在计算机表示、分析及处理时方便得多;另一方面,三角剖分是研究其他许多问题的前提。

其中Delaunay三角剖分算法是一种三角剖分的标准,实现它有多种算法。这些算法都是基于已经拥有多个点位的数据之上来建立一个三角形网格的。

Delaunay三角剖分有其特点,剖分后的多边形里的三角形必须满足:

    1.除了端点,三角形的边不包含其他任何点。

    2.除了在点上的连接,没有任何一条边是相交的。

    3.所有的面都是三角形,且所有三角形的合集是所有点集合的凸包。

第一、二点很好理解,要求三角形的边上没有任何其他点,以及没有任何一条边有中间斩断式的相交情况,但最后一点说的是凸包,说明Delaunay三角剖分算法只适用于凸包形式的三角剖分。但实际情况时,凹形区域占到了大量的面积和数量。

实际中我们需要的不只是凸多边形和凹多边形的三角形剖分,也需要考虑凹凸多边形中含有‘洞’(即不规则多边形阻挡物)的情况,甚至还有更复杂的‘洞’中有孤岛的情况,因此单单是凸多边形的三角形剖分不能满足我们实际的需求。

2002年 David Eberly 在《Triangulation by Ear Clipping》论文中提出了用切耳法构建简单多边形的三角化。

什么是简单多边形呢,简单多边形是,所有顶点都是顺时针或者逆时针排列的顶点,每个顶点只连接两条边,边与边之间没有交叉的多边形,就叫做简单多边形。

切耳算法

Ear Clipping 切耳算法是一个简单实用的三角形分割算法,其步骤可以简单的分为三步:

    在解释三步骤之前,我们先解释下几个名词的意思。

    1.耳点,耳点的意思是,多边形中相邻的三个顶点V0,V1,V2形成的三角形里,不包含任何的其他顶点,并且如果V1点是凸点,即V0-V1的连线与V1-V2的连线之间形成的夹角小于180度,则认为V1是耳点。所以一个由4个顶点组成的多边形中,至少有2个耳点。

    2.耳朵三角形,三角形顶点中有耳点的就叫耳朵三角形。

    第一,找到一个耳点。

    第二,记录这个耳朵三角形,然后去掉这个耳朵点,在剩余的顶点中,继续回到第一步

    第三,直到剩下最后3个点形成一个三角形并记录下来,把所有记录的三角形拼接起来就形成了三角化网格。

经过这三个步骤的计算,所有的耳点都被切掉后,再把所有记录的三角形拼装成三角形网格,就完成了整个三角形剖分步骤。

    图片暂时脑补
多边形含‘洞’的情况

除了普通的简单多边形(包括凹凸多边形)的三角剖分外,如果简单多边形中有‘洞’的情况怎么办。论文中也给出了解决方案,即,依旧使用上述三步骤来做三角形剖分,只是剖分之前定把‘洞’并入外围的简单多边形,即:

    1,用外围的简单多边形上的点,连接‘洞’的简单多边形,因此为了保持所有点的一致性,‘洞’必须是与外围的多边形的点的顺序是相反的。即外围如果是逆时针的顺序,‘洞’则需要顺时针的顺序。

    2,在连接处,产生两个一模一样的点,即连接点。

用这种方式来将‘洞’并入成为一个单独的简单多边形,如果有多个洞,则先并入的洞为,拥有x轴方向最大的点的‘洞’,依次并入。

也就是说,最终计算的还是一个单独的简单多边形,只是在计算之前,将‘洞’以凹形形态并入最外围的简单多边形。

我们以图为例,可以看的更加清楚一点:

    图片暂时脑补

图中展示了,如何将一个‘洞’以凹形形态的方式并入外围简单多边形的,就如同从外围简单多边形上,修了一条小小的通路到‘洞’中那样,其实我们完全可以理解为,下图那样:

    图片暂时脑补

图中从外围简单多边形的点上延伸出一条路径来连接‘洞’,使得‘洞’的空白与外围的空白联通,就像贴膜里的气泡开了个口把空气放出去了那样。

如果’洞‘并不是完全包含在外围简单多边形下,有可能是一半在外面,一半在里面,这时只要做多边形裁剪就可以了,将原来外围的简单多边形根据这个’洞‘裁剪成一个凹形,就与’洞‘彻底分离开来了,形成了新的简单多边形。

‘洞’中的’岛‘

除了有’洞‘,以及’洞‘包含在里面和’洞‘一半在里面一半在外面的情况,还有种情况是‘洞’中有’岛‘。这个‘岛’就像是湖中的‘孤岛’,虽然它也是需要三角剖分,但与外界是无法取得连接的,也就没有与最外围的简单多边形连接的需求。

因此’洞‘中有’岛‘,这个’岛‘就相当于另一个独立的简单多边形范围,可以另外单独拎出来,自己计算自己的三角化部分。

到此,这样就形成了一整个算法,即,如果有‘洞’则先合并‘洞’,如果有岛,则拎出来作为与外围的简单多边形同级别的简单多边形自行计算。所有三角化的计算过程可简单描述为,找耳朵,去耳朵,记录耳朵三角形,最后得到了所有三角形,这四个步骤。

应用到实际项目中,最外层的简单多边形,就是我们在地图中定义的可行走的多边形范围。而‘洞’则是地图上的那些静态的障碍区域,而‘洞’中的‘岛’,则是不可行走范围内的可行走的‘孤岛’。

实际项目中,构建三角寻路网格,我们首先需要找出这个最外围的简单多边形,以及孤岛,再根据切耳算法来构建三角形网格。因此我们需要根据地形来生成相应的可行走三角形网格,通过读取地图中的可行走区域的Mesh,以及读取障碍物Mesh,将它们的竖直方向y轴的值忽略后,再通过多边形合并算法来合并成为最外层的多边形,操作还包括裁切‘洞’一半在里面的情况,最后可以得到需要三角化的简单多边形,以及‘洞’的数据。最后将这些数据用切耳算法得到一个具体的三角网格。

4.拥有高度的3D三角形网格构建

前面讲了2D平面上的寻路网格构建,在实际项目中大部分时候,2D平面上的寻路就已经够用了,即使是有起伏的地面寻路,也可以用 2D寻路 + y轴射线碰撞的形式 获得位置坐标,在服务器端保存和运算的数据为2D平面数据,在客户端上展示时则加入了y轴碰撞后的数据,这样即满足了寻路的需求,也满足了高低起伏的地形。

现实项目中有一种解决方案可以用多层级的2D网格做3D寻路的,这是种古老的做法,曾在PC端的RPG网络游戏中非常流行,但在现代的网络游戏中,相对比较少见,因为现代高度网格构建算法有比较成熟和方便的解决方案,但这种多层级2D网格代替3D网格的做法任然有比较好的借鉴的意义。

我们暂且称它为‘分层平面寻路网格’,‘分层平面寻路网格’需要把所有可行走的区域分成多个层级,第一层与第二层之间有一个连接层,第二层与第三层之间也有一个连接层,这就像我们在一个多层的有楼梯的古堡中,古堡很高有4层楼这么高,每一层都用楼梯连接着,这个楼梯就是连接层与层之间的中间层。

我们任然使用2D三角形网格构建法构建每一层的可行走区域,这样构建出7层网格数据,第一层是地面三角形网格数据,Layout层级我们可以标记为1,第二层是1楼与2楼连接的楼梯层可行走区域的平面三角形网格数据,标记为2,第三层为古堡2楼的可行走三角形网格数据,标记为3,第4层为2楼与3楼连接处的楼梯的平面三角形网格数据,标记为4,依次类推,每一层包括楼梯层都有自己的可行走的平面三角形网格数据。

这7层网格数据都是独立的,每一层自己走自己的路时都不需要依靠其他层的数据来寻路。但是,如果只是独立计算各自层级中的网格数据,是无法跨越层级去其他层级的,就比如我们从大厅一楼要去楼梯上看看,或者上到二楼去看看,或者去三楼四楼。

在‘分层平面寻路网格’中,当要跨越层级寻路时,首先必须确定的是‘我’在哪一层,目的地是哪个层级,出发点是哪个层级,按次序一层层往上走或者往下走。

比如我们去的目的地是二楼,所在的起点是大厅的一楼,那么我们就必须由标记为1的地面层级,先到标记为2的楼梯层级,最后到达标记为3的二层楼,到达标记为3的层级也就是所谓的二楼后,再根据二楼的三角形网格数据进行寻路到达目的地。

每一层都有自己独立的数据网格,跨越层级的寻路就需要层与层之间的连接点或连接信息,比如第一层的某几个三角形与第二层是连接的,或者也可以是某个点的范围内,只要进入这个三角形或者圆圈的范围,就认为我们上升了一层,或者下降了一层,我们身上标记的自己所处的层级也变化了,用到的寻路网格数据也变成了当前层的数据。

因此只要我们移动到该区域内,就认为我们进入了第二层级,于是就可以开始了第二层级的网格寻路,再从第二层级移动到与第三层级相交的区域,就等于我们进入到了第三层级,最后在第三层级的网格数据上寻路,直达目的地。

下楼也是同样的道理,在每一层中都有那么一个范围是可以通往下一个层级的,只要到达这个范围以内就认为是进入了下一个层级,于是就可以在下一个层级的网格数据中寻路。所以每次跨层级寻路时,都要先寻找上楼,或下楼的那个点,先从当前层级到达那个点上下楼的点,再从该点到达其他地方,有点像瞬移,到了某个点上时,瞬移到了另外一层网格上,只是坐标不变,层级的信息和网格数据变了。

这种伪3D高度寻路解决方案其实也挺好用的,只是现在知道的人不多,用的人也少了,大家都是要么2D寻路网格够用了,要么就直接 RecastNavigation Navmesh 这种第三方解决方案,很少有人使用这种中间态的技术了,但是这种中间态的技术不是没用,它也有很多值得思考和借鉴的意义。

RecastNavigation Navmesh 解决方案在各大引擎上非常流行,虽然各自都对其本身做了相应的修改,但核心算法是不变的。

在Unreal,Unity3D上也同样应用了 RecastNavigation Navmesh,下一节我们会专门讲一讲这个 RecastNavigation Navmesh 中的核心算法,因为它的内容比较多,所以我打算专门用了一节的内容来剖析它,让大家能深刻理解它的原理。

5.三角形网格中的A星寻路

网格构建完毕了,那么就要派A星上场了。怎样才能让A星与网格数据结合呢。前面一节讲了A星的具体方法,这节就不再具体讲方法了,而是从应用的角度来看待A星的特点。

A星的特点是必须有邻近的节点可获取,并且邻近的节点与目的地是可以有距离比较的。

在这种特点的情况下,二维数组下的A星寻路很好理解,邻近节点就是周围的4个点或者8个点,并且与目的地的距离可以直接用方块之间的距离来计算。

在路点系统中,也有邻近节点,它的邻近节点就是与该节点有线条连接的点,并且与目的地的距离可以直接用点与点之间的距离计算。

在平面三角形网格中,要从一个点到另一个点,则可以使用三角形的邻近三角形来计算路径,与目的地之间的距离也可以用点与点之间的距离来计算。

在‘分层平面寻路网格’中,从一个点到另一个点的寻路,和平面三角形网格差不多的方式,也是用邻近三角形来计算路径,只是在计算过程中还需要根据关注网格的层级,每一层都有自己独立的网格。

二维数组下,计算出来的路径是这样的,[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[2,3]->[2,4]->[1,4]。

路点系统中,计算出来的路径是这样的,(id=1)->(id=3)->(id=6)->(id=12)->(id=21)。

平面三角形网格中,计算出来的路径是这样的,(trangleid=1)->(trangleid=4)->(trangleid=8)->(trangleid=13)。

‘分层平面寻路网格’中,计算出来的路径是这样的,(trangleid=1, layout=1)->(trangleid=3, layout=1)->(trangleid=5, layout=2)->(trangleid=8, layout=2)->(trangleid=1, layout=3),其中trangleid为layout层级上的三角形ID。

在三角形网格寻路后,知道了路径上需要经过哪些三角形,那么问题来了。我们行走的路径是根据点来判断的,三角形怎么定点,三角形的大小不一,有可能是宽形三角形,也有可能是扁长的三角形,如果点位定在中心点,那么行走的时候就会很怪异,每次都要先到达三角形的中点才能去下一个三角形,所以中点与中点的连线可能会很怪异。怎么办?

折中的办法我们可以考虑用边的中点来记录路径,因为相邻三角形之间的穿越都是靠邻边来穿越的,所以邻边的中点更符合三角形穿越,从ID为1的三角形穿越到ID位2的三角形上时,穿越的是ID 1与ID 2三角形的共同边,这种邻边中点计算出来的路径,有更好更平滑的路径效果。

不过这种三角形进出领边的中点还是不够靠谱,因为三角大小不一,致使三角形边的进出边也会随着三角形而改变,路径同样看起来曲折怪异。那么有没有一种方法能够更好更平滑的计算出三角形网格的路径呢。

这里就需要引入一个拐点路径算法来优化寻路后的路径。拐点算法有点像射线,所以也常常被称作为射线优化路径算法。

拐点算法其实并不复杂:

    1.从起始坐标点出发,往与下一个三角形的入口边的两个顶点v1,v2产生两个向量line1、line2,然后再往下一个三角形的入口边的两个顶点v3,v4产生两个向量line3、line4。

    2.通过计算这四个向量的叉乘,可以判定一个向量是在另一个向量的左边或者右边。我们可以计算出v3,v4是否在line1,line2形成的夹角。

这里会出现几种情况:

    1.下一组边与上一个路径点的向量全部在前一组边的范围内,直接把下一组边的两点替换前一组边的两点。

    2.下一组边的右边点与上一个路径点向量在上一组边的范围内,但左边的点不在范围内,把下一组边的右边点替换前一组边的右边点

    3.下一组边的左边点与上一个路径点向量在上一组边的范围内,但右边的点不在范围内,把下一组边的左边点替换前一组边的左边点

    4.下一组边两个点组成的向量都在上一组边的左边,那么上一组边的左边点成为拐点

    5.下一组边两个点组成的向量都在上一组边的右边,那么上一组边的右边点成为拐点

    6.假如下一组边左边的点和上一组边的左边点重合,则把上一组边的左边点成为拐点

    7.假如下一组边右边的点和上一组边的右边点重合,则把上一组边的右边点成为拐点

    8.当寻路达到最后一个多边形,直接判断终点和上一个路径点的向量是否在上一个边两点的中间,假如不是,再增加一个拐点

举例说明:从右边的开始点往左边的结束点寻路

    脑补图片1

line3,line4在line1,line2夹角内,左右都缩进。

    脑补图片2

v4在外面,左边缩进。

    脑补图片3

v3,v4都在line1 左边,v1成为拐点

    脑补图片4

从v1出发继续按上面步骤计算拐点

    脑补图片5

最后到达终点,收集所有拐点,加上起点和终点后就是正条经过优化后的路径节点。这种射线算法或者说拐点算法能将原本在三角形网格寻路后诡异的路径转化为更加平滑的直线路径。

下一节将重点来剖析一下Unity3D中嵌入的 RecastNavigation Navmesh 网格构建算法和寻路算法。

参考资料:

《Triangulation by Ear Clipping》David Eberly

《Delaunay三角剖分的几种算法综述》吴莉莉

《多边形寻路算法简单介绍》 liweizhaolili

感谢您的耐心阅读

Thanks for your reading

  • 版权申明

    本文为博主原创文章,未经允许不得转载:

    《Unity3D高级编程之进阶主程》第十章,地图与寻路(二) 寻路网格的构建

    Copyright attention

    Please don't reprint without authorize.

  • 微信公众号