코딩 테스트

---

프로그래머스 - 전력망을 둘로 나누기

실패 코드

#include <string>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int getNodeCnt(const vector<vector<int>>& graph, vector<int>& parents, int startNode, pair<int, int> excludeLine)
{
    int nodeCnt = 0;
    queue<int> nextNodes;
    nextNodes.push(startNode);
    
    while(!nextNodes.empty())
    {
        int nowNode = nextNodes.front();
        nextNodes.pop();
        for(int newNode : graph[nowNode])
        {
            if(nowNode == excludeLine.first && newNode == excludeLine.second)
            {
                continue;
            }
            else if(nowNode == excludeLine.second && newNode == excludeLine.first)
            {
                continue;
            }
            
            if(parents[newNode] == startNode)
            {
                continue;
            }
            else if(parents[newNode] != -1)
            {
                return -1;
            }
            
            parents[newNode] = startNode;
            nextNodes.push(newNode);
            nodeCnt++;
        }
    }
    
    return nodeCnt;
}
int solution(int n, vector<vector<int>> wires) {
    int answer = 100;
    vector<vector<int>> graph(100, vector<int>());
    
    for(vector<int>& row : wires)
    {
        graph[row[0]].push_back(row[1]);
        graph[row[1]].push_back(row[0]);
    }
    
    for(int i = 0; i < graph.size(); i++)
    {
        for(int j = 0; j < graph[i].size(); j++)
        {
            vector<int> parents(graph.size(), -1);
            pair<int, int> excludeLine = make_pair(i, j);
            int temp1 = getNodeCnt(graph, parents, i, excludeLine);
            int temp2 = getNodeCnt(graph, parents, j, excludeLine);
            if(temp1 == - 1 || temp2 == -1)
            {
                continue;
            }
            else if(temp1 == 100 && temp2 == 100)
            {
                continue;
            }
            
            answer = min(answer, abs(temp1 - temp2));
        }
    }
    return answer;
}

문제를 다시보니 Wires(r각 송전탑을 연결하는 선들)의 개수가 n -1, 송전탑보다 하나 작은 수이며 모두 연결되어 있다는 것은 하나를 끊으면 무조건 둘로 나뉘는 상황이라는 것이니 기존에 코드를 상당히 다르게 바꿀 수 있을 것 같네요. 일단 위회해서 연결되는 루트는 존재하지 않는 다는 거니까요.

실패 코드

#include <string>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int getNodeCnt(const vector<vector<int>>& graph, int startNode, vector<bool>& visited, pair<int, int> excludeLine)
{
    int nodeCnt = 0;
    queue<int> nextNodes;
    nextNodes.push(startNode);
    visited[startNode] = true;
    
    while(!nextNodes.empty())
    {
        int nowNode = nextNodes.front();
        nextNodes.pop();
        for(int newNode : graph[nowNode])
        {
            if(visited[newNode])
            {
                continue;
            }
            
            if(nowNode == excludeLine.first && newNode == excludeLine.second)
            {
                continue;
            }
            else if(nowNode == excludeLine.second && newNode == excludeLine.first)
            {
                continue;
            }
            
            nextNodes.push(newNode);
            visited[newNode] = true;
            nodeCnt++;
        }
    }
    
    return nodeCnt;
}
int solution(int n, vector<vector<int>> wires) {
    int answer = 100;
    vector<vector<int>> graph(100, vector<int>());
    
    for(vector<int>& row : wires)
    {
        graph[row[0]].push_back(row[1]);
        graph[row[1]].push_back(row[0]);
    }
    
    for(int i = 0; i < graph.size(); i++)
    {
        for(int j = 0; j < graph[i].size(); j++)
        {
            vector<bool> visited(graph.size(), false);
            pair<int, int> excludeLine = make_pair(i, j);
            int cnt1, cnt2;
            cnt1 = getNodeCnt(graph, i, visited, excludeLine);
            cnt2 = getNodeCnt(graph, j, visited, excludeLine);
            answer = min(answer, abs(cnt1 - cnt2));
        }
    }
    return answer;
}

여전히 틀리지만 코드의 수는 확실히 줄었습니다. 오답도 이전의 코드와 동이하게 나오고 있고요. 어디서 실수한 거람?

튜터님 조언 받기

지금 방식
BFS를 사용해서 시작노드를 끊은 선의 시작점, 끝점으로 하고 있습니다.

추천 방식
DFS를 사용. 바닥 노드에서 다른 노드로 이동할 때 걸리는 선의 개수를 기록해서 대조한다?

Unrooted와 Rooted는 루트의 결정 여부 차이이지 호환은 문제없이 된다.
Rooted로 그래프를 변경

