前言：基于Tile的导航系统

UE4的导航使用的是RecastDetour组件，这是一个开源组件，主要支持3D场景的导航网格导出和寻路，或者有一个更流行的名字叫做NavMesh。不管是Unity还是UE都使用了这一套组件。

Github上有更为详细的源码、Demo和说明：https://github.com/recastnavigation/recastnavigation

本文使用的UE4源码版本为4.26.1，2021年2月2日的版本。

这一篇是第一篇，会阐述UE4是如何划分Tile，并基于Tile构建导航数据的。在后续的文章中，会详细介绍每个Tile如何构建导航数据。

Tile 的概念

Tile的概念，就是一个正方形的格子。每个Tile中有自己独立的导航网格数据。在我看来，Tile的作用有三点：

  1. 更加友好地支持多线程构建导航网格数据。

  2. 通过标记每个Tile是否需要重新生成（Dirty属性），就能在runtime动态更新单独一个Tile的导航网格

  3. 使用Static方式的导航网格时，可以以Tile为粒度来加载导航网格

在UE4中，所有的导航网格数据都是基于Tile的。每个Tile有自己独自的FRecastTileGenerator，会对当前的Tile从体素化开始，完整执行一遍导航数据构建过程。

这里简单介绍一下每个Tile在构建导航数据时会经历的步骤：

  1. 体素化。

  2. 根据体素中存储的信息，构造连续区域。

  3. 计算每个cell与周围cell的连通性

  4. 根据配置的agentRadius裁剪可行走区域

  5. 划分区域

  6. 在竖直方向分层并进行合并

  7. 将所有数据写入到rcHeightfieldLayer类中，供detour寻路使用

上述步骤都会在后续的文章中详细说明，本文只会讲述基于Tile的导航数据构建。

下面这个Uml类图，包含了NavigationSystem和NavMesh模块一些常用的类以及介绍。可以对NavigationSystem有一个初步了解

image.png

NavigationSystem的八叉树

八叉树如何更新

在UE4中，所有的导航依赖的物理数据，都是其自身通过一颗八叉树来维护的。八叉树底层直接使用了UE4的TOctree2模板类，并提供了一个FNavigationOctreeController控制类来更新八叉树。

NavigationSystem提供了非常多的静态函数，供会影响导航网格的事件发生时调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
void UpdateActorData(AActor& Actor) { Delegates.UpdateActorData.Execute(Actor); }
void UpdateComponentData(UActorComponent& Comp) { Delegates.UpdateComponentData.Execute(Comp); }
void UpdateActorAndComponentData(AActor& Actor, bool bUpdateAttachedActors) { Delegates.UpdateActorAndComponentData.Execute(Actor, bUpdateAttachedActors); }
void UpdateComponentDataAfterMove(USceneComponent& Comp) { Delegates.UpdateComponentDataAfterMove.Execute(Comp); }
void OnActorBoundsChanged(AActor& Actor) { Delegates.OnActorBoundsChanged.Execute(Actor); }
void OnPostEditActorMove(AActor& Actor) { Delegates.OnPostEditActorMove.Execute(Actor); }
void OnComponentBoundsChanged(UActorComponent& Comp, const FBox& NewBounds, const FBox& DirtyArea) { Delegates.OnComponentBoundsChanged.Execute(Comp, NewBounds, DirtyArea); }
void OnComponentTransformChanged(USceneComponent& Comp) { Delegates.OnComponentTransformChanged.Execute(Comp); }
void OnActorRegistered(AActor& Actor) { Delegates.OnActorRegistered.Execute(Actor); }
void OnActorUnregistered(AActor& Actor) { Delegates.OnActorUnregistered.Execute(Actor); }
void OnComponentRegistered(UActorComponent& Comp) { Delegates.OnComponentRegistered.Execute(Comp); }
void OnComponentUnregistered(UActorComponent& Comp) { Delegates.OnComponentUnregistered.Execute(Comp); }
void RemoveActorData(AActor& Actor) { Delegates.RemoveActorData.Execute(Actor); }

上述情况非常多，不过主要就是会影响导航网格的Actor或者Component在添加、删除、Transform变化时来主动调用。

