Download

Vehicle NavMesh Pathfinding

I have posted a question about this on the answers site: Vehicle Pathfinding - Where To Start? - UE4 AnswerHub

However, I want to start this thread as an additional discussion about vehicle pathfinding using the NavMesh system. Users should ideally be able to place a pawn in the world and have it be able to find its way around the game world regardless of the type of pawn.

Unity3D had the same restrictions UE4 does when it comes to the NavMesh. When I had to do a similar thing in Unity3D I resorted to creating a node-like system where each road was a list of nodes and an intersection was a circle where the radius was the distance to the start nodes for the roads. I would like to implement a similar thing in UE4, but this time I need the vehicles to be able to get back onto the road if they are order offroad, such as being told to park on a pavement, enter a parking lot, drive into an alley way, etc.

If anyone has any ideas about this, please contribute. I would like to integrate this into the actual source code when finished and tested, so this will benefit the community.

I could be going way off on a tangent here, but I’ll just post some of my findings so far for Vehicle AI. If it interests you, Unreal Tournament has extended the Nav Mesh system massively, and has different path types and proxies for different pawns I believe. Pressing ‘N’ in the UT Editor may induce mini heart-attacks…

In the case of my vehicle AI, I’m trying to do it much the same way as Characters. The end goal is that I would have several different vehicle ‘classes’, which would also have their own Nav-Proxy settings, so that NavMesh generates different grids for each proxy, based on it’s abilities (like what kind of inclines it can travel up, how large the object is etc).

I’ve also (after countless hours spent tracking it down) figured out how the Navigation system talks to a Movement Component. It calls ‘Apply Requested Move’, and feeds in a ‘Velocity’ value which is basically the full-length vector from it’s target position (the next pathpoint) to it’s current position. In the case of character Movement, it normalizes that vector and applies velocity in that direction. Since CMC auto-magically orientates the character to face the direction it’s moving in, it’s quite simple to do. In my case, I overrode ‘Apply Requested Move’ and it checks the dot product of the normalized direction to the target, and the crafts forward vector. It then applies rotational input based on that so that it ends up facing the right way, then it can apply the linear thrust/acceleration.

Somewhere, there’s also a path-finding manager (I think part of the blackboard / behavior tree system maybe?) which tracks whether the AI object is getting closer to it’s path destination or if it’s stuck. if it doesn’t get closer after ‘x’ seconds, then the move fails and the pawn stops moving. I Think this check is ticked in the actual AI task, so you may be able to override that behavior and somehow check if the vehicle is trying to steer or if the steering is stuck.

That latter part makes sense for characters, but in the case of vehicles which can’t turn on-the-spot or want to turn BEFORE they jet off in that direction (or even those that need to go back and forth several times, like wheeled vehicles for instance), it’s blood irritating because the pathing fails if you’re not moving towards that location. Also, because of the steering problem, the majority of your “smart” movement for the object has to be handled in the actually movement component as part of RequestMove() or whatever it’s called, though that’s probably intended since different movement components would move differently anyway.

I’m not sure this is relevant to your question tbh, but I’m all for diversifying the AI engine beyond just characters! I want to keep the awesome flexibility of Navmesh, but I need more control than the AI engine currently seems to give.

This is also where I started. I wasn’t entirely sure as shown in my question on the answers site, but knowing that others, or at least someone else, have also found this, makes me more confident in taking this approach. This is the kind of thing I was imagining when I first thought of doing this.

This is an interesting point that will have to be overcome. I will look into overriding this for vehicles.

This is something that is ideal for what we are trying to do, because the movement isn’t hard-coded, it can be overridden, we (the users) can extend Unreal Engine to accommodate more pawn types.

This is definitely relevant :smiley: I’m glad to hear that others are interested in this sort of thing as well.

Great stuff! Hopefully we can get a nice thread / feedback sandwich going on the subject!

I won’t be working on my current implementation for a while but I’ll post source code for what I find so far, I can at least post the source to my custom ‘SteerTo’ AI task (shall do that when I get home).

