NavigationSystem.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#if UE_ENABLE_INCLUDE_ORDER_DEPRECATED_IN_5_4
#include "CoreMinimal.h"
#endif
#include "UObject/ObjectMacros.h"
#include "Templates/SubclassOf.h"
#include "UObject/WeakObjectPtr.h"
#include "Misc/CoreMisc.h"
#include "Misc/CoreDelegates.h"
#if UE_ENABLE_INCLUDE_ORDER_DEPRECATED_IN_5_4
#include "NavFilters/NavigationQueryFilter.h"
#endif
#include "AI/Navigation/NavigationTypes.h"
#include "AI/Navigation/NavigationDirtyElement.h"
#include "AI/Navigation/NavigationInvokerPriority.h"
#include "NavigationSystemTypes.h"
#include "NavigationData.h"
#include "AI/NavigationSystemBase.h"
#include "Kismet/BlueprintFunctionLibrary.h"
#include "NavigationOctree.h"
#include "AI/NavigationSystemConfig.h"
#include "NavigationOctreeController.h"
#include "NavigationDirtyAreasController.h"
#include "Math/MovingWindowAverageFast.h"
#include "AI/Navigation/NavigationBounds.h"
#include "Containers/ContainerAllocationPolicies.h"
#include "NavigationSystem.generated.h"
 
 
class AController;
class ANavMeshBoundsVolume;
class AWorldSettings;
class FEdMode;
class FNavDataGenerator;
class INavigationInvokerInterface;
class INavLinkCustomInterface;
class INavRelevantInterface;
class UCrowdManagerBase;
class UNavArea;
class UNavigationPath;
class UNavigationObjectRepository;
class UNavigationSystemModuleConfig;
struct FDebugText;
struct FNavigationRelevantData;
struct FNavigationOctreeElement;
struct FNavigationElement;
 
#if !UE_BUILD_SHIPPING
#define ALLOW_TIME_SLICE_DEBUG 1
#else
#define ALLOW_TIME_SLICE_DEBUG 0
#endif
 
DECLARE_MULTICAST_DELEGATE_OneParam(FOnNavAreaChanged, const UClass* /*AreaClass*/);
 
DECLARE_DYNAMIC_MULTICAST_DELEGATE_OneParam(FOnNavDataGenericEvent, ANavigationData*, NavData);
 
DECLARE_MULTICAST_DELEGATE(FOnNavigationInitDone);
 
namespace NavigationDebugDrawing
{
    extern const NAVIGATIONSYSTEM_API float PathLineThickness;
    extern const NAVIGATIONSYSTEM_API FVector PathOffset;
    extern const NAVIGATIONSYSTEM_API FVector PathNodeBoxExtent;
}
 
namespace FNavigationSystem
{   
    typedef ANavigationData* (*FNavigationDataInstanceCreator)(UWorld*, const FNavDataConfig&);
 
    struct FCustomLinkOwnerInfo
    {
        FWeakObjectPtr LinkOwner;
        INavLinkCustomInterface* LinkInterface;
 
        FCustomLinkOwnerInfo() : LinkInterface(nullptr) {}
        NAVIGATIONSYSTEM_API FCustomLinkOwnerInfo(INavLinkCustomInterface* Link);
 
        bool IsValid() const { return LinkOwner.IsValid(); }
    };
 
    bool NAVIGATIONSYSTEM_API ShouldLoadNavigationOnClient(ANavigationData& NavData);
 
    void NAVIGATIONSYSTEM_API MakeAllComponentsNeverAffectNav(AActor& Actor);
 
#if ALLOW_TIME_SLICE_DEBUG
    const FName DebugTimeSliceDefaultSectionName = FName(TEXT("DefaultSection"));
#endif // ALLOW_TIME_SLICE_DEBUG
}
 
struct FNavigationSystemExec: public FSelfRegisteringExec
{
protected:
    //~ Begin FExec Interface
    virtual bool Exec_Runtime(UWorld* Inworld, const TCHAR* Cmd, FOutputDevice& Ar) override;
    //~ End FExec Interface
};
 