我们在这里用一个例子来举例，详细讲一下当一个物体的Transform发生变化时，导航系统是如何进行更新的。

在每个SceneComponent的Transform发生变化时，都会执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool USceneComponent::InternalSetWorldLocationAndRotation(FVector NewLocation, const FQuat& RotationQuat, bool bNoPhysics, ETeleportType Teleport)
{
    // ...
    // we need to call this even if this component itself is not navigation relevant
    if (IsRegistered() && bCanEverAffectNavigation)
    {
        PostUpdateNavigationData();
    }
    // ...
}

void USceneComponent::PostUpdateNavigationData()
{
    SCOPE_CYCLE_COUNTER(STAT_ComponentPostUpdateNavData);
    FNavigationSystem::OnComponentTransformChanged(*this);
}

而在UNavigationSystemV1的构造函数中，会进行所有Delegate的绑定

1
2
3
4
5
6
7
8
9
10
11
12
13
UNavigationSystemBase::OnComponentTransformChangedDelegate().BindLambda([](USceneComponent& Comp) {
    if (UNavigationSystemV1::ShouldUpdateNavOctreeOnComponentChange())
    {
        UWorld* World = Comp.GetWorld();
        UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(World);
        if (NavSys != nullptr
            && (NavSys->ShouldAllowClientSideNavigation() || !World->IsNetMode(ENetMode::NM_Client)))
        {
            // use propagated component's transform update in editor OR server game with additional navsys check
            UNavigationSystemV1::UpdateNavOctreeAfterMove(&Comp);
        }
    }
});

因此，当Delegate触发时，会直接调用NavigationSystem的接口，直接调用八叉树的更新接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void FNavigationDataHandler::UpdateNavOctreeElement(UObject& ElementOwner, INavRelevantInterface& ElementInterface, int32 UpdateFlags)
{
    // 整个更新的实质，其实是先删除原节点，再注册新节点
    
    //...
    
    const bool bAlreadyExists = OctreeController.GetNavOctreeElementData(ElementOwner, CurrentFlags, CurrentBounds);

    // don't invalidate pending requests
    UpdateFlags |= FNavigationOctreeController::OctreeUpdate_Refresh;

    // always try to unregister, even if element owner doesn't exists in octree (parent nodes)
    UnregisterNavOctreeElement(ElementOwner, ElementInterface, UpdateFlags);

    const FSetElementId RequestId = RegisterNavOctreeElement(ElementOwner, ElementInterface, UpdateFlags);
    
    //...

    // 依次向上更新所有父节点
    UpdateNavOctreeParentChain(ElementOwner, /*bSkipElementOwnerUpdate=*/ true);
}

同时，在八叉树的接口中，也会去标记NavigationSystem的DirtyAreas，来驱动FRecastNavMeshGenerator的Tick逻辑去更新对应的Tile。

1
2
3
4
5
6
7
8
9
10
11
void FNavigationDataHandler::RemoveNavOctreeElementId(const FOctreeElementId2& ElementId, int32 UpdateFlags)
{
    if (ensure(OctreeController.IsValidElement(ElementId)))
    {
        const FNavigationOctreeElement& ElementData = OctreeController.NavOctree->GetElementById(ElementId);
        const int32 DirtyFlag = GetDirtyFlagHelper(UpdateFlags, ElementData.Data->GetDirtyFlag());
        // 在这里会对变化的Area进行标记
        DirtyAreasController.AddArea(ElementData.Bounds.GetBox(), DirtyFlag, [&ElementData] { return ElementData.Data->SourceObject.Get(); });
        OctreeController.NavOctree->RemoveNode(ElementId);
    }
}

NavigationSystem分块构建过程

理论上，每个Tile的构建都是自洽的，都是与其它Tile可以完全独立进行。在八叉树更新对某个Area进行标记之后，FRecastNavMeshGenerator的Tick都会去对每个PendingDirtyArea来进行更新。

为了比较直观，我们在这里分析其全量Build的整个流程。从UNavigationSystemV1::Build()入手。