인덱스의 어긋남 인덱스로 만들어서 사용하자송전탑 번호를 그대로 사용하니 그래프의 크기 100과 어긋남이 발생
송전탑 번호에 1을 빼서 인덱스로 만들기
이제 견본 테스트 케이스는 통과하나, 제출 시 정답률은 46.2%

튜터님 조언 : 인덱스 같은 것은 변수로 만들어야 오류율을 줄이기 좋다

#include <string>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int getNodeCnt(const vector<vector<int>>& graph, int startNode, vector<bool>& visited, pair<int, int> excludeLine)
{
    int nodeCnt = 0;
    queue<int> nextNodes;
    nextNodes.push(startNode);
    visited[startNode] = true;
    
    while(!nextNodes.empty())
    {
        int nowNode = nextNodes.front();
        nextNodes.pop();
        for(int newNode : graph[nowNode])
        {
            if(visited[newNode])
            {
                continue;
            }
            
            if(nowNode == excludeLine.first && newNode == excludeLine.second)
            {
                continue;
            }
            else if(nowNode == excludeLine.second && newNode == excludeLine.first)
            {
                continue;
            }
            
            nextNodes.push(newNode);
            visited[newNode] = true;
            nodeCnt++;
        }
    }
    
    return nodeCnt;
}
int solution(int n, vector<vector<int>> wires) {
    int answer = 100;
    vector<vector<int>> graph(100, vector<int>());
    
    for(vector<int>& row : wires)
    {
        int startNode = row[0] - 1;
        int endNode = row[1] - 1;
        
        graph[startNode].push_back(endNode);
        graph[endNode].push_back(startNode);
    }
    
    for(int i = 0; i < graph.size(); i++)
    {
        for(int j = 0; j < graph[i].size(); j++)
        {
            vector<bool> visited(graph.size(), false);
            pair<int, int> excludeLine = make_pair(i, j);
            int cnt1, cnt2;
            cnt1 = getNodeCnt(graph, i, visited, excludeLine);
            cnt2 = getNodeCnt(graph, j, visited, excludeLine);
            answer = min(answer, abs(cnt1 - cnt2));
        }
    }
    return answer;
}

이어서 그래프가 아니라 트리니 visited 사용 없이 스택이나 큐로도 개수를 구할 수 있다는 조언을 주셨습니다. 내일 다시 한 번 알아봐야겠네요.

---

---

어제에 이어 내비게이션 메시 공부

---

1-1 . Navigation Modifier(내비게이션 모디파이어) 보충

내비게이션 모디파이어는 AI가 이동 경로를 계산할 때 사용하는 내비게이션 메시(NavMesh)의 특정 영역에 속성을 부여하거나 비용(Cost)을 수정하여 AI의 이동 경로를 제어하는 도구입니다.

목적 : AI가 특정 구역을 피하게 하거나, 특정 구역으로만 다니게 유도하거나, 혹은 완전히 지나가지 못하게 설정합니다.
비용(Cost) 시스템 : AI는 목적지까지 가장 '비용'이 적게 드는 경로를 찾는다고 합니다. 모디파이어를 통해 특정 구역의 비용을 높이면 AI는 더 멀더라도 비용이 낮은 깨끗한 길을 선택하게 됩니다.

Volume & Component

NavModifier는 Volume과 Component의 2 종류가 존재합니다.

NavModifier Volume(볼륨)

레벨 에디터의 Plcae Actor(액터 배치) 패널에서 배치할 수 있는 브러시 형태의 액터입니다.

• 용도: 레벨 디자인 단계에서 고정된 구역의 내비게이션 속성을 지정할 때 사용합니다.
• 특징 : 월드에 고정되어 있으며, 특정 구역 전체를 감싸서 해당 구역 내의 NavMesh 생성을 변경합니다.
• 사용 예시 : 맵에 고정된 독 구덩이, 지뢰밭, 또는 AI가 우선적으로 다녀야 하는 인도 설정.

Nav Modifier Component(컴포너트)

액터 내부에 추가하 수 있는 컴포넌트입니다.

• 용도 : 동적인 오브젝트나 특정 액터의 형태에 따라 NavMesh를 수정해야 할 때 사용합니다.
• 특징 : 액터의 RootComponent(주로 Collsion Box나 Mesh)의 부피를 기준으로 NavMesh를 수정합니다. 액터가 움직이면 수정된 영역도 함꼐 움직입니다.
• 주의사항 : 하나의 액터당 하나의 Nav Modifier Component만 유효하며, 르트 컴포넌트의 볼류이 수정 기준이 됩니다.
• 사용 예시 : 파괴 간으한 장애물, 열리고 닫히는 문, 혹은 이동하는 위험 구역

Area Class(영역 클래스)

모디파이어가 NavMesh를 어떻게 바꿀지 결정하는 데이터 세트입니다. NavArea 클래슬르 상속받아 직접 만들수도 있습니다.