Checking in to make sure you finally got home :slight_smile:

Apologies! Here it is in all it’s glory, or lack of…



// Fill out your copyright notice in the Description page of Project Settings.

#pragma once

#include "BehaviorTree/Tasks/BTTask_BlackboardBase.h"
#include "BehaviorTree/Blackboard/BlackboardKeyType_Object.h"
#include "BehaviorTree/Blackboard/BlackboardKeyType_Vector.h"
#include "BehaviorTree/Blackboard/BlackboardKeyType_Rotator.h"
#include "BehaviorTree/Services/BTService_DefaultFocus.h"
#include "BTTask_SteerTo.generated.h"

/**
 * Tells a BZ Pawn to Apply Steering towards a target location.
 */
UCLASS(Config=Game)
class BZGAME_API UBTTask_SteerTo : public UBTTask_BlackboardBase
{
	GENERATED_BODY()
	
protected:
	/* Success Condition Precision In Degrees */
	UPROPERTY(config, Category = Node, EditAnywhere, meta = (ClampMin = 0.0f))
	float YawAcceptanceRadius;
	UPROPERTY(config, Category = Node, EditAnywhere, meta = (ClampMin = 0.0f))
	float PitchAcceptanceRadius;

	UPROPERTY(config, Category = Node, EditAnywhere)
	bool AlignPitch;
	UPROPERTY(config, Category = Node, EditAnywhere)
	bool AlignYaw;

private:
	/* Cached Dot Precision */
	float YawPrecisionDot;
	float PitchPrecisionDot;

public:
	UBTTask_SteerTo(const FObjectInitializer& ObjectInitializer);

	virtual void PostInitProperties() override;
	virtual void PostLoad() override;

	virtual EBTNodeResult::Type ExecuteTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory) override;
	virtual void TickTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory, float DeltaSeconds) override;
	virtual EBTNodeResult::Type AbortTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory) override;
	virtual void DescribeRuntimeValues(const UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory, EBTDescriptionVerbosity::Type Verbosity, TArray<FString>& Values) const override;
	virtual FString GetStaticDescription() const override;

	virtual uint16 GetInstanceMemorySize() const override { return sizeof(FBTFocusMemory); }

protected:

	float GetYawPrecisionDot() const { return YawPrecisionDot; }
	float GetPitchPrecisionDot() const { return PitchPrecisionDot; }
	void CleanUp(AAIController& AIController, uint8* NodeMemory);	
};




// Fill out your copyright notice in the Description page of Project Settings.

#include "BZGame.h"
#include "BehaviorTree/BlackboardComponent.h"
#include "AI/Tasks//BTTask_SteerTo.h"

UBTTask_SteerTo::UBTTask_SteerTo(const FObjectInitializer& ObjectInitializer) : Super(ObjectInitializer)
	, PitchAcceptanceRadius(10.f)
	, YawAcceptanceRadius(10.f)
	, AlignPitch(false)
	, AlignYaw(true)
{
	NodeName = "SteerTo";
	bNotifyTick = true;

	// Accept Actors, Vectors & Rotators
	BlackboardKey.AddObjectFilter(this, GET_MEMBER_NAME_CHECKED(UBTTask_SteerTo, BlackboardKey), AActor::StaticClass());
	BlackboardKey.AddVectorFilter(this, GET_MEMBER_NAME_CHECKED(UBTTask_SteerTo, BlackboardKey));
	BlackboardKey.AddRotatorFilter(this, GET_MEMBER_NAME_CHECKED(UBTTask_SteerTo, BlackboardKey));
}

void UBTTask_SteerTo::PostInitProperties()
{
	Super::PostInitProperties();

	YawPrecisionDot = FMath::Cos(FMath::DegreesToRadians(YawAcceptanceRadius));
	PitchPrecisionDot = FMath::Cos(FMath::DegreesToRadians(PitchAcceptanceRadius));
}

