Unreal RecastNavigation 开源项目详解

news/2024/10/4 5:34:18

0 前言

Recastnavigation是一个游戏AI导航库，像Unity，UE引擎中都集成了这个开源项目， HALO中使用的也是这个开源库。导航最重要的就是为NPC寻路，以及其他的寻路需求。

需要注明的是，这个寻路库虽然厉害。但是他的核心是平面寻路。也就是重力方向一直朝着 -Y 方向。如果是星球地形，既重力方向朝向球心，在任何一点重力方向都是不同的。那么这个开源库就不能使用了。

1 Recastnavigation 下载与编译

主页: https://github.com/recastnavigation/recastnavigation/tree/main?tab=readme-ov-file
编译: https://github.com/recastnavigation/recastnavigation/blob/main/Docs/_2_BuildingAndIntegrating.md

编译细节
这个项目 Recast and Detour 不依赖其他的一些库，但是 RecastDemo 即可视化的示例是需要SDL2库的，SDL2库可以理解为创建窗口应用程序所需要的库。所以我们需要下载SDL。

同时也需要 premake5 编译工具。

1.1 Windows

Grab the latest SDL2 development library release from https://github.com/libsdl-org/SDL and unzip it into RecastDemo/Contrib. Rename the SDL folder such that the path RecastDemo/Contrib/SDL/lib/x86 is valid.
- https://github.com/libsdl-org/SDL/releases

SDL2-devel-2.28.2-VC.zip 像这样的文件名的release才可以，不要直接下载 source code

// 成功后的文件夹应该是这个样子。
RecastDemo/Contribfastlzreadme-sdl.txtSDLstb_truetype.h

●Navigate to the RecastDemo folder and run premake5 vs2022
●Open Build/vs2022/recastnavigation.sln in Visual Studio 2022 or Jetbrains Rider.
●Set RecastDemo as the startup project, build, and run.

2. 代码详解

// Figure out how big the raster voxel grid will be based on the input geometry bounds.
rcCalcGridSize// Voxelize the input geometry
rcAllocHeightfield
rcCreateHeightfield
rcMarkWalkableTriangles
rcRasterizeTriangles// Clean up the voxel data and filter out non-walkable areas.
rcFilterLowHangingWalkableObstacles
rcFilterLedgeSpans
rcFilterWalkableLowHeightSpans// Consolidate the voxel data into a more compact representation
rcAllocCompactHeightfield
rcBuildCompactHeightfield// Further refine the voxel representation
rcErodeWalkableArea
rcBuildDistanceField
rcBuildRegions// Triangulate the navmesh polygons from the voxel data
rcAllocContourSet
rcBuildContours
rcAllocPolyMesh
rcBuildPolyMesh// Package the mesh with additional metadata that's useful at runtime.
rcAllocPolyMeshDetail
rcBuildPolyMeshDetail// Cleanup
rcFreeHeightField
rcFreeCompactHeightfield
rcFreeContourSet

代码详解主要为2个部分。

数据载入
高度场建立

2.1 数据载入

首先Sample_SoloMesh::handleBuild()会调用InputGeom::getMesh()

那么Mesh数据从哪里来呢？

InputGeom::loadMesh()
InputGeom::load()
rcMeshLoaderObj::addVertex(float x, float y, float z, int& cap) 其中cap是顶点的内存容量，以存8个顶点为开始，内存短缺后以2倍速度扩大。存储皆为1维数组，顶点与顶点之间的 stride==3。
void rcMeshLoaderObj::addTriangle(int a, int b, int c, int& cap)

有了Mesh之后,开始计算xz平面的栅格数量，设置为 *sizeX = &m_cfg.width, *sizeZ = &m_cfg.height。平面边缘，只要占到一半以上的cellSize,就认为是一个cell。

void rcCalcGridSize(const float* minBounds, const float* maxBounds, const float cellSize, int* sizeX, int* sizeZ)
{	// (0, 0.5) + 0.5  -> 0// [0.5, 0.999) + 0.5 -> 1*sizeX = (int)((maxBounds[0] - minBounds[0]) / cellSize + 0.5f);*sizeZ = (int)((maxBounds[2] - minBounds[2]) / cellSize + 0.5f);
}

rcCreateHeightfield(m_ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch)相当于构造函数，初始化高度场信息HeightField or HeightMap。

m_triareas = new unsigned char[ntris];角色代理可以走的三角形。

rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, verts, nverts, tris, ntris, m_triareas);这个的关键就是三角形的法向量的 y 分量，等于三角形面与 x-z 平面的夹角 cos 值。运用相似三角形。

2.2 高度场建立

主要就是利用x-z平面的网格与映射到平面上的三角形的交点，通过相似三角形获得这个交点 (x-z)-> Y在三维三角形的高度。

这个切割方法是 Sutherland-Hodgman polygon-clipping algorithm 的变种。

Sutherland-Hodgman polygon-clipping algorithm

这个算法最重要的就是判断顶点在切割窗口某一条 Edge 两侧的哪一侧。

Edge存在切割窗口的那一侧是 in，不存在则是 out.
https://stackoverflow.com/questions/21638509/determine-voxels-that-a-triangle-is-in
Abhishek Sharma : https://www.youtube.com/watch?v=OGW9Cqr5RRg&t=333s&pp=ygUTIFN1dGhlcmxhbmQtSG9kZ21hbg%3D%3D

2.2.1 高度场建立的核心函数。

bool rcRasterizeTriangles(rcContext* context,const float* verts, const int /*nv*/,const int* tris, const unsigned char* triAreaIDs, const int numTris,rcHeightfield& heightfield, const int flagMergeThreshold)
{rcAssert(context != NULL);rcScopedTimer timer(context, RC_TIMER_RASTERIZE_TRIANGLES);// Rasterize the triangles.const float inverseCellSize = 1.0f / heightfield.cs;const float inverseCellHeight = 1.0f / heightfield.ch;for (int triIndex = 0; triIndex < numTris; ++triIndex){const float* v0 = &verts[tris[triIndex * 3 + 0] * 3];const float* v1 = &verts[tris[triIndex * 3 + 1] * 3];const float* v2 = &verts[tris[triIndex * 3 + 2] * 3];if (!rasterizeTri(v0, v1, v2, triAreaIDs[triIndex], heightfield, heightfield.bmin, heightfield.bmax, heightfield.cs, inverseCellSize, inverseCellHeight, flagMergeThreshold)){context->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");return false;}}return true;
}