I’ve been doing some experiments with navigation in Unreal Engine. The navigation system is pretty powerful but does suffer a bit from a lack of documentation so I’m finding myself discovering things by trial and error and reading the underlying source code. I’m describing some of those experiments here primarily for my own benefit but hopefully others may find it useful as well.

The Level

I’ve set up a test environment, where I have one NPC and two actors, a source and a sink. The NPC first moves toward the sphere-shaped source (let’s pretend it’s picking up some resource) - once it gets there, it moves toward the cube-shaped sink (for dropping off the resource).

There is a NavMeshBoundsVolume around the entire level so there is a navigation mesh covering the whole level.

The NPC

The NPC is very simple - a Blueprint class inheriting from Character, with a SkeletalCube from the engine content for a mesh. The NPC has a State variable - an enum with Source and Sink values, representing the current target for movement.

I’m using this very simple behavior tree to control the NPC:

Behavior Tree

The PickTarget task looks at the state of the NPC and sets the Target value on the blackboard to the appropriate actor.

PickTarget

The AdvanceState task is run after the target is reached, and toggles the State value of the NPC.

AdvanceState

When I hit play, the NPC moves toward the sphere (the source). When it gets there, it turns around and moves toward the cube (the sink). At the cube it turns around again and goes to the sphere, repeating this loop forever. All the movements are in a straight line, as there is nothing interfering with its movements.

Some Obstacles

If I put a few big boxes in the level the NPC navigates around those, as they have blocking collision and cut holes in the navigation mesh. To see the navigation mesh in the editor, I press P.

To make things more interesting, I’m going to add surfaces with different movement speeds. They don’t block the NPC, but slow it down (the sandpit) or speed it up (the pavement). To accomplish that, I’ve added two surface types (sand and pavement) and created corresponding physics materials. The NPC then checks for the underlying surface type on tick and sets its movement speed depending on the surface it is on.

Now when the NPC moves along its path, it speeds up on the pavement and slows down in the sand, but it still picks the same path. If I look at the path in the gameplay debugger I see that those areas don’t affect the navigation mesh at all.

NavAreas

Fortunately there is an easy way to address this. First, I create two NavArea classes to represent the properties of those areas - NavArea_Sand and NavArea_Pavement, setting appropriate values for Default Cost.

The cost for the pavement area is 0.2, as the NPC moves at five times the regular speed in those areas. The cost for the sand is 5.0, as the movement speed is one fifth of the regular speed.

Then I add a NavModifierComponent to the BP_SandPit class and set its Area Class to NavArea_Sand, as well as the BP_Pavement class, setting its Area Class to NavArea_Pavement.

The NavModifierComponent modifies the NavMesh generation, defining an area according to its Area Class following the bounds of the owning object. This allows the pathfinding to find a path that takes the travel speed over those different surfaces into account.

Following A Spline

The NavModifierComponent doesn’t play too well with spline mesh components - if I create a simple road that follows a spline I get a quite jagged approximation of the road surface in the navigation mesh.

I can get around this by adding my own custom nav areas when I’m building up the spline meshes. I made a component, SplineMeshBuilder, that samples a spline and adds SplineMeshComponents to the owning actor. This component inherits from UNavRelevantComponent and overrides the GetNavigationData method.