void UBTTask_SteerTo::PostLoad()
{
	Super::PostLoad();

	YawPrecisionDot = FMath::Cos(FMath::DegreesToRadians(YawAcceptanceRadius));
	PitchPrecisionDot = FMath::Cos(FMath::DegreesToRadians(PitchAcceptanceRadius));
}

namespace
{
	FORCEINLINE_DEBUGGABLE float CalculateYawAngleDifferenceDot(const FVector& VectorA, const FVector& VectorB)
	{
		return VectorA.CosineAngle2D(VectorB);
	}
}

namespace
{
	FORCEINLINE_DEBUGGABLE float CalculatePitchAngleDifferenceDot(const FVector& VectorA, const FVector& VectorB)
	{
		// This may Suck Badly!
		FVector A = VectorA;
		FVector B = VectorB;

		A.Z = 0.f;
		B.Z = 0.f;
		A.Normalize();
		B.Normalize();
		return A | B;
	}
}

EBTNodeResult::Type UBTTask_SteerTo::ExecuteTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory)
{
	AAIController* AIController = OwnerComp.GetAIOwner();

	if (AIController == NULL || AIController->GetPawn() == NULL)
	{
		return EBTNodeResult::Failed;
	}

	FBTFocusMemory* MyMemory = (FBTFocusMemory*)NodeMemory;
	check(MyMemory);
	MyMemory->Reset();

	EBTNodeResult::Type Result = EBTNodeResult::Failed;

	APawn* Pawn = AIController->GetPawn();
	UBZGame_GameObjectComponent* PawnGOC = UBZGameplayStatics::GetGameObjectComponentFromActor(Pawn, true);
	ASSERTV_WR(PawnGOC != nullptr, Result, *FString::Printf(TEXT("UBTTask_SteerTo - Pawn Has no GameObjectComponent!")));
	FVector EyepointLocation, EyepointDirection;
	PawnGOC->GetEyepoint(EyepointLocation, EyepointDirection);
	const UBlackboardComponent* MyBlackboard = OwnerComp.GetBlackboardComponent();

	// Solve for Actor Target
	if (BlackboardKey.SelectedKeyType == UBlackboardKeyType_Object::StaticClass())
	{
		UObject* KeyValue = MyBlackboard->GetValue<UBlackboardKeyType_Object>(BlackboardKey.GetSelectedKeyID());
		AActor* ActorValue = Cast<AActor>(KeyValue);

		// TODO - Should Target Other Location
		if (ActorValue != NULL)
		{
			bool bYawMet = false;
			bool bPitchMet = false;

			if (AlignYaw)
			{
				const float YawAngleDiff = CalculateYawAngleDifferenceDot(EyepointDirection, (ActorValue->GetActorLocation() - EyepointLocation).GetSafeNormal());
				if (YawAngleDiff >= YawAcceptanceRadius)
				{
					bYawMet = true;
				}
			}
			else
			{
				bYawMet = true;
			}

			if (AlignPitch)
			{
				const float PitchAngleDiff = CalculatePitchAngleDifferenceDot(EyepointDirection, (ActorValue->GetActorLocation() - EyepointLocation).GetSafeNormal());
				if (PitchAngleDiff >= PitchAcceptanceRadius)
				{
					bPitchMet = true;
				}
			}
			else
			{
				bPitchMet = true;
			}

			if (bYawMet && bPitchMet)
			{
				Result = EBTNodeResult::Succeeded;
			}
			else
			{
				AIController->SetFocus(ActorValue, EAIFocusPriority::Gameplay);
				MyMemory->FocusActorSet = ActorValue;
				MyMemory->bActorSet = true;
				Result = EBTNodeResult::InProgress;
			}
		}
	}
	// Solve for Vector
	else if (BlackboardKey.SelectedKeyType == UBlackboardKeyType_Vector::StaticClass())
	{
		const FVector KeyValue = MyBlackboard->GetValue<UBlackboardKeyType_Vector>(BlackboardKey.GetSelectedKeyID());

		// Direction or Location in This?
		if (FAISystem::IsValidLocation(KeyValue))
		{
			bool bYawMet = false;
			bool bPitchMet = false;

			if (AlignYaw)
			{
				const float YawAngleDiff = CalculateYawAngleDifferenceDot(EyepointDirection, (KeyValue - EyepointLocation).GetSafeNormal());
				if (YawAngleDiff >= YawAcceptanceRadius)
				{
					bYawMet = true;
				}
			}
			else
			{
				bYawMet = true;
			}

			if (AlignPitch)
			{
				const float PitchAngleDiff = CalculatePitchAngleDifferenceDot(EyepointDirection, (KeyValue - EyepointLocation).GetSafeNormal());
				if (PitchAngleDiff >= PitchAcceptanceRadius)
				{
					bPitchMet = true;
				}
			}
			else
			{
				bPitchMet = true;
			}

			if (bYawMet && bPitchMet)
			{
				Result = EBTNodeResult::Succeeded;
			}
			else
			{
				AIController->SetFocalPoint(KeyValue, EAIFocusPriority::Gameplay);
				MyMemory->FocusLocationSet = KeyValue;
				Result = EBTNodeResult::InProgress;
			}
		}
	}
	// Solve For Rotation
	else if (BlackboardKey.SelectedKeyType == UBlackboardKeyType_Rotator::StaticClass())
	{
		const FRotator KeyValue = MyBlackboard->GetValue<UBlackboardKeyType_Rotator>(BlackboardKey.GetSelectedKeyID());

		if (FAISystem::IsValidRotation(KeyValue))
		{
			const FVector DirectionVector = KeyValue.Vector();

			bool bYawMet = false;
			bool bPitchMet = false;

			if (AlignYaw)
			{
				const float YawAngleDiff = CalculateYawAngleDifferenceDot(EyepointDirection, DirectionVector);
				if (YawAngleDiff >= YawAcceptanceRadius)
				{
					bYawMet = true;
				}
			}
			else
			{
				bYawMet = true;
			}

			if (AlignPitch)
			{
				const float PitchAngleDiff = CalculatePitchAngleDifferenceDot(EyepointDirection, DirectionVector);
				if (PitchAngleDiff >= PitchAcceptanceRadius)
				{
					bPitchMet = true;
				}
			}
			else
			{
				bPitchMet = true;
			}

			if (bYawMet && bPitchMet)
			{
				Result = EBTNodeResult::Succeeded;
			}
			else
			{
				const FVector FocalPoint = EyepointLocation + DirectionVector * (MAX_FLT / 2);
				AIController->SetFocalPoint(FocalPoint, EAIFocusPriority::Gameplay);
				MyMemory->FocusLocationSet = FocalPoint;
				Result = EBTNodeResult::InProgress;
			}
		}
	}

	return Result;
}

