Mar 19, 2025 9 min read Terralysia

Making our monsters jump

Jumping across navmesh gaps

The two maps I released Terralysia in Early Access with are pretty flat. Both maps work more like arenas with some trees and other obstacles in the way. There's hills and irregularities in the terrain but as far as gameplay is concerned, it's basically a flat landscape. Terralysia is a third-person game though, and for the third map I wanted to make use of the third dimension and add some verticality.

The new map is inspired by the Ways from The Wheel of Time books and consists of a bunch of platforms and pathways hanging in the air. This allowed me to go up and down with the level design much more than a regular landscape.

To introduce even more irregularity in these pathways, I added gaps and drops in addition to platforms hovering at different heights. This made it obvious that so far I hadn't considered verticality much when all the monster AI failed to traverse these areas.

Terralysia makes use of regular navmeshes for AI movement. There are solutions in Unreal Engine for jumping between points on navmeshes but to my knowledge they require manual setup with NavLinks, events to trigger jumps, etc. I will admit, I spent a whole two and a half minutes looking for solutions. When I couldn't find a "make my AI jump" toggle in the editor, I did what any engineer would do and decided to roll my own. For the rest of the article, please keep in mind this is probably not the best way to make your Unreal Engine 5 AI jump across navmesh gaps, but it worked for me.

The general idea of my solution goes something like this:

A behavior tree service continuously checks if the actor's current path has a gap in it. This tells us we can't reach our target, which at any time for most of our monsters is the player actor.
When our BT service detects a gap, we start doing line traces across the gap in an attempt to find a valid landing location.
Assuming we find a location on the other side of the gap, we use the point before the gap and the target landing location across the jump, and make our AI jump over it.

The DetectNavMeshGap behavior tree service

Monsters in Terralysia make use of fairly simple behavior trees. This makes it easy to add a new service that runs say every 0.5s to check if we have a gap in our current nav path. The path is usually also simple because most of the monsters just move towards the player.

The gap detection service runs its logic in the TickNode() function, and the bottom of the function (bear with me) looks something like this:

const FVector CurrentLocation = Character->GetActorLocation();
const FVector TargetLocation = TargetActor->GetActorLocation();

// prepare our jump origin and direction
FVector JumpOrigin = CurrentLocation;
FVector JumpDirection = (TargetLocation - CurrentLocation).GetSafeNormal2D();

// if we have a partial path, find where the gap is and attempt the jump from there
// but only if we're close enough to the gap
bool bNeedsJump = false;
FNavPathSharedPtr CurrentPath = PathFollowingComp->GetPath();
if (CurrentPath.IsValid() && CurrentPath->IsPartial())
{
	const TArray<FNavPathPoint>& PathPoints = CurrentPath->GetPathPoints();
	if (PathPoints.Num() > 0)
	{
		int32 LastReachableIndex = PathPoints.Num() - 1;
		const FVector GapLocation = PathPoints[LastReachableIndex].Location;
		const float DistanceToGapSqr = FVector::DistSquared(CurrentLocation, GapLocation);

		const float JumpSearchThresholdSqr = JumpSearchThreshold * JumpSearchThreshold;
		if (DistanceToGapSqr <= JumpSearchThresholdSqr)
		{
			bNeedsJump = true;
			JumpDirection = (TargetLocation - GapLocation).GetSafeNormal2D();
		}
	}
}
// no valid path exists, but target is within potential jump distance
else if (!CurrentPath.IsValid() || CurrentPath->GetPathPoints().Num() == 0)
{
	const float DistToTarget = FVector::Dist2D(CurrentLocation, TargetLocation);
	if (DistToTarget <= MaxJumpDistance)
	{
		bNeedsJump = true;
	}
}

if (!bNeedsJump)
{
	BlackboardComp->SetValueAsBool(CanJumpKey.SelectedKeyName, false);
	return;
}

// clear any only landing locations cached from potential previous runs
Memory->LandingLocations.Empty();

// start an async search task
Memory->SearchTask = MakeShared<FAsyncTask<FAsyncJumpPointSearch>>(
	AIController,
	Character,
	JumpOrigin,
	JumpDirection,
	TargetLocation,
	MaxJumpDistance,
	MaxJumpHeight,
	MaxDropDistance
);