• NavArea_Default (초록색): 기본 걷기 가능 구역입니다.
• NavArea_Null (투명/제거): NavMesh를 생성하지 않습니다. AI가 절대로 지나갈 수 없는 구역을 만들 때 사용합니다(Elimination 구역 등).
• NavArea_Obstacle (빨간색): 통과는 가능하지만 높은 비용을 부여합니다. 다른 길이 있다면 AI가 이 구역을 피하게 됩니다.
• 사용자 정의 클래스: Fixed Area Entering Cost(진입 비용)와 Default Cost(이동 비용 배수)를 설정하여 AI의 선호도를 세밀하게 조정할 수 있습니다.

설정 및 빌드 관계

• 배치 : Nav Modifier Volume을 월드에 배치하거나 액터에 Nav Modifier Component를 추가합니다.
• 영역 클래스 지정: 디테일 패널의 AreaClass에서 원하는 클래스를 선택합니다.
• 확인 : 단축치 'P"를 눌러 뷰포트에서 NavMesh 시각화를 활성화해서 확인합니다. 모디파이어가 적용된 구역은 해당 클래스에 설정된 색상(빨간색, 파란색 등)으로 변경됩니다.

성능 및 베스트 프랙티스

• Tick 사용 지양 : 내비게이션 수정은 주로 메시 생성 단계에서 처리되므로 매 프레임 로직을 돌릴 필요가 없습니다.
• 런타임 생성 : 프로젝트 설정에서 Runtime Generation을 Dynamic으로 설정하면, 게임 도중 액터가 이동하거나 생성될 때 NavMesh가 실시간으로 업데이트되어 모디파이어 효과가 즉시 반영됩니다.
• 충돌 대신 모디파이어 : 단순히 이동을 방해하는 용도라면 복잡한 물리 충돌 보나는 NavArea_Null을 사용하는 것이 AI 패스파인딩 최적화에 유리합니다.

---

1-2. 내비게이션 링크 프록시(Nav Link Proxy)

내비게이션 링크 프록시는 내비게이션 경로가 직접적으로 이어지지 않는 두 내비게이션 메시 영역을 간접적으로 연결합니다.
일반적으로 분리된 내비게이션 메시를 연결하는 다리를 생성하고, 목적지로 가는 연속된 경로를 이용할 수 없을 때 에이전트가 목적지를 향해 플랫폼에서뒤어내리거나 점프하도록 지시하는데 사용됩니다.

• 목적 : 물리적으로 떨어져 있거나 고도의 차이가 있어 NavMesh가 끊기 두 지점을 AI가 '이동 가능한 경로'로 인싣하게 만듭니다.
• 작동 방식 : 링크의 시작점(Left)과 끝점(Right)을 설정하면, AI는 두 지점 사이가 연결된 것으로 간주하여 경로를 탐색합니다.

주요 기능 및 구성요소

포인트 링크(Point Links)

• 가장 기본적인 연결 방식입니다. 시각적으로 두개의 핸들과 이를 잇는 직선/화살표로 표시됩니다.
• Left/Right Project : 내비게이션 매시 위에 정확히 핸들을 놓지 않아도, 일정 거리 내에 있으면 자동으로 가장 가까운 NavMesh에 투영(Project)되어 연결됩니다. 연결에 성공하면 뷰포트에 녹색 선이 나타납니다.
• Direction(방향성)
  • Both Way : 양방향 이동 가능
  • Left to Right / Right to Left: 일방통행(예: 높은 곳에서 아래로 떨어질 수는 있지만 다시 올라올 수는 없는 지형).

Smart Links(스마트 링크)
단순한 위치 연결을 넘어, AI가 해당 링크에 도달햇을 때 특수 동작(애니메이션)을 수행하도록 제어할 수 있는 기능입니다.

• 사용 예시: 사다리 타고 올라가기, 문 열기, 장애물 넘기, 텔레포트 등.
• Blueprint 활용: OnSmartLinkReached 이벤트를 통해 AI가 링크에 도달했을 때 특정 몽타주를 재생하거나 로직을 실행하도록 구현합니다.

주요 용도(Use Case)

• 점프 및 낙하
  • 절벽 아래로 뛰어내리는 경로를 생성할 때 사용. 방향을 일방통행으로 설정해야 다시 올라가지 못하게 제한할 수 있습니다.
• 끊어진 다리 연결
  • 시각적으로는 끊어져 있지만 AI는 건널 수 있는 투명한 다리의 역할을 수행
• 동적 통로(문/게이트)
  • 평소에는 링크를 비화성화했다가, 문이 열리는 이벤트 발생 시 링크를 활성화하여 AI가 통과하게 할 수 있습니다.

구현 및 설정

