Navigation Modifiers and Links in UE4

Introduction

Continuing on from navigation basics we covered in the last post, we're going to have a look at how we can extend the NavMesh to do all sorts of cool things.

If you haven't followed along, or just want to make sure you're on the same page, you can download what we've done so far from the bitbucket repository.

The topics that we're going to cover include:

  1. Nav Mesh Links
  2. Nav Mesh Areas and Nav Mesh Modifiers
  3. Navigation Filters
  4. Using Navigation for AI that have different sizes
  5. Runtime Nav Mesh Generation

As you can tell, there's quite a bit to cover! To make it easier to follow, I'll be splitting this up into two articles, with this one covering Navigation Links, Areas, and Modifiers.

Specifically, we're going to add:

  • a preference for the AI to avoid the stairs
  • the ability for the AI to jump off the raised platform
  • a launchpad that launches a bot onto the platform

Note: Unreal Engine 4.18 was released while this blog post was being written. This post will continue to use 4.17, although the codebase may be updated for the next post in the series (and a download link will be provided).

Before we start making anything, we'll begin by discussing the idea of navigation areas.

By default, all areas of a NavMesh are entirely equal. The AI only ever considers distance when determining what path it wants to take. We call this the "cost function". If we wanted the AI to avoid certain areas, we would need to make it "cost" something to enter or to traverse the area. We could make it "heavier" or "lighter" than the rest of the map to create preferences.

Unreal Engine uses the concept of a Nav Area for this. We can create our own areas the same way we create any class (in either Blueprints or C++):

Once we've created an area, we can tweak a few simple settings (C++ can do a lot more, but we'll cover that later).

Default Cost is used to make walking through an area be more or less attractive. The default area cost is 1.0. This is multiplied by the distance that the AI would have to walk through the area, so higher numbers cause the AI to avoid that zone.

Fixed Area Entering Cost can be used for things like the "oil spills" in Divinity: Original Sin, that apply a status effect when you first enter the zone.

Also, we can edit which colour is used to represent the Nav Area. The Default Nav Area class uses a light green, and visualising where the other areas are can help our level designers.

Lets create a NavArea_Stairs and set the Default Cost to 1.2, and the colour to a yellow/orange. We'll apply this in a second using...

Note: if you want to do this in C++, I'm sure you can figure it out! Just subclass the UNavArea class and set the values you'd like in the constructor.

Nav Areas can be applied in a few different ways. The main method for marking a space in your game as a specific Nav Area is the Nav Modifier Volume.

When you first drag one onto the stairs, you'll notice that it actually deletes the NavMesh!

This is because the Area Class is set to NavArea_Null. Lets change it to our Nav Area that we created:

The moment we do that, however, the stairs go back to green! This is because there is currently a bug in UE4 regarding custom Nav Areas. There is a simple fix for now, just restart the editor and move your nav area slightly to force a rebuild! You should then see your stairs highlighted in your chosen colour - showing that the area has been applied properly.

Our next challenge is to add the ability for the AI to "drop" from one part of the NavMesh to another part, without having to go around.

Basically, we want to create a 'link' from one predetermined point on the mesh to another, which the underlying algorithm can't find by itself. Fortunately, Unreal Engine provides us with the incredibly useful Nav Link Proxy Actor.

When you drag one into the scene, you'll see this:

And it's details panel looks like this:

This actor has some quirks, however, so lets make sure we're on the same page. Mainly, a Nav Link Proxy has two types of links that we can create: Simple links and Smart Links.

All links

Both Simple and Smart Links have the following in common:

  • They have a "left" and a "right"
  • They have a direction:
    • Left to Right
    • Right to Left
    • or Both ways
  • They can be assigned a Nav Area

Simple Links

  • Exist in an Array (called Point Links)
    • i.e. you can have multiple Simple Links per Nav Link Proxy
    • Each Nav Link Proxy actor comes with one element in the array by default
  • Visible in the Scene
    • The Left and Right visible elements are from the default Simple Link in the Actor
    • This makes Simple Links easy to move around and place in the scene

Smart Links

  • Disabled by default
    • Turn on by ticking Smart Link Is Relevant
  • Can be turned on and off at runtime
    • And will notify nearby actors who want to know!
  • No visible editor
    • You have to manually enter the Left/Right location via the Details panel
  • Only one Smart Link per Nav Link Proxy

Practical Example

