[转载]RecastNavigation

2019/10 27 21:10

一、RecastNavigation详解

  RecastNavigation定义:
    RecastNavigation是一个导航寻路工具集,使用邻接的凸多边形集合描述一个3D场景,A*寻路算法使3D场景的可达性得到保证。
    Polygon是Detour的基本寻路单元,在Poly(Polygon凸多边形)中,任意两个点是可以直线到达的。
    github:https://github.com/recastnavigation/recastnavigation

  RecastNavigation功能:
    能表达一个3D场景;
    能接近精确的赋予游戏对象3维坐标属性;
    能判断3D场景表面2个点的可达性;
    能动态改变3D场景地形。

  RecastNavigation内容:
    NavMesh(导航网格寻路)= 邻接的凸多边形(Recast) + A*寻路(Detour)
    1、Recast,用于生成邻接的凸多边形集合数据,使用参照示例:RecastDemo/Sample_SoloMesh.cpp
      ① Solo Mesh,纯粹的邻接凸多边形集合。
      ② Tile Mesh,基于Tile划分的N个邻接凸多边形集合。
      ③ Temp Obstacles,支持动态障碍物的,基于tile划分的N个邻接的凸多边形集合。
    2、Detour,基于邻接的凸多边形集合的A*寻路算法,示例参照:RecastDemo/NavMeshTesterTool.cpp

  *RecastNavigation的所有操作都是基于地表面的,对于空中对象的交互是无法完成的,这时可以结合其他引擎,如physx进行对象的空中交互。

  源码结构:
    DebugUtils 调试
    Detour 利用导航网格做寻路操作。导航网格可以使Recast生成的,也可以是其他工具生成的。
    DetourCrowd 提供群体寻路行为的功能
    DetourTileCache Tile缓存
    Recast 根据提供的模型生成用于寻路的导航网格
    RecastDemo 展现Recast、Detour提供的功能的Demo
    Test 测试

  SoloMesh生成过程(RecastDemo/Sample_SoloMesh.cpp中handleBuild函数),导航网格生成步骤:
    场景模型体素化(Voxelization),或者叫光栅化(Rasterization)。
    过滤可行走表面(Walkable Suface)
    区域生成(Region)
    轮廓生成(Contour边缘)
    轮廓网格生成(Poly Mesh)
    三角形化(Triangulation)生成细节网格(Detailed Mesh)

二、RecastNavigation构建
  RecastNavigation使用Premake5构建,需要自行安装,如果使用make进行构建,需要编写Makefile。
  Premake下载地址:https://premake.github.io/download.html

  Windows下使用vs编译
    1、RecastNavigation依赖于SDL库,下载SDL源码,解压到RecastNavigation/RecastDemo/Contrib/目录下
    2、进入SDL/VisualC/目录,打开开解决方案,编译在SDL/VisualC/Win32/Debug下生成 SDL2.dll、SDL2.lib、SDL2main.lib
    3、复制到SDL/lib/x86下,实际上这些文件下载的时候已经存在了,不需要2中的步骤
    4、下载premake5.exe到工程目录RecastNavigation/RecastDemo/下,cmd命令行进入此目录,执行premake.exe vs2017 premake5.lua,生成解决方案在RecastNavigation/RecastDemo/build/下。
    5、打开解决方案,在RecastNavigation/RecastDemo/Bin/下生成RecastDemo.exe可执行文件

  Linux下编译
    1、git clone https://github.com/recastnavigation/recastnavigation.git
    2、安装SDL,OpenGL
    SDL要编译
      进入目录 ./configure make make install
    OpenGL可以通过命令安装
      yum install mesa-libGL-devel.x86_64
      yum install mesa-libGLU-devel.x86_64
    设置环境变量export PKG_CONFIG_PATH=SDL目录,否则make的时候找不到SDL.h文件
    3、cd recastnavigation/RecastDemo/
    4、premake5 gmake
    5、cd Build/gmake/
    6、make

三、相关知识
  1、包围球:
    ……
  2、AABB包围盒:
    xmin < x < xmax
    ymin < y < ymax
    zmin < z < zmax
    顶点 (xmin, ymin, zmin),(xmax, ymax, zmax)
    中心点
    float center()
    {
      center[0] = (min[0] + max[0]) * 0.5;
      center[1] = (min[1] + max[1]) * 0.5;
      center[2] = (min[2] + max[2]) * 0.5;

      return center;
    }
  3、OBB包围盒:
    ……

  地形建模方法:
    grid(方格)
    waypoint(路径点)
    navmesh(导航网格)

四、服务器使用RecastNavigation
  1、从Unity导出场景,使用navigation寻路组件bake完成生成好的导航网格(navmesh),生成recast可识别的obj文件。
  2、使用RecastNavigation加载场景,并验证其正确性。

// 这里要用到Sample_TileMesh.h中结构体
struct NavMeshSetHeader
{
  int magic;
  int version;
  int numTiles;
  dtNavMeshParams params;
};
 
struct NavMeshTileHeader
{
  dtTileRef tileRef;
  int dataSize;
};
 
// 打开读取客户端生成的NavMesh文件
FILE* fp = fopen(navameshpath, "rb");
if (!fp) return 0;
 
NavMeshSetHeader meshHeader;
size_t len = fread(&meshHeader, sizeof(NavMeshSetHeader), 1, fp);
f (len != 1 || meshHeader.magic != NAVMESHSET_MAGIC || meshHeader.version != NAVMESHSET_VERSION)
{
  fclose(fp);
  return 0;
}
 
dtNavMesh* dtMesh = dtAllocNavMesh();
if (!dtMesh)
{
  fclose(fp);
  return 0;
}
 
dtStatus dtStatus = dtMesh->init(&meshHeader.params);
if (dtStatusFailed(dtStatus)
{
  fclose(fp);
  return 0;
}
 
// 读取所有Tiles,获取MeshQuery对象,下一步可以用MeshQuery对象进行寻路
for (int i =0; i < meshHeader.numTiles; ++i)
{
  NavMeshTileHeader tileHeader;
  len = fread(&tileHeader, sizeof(NavMeshTileHeader), 1, fp)
  ......
}

3、Detour驱动AI寻路。