• 배치: Place Actors 패널에서 Nav Link Proxy를 레벨로 드래그합니다.
• 위치 조정: 뷰포트에 나타나는 Left, Right 핸들을 조작하여 연결하려는 두 지점의 NavMesh 위에 놓습니다.
• 연결 확인: ‘P’ 키를 눌러 NavMesh 시각화를 켭니다. 두 지점을 잇는 녹색 선과 방향 화살표가 보인다면 성공적으로 연결된 것입니다.
• 비용 설정 (Area Class Override): 링크 자체에도 Area Class를 지정할 수 있습니다. 만약 점프 경로가 일반 걷기보다 힘들다면 비용이 높은 클래스를 지정하여, AI가 꼭 필요한 상황이 아니면 점프를 피하도록 유도할 수 있습니다.

자동 생성 기능 (UE 5.5 +)

최신 버저의 Unreal Engine에는 일일이 프록시를 배치하지 않아도 자동 내비게이션 링크 생성 기능을 지원한다고 합니다.

• RecastNavMesh 액터의 디테일 패널에서 Generate Nav Links를 활성화하면, 에이전트 설정(최대 점프 높이, 낙하 거리 등)에 따라 점프 가능한 구간에 링크를 자동으로 생성해 줍니다.

성능 및 베스트 프랙티스

• 정확한 투영 : 핸들이 NavMesh와 너무 멀리 떨어져 있으면 연결이 끊깁니다. 화살표가 사라지면 위치를 다시 조정해야 합니다.
• Elimination 로직과의 결합: 높은 곳에서 떨어지는 링크를 만들 때, 바닥에 위험 구역(NavArea_Null)이 있다면 AI가 그쪽으로 이동 경로를 잡지 않으므로 주의가 필요합니다.
• 복잡도 관리: 너무 많은 링크는 경로 탐색(Pathfinding) 계산량을 늘릴 수 있으므로 꼭 필요한 지점에만 배치하는 것이 좋습니다.

---

1-3. RecastNavMesh

언리얼 엔진의 내비게이션 시스템에서 핵시점인 액터로, 레벨 내의 콜리전 지오메트리를 분석하여 AI 캐릭터가 이동할 수 있는 보행 가능 영역(NavMesh)을 생성하고 관리한다고 합니다.

주요 개념 및 역할

• 보행 가능 영역 정의 : 레벨 내의 스태틱 메시나 콜리전을 기반으로 AI가 장애물을 피하며 이동할 수 있는 폴리곤 메시를 생성합니다.
• 런타임 경로 탐색 : AI 에이전트가 목표 지점까지 가는 최단 경로를 계산할 때 기준이 되는 데이터를 제공합니다.
• 타일 기반 생성 : 내비게이션 메시는 여러 개의 타일로 분할되어 관리되며 동적 내비게이션 설정 시 특정 구역의 변환에 따라 해당 타일만 다시 생성하여 효율성을 높입니다.

핵심 설정 항목(Generaction 섹션)
RecastNavMesh 액터를 선택한 후 Details(상세) 패널에서 조정할 수 있는 주요 설정들입니다.
주의 : 이 설정들은 AI의 캡슐 컴포넌트 크기와 일치해야 정확한 이동이 가능하다고 합니다.

• Agent Raius(에이전트 반지음) : AI 캐릭터가 장애물로부터 얼마나 떨어져서 이동할 지를 결정합니다. 캐릭터의 캡슐 반지름보다 작을 경우 벽에 끼는 현상이 발생할 수 있다고 합니다.
• Agent Height (에이전트 높이) : AI가 통과할 수 있는 최소 천장 높이를 정의합니다. 이 값보다 낮은 공간은 내비게인션 메시가 생성되지 않아 AI가 진입하지 못합니다.
• Agent Max Slope (최대 경사) : AI가 오를 수 있는 지면의 최대 각도를 결정합니다.
• Agent Max Step Height (최대 계단 높이) : AI가 점프하지 않고 걸어 올라갈 수 있는 턱이나 계단의 높이를 결정합니다.

성능 및 정밀도 최적화

• Cell Size & Cell Height: 내비게이션 메시를 생성할 때 사용하는 복셀(Voxel)의 크기입니다. 값이 작을수록 정밀도가 높아져 좁은 틈새도 잘 표현하지만, 생성 및 업데이트 속도가 느려집니다. 최적의 성능을 위해 eliminate해야 할 불필요한 연산을 줄이려면 정밀도가 허용하는 선에서 최대한 큰 값을 사용하는 것이 좋다고 합니다.
• Runtime Generation : 설정을 Static으로 하면 빌드 시에만 생성하고, Dynamic으로 설정하면 게임 도중 액터가 움직일 때 실시간 내비게이션 영역을 업데이트합니다.

최적화 및 주의사항

