[내일배움캠프 Day86] AI - 회피, 자동 네비게이션 링크

AI 이동 명령 및 경로 찾기(Pathfinding) 알고리즘

1) Unreal Engine의 경로탐색(Pathfinding)원리

언리얼 엔진의 AI는 A*(A-Star) 알고리즘 혹은 다익스트라(Djikstra) 알고리즘 등과 같이 특정 경로로 이동하기 위한 비용 최적화 경로 탐색 공식을 바탕으로 경로를 탐색한다.

언리얼 엔진의 Pathfinding의 알고리즘은 가장 저렴한 비용으로 목표 지점까지 이동하도록 설계되어 있다.

위 사진의 경우 Start지점에서 Goal까지 이동하기 위해 가장 저렴한 비용은 3(1+1+1)이다.

 

2) 언리얼 엔진에서의 경로탐색 알고리즘 응용

네비메시는 Runtime 중 동적 생성이 불가능하다. 엔진의 아키텍처 설계상의 이유로 Brush가 Runtime 중 재생성되지 않기 때문이다.

이렇게 네비메시의 재생성이 불가능하다면 AI가 특정 조건에서 플레이어를 추격하도록 하거나, 높은 고지로 이동했을 때 망설이게 만들거나, 지형지물의 변화가 일어날 경우 이동할 수 있도록 만드는 등의 로직 생성이 안 된다는 것이다.

하지만 이런 문제를 해결하는 방법이 있다. Nav Modifier를 활용하면 경로탐색 알고리즘의 메커니즘을 응용해서 AI의 경로를 수정하도록 유도할 수 있다. Nav Modifier의 Area Class를 활용하여 특정 구역별 비용을 차등설정하면 AI가 원하는 경로로 이동하도록 설계할 수 있다.

 

NavArea_Obstacle로 세팅한 Nav Modifier Volume를 레벨 내 세팅하면 아래사진처럼 주황색으로 변경되는데, 이는 해당 영역의 이동 비용이 주변 대비 높다는 의미다.

 

위와 같이 세팅을 한 뒤로 위아래에 target point를 지정하고 ai를 움직이면

아래와 같이 NavModifierVolume의 구역은 경로탐색 시 차순위로 산정되어 왼쪽으로 돌아서 이동하는 모습을 확인할 수 있다.

 

3) MoveToActor와 MoveToLocation

EPathFollowingRequestResult::Type MoveToLocation(
	const FVector& Dest,
	float AcceptanceRadius = -1,
	bool bStopOnOverlap = true,
	bool bUsePathfinding = true,
	bool bProjectDestinationToNavigation = true,
	bool bCanStrafe = false,
	TSubclassOf<UNavigationQueryFilter> FilterClass = nullptr,
	bool bAllowPartialPath = true
);

• Dest: 이동할 목적지 위치 벡터
• AcceptanceRadius: AI가 목적지에 도달했다고 판단할 거리 (값이 클수록 더 멀리서 "도착" 처리)
• bStopOnOverlap: 목적지와 캐릭터의 충돌 영역이 겹치면 도착으로 간주할지 여부
• bUsePathfinding: 경로 탐색 알고리즘을 사용할지 여부 (false면 직선으로 이동 시도)
• bProjectDestinationToNavigation: 목적지를 네비게이션 메시에 투영할지 여부
• bCanStrafe: AI가 측면 이동을 할 수 있는지 여부
• FilterClass: 네비게이션 쿼리에 사용할 필터 클래스
• bAllowPartialPath: 완전한 경로를 찾지 못할 경우 부분 경로라도 허용할지 여부

 

MoveToActor와 MoveToLocation는 모두 AIController의 내부 함수로 유사하다. Actor가 Location의 기능에 몇 가지 기능을 더 얹은 것이라고 볼 수 있다.

• 공통점: AI가 특정 오브젝트로 “이동”하게 만드는 함수
• 차이점: 타겟 오브젝트가 Actor냐 Location이냐의 차이. Actor를 타겟 오브젝트로 삼느냐, Location(특정위치)를 타겟 오브젝트로 삼느냐가 핵심 차이점이며 Actor의 경우 Actor가 실시간으로 이동하면 추적이 가능하고, Location의 경우 특정 좌표로만 이동한다.

 

