Path Smoothing for AI in Unreal Engine 5 with C++

Welcome to my first blog post, my dear game developer friends!!
Today I will tell you about the “Path Smoothing” technique. With this method, our AI agents will reach their target in a smoother and shorter way. Unreal Engine uses the A* algorithm to find the shortest path to the specified point on Navmesh. However, due to the operation of the A* algorithm and the optimizations made, the resulting Path resembles a zig-zag shape. This gives the feeling of a synthetic path. Although this synthetic path is not very noticeable in CharacterAI, it is noticeable in VehicleAI. “Path Smoothing” technique is used to make this path look softer and more natural, that is, to make it look like the shortest path you can think of when viewed with human eyes. There may be more than one Path Smoothing algorithm, and you can even change it according to your own needs. However, in this article, I will talk about an algorithm that is both fast, easy to implement, and works effectively. Now let’s explain the working logic of our algorithm, then let’s integrate it into the unreal engine using C++.

Let “ABC” be our Path coming from the A* algorithm. Let’s assume that each letter is the path’s points. If there is no obstacle between A and C, point B is deleted and the path is updated. Our new Path becomes “AC”.

When you look at the pictures above in order, it will be better understood how the algorithm works. The most optimal shortest path from the A* algorithm becomes a more natural path thanks to this algorithm. Starting from point “S” (index 0), it is checked to see if there is an obstacle between each point in the row. Points with indexes 1, 2, 3 and 4 were compared respectively and it was determined that there was an obstacle between them and point 4. After detecting the obstacle, by going to the previous point (i.e. point 3), all points in between were deleted (point 1 and 2). This process will then be checked until the last element of the Path by applying the same steps, starting from point 3. In this way, the Path will be smooth.

It’s time to integrate this algorithm into Unreal Engine 🙂
Since this process will run every time the AI throws a MoveRequest, the “FindPathForMoveRequest()” function under AAIController has been overridden. “NavSys = FNavigationSystem::GetCurrent(GetWorld());” NavMesh is accessed with the function and “FPathFindingResult PathResult = NavSys->FindPathSync(Query);” Path is obtained as output. The algorithm I mentioned above was applied to the resulting path. If you ask, how did you know if there was an obstacle between the points? In the 40th line, a trace was made between the points with the code “UKismetSystemLibrary::SphereTraceSingle” and it was checked whether there were any collisions. In case of a collision, it goes to the previous point and the points in between are deleted. In other words, Path is calculated and “OutPath = PathResult.Path;” given as output.

void ACustomAIController::FindPathForMoveRequest(const FAIMoveRequest& MoveRequest, FPathFindingQuery& Query,
                                                  FNavPathSharedPtr& OutPath) const
{
	SCOPE_CYCLE_COUNTER(STAT_AI_Overall);

	UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
	if (NavSys)
	{
		FPathFindingResult PathResult = NavSys->FindPathSync(Query);
		if (PathResult.Result != ENavigationQueryResult::Error)
		{
			if (PathResult.IsSuccessful() && PathResult.Path.IsValid())
			{
				if (MoveRequest.IsMoveToActorRequest())
				{
					PathResult.Path->SetGoalActorObservation(*MoveRequest.GetGoalActor(), 100.0f);
				}
				// A* Path Smoothing
				FHitResult* HitResult = new FHitResult();
				TArray<AActor*> ActorsToIgnore;
				ActorsToIgnore.Add(GetOwner());
				int PathLenght = PathResult.Path->GetPathPoints().Num();
				FNavigationPath* NewPath = PathResult.Path.Get();
				
				// Some control check
				for (int i=0; i < PathLenght; i++)
				{
					if (PathLenght <= 1)
						break;
					
					for (int j= i+2; PathLenght; j++)
					{
						if (j >= PathLenght)
							break;

						FVector Start = PathResult.Path->GetPathPoints()[i].Location + FVector(0,0, 20); //add Z up value
						FVector End = PathResult.Path->GetPathPoints()[j].Location + FVector(0,0, 20); //add Z up value

						UKismetSystemLibrary::SphereTraceSingle(GetWorld(), Start, End, 2, UEngineTypes::ConvertToTraceType(ECC_Camera), false,                       
            ActorsToIgnore,EDrawDebugTrace::ForDuration, *HitResult, true, FLinearColor::Red, FLinearColor::Blue, 20);
						// if obstacle obstructing the path, no changes
						if (HitResult->bBlockingHit)
							break;

						// if no obstacle obstructing the path, delete middle point --> j-1
						NewPath->GetPathPoints().RemoveAt(j-1);
						j++;
						PathLenght = PathResult.Path->GetPathPoints().Num();
					}
				}
				
				PathResult.Path->EnableRecalculationOnInvalidation(true);
				OutPath = PathResult.Path;
			}
	
			
		}
	}
}

Thank you for reading until the end. You can ask your questions in the comments section. See you in my other articles 🙂

REFERENCES : Mat Buckland, Programming Game AI by Example