void UBTTask_SteerTo::TickTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory, float DeltaSeconds)
{
	AAIController* AIController = OwnerComp.GetAIOwner();

	if (AIController == NULL || AIController->GetPawn() == NULL)
	{
		FinishLatentTask(OwnerComp, EBTNodeResult::Failed);
	}
	else
	{
		UBZGame_GameObjectComponent* PawnsGOC = UBZGameplayStatics::GetGameObjectComponentFromActor(AIController->GetPawn(), true);
		if (PawnsGOC)
		{
			FVector EyeDirection, EyeLocation;
			PawnsGOC->GetEyepoint(EyeLocation, EyeDirection);

			const FVector FocalPoint = AIController->GetFocalPointForPriority(EAIFocusPriority::Gameplay);

			bool bYawMet = false;
			bool bPitchMet = false;

			if (AlignYaw)
			{
				const float YawAngleDiff = CalculateYawAngleDifferenceDot(EyeDirection, (FocalPoint - EyeLocation));
				if (YawAngleDiff >= YawAcceptanceRadius)
				{
					bYawMet = true;
				}
			}
			else
			{
				bYawMet = true;
			}

			if (AlignPitch)
			{
				const float PitchAngleDiff = CalculatePitchAngleDifferenceDot(EyeDirection, (FocalPoint - EyeLocation));
				if (PitchAngleDiff >= PitchAcceptanceRadius)
				{
					bPitchMet = true;
				}
			}
			else
			{
				bPitchMet = true;
			}

			if (bYawMet && bPitchMet)
			{
				CleanUp(*AIController, NodeMemory);
				FinishLatentTask(OwnerComp, EBTNodeResult::Succeeded);
			}
		}
		else
		{
			FinishLatentTask(OwnerComp, EBTNodeResult::Failed);
		}
	}
}