流程并不复杂：

  1. 收集场景中所有的ANavMeshBoundsVolume包围盒，核心代码在GatherNavigationBounds()中，很简单就是遍历World中的类。

  2. 对每个包围盒的区域，使用配置的TileSize和CellSize，划分Tile。每个Tile依然是AABB的，直接对坐标进行除法来划分Tile。每个Tile的大小就是配置的TileSize * CellSize。核心代码在MarkDirtyTiles()函数中：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    // 这个构造函数用来计算一个包围盒换算成recast坐标的最大值和最小值
    FRcTileBox(const FBox& UnrealBounds, const FVector& RcNavMeshOrigin, const float TileSizeInWorldUnits)
    {
        check(TileSizeInWorldUnits > 0);

        // 在这里直接通过TileSize和cs来计算每个tile的大小，在这里直接划分。以(0,0)点为中心划分
        const FBox RcAreaBounds = Unreal2RecastBox(UnrealBounds);
        XMin = FMath::FloorToInt((RcAreaBounds.Min.X - RcNavMeshOrigin.X) / TileSizeInWorldUnits);
        XMax = FMath::FloorToInt((RcAreaBounds.Max.X - RcNavMeshOrigin.X) / TileSizeInWorldUnits);
        YMin = FMath::FloorToInt((RcAreaBounds.Min.Z - RcNavMeshOrigin.Z) / TileSizeInWorldUnits);
        YMax = FMath::FloorToInt((RcAreaBounds.Max.Z - RcNavMeshOrigin.Z) / TileSizeInWorldUnits);
    }

    // 将外部传入的包围盒，换算成tile坐标，并对其标记为dirty
    void FRecastNavMeshGenerator::MarkDirtyTiles(const TArray<FNavigationDirtyArea>& DirtyAreas)
    {
        // ...
        
        TSet<FPendingTileElement> DirtyTiles;
        for (const FNavigationDirtyArea& DirtyArea : DirtyAreas)
        {
            // ...
            
            // 获取到当前DirtyArea的包围盒
            FBox AdjustedAreaBounds = DirtyArea.Bounds;
            const FRcTileBox TileBox(AdjustedAreaBounds, RcNavMeshOrigin, TileSizeInWorldUnits);
            
            // 这个包围盒内部的坐标都是一个tile
            for (int32 TileY = TileBox.YMin; TileY <= TileBox.YMax; ++TileY)
            {
                for (int32 TileX = TileBox.XMin; TileX <= TileBox.XMax; ++TileX)
                {
                    // ...
                    
                    // 记录当前tile坐标
                    FPendingTileElement Element;
                    Element.Coord = FIntPoint(TileX, TileY);
                    
                    // ...
                    DirtyTiles.Add(Element);
                }
            }
        }
        
        // Dump results into array
        PendingDirtyTiles.Empty(DirtyTiles.Num());
        for(const FPendingTileElement& Element : DirtyTiles)
        {
            PendingDirtyTiles.Add(Element);
        }

        // 这里将所有tile按照距离主角的距离的远近进行排序
        if (NumTilesMarked > 0)
        {
            SortPendingBuildTiles();
        }
    }

  3. 在Build时使用多线程来生成导航数据。每个Tile由一个Task负责。这部分逻辑核心代码在FRecastNavMeshGenerator::ProcessTileTasks()中。如果在Rebuild过程中，这个过程会由FRecastNavMeshGenerator::EnsureBuildCompletion()来驱动。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void FRecastNavMeshGenerator::EnsureBuildCompletion()
    {
        // ...
        
        do 
        {
            const int32 NumTasksToProcess = (bDoAsyncDataGathering ? 1 : MaxTileGeneratorTasks) - RunningDirtyTiles.Num();
            ProcessTileTasks(NumTasksToProcess);
            
            // Block until tasks are finished
            for (FRunningTileElement& Element : RunningDirtyTiles)
            {
                Element.AsyncTask->EnsureCompletion();
            }
        }
        while (GetNumRemaningBuildTasks() > 0);
    }

而每个Task负责的内容，就是对自己Task所负责的Tile，完整运行一遍体素化、分层、区域划分、构建相邻三角形导航数据等过程。

