《Cocos NavMesh方案|社区征文》

1.0 网格导航介绍

体验地址:
Github Page:Cocos Creator | Easy_Navi
Gitee Page:Cocos Creator | Easy_Navi

视频说明
B站地址Cocos Easy NavMesh 使用说明_哔哩哔哩_bilibili

导航网格(Navigation Mesh),简称NavMesh,NavMesh会存储可行走区域的网格信息,用以在复杂的3D空间中实现导航寻路等功能,

image
导航网格是由多个多边形网格(Poly Mesh)组成的,以下简称为 Poly,即上图中的黑色描边的淡蓝色色块部分

Poly 专门指的是导航网格的组成单位,在导航网格中的寻路是以 Poly 为单位的,在同一个 Poly 中的两点,在忽略地形高度的情况下, 是可以直线到达的;如果两个点位于不同的 Poly,那么就会利用寻路算法(比如A*算法)算出需要经过的 Poly,再算出具体路径。

为什么使用NavMesh,不使用路径点

在早期3D游戏中,路径点是一种常用的寻路方式,但路径点不光生成和配置比较麻烦,还有一个更严重的缺点。

以魔兽世界中的暴风城一角为例,当使用路径点时,AI的行为是有限的,只能在路径点之间的连线上移动。

image

当使用Navmesh时,通过计算人物的信息(如体积,行走高度,可上坡角度等),用以烘焙出NavMesh信息;地图上的可以行走区域,由淡蓝色的Poly组成。

image
通过Navmesh,人物的移动区域更加灵活,可以实现更复杂的AI行为。

如下图所示,可以在河边任何位置摸鱼,也可以实现人物出城和躲避到树林当中。
image
再举一个更有说服力的例子,在魔兽世界怀旧服纳格兰的哈兰岛上,使用NavMesh可以涵盖整个区域,AI的行为和表现也会比路径点更加智能,基本可以涵盖哈兰岛的各个角落。(当然有些特殊的情况,比如跳跃等,我们还是可以通过路径点实现)

image
NavMesh同时还可以通过高度参数和角度参数实现角色的斜坡移动,实现上桥,下桥等行为,以魔兽沙塔斯城为例,参考下图Poly部分。
image
当有了这些Poly网格,就可以借助A*算法来实现寻路功能。