namespace ENavigationBuildLock
{
    enum Type
    {
        NoUpdateInEditor = 1 << 1,      // editor doesn't allow automatic updates
        NoUpdateInPIE = 1 << 2,         // PIE doesn't allow automatic updates
        InitialLock = 1 << 3,           // initial lock, release manually after levels are ready for rebuild (e.g. streaming)
        Custom = 1 << 4,
    };
}
 
 
// Use this just  before a call to TestTimeSliceFinished() to allow the time slice logging to use a debug name for the section of code being timed.
#if ALLOW_TIME_SLICE_DEBUG
#define MARK_TIMESLICE_SECTION_DEBUG(TIME_SLICER, TIME_SLICE_FNAME) \
static const FName TIME_SLICE_FNAME(TEXT(#TIME_SLICE_FNAME)); \
TIME_SLICER.DebugSetSectionName(TIME_SLICE_FNAME);
#else
#define MARK_TIMESLICE_SECTION_DEBUG(TIME_SLICER, TIME_SLICE_FNAME) ;
#endif
 
class FNavRegenTimeSlicer
{
public:
    NAVIGATIONSYSTEM_API void SetupTimeSlice(double SliceDuration);
 
    NAVIGATIONSYSTEM_API void StartTimeSlice();
 
    NAVIGATIONSYSTEM_API void EndTimeSliceAndAdjustDuration();
    double GetStartTime() const { return StartTime; }
    NAVIGATIONSYSTEM_API bool TestTimeSliceFinished() const;
 
    //* Returns the cached result of calling TestTimeSliceFinished, false by default */
    bool IsTimeSliceFinishedCached() const { return bTimeSliceFinishedCached; }
    double GetRemainingDuration() const { return RemainingDuration; }
    double GetRemainingDurationFraction() const { return OriginalDuration > 0. ? RemainingDuration / OriginalDuration : 0.; }
 
 
#if ALLOW_TIME_SLICE_DEBUG
    /*
     * Sets data used for debugging time slices that are taking too long to process.
     * @param LongTimeSliceFunction function called when a time slice is taking too long to process.
     * @param LongTimeSliceDuration when a time slice takes longer than this duration LongTimeSliceFunction will be called.
     */
    NAVIGATIONSYSTEM_API void DebugSetLongTimeSliceData(TFunction<void(FName, double)> LongTimeSliceFunction, double LongTimeSliceDuration) const;
    NAVIGATIONSYSTEM_API void DebugResetLongTimeSliceFunction() const;
 
    void DebugSetSectionName(FName InDebugSectionName) const
    {
        DebugSectionName = InDebugSectionName;
    }
#endif // ALLOW_TIME_SLICE_DEBUG
 
protected:
    double OriginalDuration = 0.;
    double RemainingDuration = 0.;
    double StartTime = 0.;
    mutable double TimeLastTested = 0.;
    mutable bool bTimeSliceFinishedCached = false;
 
#if ALLOW_TIME_SLICE_DEBUG
    mutable TFunction<void(FName, double)> DebugLongTimeSliceFunction;
    mutable double DebugLongTimeSliceDuration = 0.;
    mutable FName DebugSectionName = FNavigationSystem::DebugTimeSliceDefaultSectionName;
#endif
};
 
#if !UE_BUILD_SHIPPING
struct FTileHistoryData
{
    int32 TileX = 0;
    int32 TileY = 0;
    
    float TileRegenTime = 0.f;
 
    float TileWaitTime = 0.f;
 
    int64 StartRegenFrame = 0;
 
    int64 EndRegenFrame = 0;
};
#endif // !UE_BUILD_SHIPPING
 
class FNavRegenTimeSliceManager
{
public:
    NAVIGATIONSYSTEM_API FNavRegenTimeSliceManager();
 
    void PushTileRegenTime(double NewTime) { MovingWindowTileRegenTime.PushValue(NewTime);  }
 
    double GetAverageTileRegenTime() const { return MovingWindowTileRegenTime.GetAverage();  }
 
    double GetAverageDeltaTime() const { return MovingWindowDeltaTime.GetAverage(); }
 
    NAVIGATIONSYSTEM_API void ResetTileWaitTimeArrays(const TArray<TObjectPtr<ANavigationData>>& NavDataSet);
    NAVIGATIONSYSTEM_API void PushTileWaitTime(const int32 NavDataIndex, const double NewTime);
 
#if !UE_BUILD_SHIPPING
    NAVIGATIONSYSTEM_API void ResetTileHistoryData(const TArray<TObjectPtr<ANavigationData>>& NavDataSet);
    NAVIGATIONSYSTEM_API void PushTileHistoryData(const int32 NavDataIndex, const FTileHistoryData& TileData);
#endif // UE_BUILD_SHIPPING
 
    NAVIGATIONSYSTEM_API double GetAverageTileWaitTime(const int32 NavDataIndex) const;
    NAVIGATIONSYSTEM_API void ResetTileWaitTime(const int32 NavDataIndex);
 
    bool DoTimeSlicedUpdate() const { return bDoTimeSlicedUpdate; }
 
    NAVIGATIONSYSTEM_API void CalcAverageDeltaTime(uint64 FrameNum);
 
    NAVIGATIONSYSTEM_API void CalcTimeSliceDuration(const TArray<TObjectPtr<ANavigationData>>& NavDataSet, int32 NumTilesToRegen, const TArray<double>& CurrentTileRegenDurations);
 
    NAVIGATIONSYSTEM_API void SetMinTimeSliceDuration(double NewMinTimeSliceDuration);
 
    NAVIGATIONSYSTEM_API void SetMaxTimeSliceDuration(double NewMaxTimeSliceDuration);
 
    NAVIGATIONSYSTEM_API void SetMaxDesiredTileRegenDuration(float NewMaxDesiredTileRegenDuration);
 
    int32 GetNavDataIdx() const { return NavDataIdx;  }
    void SetNavDataIdx(int32 InNavDataIdx) { NavDataIdx = InNavDataIdx; }
 
    FNavRegenTimeSlicer& GetTimeSlicer() { return TimeSlicer; }
    const FNavRegenTimeSlicer& GetTimeSlicer() const { return TimeSlicer; }
 
#if !UE_BUILD_SHIPPING  
    NAVIGATIONSYSTEM_API void LogTileStatistics(const TArray<TObjectPtr<ANavigationData>>& NavDataSet) const;
#endif // !UE_BUILD_SHIPPING
    
protected:
    FNavRegenTimeSlicer TimeSlicer;
 
    FMovingWindowAverageFast<double, 256> MovingWindowTileRegenTime;
 
    FMovingWindowAverageFast<double, 256> MovingWindowDeltaTime;
 
    TArray<TArray<double>> TileWaitTimes;
 
#if !UE_BUILD_SHIPPING
    TArray<TArray<FTileHistoryData>> TileHistoryData;
    double TileHistoryStartTime = 0;
#endif // UE_BUILD_SHIPPING
 
    double MinTimeSliceDuration;
 
    double MaxTimeSliceDuration;
 
    uint64 FrameNumOld;
 
    float MaxDesiredTileRegenDuration;
 
    double TimeLastCall;
 
    int32 NavDataIdx;
 
    bool bDoTimeSlicedUpdate;
};
 
UCLASS(Within=World, config=Engine, defaultconfig, MinimalAPI)
class UNavigationSystemV1 : public UNavigationSystemBase
{
    GENERATED_BODY()
 
    friend UNavigationSystemModuleConfig;
 
public:
    NAVIGATIONSYSTEM_API UNavigationSystemV1(const FObjectInitializer& ObjectInitializer = FObjectInitializer::Get());
    virtual ~UNavigationSystemV1() = default;
 
    NAVIGATIONSYSTEM_API void GatherDebugLabels(TArray<FString>& InOutDebugLabels) const;
 
    UPROPERTY(Transient)
    TObjectPtr<ANavigationData> MainNavData;
 
    UPROPERTY(Transient)
    TObjectPtr<ANavigationData> AbstractNavData;
 
protected:
    UPROPERTY(config, EditAnywhere, BlueprintReadOnly, Category = Navigation)
    FName DefaultAgentName;
 
    UPROPERTY(config, EditAnywhere, BlueprintReadOnly, Category = Navigation)
    TSoftClassPtr<UCrowdManagerBase> CrowdManagerClass;
 
    UPROPERTY(config, EditAnywhere, Category=NavigationSystem)
    uint32 bAutoCreateNavigationData:1;
 
    UPROPERTY(config, EditAnywhere, Category = NavigationSystem)
    uint32 bSpawnNavDataInNavBoundsLevel:1;
 
    UPROPERTY(config, EditAnywhere, Category=NavigationSystem)
    uint32 bAllowClientSideNavigation:1;
 
    UPROPERTY(config, EditAnywhere, Category = NavigationSystem)
    uint32 bShouldDiscardSubLevelNavData:1;
 
    UPROPERTY(config, EditAnywhere, Category=NavigationSystem)
    uint32 bTickWhilePaused:1;
 
    UPROPERTY()
    uint32 bSupportRebuilding : 1; 
 
public:
    UPROPERTY(config, EditAnywhere, Category=NavigationSystem)
    uint32 bInitialBuildingLocked:1;
 
    // @todo removing it from edition since it's currently broken and I'm not sure we want that at all
    // since I'm not sure we can make it efficient in a generic case
    //UPROPERTY(config, EditAnywhere, Category=NavigationSystem)
    uint32 bWholeWorldNavigable:1;
 
    UPROPERTY(config, EditAnywhere, Category=NavigationSystem)
    uint32 bSkipAgentHeightCheckWhenPickingNavData:1;
 
    UPROPERTY(config, EditAnywhere, AdvancedDisplay, Category = NavigationSystem)
    int32 GeometryExportTriangleCountWarningThreshold = 200000;
    
protected:
    UPROPERTY(EditDefaultsOnly, Category = "Navigation Enforcing", config)
    uint32 bGenerateNavigationOnlyAroundNavigationInvokers:1;
 
    UPROPERTY(EditAnywhere, Category = "Navigation Enforcing", meta = (ClampMin = "0.1", UIMin = "0.1", EditCondition = "bGenerateNavigationOnlyAroundNavigationInvokers"), config)
    float ActiveTilesUpdateInterval;
 
    UPROPERTY(EditAnywhere, Category = "Navigation Enforcing", meta = (EditCondition = "bGenerateNavigationOnlyAroundNavigationInvokers"), config)
    double InvokersMaximumDistanceFromSeed = -1;
    
    UPROPERTY(EditDefaultsOnly, Category = "NavigationSystem", config)
    ENavDataGatheringModeConfig DataGatheringMode;
 
    UPROPERTY(config, EditAnywhere, AdvancedDisplay, Category = NavigationSystem, meta = (ClampMin = "-1.0", UIMin = "-1.0"))
    float DirtyAreaWarningSizeThreshold;
 
    UPROPERTY(config, EditAnywhere, AdvancedDisplay, Category = NavigationSystem, meta = (ClampMin = "-1.0", UIMin = "-1.0"))
    float GatheringNavModifiersWarningLimitTime;
 
    UPROPERTY(config, EditAnywhere, Category = Agents)
    TArray<FNavDataConfig> SupportedAgents;
 
    UPROPERTY(config, EditAnywhere, Category = Agents)
    FNavAgentSelector SupportedAgentsMask;
 
public:
    UPROPERTY(Transient)
    FBox BuildBounds;
 
    UPROPERTY(Transient)
    TArray<TObjectPtr<ANavigationData>> NavDataSet;
 
    UPROPERTY(Transient)
    TArray<TObjectPtr<ANavigationData>> NavDataRegistrationQueue;
 
    // List of pending navigation bounds update requests (add, remove, update size)
    TArray<FNavigationBoundsUpdateRequest> PendingNavBoundsUpdates;
 
    UPROPERTY(/*BlueprintAssignable, */Transient)
    FOnNavDataGenericEvent OnNavDataRegisteredEvent;
 
    UPROPERTY(BlueprintAssignable, Transient, meta = (displayname = OnNavigationGenerationFinished))
    FOnNavDataGenericEvent OnNavigationGenerationFinishedDelegate;
 
    FOnNavigationInitDone OnNavigationInitDone;
    
private:
    TWeakObjectPtr<UCrowdManagerBase> CrowdManager;
    
    uint32 bNavDataRemovedDueToMissingNavBounds : 1;
 
protected:  
    TSet<FNavigationBounds> RegisteredNavBounds;
 
private:
    TMap<UObject*, FNavigationInvoker> Invokers;
    TArray<FNavigationInvokerRaw> InvokerLocations;
 
    TArray<FBox> InvokersSeedBounds;
 
    double NextInvokersUpdateTime;
    NAVIGATIONSYSTEM_API void UpdateInvokers();
 
public:
#if !UE_BUILD_SHIPPING
    void DebugLogInvokers(FOutputDevice& OutputDevice) const;
#endif // !UE_BUILD_SHIPPING
 
protected:
    NAVIGATIONSYSTEM_API virtual void UpdateNavDataActiveTiles();
 
private:
    NAVIGATIONSYSTEM_API void DirtyTilesInBuildBounds();
 
    void UnregisterInvoker_Internal(const UObject& Invoker);
 
    void RegisterToRepositoryDelegates();
 
    void UnregisterFromRepositoryDelegates() const;
 
public:
    //----------------------------------------------------------------------//
    // Blueprint functions
    //----------------------------------------------------------------------//
 
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject"))
    static NAVIGATIONSYSTEM_API UNavigationSystemV1* GetNavigationSystem(UObject* WorldContextObject);
    
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject", DisplayName = "Project Point to Navigation", ScriptName = "ProjectPointToNavigation"))
    static NAVIGATIONSYSTEM_API bool K2_ProjectPointToNavigation(UObject* WorldContextObject, const FVector& Point, FVector& ProjectedLocation, ANavigationData* NavData, TSubclassOf<UNavigationQueryFilter> FilterClass, const FVector QueryExtent = FVector::ZeroVector);
 
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject", DisplayName = "Get Random Reachable Point in Radius", ScriptName = "GetRandomReachablePointInRadius"))
    static NAVIGATIONSYSTEM_API bool K2_GetRandomReachablePointInRadius(UObject* WorldContextObject, const FVector& Origin, FVector& RandomLocation, float Radius, ANavigationData* NavData = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject", DisplayName = "Get Random Location in Navigable Radius", ScriptName = "GetRandomLocationInNavigableRadius"))
    static NAVIGATIONSYSTEM_API bool K2_GetRandomLocationInNavigableRadius(UObject* WorldContextObject, const FVector& Origin, FVector& RandomLocation, float Radius, ANavigationData* NavData = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
 
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject"))
    static NAVIGATIONSYSTEM_API ENavigationQueryResult::Type GetPathCost(UObject* WorldContextObject, const FVector& PathStart, const FVector& PathEnd, double& PathCost, ANavigationData* NavData = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
 
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject"))
    static NAVIGATIONSYSTEM_API ENavigationQueryResult::Type GetPathLength(UObject* WorldContextObject, const FVector& PathStart, const FVector& PathEnd, double& PathLength, ANavigationData* NavData = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
 
    UFUNCTION(BlueprintPure, Category="AI|Navigation", meta=(WorldContext="WorldContextObject" ) )
    static NAVIGATIONSYSTEM_API bool IsNavigationBeingBuilt(UObject* WorldContextObject);
 
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject"))
    static NAVIGATIONSYSTEM_API bool IsNavigationBeingBuiltOrLocked(UObject* WorldContextObject);
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation", meta = (WorldContext="WorldContextObject"))
    static NAVIGATIONSYSTEM_API UNavigationPath* FindPathToLocationSynchronously(UObject* WorldContextObject, const FVector& PathStart, const FVector& PathEnd, AActor* PathfindingContext = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation", meta = (WorldContext="WorldContextObject"))
    static NAVIGATIONSYSTEM_API UNavigationPath* FindPathToActorSynchronously(UObject* WorldContextObject, const FVector& PathStart, AActor* GoalActor, float TetherDistance = 50.f, AActor* PathfindingContext = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
 
    UFUNCTION(BlueprintCallable, Category="AI|Navigation", meta=(WorldContext="WorldContextObject" ))
    static NAVIGATIONSYSTEM_API bool NavigationRaycast(UObject* WorldContextObject, const FVector& RayStart, const FVector& RayEnd, FVector& HitLocation, TSubclassOf<UNavigationQueryFilter> FilterClass = {}, AController* Querier = NULL);
 
    static NAVIGATIONSYSTEM_API bool NavigationRaycastWithAdditionalResults(UObject* WorldContextObject, const FVector& RayStart, const FVector& RayEnd, FVector& HitLocation, FNavigationRaycastAdditionalResults* AdditionalResults, TSubclassOf<UNavigationQueryFilter> FilterClass = {}, AController* Querier = NULL);
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation")
    NAVIGATIONSYSTEM_API void SetMaxSimultaneousTileGenerationJobsCount(int32 MaxNumberOfJobs);
    
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation")
    NAVIGATIONSYSTEM_API void ResetMaxSimultaneousTileGenerationJobsCount();
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation")
    NAVIGATIONSYSTEM_API void RegisterNavigationInvoker(AActor* Invoker, float TileGenerationRadius = 3000, float TileRemovalRadius = 5000);
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation")
    NAVIGATIONSYSTEM_API void UnregisterNavigationInvoker(AActor* Invoker);
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation|Generation")
    NAVIGATIONSYSTEM_API void SetGeometryGatheringMode(ENavDataGatheringModeConfig NewMode);
 
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation", meta=(DisplayName="Replace Area in Octree Data"))
    NAVIGATIONSYSTEM_API bool K2_ReplaceAreaInOctreeData(const UObject* Object, TSubclassOf<UNavArea> OldArea, TSubclassOf<UNavArea> NewArea);
 
    inline bool IsActiveTilesGenerationEnabled() const{ return bGenerateNavigationOnlyAroundNavigationInvokers; }
    
    DECLARE_MULTICAST_DELEGATE_OneParam(FOnNavigationDirty, const FBox&);
    static NAVIGATIONSYSTEM_API FOnNavigationDirty NavigationDirtyEvent;
 
    enum ERegistrationResult
    {
        RegistrationError,
        RegistrationFailed_DataPendingKill,         // means navigation data being registered is marked as pending kill
        RegistrationFailed_AgentAlreadySupported,   // this means that navigation agent supported by given nav data is already handled by some other, previously registered instance
        RegistrationFailed_AgentNotValid,           // given instance contains navmesh that doesn't support any of expected agent types, or instance doesn't specify any agent
        RegistrationFailed_NotSuitable,             // given instance had been considered unsuitable by current navigation system instance itself. NOTE: this value is not currently being used by the engine-supplied navigation system classes
        RegistrationSuccessful,
    };
 
    // EOctreeUpdateMode is deprecated. Use FNavigationOctreeController::EOctreeUpdateMode instead
    enum EOctreeUpdateMode
    {
        OctreeUpdate_Default = 0,                       // regular update, mark dirty areas depending on exported content
        OctreeUpdate_Geometry = 1,                      // full update, mark dirty areas for geometry rebuild
        OctreeUpdate_Modifiers = 2,                     // quick update, mark dirty areas for modifier rebuild
        OctreeUpdate_Refresh = 4,                       // update is used for refresh, don't invalidate pending queue
        OctreeUpdate_ParentChain = 8,                   // update child nodes, don't remove anything
    };
 
    //~ Begin UObject Interface
    NAVIGATIONSYSTEM_API virtual void PostInitProperties() override;
    NAVIGATIONSYSTEM_API virtual void FinishDestroy() override;
    static NAVIGATIONSYSTEM_API void AddReferencedObjects(UObject* InThis, FReferenceCollector& Collector);
#if WITH_EDITOR
    NAVIGATIONSYSTEM_API virtual void PostEditChangeChainProperty(FPropertyChangedChainEvent& PropertyChangedEvent) override;
    NAVIGATIONSYSTEM_API virtual void PostEditChangeProperty(struct FPropertyChangedEvent& PropertyChangedEvent) override;
#endif // WITH_EDITOR
    //~ End UObject Interface
 
    NAVIGATIONSYSTEM_API virtual void Tick(float DeltaSeconds) override;    
 
    UWorld* GetWorld() const override { return GetOuterUWorld(); }
 
    UCrowdManagerBase* GetCrowdManager() const { return CrowdManager.Get(); }
 
protected:
    NAVIGATIONSYSTEM_API void CalcTimeSlicedUpdateData(TArray<double>& OutCurrentTimeSlicedBuildTaskDurations, TArray<bool>& OutIsTimeSlicingArray, bool& bOutAnyNonTimeSlicedGenerators, TArray<int32, TInlineAllocator<8>>& OutNumTimeSlicedRemainingBuildTasksArray);
 
    NAVIGATIONSYSTEM_API virtual void CreateCrowdManager();
 
    NAVIGATIONSYSTEM_API void SetSupportedAgentsNavigationClass(int32 AgentIndex, TSubclassOf<ANavigationData> NavigationDataClass);
 
public:
    //----------------------------------------------------------------------//
    //~ Begin Public querying Interface                                                                
    //----------------------------------------------------------------------//
    NAVIGATIONSYSTEM_API FPathFindingResult FindPathSync(const FNavAgentProperties& AgentProperties, FPathFindingQuery Query, EPathFindingMode::Type Mode = EPathFindingMode::Regular);
 
    NAVIGATIONSYSTEM_API FPathFindingResult FindPathSync(FPathFindingQuery Query, EPathFindingMode::Type Mode = EPathFindingMode::Regular);
 
    NAVIGATIONSYSTEM_API uint32 FindPathAsync(const FNavAgentProperties& AgentProperties, FPathFindingQuery Query, const FNavPathQueryDelegate& ResultDelegate, EPathFindingMode::Type Mode = EPathFindingMode::Regular);
 
    NAVIGATIONSYSTEM_API void AbortAsyncFindPathRequest(uint32 AsynPathQueryID);
    
    NAVIGATIONSYSTEM_API bool TestPathSync(FPathFindingQuery Query, EPathFindingMode::Type Mode = EPathFindingMode::Regular, int32* NumVisitedNodes = NULL) const;
 
    NAVIGATIONSYSTEM_API bool GetRandomPoint(FNavLocation& ResultLocation, ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL);
 
    NAVIGATIONSYSTEM_API bool GetRandomReachablePointInRadius(const FVector& Origin, float Radius, FNavLocation& ResultLocation, ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL) const;
 
    NAVIGATIONSYSTEM_API bool GetRandomPointInNavigableRadius(const FVector& Origin, float Radius, FNavLocation& ResultLocation, ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL) const;
 
    NAVIGATIONSYSTEM_API ENavigationQueryResult::Type GetPathCost(const FVector& PathStart, const FVector& PathEnd, FVector::FReal& PathCost, const ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL) const;
 
    NAVIGATIONSYSTEM_API ENavigationQueryResult::Type GetPathLength(const FVector& PathStart, const FVector& PathEnd, FVector::FReal& PathLength, const ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL) const;
 
    NAVIGATIONSYSTEM_API ENavigationQueryResult::Type GetPathLengthAndCost(const FVector& PathStart, const FVector& PathEnd, FVector::FReal& PathLength, FVector::FReal& PathCost, const ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL) const;
 
    // @todo document
    bool ProjectPointToNavigation(const FVector& Point, FNavLocation& OutLocation, const FVector& Extent = INVALID_NAVEXTENT, const FNavAgentProperties* AgentProperties = NULL, FSharedConstNavQueryFilter QueryFilter = NULL)
    {
        return ProjectPointToNavigation(Point, OutLocation, Extent, AgentProperties != NULL ? GetNavDataForProps(*AgentProperties, Point) : GetDefaultNavDataInstance(FNavigationSystem::DontCreate), QueryFilter);
    }
 
    // @todo document
    NAVIGATIONSYSTEM_API bool ProjectPointToNavigation(const FVector& Point, FNavLocation& OutLocation, const FVector& Extent = INVALID_NAVEXTENT, const ANavigationData* NavData = NULL, FSharedConstNavQueryFilter QueryFilter = NULL) const;
 
    NAVIGATIONSYSTEM_API virtual ANavigationData* GetNavDataForProps(const FNavAgentProperties& AgentProperties);
 
    NAVIGATIONSYSTEM_API virtual const ANavigationData* GetNavDataForProps(const FNavAgentProperties& AgentProperties) const;
 
    NAVIGATIONSYSTEM_API virtual ANavigationData* GetNavDataForAgentName(const FName AgentName) const;
 
    NAVIGATIONSYSTEM_API virtual ANavigationData* GetNavDataForProps(const FNavAgentProperties& AgentProperties, const FVector& AgentLocation, const FVector& Extent = INVALID_NAVEXTENT) const;
 
    NAVIGATIONSYSTEM_API ANavigationData* GetDefaultNavDataInstance(FNavigationSystem::ECreateIfMissing CreateNewIfNoneFound);
    virtual INavigationDataInterface* GetMainNavData() const override { return Cast<INavigationDataInterface>(GetDefaultNavDataInstance()); }
    ANavigationData& GetMainNavDataChecked() const { check(MainNavData); return *MainNavData; }
 
    NAVIGATIONSYSTEM_API virtual void SetBuildBounds(const FBox& Bounds) override;
 
    NAVIGATIONSYSTEM_API virtual FBox GetNavigableWorldBounds() const override;
 
    NAVIGATIONSYSTEM_API virtual bool ContainsNavData(const FBox& Bounds) const override;
    NAVIGATIONSYSTEM_API virtual FBox ComputeNavDataBounds() const override;
    NAVIGATIONSYSTEM_API virtual void AddNavigationDataChunk(class ANavigationDataChunkActor& DataChunkActor) override;
    NAVIGATIONSYSTEM_API virtual void RemoveNavigationDataChunk(class ANavigationDataChunkActor& DataChunkActor) override;
    NAVIGATIONSYSTEM_API virtual void FillNavigationDataChunkActor(const FBox& QueryBounds, class ANavigationDataChunkActor& DataChunkActor, FBox& OutTilesBounds) override;
 
    ANavigationData* GetDefaultNavDataInstance() const { return MainNavData; }
 
    ANavigationData* GetAbstractNavData() const { return AbstractNavData; }
 
    NAVIGATIONSYSTEM_API virtual ANavigationData* CreateNavigationDataInstanceInLevel(const FNavDataConfig& NavConfig, ULevel* SpawnLevel);
 
    NAVIGATIONSYSTEM_API FSharedNavQueryFilter CreateDefaultQueryFilterCopy() const;
 
    NAVIGATIONSYSTEM_API bool ShouldGeneratorRun(const FNavDataGenerator* Generator) const;
 
    NAVIGATIONSYSTEM_API virtual bool IsNavigationBuilt(const AWorldSettings* Settings) const override;
 
    NAVIGATIONSYSTEM_API virtual bool IsThereAnywhereToBuildNavigation() const;
 
    bool ShouldGenerateNavigationEverywhere() const { return bWholeWorldNavigable; }
 
    bool ShouldAllowClientSideNavigation() const { return bAllowClientSideNavigation; }
    virtual bool ShouldLoadNavigationOnClient(ANavigationData* NavData = nullptr) const { return bAllowClientSideNavigation; }
    virtual bool ShouldDiscardSubLevelNavData(ANavigationData* NavData = nullptr) const { return bShouldDiscardSubLevelNavData; }
 
    NAVIGATIONSYSTEM_API FBox GetWorldBounds() const;
    
    NAVIGATIONSYSTEM_API FBox GetLevelBounds(ULevel* InLevel) const;
 
    NAVIGATIONSYSTEM_API bool IsNavigationRelevant(const AActor* TestActor) const;
 
    NAVIGATIONSYSTEM_API const TSet<FNavigationBounds>& GetNavigationBounds() const;
 
    static NAVIGATIONSYSTEM_API const FNavDataConfig& GetDefaultSupportedAgent();
    static NAVIGATIONSYSTEM_API const FNavDataConfig& GetBiggestSupportedAgent(const UWorld* World);
    
#if WITH_EDITOR
    static NAVIGATIONSYSTEM_API double GetWorldPartitionNavigationDataBuilderOverlap(const UWorld& World);
#endif
    
    NAVIGATIONSYSTEM_API const FNavDataConfig& GetDefaultSupportedAgentConfig() const;
    inline const TArray<FNavDataConfig>& GetSupportedAgents() const { return SupportedAgents; }
    NAVIGATIONSYSTEM_API void OverrideSupportedAgents(const TArray<FNavDataConfig>& NewSupportedAgents);
    NAVIGATIONSYSTEM_API void SetSupportedAgentsMask(const FNavAgentSelector& InSupportedAgentsMask);
    FNavAgentSelector GetSupportedAgentsMask() const { return SupportedAgentsMask; }
 
    NAVIGATIONSYSTEM_API virtual void ApplyWorldOffset(const FVector& InOffset, bool bWorldShift) override;
 
    NAVIGATIONSYSTEM_API bool IsNavigationDirty() const;
 
    NAVIGATIONSYSTEM_API bool CanRebuildDirtyNavigation() const;
 
    inline bool SupportsNavigationGeneration() const { return bSupportRebuilding; }
 
    static NAVIGATIONSYSTEM_API bool DoesPathIntersectBox(const FNavigationPath* Path, const FBox& Box, uint32 StartingIndex = 0, FVector* AgentExtent = NULL);
    static NAVIGATIONSYSTEM_API bool DoesPathIntersectBox(const FNavigationPath* Path, const FBox& Box, const FVector& AgentLocation, uint32 StartingIndex = 0, FVector* AgentExtent = NULL);
    
    //----------------------------------------------------------------------//
    // Active tiles
    //----------------------------------------------------------------------//
    NAVIGATIONSYSTEM_API virtual void RegisterInvoker(AActor& Invoker, float TileGenerationRadius, float TileRemovalRadius, const FNavAgentSelector& Agents, ENavigationInvokerPriority InPriority);
 
    NAVIGATIONSYSTEM_API virtual void RegisterInvoker(const TWeakInterfacePtr<INavigationInvokerInterface>& Invoker, float TileGenerationRadius, float TileRemovalRadius, const FNavAgentSelector& Agents, ENavigationInvokerPriority InPriority);
 
    NAVIGATIONSYSTEM_API virtual void UnregisterInvoker(AActor& Invoker);
    
    NAVIGATIONSYSTEM_API virtual void UnregisterInvoker(const TWeakInterfacePtr<INavigationInvokerInterface>& Invoker);
 
    static NAVIGATIONSYSTEM_API void RegisterNavigationInvoker(AActor& Invoker, float TileGenerationRadius, float TileRemovalRadius, 
        const FNavAgentSelector& Agents = FNavAgentSelector(), ENavigationInvokerPriority Priority = ENavigationInvokerPriority::Default);
    static NAVIGATIONSYSTEM_API void UnregisterNavigationInvoker(AActor& Invoker);
 
    const TArray<FNavigationInvokerRaw>& GetInvokerLocations() const { return InvokerLocations; }
    const TArray<FBox>& GetInvokersSeedBounds() const { return InvokersSeedBounds; }
 
    //----------------------------------------------------------------------//
    // Bookkeeping 
    //----------------------------------------------------------------------//
    
    // @todo document
    NAVIGATIONSYSTEM_API virtual void UnregisterNavData(ANavigationData* NavData);
 
    NAVIGATIONSYSTEM_API virtual void UnregisterUnusedNavData();
 
    NAVIGATIONSYSTEM_API virtual void RequestRegistrationDeferred(ANavigationData& NavData);
 
protected:
    NAVIGATIONSYSTEM_API void ApplySupportedAgentsFilter();
 
    NAVIGATIONSYSTEM_API void RegisterNavigationDataInstances();
 
    NAVIGATIONSYSTEM_API virtual bool ConditionalPopulateNavOctree();
 
    NAVIGATIONSYSTEM_API virtual void ConstructNavOctree();
 
    NAVIGATIONSYSTEM_API virtual void ProcessRegistrationCandidates();
 
    NAVIGATIONSYSTEM_API void ProcessCustomLinkPendingRegistration();
 
    NAVIGATIONSYSTEM_API virtual void PerformNavigationBoundsUpdate(const TArray<FNavigationBoundsUpdateRequest>& UpdateRequests);
    
    NAVIGATIONSYSTEM_API void AddNavigationBounds(const FNavigationBounds& NewBounds);
 
    NAVIGATIONSYSTEM_API virtual void GatherNavigationBounds();
 
    NAVIGATIONSYSTEM_API virtual void GetInvokerSeedLocations(const UWorld& InWorld, TArray<FVector, TInlineAllocator<32>>& OutSeedLocations);
 
    NAVIGATIONSYSTEM_API ANavigationData* GetNavDataWithID(const uint16 NavDataID) const;
 
    NAVIGATIONSYSTEM_API TSharedPtr<const FNavigationElement> GetNavigationElementForUObject(const UObject*) const;
 
    NAVIGATIONSYSTEM_API FNavigationElementHandle GetNavigationElementHandleForUObject(const UObject*) const;
 
    static NAVIGATIONSYSTEM_API void RegisterComponentToNavOctree(UActorComponent* Comp);
    static NAVIGATIONSYSTEM_API void UnregisterComponentToNavOctree(UActorComponent* Comp);
 
public:
    NAVIGATIONSYSTEM_API virtual void ReleaseInitialBuildingLock();
 
    //----------------------------------------------------------------------//
    // navigation octree related functions
    //----------------------------------------------------------------------//
    static NAVIGATIONSYSTEM_API bool SupportsDynamicChanges(UWorld* World);
    static NAVIGATIONSYSTEM_API FNavigationElementHandle AddNavigationElement(UWorld* World, FNavigationElement&& Element);
    static NAVIGATIONSYSTEM_API void RemoveNavigationElement(UWorld* World, FNavigationElementHandle ElementHandle);
    static NAVIGATIONSYSTEM_API void OnNavigationElementUpdated(UWorld* World, FNavigationElementHandle ElementHandle, FNavigationElement&& Element);
 
    static NAVIGATIONSYSTEM_API void OnNavRelevantObjectRegistered(UObject& Object);
    static NAVIGATIONSYSTEM_API void UpdateNavRelevantObjectInNavOctree(UObject& Object);
    static NAVIGATIONSYSTEM_API void OnNavRelevantObjectUnregistered(UObject& Object);
 
    static NAVIGATIONSYSTEM_API void OnComponentRegistered(UActorComponent* Comp);
    static NAVIGATIONSYSTEM_API void OnComponentUnregistered(UActorComponent* Comp);
    static NAVIGATIONSYSTEM_API void RegisterComponent(UActorComponent* Comp);
    static NAVIGATIONSYSTEM_API void UnregisterComponent(UActorComponent* Comp);
    static NAVIGATIONSYSTEM_API void OnActorRegistered(AActor* Actor);
    static NAVIGATIONSYSTEM_API void OnActorUnregistered(AActor* Actor);
 
    static NAVIGATIONSYSTEM_API void UpdateActorInNavOctree(AActor& Actor);
    static NAVIGATIONSYSTEM_API void UpdateComponentInNavOctree(UActorComponent& Comp);
    static NAVIGATIONSYSTEM_API void UpdateActorAndComponentsInNavOctree(AActor& Actor, bool bUpdateAttachedActors = true);
    static NAVIGATIONSYSTEM_API void UpdateNavOctreeAfterMove(USceneComponent* Comp);
 
protected:
    static NAVIGATIONSYSTEM_API void RegisterNavRelevantObjectStatic(const INavRelevantInterface& NavRelevantObject, const UObject& Object);
 
    NAVIGATIONSYSTEM_API void RegisterNavRelevantObjectInternal(const INavRelevantInterface& NavRelevantObject, const UObject& Object);
 
    static NAVIGATIONSYSTEM_API void UnregisterNavRelevantObjectStatic(const UObject& Object);
 
    NAVIGATIONSYSTEM_API void UnregisterNavRelevantObjectInternal(const UObject& Object);
 
    static NAVIGATIONSYSTEM_API void UpdateNavRelevantObjectInNavOctreeStatic(
        const INavRelevantInterface& InNavRelevantObject,
        const UObject& InObject,
        UNavigationSystemV1* InNavigationSystem,
        TFunctionRef<void(UNavigationSystemV1&, const TSharedRef<const FNavigationElement>&)> InCallback);
 
    static NAVIGATIONSYSTEM_API int32 GetAllAttachedActors(const AActor& RootActor, TArray<AActor*>& OutAttachedActors);
 
    static NAVIGATIONSYSTEM_API void UpdateAttachedActorsInNavOctree(AActor& RootActor);
 
public:
    static NAVIGATIONSYSTEM_API void ClearNavOctreeAll(AActor* Actor);
 
    static NAVIGATIONSYSTEM_API void UpdateNavOctreeBounds(AActor* Actor);
 
    NAVIGATIONSYSTEM_API void AddDirtyArea(const FBox& NewArea, ENavigationDirtyFlag Flags, const FName& DebugReason = NAME_None);
    NAVIGATIONSYSTEM_API void AddDirtyArea(const FBox& NewArea, ENavigationDirtyFlag Flags, const TFunction<const TSharedPtr<const FNavigationElement>()>& ElementProviderFunc, const FName& DebugReason = NAME_None);
    NAVIGATIONSYSTEM_API void AddDirtyAreas(const TArray<FBox>& NewAreas, ENavigationDirtyFlag Flags, const FName& DebugReason = NAME_None);
    UE_DEPRECATED(5.5, "Use the version taking ENavigationDirtyFlag instead.")
    NAVIGATIONSYSTEM_API void AddDirtyArea(const FBox& NewArea, int32 Flags, const FName& DebugReason = NAME_None);
    UE_DEPRECATED(5.5, "Use the version taking ENavigationDirtyFlag instead.")
    NAVIGATIONSYSTEM_API void AddDirtyArea(const FBox& NewArea, int32 Flags, const TFunction<UObject*()>& ObjectProviderFunc, const FName& DebugReason = NAME_None);
    UE_DEPRECATED(5.5, "Use the version taking ENavigationDirtyFlag instead.")
    NAVIGATIONSYSTEM_API void AddDirtyAreas(const TArray<FBox>& NewAreas, int32 Flags, const FName& DebugReason = NAME_None);
    NAVIGATIONSYSTEM_API bool HasDirtyAreasQueued() const;
    NAVIGATIONSYSTEM_API int32 GetNumDirtyAreas() const;
    float GetDirtyAreaWarningSizeThreshold() const { return DirtyAreaWarningSizeThreshold; }
 
    const FNavigationOctree* GetNavOctree() const { return DefaultOctreeController.GetOctree(); }
    FNavigationOctree* GetMutableNavOctree() { return DefaultOctreeController.GetMutableOctree(); }
 
    UE_DEPRECATED(5.5, "This method is no longer used by the navigation system.")
    NAVIGATIONSYSTEM_API static uint32 HashObject(const UObject& Object);
 
    inline const FOctreeElementId2* GetNavOctreeIdForElement(FNavigationElementHandle Element) const
    {
        return DefaultOctreeController.GetNavOctreeIdForElement(Element);
    }
    UE_DEPRECATED(5.5, "Use GetNavOctreeIdForElement instead.")
    NAVIGATIONSYSTEM_API const FOctreeElementId2* GetObjectsNavOctreeId(const UObject& Object) const;
 
    inline bool HasPendingUpdateForElement(FNavigationElementHandle Element) const
    {
        return DefaultOctreeController.HasPendingUpdateForElement(Element);
    }
    UE_DEPRECATED(5.5, "Use HasPendingUpdateForElement instead.")
    NAVIGATIONSYSTEM_API bool HasPendingObjectNavOctreeId(UObject* Object) const;
 
    UE_DEPRECATED(5.5, "This functionality should not be exposed and will be removed.")
    NAVIGATIONSYSTEM_API void RemoveObjectsNavOctreeId(const UObject& Object);
 
    UE_DEPRECATED(5.5, "This functionality should not be exposed publicly and will be removed. Derived classes should use RemoveFromNavOctree instead.")
    NAVIGATIONSYSTEM_API void RemoveNavOctreeElementId(const FOctreeElementId2& ElementId, int32 UpdateFlags);
 
protected:
    NAVIGATIONSYSTEM_API void RemoveFromNavOctree(const FOctreeElementId2& ElementId, int32 UpdateFlags);
public:
 
    NAVIGATIONSYSTEM_API const FNavigationRelevantData* GetDataForElement(FNavigationElementHandle Element) const;
    UE_DEPRECATED(5.5, "Use GetDataForElement instead.")
    NAVIGATIONSYSTEM_API const FNavigationRelevantData* GetDataForObject(const UObject& Object) const;
 
    NAVIGATIONSYSTEM_API FNavigationRelevantData* GetMutableDataForElement(FNavigationElementHandle Element);
 
    UE_DEPRECATED(5.5, "Use GetMutableDataForElement instead.")
    NAVIGATIONSYSTEM_API FNavigationRelevantData* GetMutableDataForObject(const UObject& Object);
 
    NAVIGATIONSYSTEM_API void FindElementsInNavOctree(const FBox& QueryBox, const FNavigationOctreeFilter& Filter, TArray<FNavigationOctreeElement>& Elements);
 
    NAVIGATIONSYSTEM_API void UpdateNavOctreeElement(FNavigationElementHandle Handle, const TSharedRef<const FNavigationElement>& Element, int32 UpdateFlags);
    UE_DEPRECATED(5.5, "Use the version taking FNavigationElement instead.")
    void UpdateNavOctreeElement(UObject* ElementOwner, INavRelevantInterface* ElementInterface, int32 UpdateFlags);
 
    UE_DEPRECATED(5.5, "This method will no longer be public and should not be called directly.")
    NAVIGATIONSYSTEM_API void UpdateNavOctreeParentChain(UObject* ElementOwner, bool bSkipElementOwnerUpdate = false);
 
    NAVIGATIONSYSTEM_API bool UpdateNavOctreeElementBounds(FNavigationElementHandle Handle, const FBox& NewBounds, TConstArrayView<FBox> DirtyAreas);
 
    UE_DEPRECATED(5.5, "Use the version taking FNavigationElement instead.")
    NAVIGATIONSYSTEM_API bool UpdateNavOctreeElementBounds(UObject& Object, const FBox& NewBounds, TConstArrayView<FBox> DirtyAreas);
 
    NAVIGATIONSYSTEM_API bool ReplaceAreaInOctreeData(FNavigationElementHandle Handle, TSubclassOf<UNavArea> OldArea, TSubclassOf<UNavArea> NewArea, bool bReplaceChildClasses = false);
    UE_DEPRECATED(5.5, "Use the version taking FNavigationElement instead.")
    NAVIGATIONSYSTEM_API bool ReplaceAreaInOctreeData(const UObject& Object, TSubclassOf<UNavArea> OldArea, TSubclassOf<UNavArea> NewArea, bool bReplaceChildClasses = false);
 
    //----------------------------------------------------------------------//
    // Custom navigation links
    //----------------------------------------------------------------------//
    NAVIGATIONSYSTEM_API virtual void RegisterCustomLink(INavLinkCustomInterface& CustomLink);
    NAVIGATIONSYSTEM_API void UnregisterCustomLink(INavLinkCustomInterface& CustomLink);
    int32 GetNumCustomLinks() const { return CustomNavLinksMap.Num(); }
 
    static NAVIGATIONSYSTEM_API void RequestCustomLinkRegistering(INavLinkCustomInterface& CustomLink, UObject* OwnerOb);
    static NAVIGATIONSYSTEM_API void RequestCustomLinkUnregistering(INavLinkCustomInterface& CustomLink, UObject* ObjectOb);
 
    UE_DEPRECATED(5.3, "LinkIds are now based on FNavLinkId call the version of this function that takes FNavLinkId. This function only returns nullptr.")
    INavLinkCustomInterface* GetCustomLink(uint32 UniqueLinkId) const { return nullptr; }
 
    NAVIGATIONSYSTEM_API INavLinkCustomInterface* GetCustomLink(FNavLinkId UniqueLinkId) const;
 
    NAVIGATIONSYSTEM_API void UpdateCustomLink(const INavLinkCustomInterface* CustomLink);
 
    static NAVIGATIONSYSTEM_API FBox ComputeCustomLinkBounds(const INavLinkCustomInterface& CustomLink);
 
    //----------------------------------------------------------------------//
    // Areas
    //----------------------------------------------------------------------//
    static NAVIGATIONSYSTEM_API void RequestAreaRegistering(UClass* NavAreaClass);
    static NAVIGATIONSYSTEM_API void RequestAreaUnregistering(UClass* NavAreaClass);
 
    NAVIGATIONSYSTEM_API int32 GetSupportedAgentIndex(const ANavigationData* NavData) const;
 
    NAVIGATIONSYSTEM_API int32 GetSupportedAgentIndex(const FNavAgentProperties& NavAgent) const;
 
    //----------------------------------------------------------------------//
    // Filters
    //----------------------------------------------------------------------//
    
    NAVIGATIONSYSTEM_API void DescribeFilterFlags(UEnum* FlagsEnum) const;
 
    NAVIGATIONSYSTEM_API void DescribeFilterFlags(const TArray<FString>& FlagsDesc) const;
 
    NAVIGATIONSYSTEM_API void ResetCachedFilter(TSubclassOf<UNavigationQueryFilter> FilterClass);
 
    //----------------------------------------------------------------------//
    // building
    //----------------------------------------------------------------------//
    
    NAVIGATIONSYSTEM_API virtual void Build();
 
    NAVIGATIONSYSTEM_API virtual void CancelBuild();
 
    // @todo document
    NAVIGATIONSYSTEM_API void OnPIEStart();
    // @todo document
    NAVIGATIONSYSTEM_API void OnPIEEnd();
    
    // @todo document
    inline bool IsNavigationBuildingLocked(uint8 Flags = ~0) const { return (NavBuildingLockFlags & Flags) != 0; }
 
    inline bool IsNavigationBuildingPermanentlyLocked() const
    {
        return (NavBuildingLockFlags & ~ENavigationBuildLock::InitialLock) != 0; 
    }
 
    inline bool IsNavigationOctreeLocked() const { return DefaultOctreeController.IsNavigationOctreeLocked(); }
 
    // @todo document
    UFUNCTION(BlueprintCallable, Category = "AI|Navigation")
    NAVIGATIONSYSTEM_API void OnNavigationBoundsUpdated(ANavMeshBoundsVolume* NavVolume);
    NAVIGATIONSYSTEM_API virtual void OnNavigationBoundsAdded(ANavMeshBoundsVolume* NavVolume);
    NAVIGATIONSYSTEM_API virtual void OnNavigationBoundsRemoved(ANavMeshBoundsVolume* NavVolume);
 
    NAVIGATIONSYSTEM_API bool IsNavigationBuildInProgress();
    
    NAVIGATIONSYSTEM_API virtual void OnNavigationGenerationFinished(ANavigationData& NavData);
 
    NAVIGATIONSYSTEM_API int32 GetNumRemainingBuildTasks() const;
 
    NAVIGATIONSYSTEM_API int32 GetNumRunningBuildTasks() const;
 
protected:
    NAVIGATIONSYSTEM_API virtual void DoInitialSetup();
 
    NAVIGATIONSYSTEM_API virtual void UpdateAbstractNavData();
    
    NAVIGATIONSYSTEM_API virtual void AddLevelToOctree(ULevel& Level);
 
    NAVIGATIONSYSTEM_API virtual void OnBeginTearingDown(UWorld* World);
    
public:
    NAVIGATIONSYSTEM_API virtual void CleanUp(const FNavigationSystem::ECleanupMode Mode = FNavigationSystem::ECleanupMode::CleanupUnsafe) override;
 
    NAVIGATIONSYSTEM_API virtual void OnInitializeActors() override;
 
    NAVIGATIONSYSTEM_API virtual void OnWorldInitDone(FNavigationSystemRunMode Mode);
 
    inline virtual bool IsWorldInitDone() const override { return bWorldInitDone; }
    inline bool IsInitialized() const { return bWorldInitDone; }
 
    inline FNavigationSystemRunMode GetRunMode() const { return OperationMode; }
 
    NAVIGATIONSYSTEM_API void InitializeLevelCollisions();
 
    enum class ELockRemovalRebuildAction
    {
        Rebuild,
        RebuildIfNotInEditor,
        NoRebuild
    };
    NAVIGATIONSYSTEM_API void AddNavigationBuildLock(uint8 Flags);
    NAVIGATIONSYSTEM_API void RemoveNavigationBuildLock(uint8 Flags, const ELockRemovalRebuildAction RebuildAction = ELockRemovalRebuildAction::Rebuild);
 
    NAVIGATIONSYSTEM_API void SetNavigationOctreeLock(bool bLock);
 
    virtual bool GetIsAutoUpdateEnabled() const { return bNavigationAutoUpdateEnabled; }
 
#if WITH_EDITOR
    static NAVIGATIONSYSTEM_API void SetNavigationAutoUpdateEnabled(bool bNewEnable, UNavigationSystemBase* InNavigationSystem);
 
    inline bool IsNavigationRegisterLocked() const { return NavUpdateLockFlags != 0; }
    inline bool IsNavigationUnregisterLocked() const { return NavUpdateLockFlags && !(NavUpdateLockFlags & ENavigationLockReason::AllowUnregister); }
    inline bool IsNavigationUpdateLocked() const { return IsNavigationRegisterLocked(); }
    inline void AddNavigationUpdateLock(uint8 Flags) { NavUpdateLockFlags |= Flags; }
    inline void RemoveNavigationUpdateLock(uint8 Flags) { NavUpdateLockFlags &= ~Flags; }
 
    NAVIGATIONSYSTEM_API void UpdateLevelCollision(ULevel* InLevel);
 
#endif // WITH_EDITOR
 
    inline bool IsSetUpForLazyGeometryExporting() const { return bGenerateNavigationOnlyAroundNavigationInvokers; }
 
    UE_DEPRECATED(5.5, "This creation flow is deprecation. Use FNavigationSystem::AddNavigationSystemToWorld instead.")
    static NAVIGATIONSYSTEM_API UNavigationSystemV1* CreateNavigationSystem(UWorld* WorldOwner);
 
    static NAVIGATIONSYSTEM_API UNavigationSystemV1* GetCurrent(UWorld* World);
    static NAVIGATIONSYSTEM_API UNavigationSystemV1* GetCurrent(UObject* WorldContextObject);
    
    NAVIGATIONSYSTEM_API virtual void InitializeForWorld(UWorld& World, FNavigationSystemRunMode Mode) override;
 
    // Fetch the array of all nav-agent properties.
    NAVIGATIONSYSTEM_API void GetNavAgentPropertiesArray(TArray<FNavAgentProperties>& OutNavAgentProperties) const;
 
    static inline bool ShouldUpdateNavOctreeOnComponentChange()
    {
        return (bUpdateNavOctreeOnComponentChange && !bStaticRuntimeNavigation)
#if WITH_EDITOR
            || (GIsEditor && !GIsPlayInEditorWorld)
#endif
            ;
    }
 
    NAVIGATIONSYSTEM_API virtual bool ShouldCreateNavigationSystemInstance(const UWorld* World) const override;
 
    static inline bool IsNavigationSystemStatic()
    {
#if WITH_EDITOR
        return (bStaticRuntimeNavigation && !(GIsEditor && !GIsPlayInEditorWorld))
            || IsRunningCookCommandlet(); // consider navigation static when cooking to eliminate useless operations
#else
    return bStaticRuntimeNavigation;
#endif // WITH_EDITOR
    }
 
    static NAVIGATIONSYSTEM_API void ConfigureAsStatic(bool bEnableStatic = true);
 
    static NAVIGATIONSYSTEM_API void SetUpdateNavOctreeOnComponentChange(bool bNewUpdateOnComponentChange);
 
    NAVIGATIONSYSTEM_API bool HandleCycleNavDrawnCommand( const TCHAR* Cmd, FOutputDevice& Ar );
    NAVIGATIONSYSTEM_API bool HandleCountNavMemCommand();
    
    //----------------------------------------------------------------------//
    // debug
    //----------------------------------------------------------------------//
    NAVIGATIONSYSTEM_API void CycleNavigationDataDrawn();
 
    FNavRegenTimeSliceManager& GetMutableNavRegenTimeSliceManager() { return NavRegenTimeSliceManager; }
 
    FNavigationSystemRunMode GetOperationMode() const { return OperationMode; }
 
protected:
 
    UPROPERTY()
    FNavigationSystemRunMode OperationMode;
 
    TArray<FAsyncPathFindingQuery> AsyncPathFindingQueries;
 
    TArray<FAsyncPathFindingQuery> AsyncPathFindingCompletedQueries;
 
    FGraphEventRef AsyncPathFindingTask;
 
    TAtomic<bool> bAbortAsyncQueriesRequested;
 
    FCriticalSection NavDataRegistration;
 
    TMap<FNavAgentProperties, TWeakObjectPtr<ANavigationData> > AgentToNavDataMap;
    
    FNavigationOctreeController DefaultOctreeController;
 
    TMap<FNavLinkId, FNavigationSystem::FCustomLinkOwnerInfo> CustomNavLinksMap;
 
    FNavigationDirtyAreasController DefaultDirtyAreasController;
 
    UPROPERTY(transient)
    TObjectPtr<UNavigationObjectRepository> Repository = nullptr;
 
    // async queries
    FCriticalSection NavDataRegistrationSection;
 
#if WITH_EDITOR
    uint8 NavUpdateLockFlags;
#endif
    uint8 NavBuildingLockFlags;
 
    uint8 InitialNavBuildingLockFlags;
    
    uint8 bInitialSetupHasBeenPerformed : 1;
    uint8 bInitialLevelsAdded : 1;
    uint8 bWorldInitDone : 1;
    uint8 bCleanUpDone : 1;
    uint8 bAsyncBuildPaused : 1; // mz@todo remove, replaced by bIsPIEActive and IsGameWorld
protected:
 
    mutable FBox NavigableWorldBounds;
 
    int32 CurrentlyDrawnNavDataIndex;
    
#if !UE_BUILD_SHIPPING
    static NAVIGATIONSYSTEM_API FNavigationSystemExec ExecHandler;
#endif // !UE_BUILD_SHIPPING
    
    static NAVIGATIONSYSTEM_API bool bNavigationAutoUpdateEnabled;
    static NAVIGATIONSYSTEM_API bool bUpdateNavOctreeOnComponentChange;
    static NAVIGATIONSYSTEM_API bool bStaticRuntimeNavigation;
    static NAVIGATIONSYSTEM_API bool bIsPIEActive;
 
    TSet<TObjectPtr<const UClass>> NavAreaClasses;
 
    FNavRegenTimeSliceManager NavRegenTimeSliceManager;
 
    NAVIGATIONSYSTEM_API void OnPostLoadMap(UWorld* LoadedWorld);
#if WITH_EDITOR
    NAVIGATIONSYSTEM_API void OnActorMoved(AActor* Actor);
#endif
    NAVIGATIONSYSTEM_API void OnNavigationDirtied(const FBox& Bounds);
 
    FDelegateHandle ReloadCompleteDelegateHandle;
 
    NAVIGATIONSYSTEM_API virtual void OnReloadComplete(EReloadCompleteReason Reason);
 
    NAVIGATIONSYSTEM_API virtual ERegistrationResult RegisterNavData(ANavigationData* NavData);
 
    NAVIGATIONSYSTEM_API void RegisterNavAreaClass(UClass* NavAreaClass);
 
    NAVIGATIONSYSTEM_API void UnregisterNavAreaClass(UClass* NavAreaClass);
 
    NAVIGATIONSYSTEM_API void OnNavigationAreaEvent(UClass* AreaClass, ENavAreaEvent::Type Event);
 
    NAVIGATIONSYSTEM_API FSetElementId RegisterNavigationElementWithNavOctree(const TSharedRef<const FNavigationElement>& Element, int32 UpdateFlags);
    UE_DEPRECATED(5.5, "Use the version taking FNavigationElement as parameter instead.")
    NAVIGATIONSYSTEM_API FSetElementId RegisterNavOctreeElement(UObject* ElementOwner, INavRelevantInterface* ElementInterface, int32 UpdateFlags);
 
    NAVIGATIONSYSTEM_API void UnregisterNavigationElementWithOctree(const TSharedRef<const FNavigationElement>& Element, int32 UpdateFlags);
    UE_DEPRECATED(5.5, "Use the version taking FNavigationElement as parameter instead.")
    NAVIGATIONSYSTEM_API void UnregisterNavOctreeElement(UObject* ElementOwner, INavRelevantInterface* ElementInterface, int32 UpdateFlags);
 
    NAVIGATIONSYSTEM_API bool GetNavOctreeElementData(FNavigationElementHandle Element, ENavigationDirtyFlag& OutDirtyFlags, FBox& OutDirtyBounds);
    UE_DEPRECATED(5.5, "Use the version taking FNavigationElement instead.")
    NAVIGATIONSYSTEM_API bool GetNavOctreeElementData(const UObject& NodeOwner, int32& DirtyFlags, FBox& DirtyBounds);
 
    NAVIGATIONSYSTEM_API void AddElementToNavOctree(const FNavigationDirtyElement& DirtyElement);
 
    NAVIGATIONSYSTEM_API void SetCrowdManager(UCrowdManagerBase* NewCrowdManager);
 
    NAVIGATIONSYSTEM_API void AddLevelCollisionToOctree(ULevel* Level);
    
    NAVIGATIONSYSTEM_API void RemoveLevelCollisionFromOctree(ULevel* Level);
 
    NAVIGATIONSYSTEM_API virtual void SpawnMissingNavigationData();
 
    NAVIGATIONSYSTEM_API uint8 FillInstantiatedDataMask(TBitArray<>& OutInstantiatedMask, ULevel* InLevel = nullptr);
 
    NAVIGATIONSYSTEM_API void SpawnMissingNavigationDataInLevel(const TBitArray<>& InInstantiatedMask, ULevel* InLevel = nullptr);
 
public:
    NAVIGATIONSYSTEM_API void DemandLazyDataGathering(FNavigationRelevantData& ElementData);
 
private:
    // Reduces a nav bounds only to regions overlapping loaded world partition regions (if any exist)
    void CheckToLimitNavigationBoundsToLoadedRegions(FNavigationBounds& OutBounds) const;
 
protected:
    NAVIGATIONSYSTEM_API virtual void RebuildDirtyAreas(float DeltaSeconds);
    
    // adds navigation bounds update request to a pending list
    NAVIGATIONSYSTEM_API void AddNavigationBoundsUpdateRequest(const FNavigationBoundsUpdateRequest& UpdateRequest);
 
    NAVIGATIONSYSTEM_API virtual void RebuildAll(bool bIsLoadTime = false);
         
     NAVIGATIONSYSTEM_API void OnLevelAddedToWorld(ULevel* InLevel, UWorld* InWorld);
     
    NAVIGATIONSYSTEM_API void OnLevelRemovedFromWorld(ULevel* InLevel, UWorld* InWorld);
 
    void OnWorldPostActorTick(UWorld* World, ELevelTick TickType, float DeltaTime)
    {
        TRACE_CPUPROFILER_EVENT_SCOPE(UNavigationSystemV1::OnWorldPostActorTick)
        PostponeAsyncQueries();
    }
 
    NAVIGATIONSYSTEM_API void AddAsyncQuery(const FAsyncPathFindingQuery& Query);
         
    NAVIGATIONSYSTEM_API void TriggerAsyncQueries(TArray<FAsyncPathFindingQuery>& PathFindingQueries);
 
    NAVIGATIONSYSTEM_API void PerformAsyncQueries(TArray<FAsyncPathFindingQuery> PathFindingQueries);
 
    NAVIGATIONSYSTEM_API void DispatchAsyncQueriesResults(const TArray<FAsyncPathFindingQuery>& PathFindingQueries) const;
 
    NAVIGATIONSYSTEM_API void PostponeAsyncQueries();
 
    NAVIGATIONSYSTEM_API virtual void DestroyNavOctree();
 
    NAVIGATIONSYSTEM_API bool RequiresNavOctree() const;
 
    NAVIGATIONSYSTEM_API ERuntimeGenerationType GetRuntimeGenerationType() const;
 
    NAVIGATIONSYSTEM_API void LogNavDataRegistrationResult(ERegistrationResult);
 
    NAVIGATIONSYSTEM_API bool IsAllowedToRebuild() const;
 
    NAVIGATIONSYSTEM_API void OnGenerateNavigationOnlyAroundNavigationInvokersChanged();
    
    //----------------------------------------------------------------------//
    // new stuff
    //----------------------------------------------------------------------//
public:
    NAVIGATIONSYSTEM_API void VerifyNavigationRenderingComponents(const bool bShow);
    NAVIGATIONSYSTEM_API virtual int GetNavigationBoundsForNavData(const ANavigationData& NavData, TArray<FBox>& OutBounds, ULevel* InLevel = nullptr) const;
    static NAVIGATIONSYSTEM_API INavigationDataInterface* GetNavDataForActor(const AActor& Actor);
    NAVIGATIONSYSTEM_API virtual void Configure(const UNavigationSystemConfig& Config) override;
    NAVIGATIONSYSTEM_API virtual void AppendConfig(const UNavigationSystemConfig& NewConfig) override;
    
#if !UE_BUILD_SHIPPING
    NAVIGATIONSYSTEM_API void GetOnScreenMessages(TMultiMap<FCoreDelegates::EOnScreenMessageSeverity, FText>& OutMessages);
#endif // !UE_BUILD_SHIPPING
 
    //----------------------------------------------------------------------//
    // DEPRECATED
    //----------------------------------------------------------------------//
public:
    // Note that this function was only deprecated for blueprint in 5.1
    // Note2: originally deprecated as 4.22, bumped up to 5.1 as per comment above.
    UE_DEPRECATED(5.1, "This version is deprecated.  Please use GetRandomLocationInNavigableRadius instead")
    UFUNCTION(BlueprintPure, Category = "AI|Navigation", meta = (WorldContext = "WorldContextObject", DisplayName = "GetRandomPointInNavigableRadius", ScriptName = "GetRandomPointInNavigableRadius", DeprecatedFunction, DeprecationMessage = "GetRandomPointInNavigableRadius is deprecated. Use GetRandomLocationInNavigableRadius instead"))
    static NAVIGATIONSYSTEM_API bool K2_GetRandomPointInNavigableRadius(UObject* WorldContextObject, const FVector& Origin, FVector& RandomLocation, float Radius, ANavigationData* NavData = NULL, TSubclassOf<UNavigationQueryFilter> FilterClass = {});
};
 
//----------------------------------------------------------------------//
// UNavigationSystemModuleConfig 
//----------------------------------------------------------------------//
UCLASS(MinimalAPI)
class UNavigationSystemModuleConfig : public UNavigationSystemConfig
{
    GENERATED_BODY()
 
protected:
    UPROPERTY(EditAnywhere, Category = Navigation)
    uint32 bStrictlyStatic : 1;
 
    UPROPERTY(EditAnywhere, Category = Navigation)
    uint32 bCreateOnClient : 1;
 
    UPROPERTY(EditAnywhere, Category = Navigation)
    uint32 bAutoSpawnMissingNavData : 1;
 
    UPROPERTY(EditAnywhere, Category = Navigation)
    uint32 bSpawnNavDataInNavBoundsLevel : 1;
 
public:
    NAVIGATIONSYSTEM_API UNavigationSystemModuleConfig(const FObjectInitializer& ObjectInitializer = FObjectInitializer::Get());
 
    NAVIGATIONSYSTEM_API virtual void PostInitProperties() override;
 
    NAVIGATIONSYSTEM_API virtual UNavigationSystemBase* CreateAndConfigureNavigationSystem(UWorld& World) const override;
 
#if WITH_EDITOR
    NAVIGATIONSYSTEM_API virtual void PostEditChangeProperty(FPropertyChangedEvent& PropertyChangedEvent) override;
#endif // WITH_EDITOR
 
protected:
#if WITH_EDITOR
    friend UNavigationSystemV1;
#endif // WITH_EDITOR
    NAVIGATIONSYSTEM_API void UpdateWithNavSysCDO(const UNavigationSystemV1& NavSysCDO);
};