牟骞

基于Recast&Detour的AI引擎简单分析


1.什么是NavMesh?

导航网格是二维凸多边形(多边形网格)的集合,它定义了代理可以遍历环境的哪些区域。换句话说,游戏中的角色可以在这些区域内自由地走动,不受树木,熔岩或作为环境一部分的其他障碍物的阻挡。相邻的多边形以图形相互连接。

这些多边形之一内的寻路可以直线进行,因为多边形是凸的并且是可以横越的。可以使用大量图形搜索算法(例如A *)之一来完成网格中的多边形之间的寻路。导航网络上的代理因此可以避免计算上繁重的碰撞检测检查与作为环境的一部分的障碍物。

以类似2D的形式表示可移动区域简化了在模拟真实的3D环境中才需要完成的计算,但与2D网格不同,它允许在不同高度上重叠的上下移动区域。导航网格中各种尺寸和形状的多边形可以表示比常规网格更精确的任意环境。

在机器人技术中,以这种方式使用连接的凸多边形被称为“草地映射”,家用主机游戏人工智能中的导航网格大多参考于《Game Programming Gems》的数中的 Greg Snook于2000年文章“简化3D运动和寻路使用导航网格” 。在2001年,有开发者描述的相似的结构,凸部和连接的3D多边形,被称为“区域感知系统”,用于雷神之锤3的AI系统。

除了在游戏领域,其代码的扩展延伸版本涉及到了目前风口最旺盛的人工智能领域,Google的大狗等智能机器人技术使用实时深度扫描创建NavMesh的方式进行AI路径选择。

image
KillZone4

image
Google的大狗

2.NavMesh如何创建

导航网格可以手动,自动地或通过两者的某种组合来创建。在家用机游戏中,关卡设计人员可能会在关卡编辑器中手动定义navmesh的多边形。这种做法可能相当体力活。或者,可以创建一个应用程序,其将关卡几何体作为输入并自动输出导航。

通常假设由navmesh表示的环境是静态的,它不会随着时间的推移而变化,因此导航可以离线创建并且是不可变的。当然,有一些动态环境导航网络需要实时更新来完成,比如动态变化场景。

3.Recast & Detour

Recast &Detour是一个开源的寻路引擎,其遵循zlib协议,基本上你可以免费且无限制的将它用作个人和商业产品中。

从名字中我们可以看到,这个引擎分成两部分:

第一部分是Recast,主要功能是将场景网格模型生成用于寻路的网格模型(Navigation Mesh)。所生成的寻路网格模型当然要比原模型简单很多,这也提高了实时寻路算法的效率。

第二部分是Detour,主要功能是利用上一步所生成的Navigation Mesh进行寻路,其包含了多种寻路算法,根据不同的路径光滑程度与寻路时间效率的要求可做不同的选择。

Recast & Detour本身是个独立的程序库,其源码所带的Demo用到了SDL库。

SDL(Simple DirectMedia Layer)是一套开放源代码的跨平台多媒体开发库,使用C语言写成。SDL提供了数种控制图像、声音、输出入的函数,让开发者只要用相同或是相似的代码就可以开发出跨多个平台(Linux、Windows、Mac OS X等)的应用软件。目前SDL多用于开发游戏、模拟器、媒体播放器等多媒体应用领域。

它被广泛的用于许多著名的游戏。最著名的游戏是赢得Linux组游戏开发大奖的 文明:权利的召唤(Civilization: Call To Power)。

SDL内置了调用OpenGL的函数。

SDL的编译又需要Direct X。

4.以Solo圆柱体形状的方式构建NavMesh(Sample_SoloMesh::handleBuild)

一、填写build的配置结构体rcConfig

a) Voxels信息:网格的宽度和高度单位

b) Agent信息:角色高度,半径,最大可爬高度、最大转向角度

c) Region信息:最小Region尺寸,合并范围

高度域分离方式:Watershed