void UBTTask_SteerTo::CleanUp(AAIController& AIController, uint8* NodeMemory)
{
	FBTFocusMemory* MyMemory = (FBTFocusMemory*)NodeMemory;
	check(MyMemory);

	bool bClearFocus = false;
	if (MyMemory->bActorSet)
	{
		bClearFocus = (MyMemory->FocusActorSet == AIController.GetFocusActorForPriority(EAIFocusPriority::Gameplay));
	}
	else
	{
		bClearFocus = (MyMemory->FocusLocationSet == AIController.GetFocalPointForPriority(EAIFocusPriority::Gameplay));
	}

	if (bClearFocus)
	{
		AIController.ClearFocus(EAIFocusPriority::Gameplay);
	}
}

EBTNodeResult::Type UBTTask_SteerTo::AbortTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory)
{
	AAIController* AIController = OwnerComp.GetAIOwner();

	if (AIController != NULL)
	{
		CleanUp(*AIController, NodeMemory);
	}

	return EBTNodeResult::Aborted;
}

void UBTTask_SteerTo::DescribeRuntimeValues(const UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory, EBTDescriptionVerbosity::Type Verbosity, TArray<FString>& Values) const
{
	FString KeyDesc = BlackboardKey.SelectedKeyName.ToString();
	Values.Add(FString::Printf(TEXT("%s: %s"), *Super::GetStaticDescription(), *KeyDesc));

	AAIController* AIController = OwnerComp.GetAIOwner();

	if (AIController != NULL && AIController->GetPawn() != NULL)
	{
		UBZGame_GameObjectComponent* PawnsGOC = UBZGameplayStatics::GetGameObjectComponentFromActor(AIController->GetPawn(), true);
		if (PawnsGOC)
		{
			FVector EyeDirection, EyeLocation;
			PawnsGOC->GetEyepoint(EyeLocation, EyeDirection);

			const FVector FocalPoint = AIController->GetFocalPointForPriority(EAIFocusPriority::Gameplay);

			if (FocalPoint != FAISystem::InvalidLocation)
			{
				const float CurrentYawAngleRadians = CalculateYawAngleDifferenceDot(EyeDirection, (FocalPoint - EyeLocation).GetSafeNormal());
				const float CurrentPitchAngleRadians = CalculateYawAngleDifferenceDot(EyeDirection, (FocalPoint - EyeLocation).GetSafeNormal());
				Values.Add(FString::Printf(TEXT("Current Yaw: %.2f Current Pitch: %.2f"), FMath::DegreesToRadians(FMath::Acos(CurrentYawAngleRadians)), FMath::DegreesToRadians(FMath::Acos(CurrentPitchAngleRadians))));
			}
			else
			{
				Values.Add(TEXT("FocalPoint is an Invalid Location"));
			}
		}
		else
		{
			Values.Add(TEXT("GameObjectComponent is Invalid"));
		}
	}
	else
	{
		Values.Add(TEXT("Controller or Pawn is NULL"));
	}
}

FString UBTTask_SteerTo::GetStaticDescription() const
{
	FString KeyDesc = BlackboardKey.SelectedKeyName.ToString();
	return FString::Printf(TEXT("%s: %s"), *Super::GetStaticDescription(), *KeyDesc);
}


Hi I am new to unreal engine, currently I am working with racing game, especially car Ai, can you give a demo for this which will help us lot,