Actor의 위치도 Location이므로, MoveToActor는 Location을 실시간 업데이트 하고 있는 것과 동일하다. 따라서 MoveToActor가 MoveToLocation보다 연산 비용이 조금 더 발생한다.

 

RVO를 활용한 AI의 장애물 회피

1) RVO란?

RVO(Reciprocal Velocity Obstacles)는 움직이는 객체들이 서로의 속도와 방향을 고려하여 충돌을 피하는 방법이다.

예를 들어, 사람들이 붐비는 거리에서 우리는 주변 사람들의 움직임을 보며 길을 막고 있으면 천천히 걷거나, 자신을 향해 오면 피해 주거나 등등의 방식으로 자신의 속도와 방향을 조절한다. 이러한 원리를 언리얼 엔진 내에 적용한 것이 RVO이다.

한마디로 RVO는 동적 액터들이 서로를 장애물로 인식하고 충돌을 피하는 알고리즘이다. 특히 경로 재계산 없이 속도와 방향만 조정하여 실시간 회피가 가능하므로 다수의 액터가 있을 때 효율적, 자연스러운 움직임 제공하는 게 장점이다.

 

2) RVO 구현 핵심 코드

GetCharacterMovement()->bUseRVOAvoidance = true;
GetCharacterMovement()->AvoidanceConsiderationRadius = 200.0f;
GetCharacterMovement()->AvoidanceWeight = 0.5f;

 

GetCharacterMovement()->bUseRVOAvoidance = true;

RVO(Reciprocal Velocity Obstacles) 회피 시스템의 활성화 여부를 결정하는 가장 기본적인 설정

• 기능: RVO 충돌 회피 알고리즘 활성화 On/Off
• 값의 의미: true로 설정하면 캐릭터가 다른 오브젝트나 장애물과의 충돌을 피하기 위한 자동 회피 기능이 작동. 이 값이 false라면 회피 기능이 작동하지 않는다.
• 적합한 상황: 여러 AI 캐릭터가 서로 상호작용하며 이동해야 하는 상황에서 필수적

 

GetCharacterMovement()->AvoidanceConsiderationRadius = 200.0f;

이 코드는 AI가 다른 오브젝트를 감지하고 회피를 시작하는 거리를 결정

• 기능: 회피 반경 세팅
• 값의 의미: 200 uu(Unreal Unit) 내에 다른 오브젝트가 들어오면 회피를 시작
• 영향:
  • 값이 작을 경우 오브젝트가 가까워질 때까지 회피하지 않으므로 급격한 회피 동작이 발생할 수 있으며, 충돌 위험이 높아진다.
  • 값이 클 경우 오브젝트가 멀리 있을 때부터 회피를 시작하므로 부드러운 회피가 가능하지만, 불필요한 자원낭비가 증가할 수 있다.

 

GetCharacterMovement()->AvoidanceWeight = 0.5f;

이 코드는 해당 클래스를 상속받은 캐릭터의 회피 우선순위를 결정한다.

• 기능: 회피 가중치 세팅
• 값의 범위: 0.0f ~ 1.0f
• 값의 의미:
  • 0.0f에 가까울수록 이 캐릭터가 다른 캐릭터를 먼저 회피한다. (낮은 계급이 됨)
  • 1.0f에 가까울수록 다른 캐릭터들이 이 캐릭터를 먼저 회피한다. (높은 계급이 됨)

 

자동 네비게이션 링크 생성(구 NavLinkProxy) 활용

1) 자동 네비게이션 링크 생성 기능 개요

자동 네비게이션 링크 생성기능은 내비게이션 메쉬의 끊어진 부분을 자동으로 연결하여 AI 캐릭터의 경로 탐색을 향상시키는 기능이다. 네비게이션 메쉬를 분석한 후 특정 요건을 충족하면 뛰어 내리거나 점프해서 이동할 수 있도록 연결한다.

 

2) 자동 네비게이션 링크 생성

해당 기능은 5.5부터 자동화되는 방향으로 업데이트되었다. 기존에는 Nav Link Proxy라는 오브젝트를 레벨 내에 하나씩 배치하여 네비메시가 끊긴 부분마다 디자인해줘야 했었는데, 이제는 아래와 같이 RecastNavMesh-Default 내 Generation 기능을 활용하면 자동으로 생성된다.

 

 

 

출처

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/navigation-system-in-unreal-engine

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/using-avoidance-with-the-navigation-system-in-unreal-engine

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/automatic-navigation-link-generation