AI Pathfinding Algorithm

정혜창·2025년 4월 24일
AI_Systemunreal내일배움캠프프로그래밍

내일배움캠프

목록 보기
47/64
post-thumbnail

🎮 Unreal Pathfinding Algorithm

최단경로 알고리즘은 다익스트라 알고리즘, A-Star 알고리즘 등이 있지만 언리얼 엔진의 최단경로 알고리즘 즉 Pathfinding 알고리즘은 업계의 비밀이라 자세하게는 어떤 형식의 알고리즘인지는 알 수 없지만 가장 저렴한 비용으로 목표 지점까지 이동하도록 설계되어있다고 홍보한다.

하지만 낮은 비용으로 선택하는 원리는 같다. 따라서 비용설정을 통해 AI의 경로를 유도할 수 있다.

1️⃣ Nav Modifier Volume

Nav Modifier Volume 생성을 통해 고비용 Obstacle을 배치함으로써 AI 이동을 유도할 수 있다.

📌 Volume 생성

  • Nav Modifier Volume을 생성하면 다음과 같이 NavMesh 안에 빈곳이 생기게 된다. (Project Setting Runtime : Dynamic)
  • Area Class Default 설정이 Null로 설정되어 있기 때문인데 Obstacle(장애물)로 설정하면 다음과 같이 보인다.
  • 장애물을 피해서 경로를 탐색하는 것을 확인하기 위해 다음과 같이 액터들을 배치해보았다. (Target Point)

이후 C++ 코드에서 TargetPoint를 찾아서 이동하는 로직 추가


2️⃣ Use Pathfinding Algorithm

MoveToLocation, MoveToActor 함수를 통해 언리얼의 Pathfinding Algorithm을 사용할 수 있다.
World에서 TargetPoint를 찾고 Destination을 bIsSucceeded 값의 토글을 통해 전환하도록 로직을 설계되었다.
세부로직은 다음과 같다.

📌 C++ 이동 로직 추가

📋 AI_TestCharacter.h
// 헤더 추가
#include "AIController.h"
#include "Engine/TargetPoint.h"

.
.
.

public:

	// Property and Function about AI Modifier Test
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "AI Movement")
	bool bIsSucceeded;

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "AI Movement")
	AActor* Target;

	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "AI Movement")
	AActor* Target2;
	
    // 이 반경 안으로 들어오면 도착한 것으로 치겠다. 라고 설정하기 위해 만든 Radius
	UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "AI Movement")
	float AcceptanceRadius = 50.0f;

	UFUNCTION(BlueprintCallable, Category = "AI Movement")
	void MoveToTarget();

	UFUNCTION()
	void OnMoveCompleted(FAIRequestID RequestID, EPathFollowingResult::Type Result);

	// Callable at Blueprint - MoveStart
	UFUNCTION(BlueprintCallable, Category = "AI Movement")
	void StartMoving();

	UFUNCTION(BlueprintCallable, Category = "AI Movement")
	void FindTargetPoints();

protected:
	virtual void BeginPlay() override;

private:
	UPROPERTY()
	AAIController* AIController;

	UPROPERTY()
	bool bIsMoving;
};
📋 AI_TestCharacter.cpp
// 헤더 추가
#include "Kismet/GameplayStatics.h"
#include "NavigationSystem.h"
#include "Navigation/PathFollowingComponent.h"


AAI_TestCharacter::AAI_TestCharacter()
{
    .
    .
    
	// AI Modifier Test Initialize
	bIsSucceeded = false;
	bIsMoving = false;
	AcceptanceRadius = 50.0f;
}

void AAI_TestCharacter::BeginPlay()
{
	Super::BeginPlay();

	// Find AI Controller
	AIController = Cast<AAIController>(GetController());

	if (AIController)
	{
		AIController->ReceiveMoveCompleted.RemoveDynamic(this, &AAI_TestCharacter::OnMoveCompleted);
		AIController->ReceiveMoveCompleted.AddDynamic(this, &AAI_TestCharacter::OnMoveCompleted);
	}

	// Find TargetPoint
	FindTargetPoints();
	StartMoving();
}