void USplineMeshBuilder::AddMeshesToOwner()
{
  if (!Mesh || !Spline)
  {
    return;
  }
  float SectionLength = Mesh->GetBounds().BoxExtent.X * 2.0f;
  float SectionHalfWidth = Mesh->GetBounds().BoxExtent.Y * 0.75f;
  float SplineLength = Spline->GetSplineLength();
  int32 NumSegments = SplineLength / SectionLength;

  Bounds.Init();
  
  for (int32 Index = 0; Index < NumSegments; ++Index)
  {
    float Distance = SectionLength * Index;

    FVector StartPos = Spline->GetLocationAtDistanceAlongSpline(Distance, ESplineCoordinateSpace::World);
    FVector StartTangent = Spline->GetTangentAtDistanceAlongSpline(Distance, ESplineCoordinateSpace::World);
    StartTangent = StartTangent.GetClampedToMaxSize(SectionLength);
    FVector EndPos = Spline->GetLocationAtDistanceAlongSpline(Distance + SectionLength, ESplineCoordinateSpace::World);
    FVector EndTangent = Spline->GetTangentAtDistanceAlongSpline(Distance + SectionLength, ESplineCoordinateSpace::World);
    EndTangent = EndTangent.GetClampedToMaxSize(SectionLength);

    USplineMeshComponent* MeshComponent = CreateMeshComponent(StartPos, StartTangent, EndPos, EndTangent);

    GetOwner()->AddOwnedComponent(MeshComponent);
    MeshComponent->RegisterComponent();
    
    SplineMeshComponents.Add(MeshComponent);

    if (AddNavAreas)
    {

      FVector StartRight = Spline->GetRightVectorAtDistanceAlongSpline(Distance, ESplineCoordinateSpace::World);
      FVector EndRight = Spline->GetRightVectorAtDistanceAlongSpline(Distance + SectionLength, ESplineCoordinateSpace::World);

      FVector ZOffset(0.0f, 0.0f, 200.0f);
    
      TArray<FVector> Points;
      Points.Add(StartPos + SectionHalfWidth*StartRight);
      Points.Add(StartPos - SectionHalfWidth*StartRight);
      Points.Add(StartPos + SectionHalfWidth*StartRight + ZOffset);
      Points.Add(StartPos - SectionHalfWidth*StartRight + ZOffset);
      Points.Add(EndPos + SectionHalfWidth*EndRight);
      Points.Add(EndPos - SectionHalfWidth*EndRight);
      Points.Add(EndPos + SectionHalfWidth*EndRight + ZOffset);
      Points.Add(EndPos - SectionHalfWidth*EndRight + ZOffset);

      NavAreas.Add(Points);

      for (auto Point : Points)
      {
        Bounds += Point;
      }
    }
  }

  bBoundsInitialized = true;
  RefreshNavigationModifiers();
}

USplineMeshComponent* USplineMeshBuilder::CreateMeshComponent(FVector StartPos, FVector StartTangent, FVector EndPos, FVector EndTangent)
{
  FName Name = MakeUniqueObjectName(GetOwner(), USplineMeshComponent::StaticClass());
  USplineMeshComponent* MeshComponent = NewObject<USplineMeshComponent>(this, Name);
  MeshComponent->SetStaticMesh(Mesh);
  MeshComponent->SetStartAndEnd(StartPos, StartTangent, EndPos, EndTangent);
  MeshComponent->SetCollisionProfileName(CollisionProfile.Name);
  MeshComponent->SetMobility(EComponentMobility::Movable);
  MeshComponent->CreationMethod = EComponentCreationMethod::Instance;
  MeshComponent->SetPhysMaterialOverride(PhysicalMaterial);

  return MeshComponent;
}

void USplineMeshBuilder::GetNavigationData(FNavigationRelevantData& Data) const
{
  for (int32 Idx = 0; Idx < NavAreas.Num(); Idx++)
  {
    FAreaNavModifier Area = FAreaNavModifier(NavAreas[Idx], ENavigationCoordSystem::Unreal, FTransform::Identity, AreaClass);
    Data.Modifiers.Add(Area);
  }
}

The GetNavigationData method fills in a FNavigationRelevantData structure - in particular it adds to the Modifiers array. The data used to create the areas is built up in the AddMeshesToOwner method, using the spline directly. For each section, the points of each corner are added to an array, which is later used to build up a convex hull around the section.

I could probably be more clever about this - the nav areas don’t have to use the same step size as the meshes when setting this up, and should probably use a varying step size, based on the rate of directional change in the spline. Still, I get a much better fit (and control over it) than when simply using the UNavModifierComponent.

Get the Code

The code for this project is on Github: https://github.com/snorristurluson/Navigation

Any feedback and comments are welcome!