Lets make a simple nav link first, and we can play with the advanced options later on. If we just want our bot to be able to jump off the cliff, lets put our Proxy Actor in the middle, and set up a few simple links like so:

Note: There are three simple links from one Nav Link Proxy, and each has been set as a Left to Right link.

This easy setup will allow our AI to path off of that ledge - it's that simple!

If we want to create a two-way Nav Link (or a Nav Link that doesn't just fall down a cliff), we need to have a way of moving our AI from one place to the other. This isn't very difficult to do, but can be a bit hard to wrap your head around when starting out.

We're going to create a Launchpad actor (similar to the Blueprint Quick Start), which will launch our AI to a specific point, and work with our Nav Mesh.

There are a few different ways to do this in C++, so for now we're just going to use a simple method that mimics what we can do in Blueprints. We'll investigate other options in later posts.

Blueprint: Launchpad

Unfortunately, this isn't currently possible to do in Blueprints only (I will be submitting a Pull Request after this blog post goes live, to try and get it working for 4.19)!

We're going to have to create a little C++ helper class. The following steps will get you back into blueprints pretty quickly.

C++ Nav Link Component

Create a C++ Class based on the NavLinkComponent. You'll need to tick "Show All Classes". Call it BlueprintableNavLinkComponent.

Once the class has been created and opened, we're going to have to edit two files. One is called BlueprintableNavLinkComponent.h and is known as a "header" file, the other has the .cpp extension as is called a "source" file.

We'll make two slight additions to the header file.

Firstly, find the line that looks like UCLASS(), and add meta = (BlueprintSpawnableComponent) in between the brackets, so it looks like:

UCLASS(meta = (BlueprintSpawnableComponent))

Then, add the following two lines of code under the GENERATED_BODY() line:

UFUNCTION(BlueprintCallable)
void SetupLink(FVector Left, FVector Right, ENavLinkDirection::Type Direction);

This declares that we want to create a function called Setup Link which accepts two Vector input pins and a Link Direction.

In the source file (BlueprintableNavLinkComponent.cpp), add the following code:

void UBlueprintableNavLinkComponent::SetupLink(FVector Left, FVector Right, ENavLinkDirection::Type Direction)
{
    this->Links[0].Left = Left;
    this->Links[0].Right = Right;
    this->Links[0].Direction = Direction;
}

This says that when we call the function, get the first link in the Links array (which has an index of 0) and assign the values which we pass in to the function.

Remember that the Simple Links array has one value by default, this is the value that we're changing now! If you wanted to be able to set values for multiple simple links, you'd want to change the 0 using another input parameter - and you'd have to check that link existed too!

Blueprint Launchpad

Now we've done that, we can jump back into blueprints and create a class (based on an Actor), which has the following components:

  • Root: Scene Component
    • Static Mesh
      • Collider (I used a sphere)
    • Billboard
    • Blueprintable Nav Link

Select any mesh that you like (I use a flatish hexagonal cylinder). Then, add a Vector variable called Target, set its default value to (200, 0, 0), and check both Instance Editable and Show 3D Widget in the details panel.

Now we can start writing some scripts to make this useful! To make it work with Nav Meshes, all we need to do is call the the function we created in the Construction Script!

Now we can drag the actor into our scene, and set it up! You should notice that when you drag around the Target widget, the Nav Link automatically updates to point towards it!

Note: You can't use a Component as a Target, it has to be a plain Vector, because of a known issue in the engine.

Now we need to make the AI get launched when they touch our collider. This will require a new function - Calculate Launch Velocity.

This function is pretty simple, if we use Unreal's in-built capability to Suggest Projectile Velocity. Specifically, we can use Custom Arc version of the node, which is a bit easier to make work:

Tip: You can split Structs (like Vectors) by right clicking on them! This is handy when you just want to utilise one component, like the Z axis value, above.

Note: If you wanted this Launchpad to only launch up to a certain velocity, you could use the base version of this node. However, you'd probably want to add a Construction Script check that the destination was reachable!

Now we need to utilise this calculation. Unfortunately (See Issue #1, below), we can't use the Launch Velocity node. We have to do the following instead:

Note: This is the perfect place to use a Custom Movement Mode, but for now we're just going to use the "falling" mode, which is perfectly fine to override the way we're doing it.

This almost works!

If you run it now, you'll see your AI launching correctly, but then halfway through the jump they fall straight down.

Blueprint Character

This appears to have something to do with the Controller. The default Controller logic will stop the Character's X and Y movement at the apex of a jump (apparently because the default AIController isn't designed to deal with external movement).

To make this work, we need to disable the Path Following Component on our character when we jump, and then re-enable it when we land!

There are two functions already provided for us in the Character class, which we can override in our blueprint (BP_TagCharacter) - On Landed and On Movement Mode Changed!

Override the On Movement Mode Changed function under the function section on the blueprint:

The first thing to do is to make sure we still call the default logic for this event. Do this by adding a call to the parent function:

Then, if the movement mode changed to Falling, we want to get the AIController (if any) and Deactivate the Path Following Component:

Our AI will now jump all the way to end of our nav link path! Although once it gets there, it's just going to stand still.

To fix this, lets add a similar bit of logic by overriding the On Landed event to re-activate the Path Following Component:

And that's it! We've now got a shortcut for AI to get up on the ledge without having to go up the stairs - and the AI will properly follow our path using physics!

END ACCORDION

C++: Launchpad

Our first C++ method is (nearly) identical to the BP method above. In fact, this is simpler to do in C++ because we don't have to create a custom UNavLinkComponent to be able to edit the properties!

We'll create one class (ALaunchpad) and edit our ATagController class a little bit, and that's it.

Launchpad

For ALaunchpad, create a new class derived from AActor, and fill the header out with the following:

public:
    ALaunchpad();

    UPROPERTY(VisibleAnywhere)
        class USceneComponent* Root;

    UPROPERTY(VisibleAnywhere)
        class UStaticMeshComponent* Launchpad;

    UPROPERTY(VisibleAnywhere)
        class USphereComponent* TriggerVolume;

    // This component's details are automatically set in the Construction Script
    UPROPERTY(VisibleAnywhere)
        class UNavLinkComponent* NavLink;

    UPROPERTY(EditAnywhere, BlueprintReadWrite, meta = (MakeEditWidget = ""))
        FVector Target;

    UFUNCTION(BlueprintPure)
        FVector CalculateLaunchVelocity(AActor* LaunchedActor);

    // When our Trigger Volume overlaps with something, this function gets called
    UFUNCTION()
        void OnTriggerBeginOverlap(UPrimitiveComponent* OverlappedComp, AActor* Other, UPrimitiveComponent* OtherComp, int32 OtherBodyIndex, bool bFromSweep, const FHitResult& SweepResult);

private:
    UFUNCTION()
        void LaunchCharacter(ACharacter* Character);

    // Whenever we edit the Actor Transform or any properties via the Details panel, this will trigger.
    void OnConstruction(const FTransform& Transform) override;

    // Update the Nav Link Component to link from the Mesh to the Target
    void UpdateNavLinks();

This sets up our basic Components (a Root, a Mesh, a Trigger Collider, and our Nav Link), a single public UPROPERTY for our target destination, and a few functions.

Note: The LaunchCharacter function must be a UFUNCTION to work with Binding, which we'll use in our constructor.

Note: We use meta = (MakeEditWidget = "") to make our FVector have a visible 3D Widget in the editor, this makes it nice and easy for our designers to use our class.

Note: you can set up any kind of Collider component that you like instead of a Sphere. For my particular Launchpad mesh, the Sphere works perfectly.

Don't forget to add the following includes:

#include "Components/StaticMeshComponent.h"
#include "Components/SphereComponent.h"
#include "AI/Navigation/NavLinkComponent.h"

Now we can write our source file. At the top, include the following:

#include "UObject/ConstructorHelpers.h"
#include "Runtime/Engine/Classes/Kismet/GameplayStatics.h"
#include "Runtime/Engine/Classes/GameFramework/Character.h"
#include "Runtime/Engine/Classes/GameFramework/CharacterMovementComponent.h"
#include "AI/Navigation/NavigationSystem.h"

For the constructor, we simply set up our components and default values to reasonable defaults (including loading a mesh), and then we need to bind a delegate, so that when the TriggerVolume component begins to overlap with another actor, our OnTriggerBeginOverlap function is called.

ALaunchpad::ALaunchpad()
{
    // We don't need our Launchpad to Tick
    PrimaryActorTick.bCanEverTick = false;

    // Create our Components and setup default values
    Root = CreateDefaultSubobject<USceneComponent>(TEXT("Root"));
    RootComponent = Root;

    Launchpad = CreateDefaultSubobject<UStaticMeshComponent>(TEXT("Launchpad"));
    Launchpad->SetupAttachment(Root);
    Launchpad->SetRelativeLocation(FVector::ZeroVector);

    // Load the Launchpad Mesh from our Content folder
    static auto LaunchpadMesh = ConstructorHelpers::FObjectFinderOptional<UStaticMesh>(TEXT("/Game/Meshes/SM_Launchpad"));
    if (LaunchpadMesh.Succeeded())
    {
        Launchpad->SetStaticMesh(LaunchpadMesh.Get());
    }

    TriggerVolume = CreateDefaultSubobject<USphereComponent>(TEXT("Trigger Volume"));
    TriggerVolume->SetupAttachment(Launchpad);
    TriggerVolume->SetSphereRadius(25.f, true);

    NavLink = CreateDefaultSubobject<UNavLinkComponent>(TEXT("Nav Link"));
    NavLink->SetupAttachment(Root);

    // Set a default target to be slightly outside our mesh
    Target = { 100.f, 0.f, 0.f };

    // Bind so that when the trigger gets touched we get notified
    TriggerVolume->OnComponentBeginOverlap.AddUniqueDynamic(this, &ALaunchpad::OnTriggerBeginOverlap);
}

Note: If you make a mistake with the Constructor Helper line (ConstructorHelpers::FObjectFinderOptional<UStaticMesh>(TEXT("/Game/Meshes/SM_Launchpad"));), it may cause your project to crash upon opening. It's easy enough to open the code file and comment it out. Just be careful with the line and you should be ok! Consider yourselves warned.

At this point, create empty functions for all of the signatures we created. We're going to quickly get this working nicely with the Nav Links, before moving back to working on the AI side of things.

To get the Nav Link to update every time we edit the Target vector, we can use the OnConstruction function, which works exactly like the Construction Script in blueprints! To make this clean and easy to read, we create a simple function helper UpdateNavLinks as well:

void ALaunchpad::OnConstruction(const FTransform& Transform)
{
    Super::OnConstruction(Transform);

    UpdateNavLinks();
}

void ALaunchpad::UpdateNavLinks()
{
    // We should never manually edit this actor's links.
    NavLink->SetRelativeLocation(FVector::ZeroVector);

    // Assert that we haven't added or removed any Simple Links
    check(NavLink->Links.Num() == 1);

    // Setup link properties
    auto& Link = NavLink->Links[0];
    Link.Left = FVector::ZeroVector;
    Link.Right = Target;
    Link.Direction = ENavLinkDirection::LeftToRight;

    // Force rebuild of local NavMesh
    auto World = GetWorld();
    if (World)
    {
        auto NavSystem = World->GetNavigationSystem();
        if (NavSystem)
        {
            NavSystem->UpdateComponentInNavOctree(*NavLink);
        }
    }
}

Now you should be able to place your actor in the world and move around the Target widget, and see the Nav Link updating in the editor!

Next, we want to have the AI actually get launched! We'll need to handle our trigger event at this point. Our OnTriggerBeginOverlap function is quite simple, it just calls our LaunchCharacter function if the overlapping actor is the right type:

void ALaunchpad::OnTriggerBeginOverlap(UPrimitiveComponent* OverlappedComp, AActor* Other, UPrimitiveComponent* OtherComp, int32 OtherBodyIndex, bool bFromSweep, const FHitResult& SweepResult)
{
    auto Character = Cast<ACharacter>(Other);

    if (Character)
    {
        LaunchCharacter(Character);
    }
}

Note: you may run into issues where the Character doesn't believe that it sucessfully reached the entry point of the Nav Link. If that happens, your trigger collider may be too wide! You can resolve this issue by using a Timer to wait a short time (0.1s is likely enough) before launching the character.

Our LaunchCharacter function is fairly simple, although not as perfectly simple as we'd like - because the in-built ACharacter::LaunchCharacter function doesn't allow us to set X/Y movement when using Root Motion animations (see Issue #1, below)!

void ALaunchpad::LaunchCharacter(ACharacter* Character)
{
    // Set the Velocity and Mode manually
    auto MovementComponent = Character->GetCharacterMovement();
    MovementComponent->Velocity = CalculateLaunchVelocity(Character);
    MovementComponent->SetMovementMode(EMovementMode::MOVE_Falling);
}

Note: the above is the perfect place to use a Custom Movement Mode! We use the in-built Falling movement mode, but you could use a Custom one if you wanted.

Our Launch Velocity calculation is quite simple, thankfully, due to the SuggestProjectileVelocity function which UE4 provides for our use (specifically the simpler _CustomArc version):

FVector ALaunchpad::CalculateLaunchVelocity(AActor* LaunchedActor)
{
    // Launch from the "feet" of the Character
    auto Start = LaunchedActor->GetActorLocation();
    Start.Z -= LaunchedActor->GetSimpleCollisionHalfHeight();

    // Launch to the Target in WS
    auto End = GetActorTransform().TransformPosition(Target);

    FVector Result;
    UGameplayStatics::SuggestProjectileVelocity_CustomArc(this, Result, Start, End);

    return Result;
}

And with all that, we should have a perfectly working launchpad!

But if you try it out... our AI "derps" a little bit! In the middle of the jump, the AI stops moving along the X/Y direction, and just falls straight down!

Controller

To fix this, we're going to have to tweak our ATagController class. Actually, we're going to tweak the ACharacter class and add some additional logic to the Landed and OnMovementModeChanged functions. We could do this in two ways: we could either create a ATagCharacter and just override the two functions, or we can bind the events from our ATagController and create two functions to handle it.

It's slightly more complicated to do it via the Controller, but I believe that it's the "better" option, so lets do it that way.

This is because we're going to be accessing the Controller inside our handlers anyway - it's Controller logic that we're handling, but triggered by the Character events!

Create the following two functions in our ATagController:

private:
    UFUNCTION()
        void OnMovementModeChanged(ACharacter* MovedCharacter, EMovementMode PrevMovementMode, uint8 PreviousCustomMode = 0);

    UFUNCTION()
        void OnLanded(const FHitResult& Hit);

At the end of our ATagController::BeginPlay(), we want to bind these to the events in our Character:

auto Character = GetCharacter();

    if (Character)
    {
        Character->MovementModeChangedDelegate.AddUniqueDynamic(this, &ATagController::OnMovementModeChanged);
        Character->LandedDelegate.AddUniqueDynamic(this, &ATagController::OnLanded);
    }

And finally, we want to fill them out. Whenever the character enters the Falling state, we want to Deactivate the UPathFollowingComponent of the Controller. Whenever we land, we just re-enable it!

void ATagController::OnMovementModeChanged(ACharacter* MovedCharacter, EMovementMode PrevMovementMode, uint8 PreviousCustomMode)
{
    // If the new movement mode is Falling
    if (MovedCharacter->GetCharacterMovement()->MovementMode == EMovementMode::MOVE_Falling)
    {
        GetPathFollowingComponent()->Deactivate();
    }
}

void ATagController::OnLanded(const FHitResult & Hit)
{
    GetPathFollowingComponent()->Activate();
}

And now our AI won't stop mid-air - and that's all we need to do to have a working Launchpad!

Note: An even more "correct" way to do this, rather than deactivating the PathFollowingComponent, would be to use a custom movement mode, which we will explore in a later post.

END ACCORDION

Wrapping up

Now you know how to modify the Nav Mesh to make it as accessible, or inaccessible, as you would like!

For the next post, I'm actually undecided which way I want to go! I'm tossing up between starting on the Behaviour Tree for our AI (making them "think"!), or continuing with navigation, making our AI act differently as it reaches different sections of our mesh, using custom Movement Modes and Path Following Components.

What do you think? Leave a comment, or tweet at me and let me know!

You can subscribe to this blog using any old RSS reader, if it tickles your fancy to follow along! Just plug https://vikram.codes/blog into your RSS reader of choice and it should work.

Issues

  1. Unfortunately, simply using Launch Character does not work! This appears to be because the mesh/animation set we are using uses Root Motion.
    • To work around this, we Set Velocity on the Movement Component directly, and then Set Movement Mode to Falling.
  2. Even with the above fix, the Character stops moving at the Apex of the jump.
    • The default Controller logic will stop the Character's X and Y movement at the apex of a jump (apparently because the default AIController isn't designed to deal with external movement).
    • Deactivating and reactiving the PathFollowingComponent will fix this issue.
    • In future installments, we'll investigate writing our own PathFollowingComponent and Movement Mode which will handle this for us.
  3. It's impossible to edit Nav Link component Simple Links in Blueprints - this makes us need the BlueprintImplementableNavLink
    • This is because the FVector FNavigationLink.Right is not marked BlueprintReadWrite in the engine source code.
    • If that property was marked as such, we could make the nav link work entirely via construction script, instead of requiring the C++ component class (hook up the Target Relative Location to the added Right input node):