void AAI_TestCharacter::NotifyControllerChanged()
{
	Super::NotifyControllerChanged();

	// Add Input Mapping Context
	if (APlayerController* PlayerController = Cast<APlayerController>(Controller))
	{
		if (UEnhancedInputLocalPlayerSubsystem* Subsystem = ULocalPlayer::GetSubsystem<UEnhancedInputLocalPlayerSubsystem>(PlayerController->GetLocalPlayer()))
		{
			Subsystem->AddMappingContext(DefaultMappingContext, 0);
		}
	}
	else
	{
		AIController = Cast<AAIController>(Controller);
		if (AIController)
		{
			AIController->ReceiveMoveCompleted.AddDynamic(this, &AAI_TestCharacter::OnMoveCompleted);
		}
	}
}

//////////////////////////////////////////////////////////////////////////
// AI Modifier 테스트용 Movement Logic 구현.

void AAI_TestCharacter::FindTargetPoints()
{
	// 타겟 포인트가 설정되어 있지 않은 경우 자동으로 찾기
	// "||"는 A OR B로 A 혹은 B가 True일 경우 True를 반환하는 논리연산자입니다. 
	// 여기서는 역논리 연산자가 bool 변수 앞에 붙어있으므로 bool변수가 하나라도 false 일 경우 True로 판정합니다.
	if (!Target || !Target2)
	{
		TArray<AActor*> FoundTargets;
		UGameplayStatics::GetAllActorsOfClass(GetWorld(), ATargetPoint::StaticClass(), FoundTargets);

		if (FoundTargets.Num() >= 2)
		{
			Target = FoundTargets[0];
			Target2 = FoundTargets[1];
			UE_LOG(LogTemplateCharacter, Display, TEXT("Found TargetPoints: %s and %s"),
				*Target->GetName(), *Target2->GetName());
		}
		else
		{
			UE_LOG(LogTemplateCharacter, Warning, TEXT("Not enough TargetPoints found in the level, need at least 2!"));
		}
	}
}

void AAI_TestCharacter::StartMoving()
{
	// 타겟 포인트를 찾고 이동 시작
	FindTargetPoints();
	MoveToTarget();
}

void AAI_TestCharacter::MoveToTarget()
{
	if (!AIController)
	{
		UE_LOG(LogTemplateCharacter, Error, TEXT("AIController is not valid! Make sure the character is possessed by an AIController."));
		return;
	}

	if (bIsMoving)
	{
		// 이미 이동 중이면 중복 호출 방지
		return;
	}

	// IsSucceeded 값에 따라 타겟 선택
	AActor* SelectedTarget = bIsSucceeded ? Target : Target2;

	if (SelectedTarget)
	{
		bIsMoving = true;

		// AI MoveTo 함수 호출
		FVector TargetLocation = SelectedTarget->GetActorLocation();
		EPathFollowingRequestResult::Type MoveResult = AIController->MoveToLocation(
			TargetLocation,
			AcceptanceRadius,
			true,  // 목적지에 오버랩 되면 도착으로 판정할지 여부.
			true,  // 경로 찾기 사용
			false, // 프로젝션 사용 안함
			true   // 네비게이션 데이터 사용
		);

		if (MoveResult == EPathFollowingRequestResult::Failed)
		{
			UE_LOG(LogTemplateCharacter, Warning, TEXT("Failed to start movement to target!"));
			bIsMoving = false;
		}
		else
		{
			UE_LOG(LogTemplateCharacter, Display, TEXT("Moving to %s (IsSucceeded: %s)"),
				*SelectedTarget->GetName(), bIsSucceeded ? TEXT("True") : TEXT("False"));
		}
	}
	else
	{
		UE_LOG(LogTemplateCharacter, Error, TEXT("Selected target is not valid! Make sure Target and Target2 are set."));
	}
}

