일정표
| 시간 | 할 일 | 비고 |
| 08:00~10:00 | 코드카타, Atanny, 코드프로그래머스 | |
| 10:00~13:00 | 오늘의 수학, 팀프로젝트 | |
| 14:00~18:00 | 디자인 패턴, 팀프로젝트 | |
| 19:00~21:00 | 개인 공부 | |
| 21:00~22:00 | 운동 | |
| 22:00~23:30 | 개인 공부 |
*오늘의 코드카타*
문제. 숫자 문자열과 영단어
네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다 이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요
#include <string>
#include <vector>
using namespace std;
int solution(string s) {
vector<string> words = {
"zero", "one", "two", "three", "four", "five",
"six", "seven", "eight", "nine"
};
for (int i = 0; i < 10 ; ++i)
{
size_t pos = s.find(words[i]);
while (pos != string::npos)
{
s.replace(pos, words[i].length(), to_string(i));
pos = s.find(words[i], pos + 1);
}
}
return stoi(s);
}(문자열 s 안에서 영단어가 시작되는 인덱스를 반환하여, 만약 없다면 string::npos를 반환하게 한다.
replace 함수를 사용한다. 특정 구간의 문자열을 원하는 다른 문자열로 바꿔주기 위해서이다. 여기에서는 영단어의 길이만큼을 숫자 하나로 교체하도록 한다.
마지막으로 정답을 반환할 때 모든 영단어가 숫자로 바뀐 최종 문자열을 실제 계산 가능한 정수형으로 변환(stoi)한다.
*수학 공부*
주제 : 이산수학과 그래프 이론(Discrete Math & Graph Theory)
이산수학과 그래프 이론은 월드의 뼈대를 조립하고 AI의 두뇌가 작동하는 기반이다.
맵을 네모난 타일(Tile)로 쪼개면, 무한한 공간이 이산적인 노드로 구분되는 공간으로 바뀌게 된다. 그래프 탐색을 활용해서 무한한 공간 안에서도 길 찾기를 할 수 있게 만드는 것이다.
그래프 이론 : 길찾기, 스킬 트리, 퀘스트의 선행/후행 조건, NPC 대화 선택 분기
유한 상태 기계 : AI의 두뇌
조합론과 논리 : 아이템 조합 시스템, 인벤토리 정렬, 게임 규칙
에이스타 알고리즘, NavMesh, 퀘스트 상태 머신 순으로 알아보자.
1. A* 알고리즘
수학적 원리 : f(n) = g(n) + h(n)
원시적인 AI(다익스트라 알고리즘 등)는 목적지가 어디인지 모르는 상태로 사방으로 탐색 영역을 넓혀가며 길을 찾았다. 연산량이 매우 낭비되는 방식이었다.
따라서 에이스타 알고리즘은 '목적지'를 저쪽 쯤에 있을 것이라고 판단하고 이를 방정식에 대입했다.
g(n) = 과거의 비용. 출발점에서 현재 노드(n)까지 오는 데 실제로 걸린 비용이다.
h(n) = 휴리스틱(Heuristic). 미래의 예상 비용. 현재 노드(n) 에서 목적지까지 남은 '예상' 거리로 장애물을 무시하고 대충 그은 직선 거리이다.
f(n) = 최종 평가 점수. 과거의 비용과 미래의 예상 비용을 더한 값으로 AI 는 주변의 갈 수 있는 길 중 무조건 f(n) 값이 가장 낮은 타일을 다음 이동 위치로 선택한다.
다만 에이스타 알고리즘을 적용할 때에는 게임의 장르(그리드 형태)에 따라 남은 거리를 추측하는 휴리스틱(h)의 수학 공식이 달라져야 한다.
1) 맨해튼 거리 (Manhattan Distance) : 십자 이동(상하좌우 4방향)만 가능한 타일 맵 게임에 사용한다. 대각선을 가로지를 수 없으므로, X축 차이와 Y축 차이의 절댓값을 그냥 더하는 방식으로 계산한다.
2) 유클리드 거리 (Euclidean Distance) : 대각선 이동이나 자유로운 8방향 이동이 가능한 3D 게임에서 사용한다. 피타고라스의 정리를 그대로 사용.
에이스타 알고리즘을 코드로 짤 때 프로그래머는 두 개의 List를 관리하게 된다.
Open List : 탐색 대기열. 앞으로 가볼 만한 타일들의 목록이고, f(n)이 가장 낮은 타일이 맨 위에 오도록 우선순위 큐(Priority Queue) 자료 구조 사용.
Closed List : 방문 완료. 이미 계산이 끝나서 다시 탐색하지 않을 타일들의 목록이다. 무한 루프를 방지한다.
#include "CoreMinimal.h"
// 길찾기 노드 구조체
struct FNavNode {
FVector Position;
float GCost; // 시작점부터 여기까지의 실제 비용
float HCost; // 목적지까지의 예상 비용 (휴리스틱)
FNavNode* Parent; // 내가 어디서 왔는지 기록 (나중에 길을 역추적할 때 필수!)
// F 비용은 G + H
float GetFCost() const { return GCost + HCost; }
};
// A* 메인 함수
TArray<FVector> FindPathAStar(FNavNode* StartNode, FNavNode* TargetNode)
{
TArray<FNavNode*> OpenList;
TArray<FNavNode*> ClosedList;
OpenList.Add(StartNode);
while (OpenList.Num() > 0)
{
// 1. Open List에서 F 비용이 가장 낮은 노드를 꺼냄 (우선순위 큐 활용 권장)
FNavNode* CurrentNode = GetLowestFCostNode(OpenList);
// 2. 목적지에 도착했는가?
if (CurrentNode->Position == TargetNode->Position)
{
return RetracePath(StartNode, CurrentNode);
// Parent를 따라 역추적하여 최종 경로 반환
}
// 3. 현재 노드를 Open에서 빼고 Closed(방문 완료)에 넣음
OpenList.Remove(CurrentNode);
ClosedList.Add(CurrentNode);
// 4. 현재 노드의 이웃 타일(보통 4방향 또는 8방향)들을 순회
for (FNavNode* Neighbor : GetNeighbors(CurrentNode))
{
// 갈 수 없는 벽이거나, 이미 방문한 타일이면 무시
if (!IsWalkable(Neighbor) || ClosedList.Contains(Neighbor))
continue;
// 이 길로 가는 것이 기존에 알던 길보다 더 빠른가?
float NewCostToNeighbor = CurrentNode->GCost + GetDistance(CurrentNode, Neighbor);
if (NewCostToNeighbor < Neighbor->GCost || !OpenList.Contains(Neighbor))
{
// 이웃 노드의 비용을 갱신하고, 부모를 현재 노드로 설정
Neighbor->GCost = NewCostToNeighbor;
Neighbor->HCost = GetDistance(Neighbor, TargetNode); // 휴리스틱 계산
Neighbor->Parent = CurrentNode;
if (!OpenList.Contains(Neighbor))
{
OpenList.Add(Neighbor); // 새로 발견한 길이면 탐색 대기열에 추가
}
}
}
}
return TArray<FVector>(); // 길을 찾을 수 없음 (고립됨)
}
에이스타 알고리즘은 다음과 같이 활용될 수도 있다.
AI가 지나가려는 길의 타일이 불길에 휩싸여 있을 때, g(n)에 페널티 비용 +9999를 더해버리면 AI는 거리가 멀더라도 안전하게 우회하는 경로를 수학적으로 찾아내게 할 수 있다. 또는, 길에 따라 이동 비용을 다르게 주면 AI는 자연스럽게 이동 비용이 가장 값싼 길을 선택해서 이동하려고 할 것이다.
다만, 에이스타 알고리즘은 정지해 있는 벽을 피하는 데에는 완벽하지만 움직이는 아군을 피하는 건 매우 힘들다. 따라서 여러 AI가 동시에 움직일 때 움직이는 아군이 그 순간 장애물로 인식되면 뒤에 있던 AI는 길이 막혔다고 판단하고 엉뚱한 방향으로 에이스타 알고리즘을 다시 돌려버리는 현상이 발생하기도 한다.
2. NavMesh
언리얼을 다룬다면 몰라서는 안되는 개념. 현대 게임 엔진의 기본 길찾기 시스템이자, 3D 공간의 그래프 이론의 꽃이라 불리는 Navigation Mesh에 대해서 알아보자.
1) NavMesh?
내비메시의 핵심은 "세상을 볼록 다각형으로 덮는 것" 이다. 맵의 걸어 다닐 수 있는 바닥을 수많은 볼록 다각형(Convex Polygon)으로 쪼개서 덮어버리는 것이다. 수학에서 볼록 다각형은 "도형 내부의 임이의 두 점 A와 B를 직선으로 이었을 때, 그 선은 절대 도형 밖을 벗어나지 않는다"라는 특성을 가지고 있다. 이는 굉장히 중요한 성질인데, AI가 같은 다각형 안에 있는 목표를 향해 걸어갈 때는 장애물 검사나 길찾기를 할 필요가 전혀 없이 그냥 직진(Lerp)만 해도 절대 벽에 부딪히지 않게 된다.
2) 그래프 이론을 NavMesh에 적용하기
그럼 이제 이 NavMesh에 그래프 이론을 적용해보자.
각각의 볼록 다각형은 그래프의 '점(Node)'이 되고, 다각형끼리 서로 맞닿아 있는 경계선(Portal)이 그래프의 '선(Edge)'이 된다.
AI가 목적지를 찾아가려 할 때, 맵 전체를 탐색하는 것이 아니라 에이스타 알고리즘을 이 다각형 그래프 위에서 똑같이 돌린다. 그렇게 되면 "A번 다각형 -> B번 다각형 -> C번 다각형을 거쳐간다"와 같이 이산적 경로를 수학적으로 찾아내게 된다.
3) 펀넬 알고리즘 (Funnel Algorithm / String Pulling)
다각형의 순서만 알아냈다고 길찾기가 끝나는 것은 아니다. 다각형의 중심점만 밟고 걸어가면 AI가 지그재그로 걸어가는 문제점이 발생한다. 우리가 원하는 것은 NavMesh 위 모퉁이를 아슬아슬하게 스치며 지나가면서, 최단 거리의 부드러운 곡선(연속적인 경로)으로 움직이는 것이다. 이때 사용되는 것이 계산 기하학의 알고리즘인 펀넬 알고리즘(끈 당기기 알고리즘)이다.
수학적 원리 : 외적(Cross Product)을 이용한 끈 당기기
-1. AI가 지나가야 할 다각형들의 맞닿은 경계선들의 왼쪽 끝점과 오른쪽 끝점들을 쭉 나열한다.
-2. 출발점에서 도착점까지 팽팽한 끈을 통과시켰다고 상상하고, 양쪽에서 끈을 잡아당긴다. 이를 '벡터의 외적'을 사용해서 계산한다.
-3. 다음 경계선의 왼쪽 점이 현재의 끈 안쪽으로 들어오는지 수학적으로 검사한다. 이는 외적의 방향이 바뀌는지 검사하여 알 수 있다. 만약 끈이 꺾이는 지점(모퉁이)이 발견되면, 그곳을 새로운 웨이포인트로 확정짓는다.
핵심은 '펀넬 알고리즘' 덕분에 AI가 모퉁이를 부드럽게 깎아지르며 최단 거리로 달릴 수 있게 되었다는 것이다.
4) 언리얼 엔진 내비메시 시스템
실제 언리얼 엔진의 UNavigationSystemV1 내부에는 업계 표준 내비메시 오픈소스인 Recast & Detour 라이브러리가 통째로 들어있는 것을 확인할 수 있다. Recast가 3D 메쉬를 Voxel로 부수고 볼록 다각형으로 구워내면(Baking), Detour가 에이스타 알고리즘과 펀넬 알고리즘을 쉴 새 없이 돌려준다. 프로그래머는 C++에서 이 엔진의 두뇌를 호출하기만 하면 된다.
(개념 C++에 접목하기 : AI의 완벽한 궤적 뽑아내기)
#include "NavigationSystem.h"
#include "NavigationPath.h"
void AMyAIController::MoveToTargetPerfectly(FVector TargetPos)
{
// 1. 현재 월드를 지배하는 내비게이션 시스템(그래프 뇌)을 가져옴
UNavigationSystemV1* NavSys = UNavigationSystemV1::GetCurrent(GetWorld());
if (!NavSys) return;
FVector StartPos = GetPawn()->GetActorLocation();
// 2. 엔진에 길찾기 요청 (이 한 줄 안에서 A*와 펀넬 알고리즘이 계속 돌아감)
UNavigationPath* NavPath = NavSys->FindPathToLocationSynchronously(GetWorld(), StartPos, TargetPos);
if (NavPath && NavPath->IsValid())
{
// 3. NavPath->PathPoints 에는 펀넬 알고리즘으로 팽팽하게 당겨진 '모퉁이 점'들만 딱딱 들어있음
const TArray<FVector>& OptimizedCorners = NavPath->PathPoints;
UE_LOG(LogTemp, Log, TEXT("발견된 모퉁이(웨이포인트) 개수: %d"), OptimizedCorners.Num());
// 4. 추출된 코너 점들을 화면에 빨간색 선으로 그려서 (디버그) AI의 경로를 시각적으로 확인
for (int32 i = 0; i < OptimizedCorners.Num() - 1; ++i)
{
DrawDebugLine(GetWorld(), OptimizedCorners[i], OptimizedCorners[i+1], FColor::Red, false, 3.0f, 0, 5.0f);
}
// 실제 이동 명령 하달
// MoveToLocation(TargetPos);
}
else
{
UE_LOG(LogTemp, Warning, TEXT("수학적으로 도달할 수 없는 곳입니다. (고립 상태)"));
}
}
이에 더해 최신 언리얼 엔진은 Dynamic NavMesh(동적 내비메시)모드를 지원한다. 장애물이 생성된 좁은 구역(Tile)만 비동기 스레드에서 빠르게 다시 계산(Re-baking)해서 그래프의 간선(Edge)를 끊어버리는 식으로 인게임에서 건물이 부서지거나 새로운 장애물이 생겨서 길이 막히는 경우 AI들이 실시간으로 에이스타 경로를 재탐색하여 우회하도록 만든다.
5) 언리얼 엔진의 NavMesh 단절 현상
언리얼 엔진 에디터에서 NavMeshBoundsVolume 박스를 깔고 P 키를 누르면 초록색 영역이 깔린다. 이 과정이 "3D 공간을 Voxel로 쪼갠 뒤 Convex Polygon으로 Baking하는 수학적 연산"이다. 이를 엔진 내부의 Recast 모듈이 자동으로 대신해주는 것이라고 이해하면 된다.
그런데 가끔 멀쩡한 땅인데 AI가 길을 찾지 못하는 경우가 발생(NavMesh 단절 현상)하곤 하는데, 이는 수학적 '에이전트 제약 조건(Agent Constraints) 때문이다.
-1. 에이전트 반지름 (Agent Radius) : NavMesh는 벽에 딱 붙어서 생성되지 않는다. AI가 벽에 계속 비비는 것을 막기 위해서 AI의 크기(Radius)만큼 벽에서 NavMesh를 안쪽으로 깎아내서 생성한다. 만약 문 틈이나 두 장애물 사이의 좁은 길이 (에이전트 반지름 x 2) 보다 좁다면, 그 사ㅣㅇ의 다각형이 아예 생성되지 않고 끊어져버린다.
-2. 경사각과 계단 높이 (Max Slope & Step Height) : 경사가 45도 이상이거나 계단 턱이 너무 높으면 엔진은 "인간형 AI가 걸어서 못 올라가는 절벽"이라고 수학적으로 판단내린 뒤 NavMesh를 끊어버린다.
이를 해결하기 위해서 NavMesh 또는 Nav Modifier Volume을 수동으로 덧대어 고치곤 한다. 수학적 조건 때문에 서로 끊어져 버린 다각형 사이를 강제로 연결해주는 다리(Edge)를 만들어 주는 것이다.
3. 퀘스트 상태 머신
길찾기와 유사한 논리로, AI가 지금 무엇을 해야 할지(상태)를 결정하는 구조 역시 이산수학의 오토마타 이론(Automata Theory)과 트리(Tree) 그래프에 완벽하게 기반을 두고 있다.
1) 유한 상태 기계 (FSM)
예전에는 몬스터의 행동을 설계할 때 이산수학의 '상태(State)'라는 개념을 사용했다. 몬스터는 유한한 개수의 상태 중 단 하나에만 머무를 수 있고, 특정 조건(Event/Condition)이 만족되면 다른 상태로 전이(Transition)된다.
// 1. 유한한 상태들을 Enum으로 정의 (이산적인 데이터)
UENUM(BlueprintType)
enum class EMonsterState : uint8
{
Idle,
Patrol,
Chase,
Attack
};
void AMyMonster::Tick(float DeltaTime)
{
Super::Tick(DeltaTime);
// 2. 현재 상태에 따라 행동을 분기 (Switch-Case 오토마타)
switch (CurrentState)
{
case EMonsterState::Idle:
if (CanSeePlayer())
{
// 상태 전이 (Transition)
ChangeState(EMonsterState::Chase);
}
break;
case EMonsterState::Chase:
MoveToPlayer();
if (DistanceToPlayer() <= AttackRange)
{
ChangeState(EMonsterState::Attack);
}
else if (!CanSeePlayer())
{
ChangeState(EMonsterState::Patrol);
}
break;
case EMonsterState::Attack:
PerformAttack();
break;
// ... 기타 상태들
}
}가장 기본적이고 직관적인 FSM 구조. 보스 몬스터의 큰 페이즈(Phase 1, 2, 3)를 나눌 때에도 여전히 자주 사용된다.
그러나 예상했다시피, FSM은 상태가 3~4개 또는 그 이상의 복잡한 요구사항을 구현해야 할 수록 모든 상태끼리 Transition 선이 복잡하게 얽히는 스파게티 그래프가 되어버린다. 결국 유지보수가 불가능해지는 '상태 폭발(State Explosion)' 문제에 직면하게 된다.
2) 현대 AI의 표준 두뇌 : 비헤이비어 트리(Behavior Tree, BT)
FSM의 한계를 극복하기 위해서 헤일로 개발진이 고안하고, 언리얼 엔진이 기본으로 채택한 시스템이 바로 비헤이비어 트리이다.
수학적 원리 : 방향성 비순환 그래프(DAG)와 논리 연산
BT는 이름 그대로 Tree 형태의 이산수학 그래프이다. Root에서 시작하고, 위에서 아래로, 왼쪽에서 오른쪽으로 흐르며 각 노드는 오직 Success/Failed/In Progress 3가지 논리값만을 반환한다.
BT를 지배하는 2가지 핵심 제어 노드를 이해하면 된다.
-1. 시퀀스
Sequence. -> 기호. 논리곱(And, &&)과 같다. 자식 노드들을 왼쪽부터 실행하다가 하나라도 실패하면 즉시 멈추고 부모에게 Failed를 반환한다.
-2. 셀렉터
Selector. ? 기호. 논리합(Or, ||)과 같다. 자식 노드들을 왼쪽부터 실행하다가 하나라도 성공하면 즉시 멈추고 부모에게 Success를 반환한다.
언리얼에서 BT를 짤 때 프로그래머는 C++로 가장 말단에 있는 행동인 '태스크 노드(Task Node)' 단위만 모듈처럼 만들어둔다. 이렇게 하면 기획자가 에디터에서 이 블록들을 자유롭게 조립하며 AI의 행동을 만들어 나갈 수 있다.
(사례 : 커스텀 Task Node 만들기)
#include "BehaviorTree/BTTaskNode.h"
#include "BehaviorTree/BlackboardComponent.h"
#include "NavigationSystem.h"
// UBTTaskNode를 상속받아 새로운 AI 행동 블록(레고 조각)을 생성
UCLASS()
class UBTTask_FindRandomPatrol : public UBTTaskNode
{
GENERATED_BODY()
public:
UBTTask_FindRandomPatrol()
{
NodeName = "Find Random Patrol Point"; // 에디터에 표시될 이름
}
// 트리가 이 노드를 실행할 때 무조건 호출되는 핵심 수학/로직 함수
virtual EBTNodeResult::Type ExecuteTask(UBehaviorTreeComponent& OwnerComp, uint8* NodeMemory) override
{
// 1. AI 컨트롤러와 폰(Pawn) 정보 가져오기
AAIController* AIController = OwnerComp.GetAIOwner();
APawn* AIPawn = AIController->GetPawn();
// 2. 내비메시 시스템 호출 (NavMesh 시스템의 활용)
UNavigationSystemV1* NavSys = UNavigationSystemV1::GetCurrent(GetWorld());
FNavLocation RandomLocation;
// 반경 1000 유닛 내의 걸을 수 있는 랜덤 다각형(NavMesh) 좌표를 수학적으로 추출
if (NavSys->GetRandomReachablePointInRadius(AIPawn->GetActorLocation(), 1000.0f, RandomLocation))
{
// 3. 블랙보드(AI의 메모리)에 찾은 좌표를 덮어씌움
// (에디터에서 기획자가 지정한 Key 이름으로 접근)
OwnerComp.GetBlackboardComponent()->SetValueAsVector("PatrolTarget", RandomLocation.Location);
// 4. 이 행동이 성공적으로 끝났음을 트리에 보고 (부모인 시퀀스/셀렉터가 이를 받아 다음 행동을 결정함)
return EBTNodeResult::Succeeded;
}
// 길을 찾지 못했다면 실패를 반환 (시퀀스가 끊어지고 다른 대안 행동을 찾게 됨)
return EBTNodeResult::Failed;
}
};
BT는 FSM에 비해 목표 중심(Goal-Driven)이고 완벽하게 모듈화되어있다. 예를 들어, 위의 C++ 코드에서 볼 수 있듯이 UBTTask_FindRandomPatrol이라는 함수 하나만 만들어 두면 어떤 형태의 AI에서라도 그대로 드래그 앤 드롭해서 재사용할 수 있게 된다.
3) 스테이트 트리 (State Tree) + 모션 매칭 (Motion Matching)
스테이트 트리는 BT 를 대체 또는 보완하기 위해 나온 UE5의 AI 시스템이다. FSM의 직관성과 BT의 모듈화 장점을 합친 트리형 상태 머신이다. 기존 BT보다 연산이 훨씬 가볍고 빠르며, 언리얼의 대규모 군중 시스템인 매스 엔티티(Mass Entity, ECS 구조)와 완벽하게 호환된다.
모션 매칭은, 기존의 애니메이션 블루프린트에서 트랜지션을 일일이 거미줄 처럼 짜던 방식 말고, 수백 개의 애니메이션 클립을 그냥 다 집어넣어 놓으면 엔진이 매 프레임 캐릭터의 '현재 속도와 물리 궤적'을 수학적으로 계산해서 가장 자연스러운 애니메이션 포즈를 알아서 찾아 틀어주는 기능이다.
*개인 프로젝트 및 개인 공부*
탑다운 뷰로 간단한 게임 기능 만들어보기 연습을 했다. 같은 기능을 블루프린트 기능을 활용하는 방법과, C++을 사용해서 구현하는 방법 두 가지를 병행했다.