일정표
| 시간 | 할 일 | 비고 |
| 08:30~10:00 | 코드카타, 개인 작업 | |
| 10:00~13:00 | 오늘의 수학 + 개인 작업 | |
| 14:00~18:00 | 2시 스크럼 + 팀프로젝트 | |
| 19:00~21:00 | 저녁 스크럼 + 팀프로젝트 + TIL | |
| 21:00~22:00 | 운동 | |
| 22:00~23:30 | 개인 작업 |
*오늘의 코드카타*
문제. 두 개 뽑아서 더하기
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요
#include <vector>
#include <set>
using namespace std;
vector<int> solution(vector<int> numbers) {
set<int> sum_set;
for (size_t i = 0; i < numbers.size(); ++i) {
for (size_t j = i + 1; j < numbers.size(); ++j) {
sum_set.insert(numbers[i] + numbers[j]);
}
}
return vector<int>(sum_set.begin(), sum_set.end());
}(1) 문제의 특성상 set 자료구조를 활용하는 것이 가장 적합해 보였다. set 자료구조는 중복된 값을 알아서 제거하고 오름차순 정렬하는 특성을 가지고 있다. 따라서 set에 insert 한 뒤에 마지막에 vector로 변환하여 반환하는 방식으로 문제를 풀이했다.
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> numbers) {
vector<int> answer;
answer.reserve(numbers.size() * numbers.size() / 2);
for (size_t i = 0; i < numbers.size(); ++i) {
for (size_t j = i + 1; j < numbers.size(); ++j) {
answer.emplace_back(numbers[i] + numbers[j]);
}
}
sort(answer.begin(), answer.end());
answer.erase(unique(answer.begin(), answer.end()), answer.end());
return answer;
}(2) 데이터의 크기가 매우 크거나 시간 제한이 타이트한 경우, set은 insert할 때마다 정렬하므로 시간이 많이 걸리게 된다. 따라서 vector를 사용해서 데이터를 다 모은 후 한 번에 정렬하는 것이 효율적이다. 우선 전부다 벡터에 모은 후 sort로 오름차순을 실행한다. 그 이후 unique를 이용해서 중복된 값들은 뒤로 보낸 뒤에 erase로 지워낸다.
*수학 공부*
주제 : 공간 분할 알고리즘 (Spatial Partitioning)
비헤이비어 트리로 AI의 두뇌를 만들었으면, 이제 수많은 AI들이 좁은 공간에서 서로 부딪히고 타겟을 찾을 때 발생하는 서버 렉(Lag)을 수학적으로 소멸시켜버리는 방법인 공간 분할 알고리즘을 배워보자.
1. 2D : 쿼드트리(Quadtree)
모든 AI가 각각의 거리를 재고 이에 상응하는 상호작용을 하도록 만들면 그대로 O(N^2)의 연산을 매 프레임마다 CPU가 실행하여 불타버리고 말 것이다. 따라서, 게임 속 세상을 4등분(Quad)의 나무(Tree) 모양으로 쪼개면서 시작하는 것이 쿼드트리 알고리즘이다.
프로그래머가 'Capacity' 를 정하면, 한 사각형 안에는 해당 Capa 만큼만 들어갈 수 있다. 만약 Capa를 넘어서는 유닛이 들어서게 되면, 그 사각형은 정확히 십자가 모양으로 4등분(NW, NE, SW, SE)된다. 유닛이 한 사각형 안에 몰리면 몰릴 수록 해당 사각형이 또 4등분 되는 재귀적 분할 형태를 띈다.
이렇게 분할하게 되면, 해당 유닛이 속해 있는 가장 작은 사각형과 사거리가 걸쳐 있는 인접한 사각형에 있는 유닛들과 거리를 재기만 하면 끝이다. 연산량을 매우 절감할 수 있는 방법이다.
게임 엔진 내부에서 쿼드트리 구조를 C++ 코드로 어떻게 작성되어있는지 핵심 로직만 살펴보자.
// 쿼드트리의 한 구역(노드)을 나타내는 클래스
class FQuadtreeNode {
public:
FBox2D Boundary; // 이 구역의 물리적 경계 (AABB)
int32 Capacity = 4; // 한 구역에 들어갈 수 있는 최대 유닛 수
TArray<AActor*> Units; // 현재 구역에 있는 유닛들
bool bIsDivided = false; // 4등분 되었는가를 판단.
// 자식 노드 4개 (북서, 북동, 남서, 남동)
FQuadtreeNode* NorthWest;
FQuadtreeNode* NorthEast;
FQuadtreeNode* SouthWest;
FQuadtreeNode* SouthEast;
// 유닛 추가 함수
bool Insert(AActor* NewUnit) {
// 1. 유닛이 이 구역을 벗어났다면 거절
if (!Boundary.IsInside(NewUnit->GetActorLocation2D())) return false;
// 2. 아직 정원이 안 찼고, 분할도 안 됐다면 여기에 저장
if (Units.Num() < Capacity && !bIsDivided) {
Units.Add(NewUnit);
return true;
}
// 3. 정원이 찼다면 4등분으로 쪼개기 (Subdivide)
if (!bIsDivided) {
Subdivide();
}
// 4. 4개의 자식 중 하나에 밀어 넣기
if (NorthWest->Insert(NewUnit)) return true;
if (NorthEast->Insert(NewUnit)) return true;
if (SouthWest->Insert(NewUnit)) return true;
if (SouthEast->Insert(NewUnit)) return true;
return false;
}
// 탐색 반경 내의 유닛만 반환하는 쿼리 함수
void Query(FSphere SearchArea, TArray<AActor*>& OutFoundUnits) {
// 내 구역이 탐색 원형 범위와 안 겹친다면 -> 즉시 종료 (Early Exit - 최적화의 핵심)
if (!Boundary.Intersect(SearchArea)) return;
// 겹친다면, 이 구역 안에 있는 유닛들을 모두 검사 대상으로 추가
for (AActor* Unit : Units) {
if (SearchArea.IsInside(Unit->GetActorLocation2D())) {
OutFoundUnits.Add(Unit);
}
}
// 자식 구역들이 있다면 그쪽으로도 파고들기
if (bIsDivided) {
NorthWest->Query(SearchArea, OutFoundUnits);
NorthEast->Query(SearchArea, OutFoundUnits);
SouthWest->Query(SearchArea, OutFoundUnits);
SouthEast->Query(SearchArea, OutFoundUnits);
}
}
};이 로직을 바탕으로, Query 함수를 호출하면 전체 맵을 뒤지는 것이 아니라 탐색 범위와 겹치는 상자들만 골라서 파고드는 방식으로 탐색하게 된다(DFS 방식). 서버 렉을 없앨 수 있는 효율적인 방법이다.
2. 3D : 옥트리(Octree)와 BVH(Bounding Volume Hierarchy)
쿼드트리의 3D 버전이 옥트리이다. 네모난 타일 대신에 정육면체(큐브) 공간을 사용하게 된다. 정원이 초과되면 큐브 하나가 8개의 작은 큐브(Oct)로 쪼개진다. 주로 비행 시뮬레이터나 우주 공간, 수만 개의 3D 파티클 충돌을 계산할 때 쓰인다.
쿼드트리/옥트리는 '공간'을 계속 쪼개는 방식이라면, BVH(Bounding Volume Hierarchy)는 물체들이 모여있는 덩어리를 기준으로 쪼개는 방식이다. 빈 공간은 아예 계산을 하지 않기 때문에 언리얼 엔진의 렌더링(프러스텀 컬링)과 Chaos 물리 엔진의 기본 구조로 가장 많이 쓰이는 최적화 트리이다.
옥트리와 BVH에 대해서 좀 더 자세히 살펴보자.
2-1) 옥트리
큐브 형태의 맵에 오브젝트가 꽉 차면, 그 큐브를 정확히 8개의 작은 큐브로 분할한다. 오직 "이 좌표는 어느 큐브 구역에 속하는가?"라는 절대적인 공간의 격자(Grid)만 가지고 판별한다.
장점 : 물체가 이동할 때, 단순히 좌표만 보고 수학적 연산만 하면 된다. 움직이는 물체를 처리하는 데 압도적으로 빠르다.
단점 : 맵의 구석에 아주 작은 오브젝트를 배치하면, 그 오브젝트 때문에 빈 공간까지 불필요하게 8등분으로 쪼개지는 메모리 낭비가 발생한다.
언리얼 엔진은 화면에 무엇을 그릴지 결정할 때(Frustum Culling) 내부적으로 옥트리를 사용한다. 유저가 고개를 돌렸을 때, 카메라 시야(Frustum) 상자 하나와 옥트리 큐브들을 충돌 검사해서 시야 바깥에 있는 큐브를 통째로 수백 개의 몬스터와 파티클을 단 한번의 연산으로 렌더링에서 날려버린다.
언리얼 엔진에서는 이 기능을 FScene::PrimitiveOctree로 사용할 수 있다.
다만, 물체가 큐브와 큐브의 경계선에 정확히 걸쳐 있으면 어느 큐브에도 들어가지 못하고 부모 큐브로 밀려나서 최적화가 깨지는 버그가 발생할 수 있다. 해당 오브젝트가 어떠한 큐브에도 속하지 않는다면 결국 맵 전체를 감싸는 최상위 부모 큐브(Root Node)로 밀어 올려버리기 때문이다. 따라서 언리얼 엔진은 큐브의 크기를 살짝 더 크게 부풀려서 서로 겹치게 만드는 '루즈 옥트리(Loose Octree)' 라는 변형 수학을 사용하여 이 문제를 해결하고 있다.
언리얼 엔진의 GenericOctree.h 내부를 살펴보면, 물체가 어느 자식 노드에 들어갈지 판별할 때 단순히 부등호로 중앙선을 넘었는지 검사하지 않는다. 물체의 AABB(축 정렬 경계 상자) 전체가 노드의 영역(루즈 옥트리) 안에 완전히 들어가는지를 검사한다.
// 물체가 특정 자식 노드(Child Node)에 들어갈 수 있는지 검사하는 C++ 수학
bool CanFitInChildNode(FBox CenterAndExtent, FBox ObjectBounds)
{
// 일반 옥트리라면 자식 노드의 반지름(Extent)을 그대로 씀
FVector NormalExtent = CenterAndExtent.Extent;
// 루즈 옥트리: 노드의 경계를 수학적으로 살짝 부풀림 (예: Looseness Factor)
// 언리얼 엔진은 엔진 상수(K)를 사용해 공간을 헐렁하게 만듦
FVector LooseExtent = NormalExtent + FVector(Margin);
FBox LooseNodeBounds = FBox(CenterAndExtent.Center - LooseExtent,
CenterAndExtent.Center + LooseExtent);
// 부풀려진 상자 안에 물체가 완전히 들어가는지 검사
return LooseNodeBounds.IsInside(ObjectBounds);
}
2-2) BVH
BVH는 오브젝트를 감싸 안는 포장지라고 생각하면 된다. BVH는 공간을 반으로 가르면서 시작하지 않고, 물체 그 자체에서부터 시작한다. 가까이 있는 물체 두개를 하나의 가상 상자(AABB)로 묶고, 그 상자들과 또 가까운 상자를 묶어서 더 큰 상자로 묶는다. Bottom-Up 방식의 Tree 형태를 만들면서 올라가는 방식이다.
장점 : 물체가 없는 허공에는 아예 상자가 생성되지 않고, 물체에 딱 맞게 상자가 쪼그라들기 때문에 옥트리보다 충돌(교차) 테스트의 수학적 정밀도가 높다.
단점 : 캐릭터가 박스 A에서 Z로 뛰어가버리면 기존 BVH 구조가 변경되면서 전체 트리의 밸런스가 붕괴된다(Tree Rot). 이걸 다시 묶으려면(Rebuild), 엄청난 CPU 연산이 필요하게 된다. 즉, 가만히 있는 물체(Static Mesh)에만 유리한 구조이다.
BVH를 레이트레이싱(하드웨어 레이트레이싱, RTX)에 주로 사용한다. 빛(Ray)을 수백만 가닥 쏠 때, 옥트리를 쓰면 텅 빈 허공도 검사해야 해서 프레임이 박살나게 된다. GPU는 정밀하게 물체를 감싼 BVH 트리만을 사용해서 빛의 반사를 계산하여 최적화하는 방식을 사용하게 된다. 멈춰있는 배경은 TLAS, 움직이는 캐릭터는 매 프레임 모양이 변하는 BLAS라는 두 개의 BVH를 분리해서 연산하는 식이다.
또한, Static Mesh에 총알이 맞았을 때 어느 폴리곤에 맞았는 지 찾기 위해서 물리 엔진(Chaos Physicss)은 맵을 로딩할 때 보이지 않는 BVH를 백그라운드에서 Bake해서 초고속으로 충돌을 검사하게 된다.
실제로 프로그래머가 C++로 옥트리나 BVH를 new Node() ... 해가면서 밑바닥부터 짤 일은 거의 없다. 이미 엔진에 구현되어있으니 사용만 잘 하면 된다. 엔진이 제공하는 TOctree 템플릿 클래스를 가져다가 나만의 규칙을 정의해서 쓰기만 하면 된다.
#include "Math/GenericOctree.h"
// 1. 옥트리에 들어갈 요소(Element) 정의
struct FMyUnitOctreeElement
{
AActor* UnitActor;
FBoxCenterAndExtent Bounds; // 이 유닛의 중심점과 반지름(크기)
};
// 2. 언리얼 옥트리 시스템에게 이 요소를 어떻게 다룰지 알려주는 '의미론(Semantics)' 구조체
struct FMyUnitOctreeSemantics
{
// 최대 몇 깊이(Depth)까지 쪼갤 것인가? 한 노드당 몇 명까지 허용할 것인가?
enum { MaxElementsPerLeaf = 16 };
enum { MinInclusiveElementsPerNode = 7 };
enum { MaxNodeDepth = 12 };
// 엔진이 물체의 위치를 요구할 때 Bounds를 반환
static FBoxCenterAndExtent GetBoundingBox(const FMyUnitOctreeElement& Element)
{
return Element.Bounds;
}
// ... (기타 필수 함수들 생략)
};
// 3. 실제 옥트리 타입 정의
typedef TOctree<FMyUnitOctreeElement, FMyUnitOctreeSemantics> FMyUnitOctree;
// --- 실제 사용 예시 ---
void AMyGameMode::FindEnemiesInSkillRadius(FVector SkillCenter, float SkillRadius)
{
FBoxCenterAndExtent SkillBounds(SkillCenter, FVector(SkillRadius));
TArray<AActor*> FoundEnemies;
// 4. 옥트리를 순회하며 스킬 범위와 겹치는 큐브(노드) 안의 유닛만 추출
MyGameOctree->FindElementsWithBoundsTest(SkillBounds, [&FoundEnemies](const FMyUnitOctreeElement& Element)
{
// 큐브 단위로 대충 걸러진 유닛들을 대상으로, 정확한 구형(Sphere) 거리 테스트를 한 번 더 진행
FoundEnemies.Add(Element.UnitActor);
});
UE_LOG(LogTemp, Log, TEXT("스킬에 맞은 적: %d 명"), FoundEnemies.Num());
}Math/GenericOctree.h 로 헤더에 인클루드 하고, 옥트리에 들어갈 요소를 정의한 후, 옥트리 시스템에게 요소를 어떻게 다룰지 알려주는 '구조체'를 설명한다. 예를 들어, 최대 어디까지 쪼갤 것인가? 한 노드당 몇 개의 유닛까지 허용할 것인가? 등의 규칙을 정의한다.
이후 옥트리를 순회하며 스킬 범위와 겹치는 큐브 안의 유닛만 추출하고 이들을 대상으로 정확한 Sphere 거리 테스트를 진행하면 된다. 맵 안의 모든 유닛을 대상으로 거리 계산을 하는 것이 아니라, 정확한 거리 계산을 할 대상을 사전에 걸러내는 방식으로 메모리 최적화를 하는 방법이다.
3. 정리
동적(Dynamic) 오브젝트가 많으면 : 파티클, 움직이는 캐릭터, 수많은 탄막이 주가 된다면, 업데이트가 빠른 공간 중심의 Octree를 사용하자.
정적(Static) 오브젝트의 정밀한 충돌이 필요하면 : 복잡한 지형 충돌, 레이트레이싱, 보이지 않는 벽 컬링이 주가 된다면, 정밀한 검색이 가능한 물체 중심의 BVH를 쓰자.
*팀 프로젝트*
1. 작업한 내용들
오늘은 크게 진행된 사항이 없었고, 자잘한 오류 수정 정도를 진행했다. 추가 시간엔 Fab을 돌아다니면서 게임에 사용할 에셋을 찾아보았다.
남는 시간에는 주로 개인 작업(연습)을 진행했다.
2. 다른 팀원 코드 훔쳐보기(저녁 스크럼 이후)
["Core" 폴더]
<1> 게임의 규칙 및 심판 : AParcelGameMode -> UDeliveryRuleComponent
특징 : 네트워크 동기화 매크로(Replicated)가 전혀 없다. 게임 플레이의 규칙과 판정은 오직 서버에서만 안전하게 연산되어야 하기 때문이다.
(AParcelGameMode)
생성자에서 게임모드와 짝을 이루는 RuleComponent를 붙여주는 역할만 수행한다.
(UDeliveryRuleComponent)
AParcelGameMode에 부착되어 작동한다. 배송이 성공했는지 실패했는지 최종 판정을 내리고, 박스 종류/현재 콤보/감점 요소를 종합해 최종 점수를 계산한다.
라운드 시작 시 타이머를 가동하고 종료 시 멈추는 함수가 포함되어있다. 또한 초 단위로 시간이 흐름에 따라 감점되는 기믹이 포함되어 있다.
<2> 게임의 현재 상태와 전체 팀 점수/시간 : AParcelGameState -> UTeamScoreComponent
(AParcelGameState)
생성자에서 짝을 이루는 ScoreComponent를 붙여주는 역할만 수행한다.
(UTeamScoreComponent.h)
모든 플레이어가 화면에서 보게 되는 점수 현황판.
TeamScore의 경우 ReplicatedUsing=OnRep_TeamScore로 선언되어 서버에서 팀 점수가 바뀌는 순간 모든 클라이언트의 컴퓨터에서 OnRep_TeamScore()가 자동으로 실행되어 화면의 HUD 점수를 갱신한다.
마찬가지로 서버 타이머를 기준으로 남은 시간을 클라이언트들에게 동기화하는 로직이 포함되어있다.
<3> 플레이어 개인의 점수와 연속 배송 콤보 시스템 : AParcelPlayerState -> UPlayerStatComponent
(AParcelPlayerState)
생성자에서 짝을 이루는 StatComponent를 붙여주는 역할만 수행한다.
(UPlayerStatComponent)
플레이어 개개인의 점수 현황판.
UPROPERTY(Replicated)가 붙어 있어 서버가 값을 바꾸면 클라이언트의 UI에 즉각 반영되도록 했다.
<4> 기타 컴포넌트 및 인터페이스 : IHealthInterface.h
(IHealthInterface.h)
체력이 필요한 오브젝트라면 무엇이든 상속받아 쓸 수 있는 공용 인터페이스. 현재 HP/ 최대 HP를 조회하고, 데미지 처리 및 회복, 사망 판정 및 래그돌/리스폰 연출 트리거가 포함되어 있다.
*개인 프로젝트 및 개인 공부*
<진행 상황>
1. Project 재 생성(코드 경로 등이 꼬이는 바람에 처음부터 다시.
2. 기획서 수정(추가 사항, 접두사 규칙 등 정립)
3. DGALocationTags : 레벨 위치 및 공간 전환에 사용할 네임 태그 공간 생성.
4. DGALevelDataAsset 데이터 에셋 : 개벌 레벨의 태그와 실제 맵 에셋 소프트 경로 정보를 담는 구조체 작성. 추가로 해당 파일에서 프로젝트의 모든 인게임 레벨 지도를 전역 관리할 데이터 에셋 클래스를 관리함.
5. DGALevelManagerSubsystem : 프로젝트의 전역 레벨 전환 및 카메라 페이드 아웃 연출을 총괄하는 핵심 서브시스템임.
나중에 위젯(UI)에서 해당 서브시스템을 호출하면 '태그'를 사용해서 안전하게 공간 이동을 하고 페이드 아웃 효과까지 자동으로 실행되도록 구현.
페이드인의 경우 레벨 전환 시 PlayerController를 받아올 때 연출을 넣기로 했음.
<why?>
언리얼 엔진의 '레벨 전환 시 객체의 생명주기' 때문.
레벨 이동이 시작되면 엔진은 OpenLevel을 실행하며 기존 레벨에 있는 GameMode, PlayerController, UI 위젯을 Destroy한다. 그러나, GameInstanceSubsystem은 레벨이 바뀌어도 절대로 파괴되지 않기 때문에 레벨이 넘어가는 과도기 동안 입력을 안전하게 차단하고 페이드아웃 타이머를 끝까지 책임질 수 있다.
새로운 레벨이 열리면 새로운 게임모드와 새로운 플레이어 컨트롤러를 받게 된다. 이때 화면은 서브시스템이 걸어둔 Fade Out 때문에 여전히 까만 상태이다. 따라서, 새로 만들어진 PlayerController가 BeginPlay() 시점에서 Fade In 역할을 담당하게 하는 것이 자연스럽고 결합도도 낮아지게 된다.
6. DGAMainMenuWidget : 게임 시작 시 처음 보이는 화면. Start, Quit 버튼만 현재 존재하는 상황이며, 레벨 블루프린트 노드를 사용해서 직접 연결하였음.
7. DGAPlayerController : 게임의 인게임 조작 및 카메라 페이드인을 총괄하는 플레이어 컨트롤러.
8. DGAGameModeBase : 게임의 인게임 규칙을 관장하는 게임모드. 기본 게임모드이며 나중에 미니게임이나 다른 게임 모드가 필요할 경우 추가로 구현해야함.
9. DGAPlayerCharacter : 플레이어 탑다운 캐릭터를 위한 마스터 클래스. 추후 Enhanced Input 에셋들을 동적으로 바인딩할 함수, 탑다운 카메라 뷰 구현을 위한 CameraBoom, TopDownCamera 컴포넌트 등이 부착되어있다. >> 검토를 해보니, 입력 뿐만 아니라 카메라 세팅까지도 별도로 분리하기로 결정. 최대한 캐릭터 클래스는 빈 껍데기만 남겨놓는 방향으로 구현한다.
10. DGACameraComponent : 캐릭터와 분리되어 탑다운 쿼터뷰 시점을 독립적으로 주입하는 카메라 전담 컴포넌트. 나중에 카메라 시점 변경이 요구되면 별개의 카메라컴포넌트를 더 만들 예정이다. 컴포넌트가 가동되는 순간 부모 캐릭터 몸통 위에 CameraBoom을 동적 조립한다.
11. DGAHeroComponent : 캐릭터와 완전히 분리되어 'Enhanced Input 및 탑다운 전용 회전 규칙을 주입하는 핵심 조작 컴포넌트. 부모 캐릭터의 SetupPlayerInputComponent 단계에서 호출되어 입력을 대신 받고, 마우스 회전, 캐릭터 몸통 회전, 이동 방향 자동 바라보기 규칙 세팅, EILocalPlayerSubsystem 등록까지 진행한다. 또한 화면 기준 절대 방향 쿼터뷰 이동 수식을 적용한다.
*오늘의 총평*
스스로 학습하는 시간이 많았다. 다만 오후 스크럼을 진행하는 과정에서 추가적으로 수정해야 할 사항들이 발견되었다. 간단하게 ToDo 리스트에 정리해 두었고, 수정하는 대로 코드 리뷰를 팀원들과 진행하고 1차 완성본을 만들어 낼 예정이다.