e) Polygonization信息:最大三角边长度、最大边容错、每个三角形顶点数

f) DetailMesh信息:角色距离、最大角色容错

image

image

二、光栅化输入的polygon信息

a) 创建体素高度域rcHeightfield:rcAllocHeightfield,rcCreateHeightfield

image

b) 创建存储三角形的索引缓存:m_triareas = new unsigned char[ntris];

c) 根据斜率搜寻可走的三角形,然后光栅化它们:rcMarkWalkableTriangles,rcRasterizeTriangles

image

三、过滤可走面

a)删除突出的障碍rcFilterLowHangingWalkableObstacles

b)删除架状突出物rcFilterLedgeSpans

c)删除玩家不可能站立的区域rcFilterWalkableLowHeightSpans

四、分割可走面为简单多边形

a) 紧缩高度域以加速:rcAllocCompactHeightfield,rcBuildCompactHeightfield

b) 根据可走半径腐蚀可走区域:rcErodeWalkableArea

c) (可选)标记凸多边形区域:对于每个getConvexVolumes:rcMarkConvexPolyArea

d) 分割高度域(heightfield)以可用简单算法来三角化可走区域。有三种分割算法可选:

1) Watershed partitioning

  • the classic Recast partitioning
  • creates the nicest tessellation
  • usually slowest
  • partitions the heightfield into nice regions without holes or overlaps
  • the are some corner cases where this method creates produces holes and overlaps
  • holes may appear when a small obstacles is close to large open area (triangulation can handle this)
  • overlaps may occur if you have narrow spiral corridors (i.e stairs), this make triangulation to fail
  • generally the best choice if you precompute the nacmesh, use this if you have large open areas
    rcBuildDistanceField,rcBuildRegions

2) Monotone partioning

  • fastest
  • partitions the heightfield into regions without holes and overlaps (guaranteed)
  • creates long thin polygons, which sometimes causes paths with detours
  • use this if you want fast navmesh generation
    rcBuildRegionsMonotone

3) Layer partitoining

  • quite fast
  • partitions the heighfield into non-overlapping regions
  • relies on the triangulation code to cope with holes (thus slower than monotone partitioning)
  • produces better triangles than monotone partitioning
  • does not have the corner cases of watershed partitioning
  • can be slow and create a bit ugly tessellation (still better than monotone)
    if you have large open areas with small obstacles (not a problem if you use tiles)
  • good choice to use for tiled navmesh with medium and small sized tiles
    rcBuildLayerRegions

image

image

image

五、跟踪并简化区域轮廓

rcAllocContourSet,rcBuildContours

image

image

image

六、通过轮廓创建多边形网格(Mesh)

rcAllocPolyMesh,rcBuildPolyMesh

image

七、创建细节网格(允许访问每个多边形的近似高度)

rcAllocPolyMeshDetail,rcBuildPolyMeshDetail
(至此,Navigation Mesh数据rcPolyMesh已经生成完毕)

image

5.Detour查询

在完成上述创建之后,可以从Recast网格创建Detour数据
填写dtNavMeshCreateParams结构
创建NavMesh数据:dtCreateNavMeshData
分配Mesh结构:dtAllocNavMesh
初始化Mesh:
status = m_navMesh->init(navData, navDataSize, DT_TILE_FREE_DATA);
所有的查询函数全部封装在dtNavMeshQuery
recastnavigation-master\RecastDemo\Source\Sample_SoloMesh.cpp第355行开始

image

image

其中可以查询到的信息非常多,包括基本功能寻路之外,射线查询、离墙查询、查找区域内的三角面,查找附近连接点等。

寻路查询

image

连通区域查询(用于服务器端)

image

离墙查询

image

射线查询

image

区域内三角形查询

image

临近区域查询(巡逻)

image

最终,作者还提供了一个非常简单的AI模拟工具,包括性能分析统计等。

image

image