• AI 캐릭터가 너무 많거나 맵이 거대한 경우, 타일 크기(Tile Size UU)를 조절하여 메모리 사용량과 경로 탐색 속도를 균형 있게 맞춰야 합니다.
• 복잡한 지형에서 AI가 비정상적으로 멈추거나 낙하나는 경우, Agent Max Slope와 Cell Size를 우선적으로 점검하여 내비게이션 데이터의 연속성을 eliminate해야 한다고 합니다.

---

1-4. 내비게이션 인보커 보충

Navigation Invoker(내비게이션 인보커)는 대규모 오픈 월드나 무한 맵에서 내비게이션 시스템을 효율적으로 운영하기 위한 핵심 도구입니다.
인보커는 “필요한 곳에만 실시간으로 경로를 생성”하는 역할을 합니다.

• 목적 : 우러드 전체의 NavMesh를 메모리에 올리는 대신, 에이전트(AI 또는 플레이어) 주변의 일정 영역만 동적으로 생성하여 메모리 사용량과 CPU 부하를 획적으로 줄일 수 있습니다.
• 작동 방식 : 인보커 컴포넌트가 부착된 액터를 중심으로 설정된 반경 내에서만 NavMesh 타일이 활성화(Generation)되고, 범위를 벗어나면 제거(Removal)됩니다.

주요 설정 및 파라미터

인보커 컴포넌트를 액터에 추가하면 다음과 같은 핵심 설정을 조절할 수 있습니다.

• Tile Generation Radius (생성 반경) : 에이전트를 중심으로 NavMesh를 생성할 거리입니다. AI의 감지 범위나 이동 속도를 고려하여 설정합니다. (인식 범위보다 약간 크게?)

• Tile Removal Radius(제거 반경) : 에이전트가 멀어졌을 때 생성된 NavMesh를 파기할 거리입니다.

  • 주의: ‘생성 반경’보다 크게 설정해야 에이전트가 경계선에서 움직일 때 NavMesh가 빈번하게 생성/제거를 반복하는 현상(Thrashing)을 방지할 수 있습니다.

장점 및 차별점

• 메모리 최적화 : 오픈 월드 게임에서 수 킬로미터에 달하는 NavMesh를 미리 빌드하여 저장하면 데이터 용량이 매우 커집니다. 인보커는 현재 활동 중인 에이전트 주변만 계산하므로 메모리 점유율이 낮습니다.

• 로딩 시간 단축 : 레벨을 로드할 때 거대한 NavMesh 데이터를 불러올 필요가 없어 초기 로딩 속도가 향상됩니다.

• 동적 환경 대응 : Dynamic Runtime Generation과 결합하여, 실시간으로 변하는 지형이나 장애물에도 즉각적으로 반응하는 경로를 생성합니다.

고급 프로젝트 설정

• Invokers Maximum Distance from Seed : 프로젝트 세팅에서 설정 가능합니다. 플레이어(Seed)로부터 너무 멀리 떨어진 곳에 있는 인보커(멀리 있는 AI 등)는 NavMesh 생성을 중단하게 하여 CPU 자원을 절약한다고 합니다. (멀티에서는 어떻게 동작할 지 궁급하네요.)

• Fixed Tile Pool Size : 월드 파티션(World Partition)을 사용하는 경우, 생성되는 타일의 최대 개수를 제한하여 내비게이션 시스템이 사용하는 메모리 상한선을 강제로 고정할 수 있습니다.

구현 프로세스 및 확인 방법