void AAI_TestCharacter::OnMoveCompleted(FAIRequestID RequestID, EPathFollowingResult::Type Result)
{
	bIsMoving = false;

	// 이동 결과에 따라 IsSucceeded 값 토글
	if (Result == EPathFollowingResult::Success)
	{
		// 성공적으로 이동 완료됨
		bIsSucceeded = !bIsSucceeded;  // 값 토글
		UE_LOG(LogTemplateCharacter, Display, TEXT("Move completed successfully. IsSucceeded toggled to: %s"),
			bIsSucceeded ? TEXT("True") : TEXT("False"));

		// 지연 후 다음 이동 시작
		FTimerHandle TimerHandle;
		GetWorldTimerManager().SetTimer(TimerHandle, this, &AAI_TestCharacter::MoveToTarget, 0.5f, false);
	}
	else
	{
		// 이동 실패
		UE_LOG(LogTemplateCharacter, Warning, TEXT("Move failed with result: %d"), static_cast<int32>(Result));

		// 실패 시에도 다시 시도
		FTimerHandle TimerHandle;
		GetWorldTimerManager().SetTimer(TimerHandle, this, &AAI_TestCharacter::MoveToTarget, 1.0f, false);
	}
}

  • 맵에 있는 TargetPoint를 찾아서 토글에 따라 2개의 TargetPoint가 도착지로서 이용된다.

  • EPathFollowingRequestResult는 MoveToLocation 또는 MoveToActor 요청이 유효했는지 결과를 반환한다.

    • EPathFollowingRequestResult namespace안의 Enum Type이 있음.

  • AIController는 UPathFollowingComponent 를 통해 경로를 따라가고, 도착, 중단, 실패 등의 상황이 발생하면 자동으로 ReceiveMoveCompleted를 호출한다.

    • OnOverlap을 생각하면 쉬움
    • 우리는 앞서 AddDynamic을 통해 OnMoveCompleted를 바인딩했음.

  • ReceiveMoveCompleted을 추적해보면 다음과 같다.

  • 도착하면 ReceiveMoveCompleted가 호출되고 거기에 바인딩 되어있는 OnMoveCompleted을 호출한다.

    • 언리얼 델리게이트 매크로 문법 : 고정된 매개변수 구조를 요구한다. C++ 처럼 (타입 이름) 으로 쓰면 안되고 하나씩 나누어서 쓴다.
    • 따라서 (델리게이터 타입, 인풋1 타입, 변수명, 인풋2 타입, 변수명) 이런식으로 쓴다.

  • 인풋파라미터로 들어가는 FPathFollowingResult의 구조체는 다음과 같다.

    • 따라서 도착결과에 따른 이후 로직으로 확장할 수 있다. 위의 로직에서는 성공하면 0.5초뒤에, 실패하면 1초뒤에 MoveToTarget 호출하도록 함.

📌 적용

  • AI로 부터 TargetPoint로 가는 직선거리가 원래 최소 비용이지만 중간에 고비용 obstacle을 생성했으므로 우회해서 돌아가는 걸 유추할 수 있다.
  • 실행해보면 다음과 같이 움직이는 것을 확인할 수 있다
  • 좀더 극적인 변화를 관찰하기 위하여 레벨 블루프린트에서 키다운 이벤트를 통해 obstacle이 Target Point 사이에 위치하도록 해보았다.
    • 또한 Obstacle이 런타임중에 이동이 가능하도록 설정하기 위해 movable로 설정
    • 직선으로 이동을하다가 '0' 키를 누르는 순간 obstacle이 위치로 이동되면서 경로가 바뀌는 것을 볼 수 있다.
profile
정혜창
Unreal 1기
이전 포스트

AI Navigation System

다음 포스트

AI RVO

0개의 댓글