Memory->SearchTask->StartBackgroundTask();
Memory->bSearchInProgress = true;

First we make sure that we need to jump, and we do this by checking the current path. A valid but partial path tells us we're moving towards a target but we can't get there on the navmesh. When we detect this, we look at the last point on the path which gives us the last valid location we can reach before the gap. We check our distance to this point and when we get close enough to the gap, we set the bNeedsJump flag that tells us we should start looking for a landing spot and also record in which direction we want to jump (i.e. towards our target). We also allow a jump in case we have no valid path but are close enough to the target that a jump could take us the rest of the way. Once we know we want to jump, we launch our async task.

Please note we're storing all instance data in our node instance memory. Do not store any per-instance data directly on this object because the UBTService object is shared across multiple instances.

That was the bottom of the TickNode function. It made more sense to start there because that's where the async task to search for a landing spot is scheduled. What we need to add at the top of the TickNode function is a check to see if we have any results in case we've already started our background task. Before the above code, we have the following:

if (Memory->bSearchInProgress && Memory->SearchTask.IsValid())
{
	if (Memory->SearchTask->IsDone())
	{
		Memory->bSearchInProgress = false;

		// get landing location, if we found one
		FAsyncJumpPointSearch& SearchInstance = Memory->SearchTask->GetTask();
		if (SearchInstance.FoundLandingLocation())
		{
			Memory->LandingLocations = SearchInstance.GetLandingLocations();

			// pick a random location from all results
			const FVector RandomLocation = Memory->LandingLocations[FMath::RandRange(0, Memory->LandingLocations.Num() - 1)];

			BlackboardComp->SetValueAsVector(JumpTargetKey.SelectedKeyName, RandomLocation);
			BlackboardComp->SetValueAsBool(CanJumpKey.SelectedKeyName, true);
		}

		Memory->SearchTask.Reset();
	}
	else
	{
		// still searching...
		return;
	}
}

If we know we have a task running, the first thing we want to do is check if it has completed and has any results for us. There's no point in running additional tasks until we hear back from the first one we triggered. This service runs at specific intervals and could run again while an async task is still running or after it's completed.

If we do have a previously started task which has finished, we check in case it has results for us and if it does, we randomly pick one of them as our landing location. The random selection works for my game, but you may want a different behavior here. Similarly, you may need the ability to discard results and trigger a new search, depending on project needs. For example, if an AI can change its mind and move in a different direction away from the gap before the jump happened.

The async jump search task

Doing a few line traces to find a valid location on the ground isn't super expensive, but in this game we can end up with a lot of AI actors moving all over the place, including many trying to jump at the same time. As you've already noticed above, we're being a little naughty and have prematurely optimized by using an async task to perform the line traces instead of running it all on the game thread. Terralysia doesn't offload a lot of work to other threads (yet), so I consider this cost essentially free. As a general rule though, don't skip the profiling to verify any optimization work.

We use a simple FNonAbandonableTask for the async jump search work and the meat of the DoWork() function in this class looks like this:

FCollisionQueryParams CollisionParams;
CollisionParams.AddIgnoredActor(Character.Get());

// sweep in an arc around the jump direction
const float ArcAngle = 60.f;
const float AngleStep = 15.f;
const float StartAngle = -ArcAngle * 0.5f;
const float EndAngle = ArcAngle * 0.5f;

for (float Angle = StartAngle; Angle <= EndAngle; Angle += AngleStep)
{
	const FVector SearchDir = JumpDirection.RotateAngleAxis(Angle, FVector::UpVector);
	const FVector PotentialLocation = JumpOrigin + SearchDir * MaxJumpDistance;

	// trace to find ground
	FHitResult HitResult;
	const FVector TraceStart = PotentialLocation + FVector(0, 0, MaxJumpHeight);
	const FVector TraceEnd = PotentialLocation - FVector(0, 0, MaxDropDistance);

	if (World->LineTraceSingleByChannel(HitResult, TraceStart, TraceEnd, ECC_Visibility, CollisionParams))
	{
		// check if we're on the navmesh
		FNavLocation NavLocation;
		if (NavSys->ProjectPointToNavigation(HitResult.Location, NavLocation))
		{
			// make sure we can reach the target from this point
			const ANavigationData* NavData = NavSys->GetNavDataForProps(Controller->GetNavAgentPropertiesRef(), NavLocation);
			if (NavData)
			{
				FPathFindingQuery Query(Controller.Get(), *NavData, NavLocation, TargetLocation);
				FPathFindingResult Result = NavSys->FindPathSync(Query);
				if (Result.IsSuccessful())
				{
					LandingLocations.Emplace(NavLocation.Location);
				}
			}
		}
	}
}