• 컴포넌트 추가 : AI 캐릭터나 플레이어 블루프린트에 Navigation Invoker Component를 추가합니다.
• 프로젝트 설정 : Generate Navigation Only Around Navigation Invokers 활성화. Runtime Generation을 Dynamic으로 변경.
• 내비게이션 볼륨 배치 : 인보커를 사용하더라도 전체 맵을 덮는 NavMeshBoundsVolume은 여전히 필요합니다. 이는 내비게이션이 생성될 수 있는 ‘잠재적 영역’을 정의하는 역할을 합니다.
• 시각화해서 확인 : 게임 실행 중 콘솔 명령어(` 키)로 show Navigation을 입력하거나 ‘P’ 키를 눌러 에이전트가 이동함에 따라 발밑에 NavMesh가 실시간으로 생성되고 뒤쪽이 사라지는지 확인합니다

성능 및 베스트 프랙티스

• 에이전트 수 관리 : 너무 많은 AI가 동시에 인보커를 사용하면 실시간 내비게이션 빌드 계산량이 급증하여 프레임 드랍이 발생할 수 있습니다. 멀리 있는 AI는 인보커를 비활성화하거나 생성 반경을 줄이는 최적화가 필요합니다.
• Elimination 및 데이터 관리 : 인보커를 통해 생성된 NavMesh 내에서도 이전의 Navigation Modifier가 정상 작동합니다. 즉, 동적으로 생성된 길 위에서 특정 위험 구역을 피하게 설정하는 등의 결합이 가능합니다.
• Cell Size 조정 : 생성 속도가 느리다면 RecastNavMesh 설정에서 Cell Size와 Cell Height를 높여 계산 복잡도를 낮추는 것을 추천하고 있습니다.

---

1-4. 내비게이션 시스템 사용 고려 순위 및 비교

각각의 목적과 부하의 성격이 다르므로, 프로젝트의 규모와 AI의 복잡도에 따라 우선순위를 결정해야 한다고 합니다.

대규모 레벨 기준

---

시스템	핵심 용도	성능 부하 (CPU/Mem)	우선순위 및 사용 고려 사항
Nav Invoker	대규모 맵 최적화	CPU 상(실시간 빌드) / Mem 최저	1순위 (월드 규모 기준): 오픈 월드라면 가장 먼저 고려. 에이전트가 많을수록 CPU 부하가 증가하므로 생성 반경 최적화 필수.
Nav Modifier	경로 선호도 및 속성 제어	CPU 저 / Mem 저	2순위 (디테일 기준): AI의 지능적인 움직임(길 찾기 전략)이 필요할 때 사용. Null 영역을 적절히 써서 불필요한 경로 계산을 차단.
Nav Link Proxy	단절된 메시 연결	CPU 중(링크 유효성 체크) / Mem 저	3순위 (특수 상황): 점프, 사다리, 낙하 등 일반 보행으로 불가능한 경로에만 배치. 과도한 배치는 경로 탐색 복잡도를 높임.

최적화를 위한 베스트 프랙티스

• 인보커(Invoker) 최적화 : 모든 NPC에게 인보커를 넣지 말고, 플레이어 주변이나 현재 활성화된(Active) AI 그룹에게만 컴포넌트를 부여하여 CPU 사용량을 관리해야 합니다.
• 해상도(Resolution) 활용 : Nav Modifier의 최신 기능인 Nav Mesh Resolution 설정을 활용하면 좋다고 합니다. 정교한 이동이 필요 없는 외곽 지역은 ‘Low’ 해상도 모디파이어로 덮어 NavMesh 빌드 시간을 단축할 수 있다고 합니다.
• 비용(Cost) 관리 : Nav Link Proxy에 너무 낮은 비용을 책정하면 AI가 멀리 돌아가는 대신 무조건 점프만 하려 할 수 있습니다. NavArea 클래스를 통해 적절한 비용 밸런스를 유지해야 합니다.
• 동적 생성 제한 : Dynamic 생성을 사용할 때, 움직이지 않는 정적 오브젝트에는 Can Ever Affect Navigation 옵션을 끄거나 신중히 설정하여 불필요한 Rebuild를 eliminate(제거)해야 합니다.

---

소규모 레벨 기준

---

소규모 레벨에서는 모든 NavMesh를 미리 빌드해 두는 것이 훨씬 이득이므로, 실시간 계산이 필요한 시스템의 순위가 뒤로 밀립니다.

시스템	소규모 레벨에서의 역할	우선순위 변화	이유
Nav Modifier	지형 속성 및 정교한 AI 제어	1순위	좁은 공간일수록 AI가 장애물을 정교하게 피하거나 특정 경로를 선호하게 만드는 디테일한 설정이 중요해집니다.
Nav Link Proxy	복층 구조 및 수직 이동	2순위	소규모 맵은 수직적 디자인(점프, 사다리)이 많은 경우가 많아, 끊어진 메시를 잇는 링크의 중요도가 높아집니다.
Nav Invoker	실시간 생성 (거의 사용 안 함)	3순위	맵 전체를 메모리에 올려도 무리가 없으므로, CPU를 소모하며 실시간으로 NavMesh를 생성할 이유가 사라집니다.

소규모 레벨 최적화 및 사용 시나리오

• Static NavMesh + Dynamic Obstacles (권장 전략) :
  인보커를 사용하는 대신, 맵 전체에 NavMesh를 미리 빌드(Static)합니다.
  대신 움직이는 문이나 상자 같은 액터에는 Nav Modifier를 사용하거나, 해당 액터의 충돌 설정에서 Can Ever Affect Navigation을 켜서 해당 부분만 실시간 업데이트되도록 합니다. 이를 통해 불필요한 전체 재빌드 부하를 eliminate(제거)합니다.

• 정교한 구역 분리 (Modifier 중심) : 맵이 좁으므로 AI가 끼이는 현상을 방지해야 합니다. Nav Modifier를 사용해 벽 근처나 좁은 틈새에 NavArea_Obstacle을 설정하여 AI가 벽에 비비지 않고 중앙으로 걷도록 유도합니다.

• 수직적 경로 최적화 (Link Proxy 중심) : 소규모 레벨의 재미 요소인 ‘지름길(점프 구간)‘을 Nav Link Proxy로 연결합니다. 맵 전체가 이미 빌드되어 있으므로 링크의 연결 안정성이 매우 높습니다.

소규모 레벨을 위한 제언

소규모 레벨에서는 Navigation Invoker를 사용하지 않는 것이 오히려 최적화입니다. 인보커는 NavMesh를 ‘생성’하는 데 CPU를 쓰지만, Static NavMesh는 이미 생성된 데이터를 ‘조회’만 하기 때문입니다.

• 추천 설정 : 맵 전체를 NavMeshBoundsVolume으로 감싸고, 프로젝트 세팅에서 Generate Navigation Only Around Navigation Invokers를 해제합니다.
• Modifier 활용 : AI가 특정 가구 위로 올라가지 못하게 하거나, 문이 닫혔을 때 해당 구역을 Null로 바꾸는 식으로 Nav Modifier를 적극 활용하여 지능적인 동선을 설계하십시오.

소규모 레벨에서는 시스템의 복잡도를 줄여 잠재적인 버그를 eliminate(제거)하고, 대신 풍부한 Nav Modifier와 Nav Link Proxy를 통해 AI의 행동 품질을 높이는 데 집중하는 것이 정석이라 합니다.

사용 고려 순위 비교표 (소규모 vs 대규모)

비교 항목	대규모 월드 (Open World)	소규모 레벨 (Arena/Indoor)
최우선 과제	메모리 점유율 및 로딩 시간 감소	경로의 정확도 및 AI의 반응성
핵심 시스템	Navigation Invoker	Navigation Modifier
Generation 방식	Dynamic (인보커 주변 실시간)	Static 또는 Dynamic Obstacles
CPU 관리	실시간 타일 생성 부하 관리	복잡한 경로 탐색(A*) 계산 관리
오류 관리	NavMesh 미생성 구역 진입 방지	좁은 길 끼임 및 비효율적 경로 eliminate

---

멀티 플레이에서의 Invokers Maximum Distance from Seed

해당 옵션은 옵션은 멀티플레이어 환경에서 서버의 부하를 관리하기 위한 매우 중요한 최적화 설정이라고 합니다.

작동 원리

멀티플레이어 환경에서 ‘Seed(시드)’는 일반적으로 서버에 접속한 각 플레이어의 위치(PlayerController의 위치 또는 ViewTarget)를 의미합니다.

• 서버의 판단 : 서버는 접속한 모든 플레이어의 위치를 ‘Seed’ 목록으로 관리합니다.
• 거리 체크 : 서버는 월드에 존재하는 모든 Navigation Invoker를 전수 조사하여, 해당 인보커가 어떤 플레이어(Seed)로부터라도 설정된 Maximum Distance 내에 있는지 확인합니다.
• 활성화 조건 : 인보커가 최소 한 명의 플레이어와 거리 내에 있다면 → 해당 인보커 주변의 NavMesh를 서버에서 생성/유지합니다.
  인보커가 모든 플레이어로부터 거리 밖에 있다면 → 해당 인보커는 휴면 상태가 되며, 서버는 그 주변의 NavMesh를 생성하지 않거나 제거하여 자원을 절약합니다.

멀티플레이어에서의 주요 특징

• 서버 중심 연산 : NavMesh는 기본적으로 서버(Authority)에서 생성되고 관리됩니다. AI의 이동 결정은 서버에서 이루어져야 하기 때문입니다. 따라서 이 거리 체크 로직도 서버 CPU에서 실행됩니다.
• 플레이어별 독립 체크 : 플레이어 A와 B가 서로 멀리 떨어져 있을 때, 플레이어 A 근처에 있는 AI 인보커는 A라는 Seed 덕분에 NavMesh를 생성합니다. 플레이어 B 근처의 인보커도 마찬가지입니다. 즉, Seed가 많아질수록 서버가 관리해야 할 NavMesh 영역도 늘어납니다.
• 관찰자 중심의 최적화 : 이 설정의 핵심은 “플레이어가 보지 않거나 상호작용할 가능성이 없는 먼 곳의 AI를 위해 서버가 NavMesh를 계산할 필요가 없다”는 점입니다. 이를 통해 불필요한 서버 자원 낭비를 eliminate(제거)합니다.

멀티플레이어 설정 시 주의사항

• AI 가청/가시 거리 고려 : Maximum Distance from Seed 값은 AI가 플레이어를 인지하고 추격하기 시작하는 거리보다 커야 합니다. 만약 이 거리가 너무 짧으면, 플레이어가 AI를 발견하기도 전에 AI 발밑의 NavMesh가 사라져 AI가 제자리에 멈추는 현상이 발생할 수 있습니다.
• 전용 서버(Dedicated Server) 부하 : 플레이어 수가 많아지면 Seed의 수도 늘어납니다. 만약 플레이어들이 맵 전체에 흩어져 있다면 결과적으로 맵 전체의 NavMesh가 생성될 수 있으므로, 적절한 거리 값을 찾아 서버의 메모리 점유율을 관리해야 합니다.
• 네트워크 복제(Replication)와 무관 : NavMesh 데이터 자체가 클라이언트로 복제되는 것은 아닙니다. 클라이언트는 시각적인 확인을 위해 자체적으로 NavMesh를 생성할 수 있지만, 실제 AI 이동 로직은 서버의 NavMesh 데이터를 기반으로 동작합니다.

권장 설정 시나리오

• 협동(Co-op) 게임 : 보통 플레이어들이 뭉쳐 다니므로 Maximum Distance from Seed를 비교적 타이트하게 잡아도 서버 부하가 낮습니다.

• 배틀로얄/오픈월드 : 플레이어가 광범위하게 퍼지므로, Seed 거리를 너무 크게 잡으면 서버 메모리가 부족해질 수 있습니다. 이 경우 NavMesh 타일의 크기(Tile Size)를 키우고 해상도를 낮추어 전체적인 계산량을 eliminate(제거)하는 전략을 병행해야 합니다.

  이 옵션은 “플레이어가 있는 곳 근처의 인보커만 서버가 신경 쓰겠다”는 필터링 메커니즘으로 작동하여 멀티플레이어 서버 최적화에 기여합니다.

---

---

Unreal Engine 고급 기술 활용

언리얼 엔진의 RVO 시스템

RVO란?

RVO(Reciprocal Velocity Obstacles)란 움직이는 객체들이 서로의 속도와 방향을 고려하여 충돌을 피하는 방법입니다. 쉽게 말해 동적 액터들이 서로를ㄹ 장애물로 인식하고 충돌을 피하는 알고리즘입니다.

경로 재계산 없이 속도와 방향만 조절하여 실시간 회피가 가능하므로 다수의 액터가 있을 때 효율적, 자연스러운 움직임을 제공하는 장점이 있습니다.

핵심 코드

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

GetCharacterMovement()->bUseRVOAvoidance = true;
RVO 회피 시스템의 활성화 여부를 결정하는 가장 기본적인 설정입니다.

• 기능 : RVO 충돌 회피 알고리즘 On/Off
• 값의 의미 : true로 설정하면 자동 회피 기능이 작동하고, false이면 회피 기능이 작동하지 않습니다.
• 적합한 상황 : 여러 AI 캐릭터가 서로 상호작용하며 이동해야 하는 상황에서 필수적입니다.

GetCharacterMovement()->AvoidanceConsiderationRadius = 200.0f;
AI가 다른 오브젝트를 감지하고 회피를 시작하는 거리를 결정합니다.

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

GetCharacterMovement()->AvoidanceWeight = 0.5f;
해당 클래스를 상속받은 캐릭터의 회피 우선순위를 결정합니다.

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

시나리오 두 AI 집단이 있고 목표지점은 반대편 집단의 너머에 존재합니다.
길목은 Modifier를 사용해서 좁게 설정했습니다.

=== RVO 활성 화면

=== RVO 비활성 화면

Nav Link 자동 생성하기
5.5 이상 부터는 Nav Link를 자동생성해 주는 기능이 생겼다고 합니다.

=== Nav Link 자동 생성 체크

여기서 Generated라 써져 있는 것을 클릭하면 됩니다.

=== 생성 전

=== 생성 후

맵에 Nav Link(녹색 곡선)이 추가된 것을 확인할 수 있습니다.
이 상태로는 그냥 NavLink가 추가되었을 뿐 AI가 점프를 하는 것은 불가능합니다.
추가로 작업이 필요합니다.

1. Generated Nav Link Proxy를 상속한 BP를 생성합니다.
2. Receive Smart Link Reached 이벤트로 캐릭터를 쏘아 보내는 로직을 작성합니다.
   === BP 이미지

• 자동 생성된 Link에 도달할 경우 수행되는 이벤트로 보입니다.

3. 작업이 완료된 BP를 RecastNavMesh에 집어넣습니다.

• 디테일에서 Generation -> Nav Mesh Jump Down Config -> Link Proxy Class에 집어넣습니다.
• 그러면 모든 Link Proxy에 적용된다고 합니다.

=== Generation -> Nav Mesh Jump Down Config

=== 내부 설정

=== 클래스 집어넣기

=== 최종 설정 이미지

=== 테스트 화면

---

QA는 진행하지 못했습니다. 목표하던 학습량에 도달하지 못해 아쉽습니다. 내일은 QA를 우선적으로 진행하고 그 뒤 Unreal 강의 2챕터를 진행하고자 합니다.