这里使用了bgrin大佬的A*开源库,并翻译和修改了数学库,转换了成了TS版本。(https://github.com/bgrins/javascript-astar)

传统A 的搜寻路线如下图,基于网格,和网格中的障碍点网格,进行寻路算法。


在NavMesh生成的Poly块中,数据已经基于实现了基于地图的网格化,我们考虑的问题是,如果寻找最优的落地点,而不是让沿着下图Poly的黄线移动,或者直接从起点走到终点。

image
3.0 Cocos 的NavMesh解决方案

考虑到目前Cocos 3.0 有部分产品主要面向H5或者快游戏市场,对包体大小和性能消耗的需求都比较严格。

所以Easy NavMesh 采用了基于PatrolJS (https://github.com/nickjanssen/PatrolJS)方案实现的轻量级TS库,放弃了使用recast.js+wasm的组合。
image

整套库的大小只有40KB不到。

image

PatrolJs采用了比较简单的漏斗算法(Simple Stupid Funnel Method)+A*的组合,通过漏斗算法正好可以解决上一章我们遇到了Poly移动问题。

漏斗算法放弃了找寻Poly的边缘的中点(虽然这方法可以让路径变得平滑,在生或死4中有采取过类似方案),而是通过循环算法,不断的缩小三角形漏斗的范围(可以理解为三角形的角度),这个方法计算频率高,但是更简单而有效。

下面我们通过几个实例图,演示漏斗算法通过算小漏斗角度,定位出路径点的过程


–检查A图的第一个Poly左右2个点,是否在红线和蓝线组成的三角形漏斗范围内,再依次走B图到D图的3个Poly,我们看到,三角形漏斗的角度不断变小,漏斗的范围变得越来越小。

–接着我们历遍E图和F图新增的2个Poly,我们发现E图右边的端点(标记x的一边,为了方便理解,这里的位置都是图片上实际的位置,不是Poly顶点的位置)在之前D图生成的三角形漏斗之外,而且D图的红线能到达E图的第5个Poly,这里漏斗就停止更新,不缩小角度。

–E图没有更新,接着F图新增的蓝线又在漏斗外,D图的红线无法到达第6个poly,这时候我们结束漏斗算法,把直接A到D生成的红线作为第一个路径,从G图开始,重新生成了一个新的三角形漏斗,开始新的漏斗算法。

有了漏斗算法之后,我们就可以使用A*配合漏斗,获取正确的路线。

static findPath(startPosition:Vec3, targetPosition:Vec3, zoneID:string, groupID:number) {

        const allNodes = this.zone[zoneID].groups[groupID];

        const vertices = this.zone[zoneID].vertices;

        let closestNode = null;

        let distance = Infinity;

        let measuredDistance

        for (let i = 0, len = allNodes.length; i < len; i++) {

            const node = allNodes[i];

            measuredDistance = Vec3.squaredDistance(node.centroid, startPosition);

            if (measuredDistance < distance) {

                closestNode = node;

                distance = measuredDistance;

            }

        }

        let farthestNode = null;

        distance = Infinity;

        for (let i = 0, len = allNodes.length; i < len; i++) {

            const node = allNodes[i];

            measuredDistance = Vec3.squaredDistance(node.centroid, targetPosition);

            if (measuredDistance < distance &&

                nUtils.isVectorInPolygon(targetPosition, node, vertices)) {

                farthestNode = node;

                distance = measuredDistance;

            }

        }

        // If we can't find any node, just go straight to the target

        if (!closestNode || !farthestNode) {

            return null;

        }

        //A*寻路算法

        const paths = Astar.search(allNodes, closestNode, farthestNode);

        const getPortalFromTo = function (a, b) {

            for (let i = 0; i < a.neighbours.length; i++) {

                if (a.neighbours[i] === b.id) {

                    return a.portals[i];

                }

            }

        };

        //使用漏斗算法,结算出最佳路线

        // Got the corridor,pull the rope

        const channel = new Channel();

        channel.push(startPosition);

        for (let i = 0; i < paths.length; i++) {

            const polygon = paths[i];

            const nextPolygon = paths[i + 1];

            if (nextPolygon) {

                const portals = getPortalFromTo(polygon, nextPolygon);

                channel.push(vertices[portals[0]], vertices[portals[1]]);

            }

        }

        channel.push(targetPosition);

        channel.stringPull();

        // Return the path, omitting first position (which is already known).

        return channel.path;

    }

为了减少数据开销,Easy Navmesh使用预烘焙方案,提前把Navmesh数据以Json格式导出,方便跨平台支持。

image
不同于其他引擎,比如在Unity中,有提供专门的Navigation, 用于寻路导航,玩家可以根据角色的高矮胖瘦,和角色能攀爬的最大角度,预先烘焙好NavMesh;或者在babylon.js 中,用户也可以通过wasm+recast.js 实现类似的需求。

3.1 NavMesh信息优化

EasyNavMesh 通过以下3中途径获取NavMesh的Json信息。

–支持recast.js 导出 json数据(recast.js+wasm 封装到了导出插件中,下文做详细介绍。


–支持 Unity NavMesh插件导出(可以使用CocosNavmesh.unityasset 进行安装,包含在插件当中,这里只导出需要的面和顶点信息等数据,同时支持小数点的精度调整,方便压缩Json的体积)
这里的导出方案我们使用了Cocos自带消息通知,支持导出整个场景或导出NavMesh需要的Json Mesh

–支持 Blender Navmesh 导出Obj,再使用 Python 脚本进行转换,这个脚本是基于OBJ to three.js Json Mesh 进行了修改,剔除了无用了normal,uv等信息。(原作者:AlteredQualia http://alteredqualia.com)

通过Cocos解析这些Json后,我们就可以使用Json中的定点信息和面的信息,构建导航网格的数据,为了灵活适配,这些网格信息也可以放在服务器或者通过脚本新建对象来储存。
image

3.2 其他优化

image
A. 剔除了第三方Vector3 的数学库,使用Cocos的Vec3替代,避免了Cocos 的Vec3类和其他V3坐标类之间的2次转换。(剔除其他引擎的V3类数学库,全部使用Cocos的Vec3)

image
B. 原库使用了OBJ格式,或者Three.js 的Json Model,这里一步到位,可以直接通过Cocos或者Unity导出Json信息,信息提前做了小数点精度保留,减少了Json体积和处理OBJ信息的运算量,Size Does Matter~

C. 提供了可视化的Cocos NavMesh烘焙工具和Unity 烘焙导出工具,目前Cocos NavMesh烘焙数据基于recast.js 参数较多,烘焙效果不如Unity理想。如果为了追求最佳效果,可以使用Cocos NavMesh导出工具,导出整个场景到OBJ文件,再在Unity内烘焙这个OBJ场景。整个工作流比Unity导出 NavMesh的OBJ,再通过Python转换,再做精度处理要节省了50%以上的时间。

4.0 更多内容

移植了ThreeJS的Plane和Triangle类,重新使用Cocos的 Vec3 Mat4数学库进行了编译。

实现了基于NavMesh ClampSteped的移动。
借助ClampSteped,无需使用 Cocos自带的Cannon或者Ammo物理引擎,人物也无需添加刚体,是基于ThreeJs的Plane和Triangle库的数学方法实现的。

ClampSteped是一个不太成熟的方案,目前只提供了基础Demo,后续的优化需要依靠各位大佬,使用ClampSteped替代物体,需要注意设置好物体半径,太小容易导致穿模,太大容易穿墙。

5.0 to-do-list

*加入更多基于NavMesh 的游戏Demo,比如捉迷藏

*clampstep 优化,实现基于clampstep 的FPS NavMesh Demo(下次一定!)

6.0 FAQ

Q1: 为什么有时候路径不是视觉上最近的?

A: 在NavMesh中A*算法是以Poly作为网格的,在复杂的网格地形中,到最近的距离点的Poly组数反而可能比较多。

Q2:为什么ClampStep这个东西容易穿墙

A: 目前数学库都是从Three.js翻译的,这个ClampStep在Three的项目中使用也较少,可以参考的demo不多,需要进一步适配cocos,后续版本会不停调优。

Q3:这么多导出NavMesh Json的方法,那个最好

A: 目前来Unity烘焙的NavMesh效果最好,但Cocos版本借助开源的recast.js,和编辑器结合紧密,更加方便,大佬们有更优的方案,请多多指导。

Q4: 为什么Unity 导出的无法像Demo里一样走楼梯

A: 这里使用的是A*算法,楼梯上Poly必须连到一起,可以通过改变人物的高度(Agent Height)和人物的移动高度(Step Height)使楼梯变成斜坡,解决这个问题

image
Q5:为什么这次不给白嫖?

A: 本文阐述了原理,为了能熬夜水更多,大佬们可以支持我一杯咖啡,从商店下载更方便喔~

7.0 Support Me

深圳疫情严重,居家隔离办公,开发不易,目前Cocos 商店已经上架了,限时骨折价(1 coffee only!),大佬们请多多支持。

商店地址Easy NavMesh 网格导航寻路 | Cocos Store

22赞

为大佬打call~

商店地址点开已下架

cocos的大佬还是审核ing,没有bug的话,今天就可以上架喔

强大,迫不及待要递上咖啡:coffee:

1赞


大佬,商店已经上架,限时优惠,1 个星巴克的中杯即可!

咖啡已下单,真香

:kissing_cat: :kissing_cat: :kissing_cat: :kissing_cat: :kissing_cat:

感谢楼主对Cocos社区贡献的一份超能力量 :muscle:
我预测楼主的 Easy NavMesh 将会续 ShaderEditorCocosInspector 在Cocos社区与CocosStore的历史上画出惊天彩虹 :rainbow:

来了来了:smirk:

能不能来一个星巴克小杯

罗先生,对不起,我们只有,中杯,大杯和特大杯 :crying_cat_face:

1赞

:+1::+1::+1::+1:

6666666 :+1:

已经购买, 支持大佬 :+1:

感谢 大佬支持! :kissing_cat: :kissing_cat:

买了怎么用啊?

可以详细见项目里的Markdown文件,今天也会更新一版本使用视频,上传B站

:cow::beer::cow::beer::cow::beer:

已购买 感谢大佬