This task is scheduled from the DetectNavMeshGap service which passes in the JumpOrigin and JumpDirection along with some other variables that can be configurable, for example MaxJumpDistance, MaxJumpHeight, etc.

We take these variables and sweep in an arc around the jump direction while doing vertical traces trying to find a valid ground location. When we find a ground location, we project this on the navmesh to make sure it's a valid location we can move on. Finally, we check if we can reach the target along the navmesh from this location.

Each valid location we find gets added to an array which we then randomly pick from when deciding where to jump. This can be done in different ways. You might, for instance, want to keep track of the location closest to the jump origin, or perhaps the location closest to the target. Because we have so many monsters in Terralysia, I wanted multiple valid landing locations so I can pick different ones when there's many AI actors jumping at the same time.

I should point out that EQS is a solid system and could handle this search very well. This is an option to consider. In my case, I felt it was simple enough to do the line traces manually.

The Jump

We have a BT service that detects when an AI has a gap in their path. When the AI gets close to the gap, it launches an async task to find a valid landing location, waits for the results, and when we have the location we…what do we do?

Well, since we have most of our AI logic driven by a behavior tree, we can easily add a new task that performs the Jump. You may have noticed earlier how we're setting a couple of blackboard values when we have successfully found our landing location:

BlackboardComp->SetValueAsVector(JumpTargetKey.SelectedKeyName, RandomLocation);
BlackboardComp->SetValueAsBool(CanJumpKey.SelectedKeyName, true);

This sets the target location to jump to, and a boolean flagging that we are good to jump. In the behavior tree, we have a new custom task node that gets triggered when we detect this boolean to be true.

The jump task is a simple one.

EBTNodeResult::Type UMVBTTaskNode_JumpToLocation::ExecuteTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory)
{
	AAIController* AIController = OwnerComp.GetAIOwner();
	if (!AIController)
	{
		return EBTNodeResult::Failed;
	}

	AMVAICharacter* Character = Cast<AMVAICharacter>(AIController->GetPawn());
	if (!Character)
	{
		return EBTNodeResult::Failed;
	}

	UBlackboardComponent* BlackboardComp = OwnerComp.GetBlackboardComponent();
	if (!BlackboardComp)
	{
		return EBTNodeResult::Failed;
	}

	BlackboardComp->SetValueAsBool(CanJumpKey.SelectedKeyName, false);

	FVector JumpTarget = BlackboardComp->GetValueAsVector(JumpTargetKey.SelectedKeyName);
	FVector CurrentLocation = Character->GetActorLocation();

	// calculate launch speed
	float RequiredSpeed;
	UMVGameplayFunctionLibrary::CalculateJumpVelocity(Character, CurrentLocation, JumpTarget, RequiredSpeed);

	FVector JumpDirection = (JumpTarget - CurrentLocation);
	JumpDirection.Z = 0;
	JumpDirection.Normalize();

	// create launch velocity vector with 45-degree angle
	FVector LaunchVelocity = JumpDirection * RequiredSpeed * 0.7071f; // 0.7071 = cos(45°)
	LaunchVelocity.Z = RequiredSpeed * 0.7071f; // 0.7071 = sin(45°)

	Character->GapJump(LaunchVelocity, true, true);

	return EBTNodeResult::Succeeded;
}

We assume the character will jump at a 45 degree angle so we calculate the speed needed for the launch to land at the correct spot. We then create our vector and launch the character.

GapJump() in this case is a custom wrapper around ACharacter::LaunchCharacter() that sets some project-specific flags not relevant to this particular feature.