其关键函数在FRecastTileGenerator::GenerateCompressedLayers()和FRecastTileGenerator::GenerateNavigationData()中。详细流程将会后续文章中详细阐述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool FRecastTileGenerator::GenerateCompressedLayers(FNavMeshBuildContext& BuildContext)
{
    // 函数有简化，略去了一些不影响流程阅读的判断和变量初始化

    // 创建高度场，准备构建体素
    if (!CreateHeightField(BuildContext, RasterContext))
    {
        return false;
    }
    
    // 将三角形光栅化到体素上
    ComputeRasterizationMasks(BuildContext, RasterContext);
    RasterizeTriangles(BuildContext, RasterContext);
    
    // 如果配置开启，将根据边界来剔除边界之外的体素
    if (TileConfig.bPerformVoxelFiltering && !bFullyEncapsulatedByInclusionBounds)
    {
        ApplyVoxelFilter(RasterContext.SolidHF, TileConfig.walkableRadius);
    }
    
    // 构建压缩高度场
    if (!BuildCompactHeightField(BuildContext, RasterContext))
    {
        return false;
    }
    
    // 
}

Tile 的加载和使用

对于UE4来说，每个Tile只是存储当前线下已经预生成的导航数据。生成之后，实际使用A*算法来进行寻路时，直接用生成好的导航数据来进行寻路。

在UE4中，承载recast数据的类是FRecastTileData。其结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct FRecastTileData
{
    struct FRawData
    {
        FRawData(uint8* InData);
        ~FRawData();

        uint8* RawData;
    };

    FRecastTileData();
    FRecastTileData(int32 TileDataSize, uint8* TileRawData, int32 TileCacheDataSize, uint8* TileCacheRawData);
    
    // Location of attached tile
    int32                    OriginalX;    // Tile X coordinates when gathered
    int32                    OriginalY;    // Tile Y coordinates when gathered
    int32                    X;                    
    int32                    Y;                    
    int32                    Layer;
        
    // Tile data
    int32                    TileDataSize;
    // 这个RawData是recast使用的数据
    TSharedPtr<FRawData>    TileRawData;

    // Compressed tile cache layer 
    int32                    TileCacheDataSize;
    TSharedPtr<FRawData>    TileCacheRawData;

    // Whether this tile is attached to NavMesh
    bool                    bAttached;    
};

对于UE4来说，对于PersistantLevel，加载Level时会自动在场景中创建一个ARecastNavMesh类，导航数据会直接生成在场景中的ARecastNavMesh对象中。

而对于SubLevel，导航数据会序列化到ULevel类上的NavMeshChunk对象中。及导航数据会跟随场景加载。

加载上来的数据，将会在FPImplRecastNavMesh::Serialize()过程中，读取文件中的数据存储至DetourNavMesh对象上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void FPImplRecastNavMesh::Serialize( FArchive& Ar, int32 NavMeshVersion )
{
    //...
    if (Ar.IsLoading())
    {
        // allocate the navmesh object
        ReleaseDetourNavMesh();
        DetourNavMesh = dtAllocNavMesh();
    }
    
    //...
    
    // 这里读取每个Tile的内容，添加到DetourNavMesh中
    for (int i = 0; i < NumTiles; ++i)
    {
        // ...
        
        unsigned char* TileData = NULL;
        TileDataSize = 0;
        // 读取每个TileData的内容。这个TileData实际上是dtMeshHeader结构
        SerializeRecastMeshTile(Ar, NavMeshVersion, TileData, TileDataSize);

        if (TileData != NULL)
        {
            // 直接将每个Tile数据添加到DetourNavMesh中
            dtMeshHeader* const TileHeader = (dtMeshHeader*)TileData;
            DetourNavMesh->addTile(TileData, TileDataSize, DT_TILE_FREE_DATA, TileRef, NULL);
            
            //... 处理CompressedData序列化
        }
    }
}

总结

这一篇作为系列第一篇，从整个框架层，来分析了UE4是如何划分导航的Tile，如何分Tile构建导航网格，Tile的存储方式，以及加载上来如何使用Tile，并简单介绍了UE4如何支持动态更新导航。

下一篇将会介绍UE4导航的整个体素化过程。