[DirectX 11 Eternal Return 모작] 12. NavMesh

전체 코드 : https://github.com/HyangRim/DirectX11-Engine-Client

---

 

NavMesh 시스템 구현

1. NavMesh와 NavMeshAgent란?

NavMesh ( Navigation Mesh ) 란?

NavMesh는 게임 내 캐릭터들이 이동할 수 있는 영역을 삼각형 메시로 표현한 데이터 구조다. 각 삼각형은 이동 가능한 평면을 나타내며, 인접한 삼각형들을 연결하여 전체 이동 가능 영역을 구성한다.

 

NavMeshAgent란?

NavMeshAgent는 NavMesh 위에서 자동으로 경로를 찾아 이동하는 컴포넌트다. 목적지를 설정하면 A* 알고리즘을 통해 최적 경로를 계산하여 이동한다.

 

 

2. NavMesh 시스템 구조

2.1 삼각형 기반 NavMesh 구조

struct NavMeshTriangle
{
    Vec3 vertices[3];
    Vec3 center;
    Vec3 normal;
    vector<int> neighbors;
    int index = -1;
    AABB bounds;
};

struct PathNode
{
    int triangleIndex = -1;
    Vec3 position;
    float gCost = 0.0f;
    float hCost = 0.0f;
    float fCost = 0.0f;
    int parent = -1;
    
    bool operator<(const PathNode& other) const {
        return fCost > other.fCost;
    }
};

 

특징

• 삼각형 기반 표현 : 복잡한 지형도 모델링
• 인접성 그래프 : 각 삼각형이 연결된 이웃 삼각형 정보 보유
• 법선 벡터 저장 : 경사면 판단 및 투영 계산 최적화

 

NavMesh는 삼각형 기반의 네비게이션 메쉬로 구성된다. 각 삼각형은 인접한 삼각형들과의 연결 정보를 가지고 있어 경로 탐색이 가능하다.

 

2.2 메시 파일 기반 NavMesh 로딩

void NavMesh::LoadNavMeshData()
{
    // 기존 3D 모델 파일에서 NavMesh 데이터 추출
    auto modelRenderer = gameObject->GetModelRenderer();
    m_navMeshModel = modelRenderer->GetModel();
    
    const auto& meshes = m_navMeshModel->GetMeshes();
    auto transform = gameObject->GetTransform();
    Matrix worldMatrix = transform->GetWorldMatrix();

    // 각 메시에서 삼각형 데이터 추출 및 월드 좌표 변환
    for (size_t i = 0; i + 2 < indices.size(); i += 3)
    {
        NavMeshTriangle triangle;
        // 월드 좌표로 변환하여 삼각형 생성
        for (int j = 0; j < 3; j++)
        {
            Vec4 worldPos = XMVector4Transform(localPos, worldMatrix);
            triangle.vertices[j] = Vec3(worldPos.x, worldPos.y, worldPos.z);
        }
        // 삼각형 유효성 검사 및 법선 벡터 계산
        triangle.normal = edge1.Cross(edge2).Normalize();
        triangle.center = (triangle.vertices[0] + triangle.vertices[1] + triangle.vertices[2]) / 3.0f;
    }
}

 

특징

• 별도 NavMesh 제작은 하지 않고 기존 저장된 파일을 불러와서 사용
• 월드 변환 : Transform Matrix를 통한 좌표 변환

 

2. 성능 최적화

2.1 공간 분할 최적화 (Spatial Grid)

struct SpatialGrid {
    float cellsize = 25.f;
    unordered_map<uint64, vector<int>> grid;
    
    uint64 GetKey(const Vec3& pos) const {
        int x = static_cast<int>(pos.x / cellsize);
        int z = static_cast<int>(pos.z / cellsize);
        return (static_cast<uint64>(x) << 32) | static_cast<uint64>(z);
    }
    
    void AddTriangle(int idx, const NavMeshTriangle& tri) {
        // 삼각형이 겹치는 모든 그리드 셀에 인덱스 추가
        for (int x = minX; x <= maxX; x++) {
            for (int z = minZ; z <= maxZ; z++) {
                uint64_t key = (static_cast<uint64_t>(x) << 32) | static_cast<uint64_t>(z);
                grid[key].emplace_back(idx);
            }
        }
    }
};

 

최적화 효과

• O(n) -> O(1) 검색 : 전체 삼각형 순회 대신 해당 그리드 셀만 검색
• 비트 쉬프트 해상 : 빠른 2D좌표 -> 1D 키 변환
• 메모리 효율성 : 필요한 셀에만 데이터 저장

 

2.2 캐싱 기반 삼각형 탐색

int NavMesh::FindTriangleContaining(const Vec3& point)
{
    // 1단계: 이전 검색 결과 캐시 활용
    if (m_lastFoundTriangle != -1 && IsPointInTriangle(point, m_triangles[m_lastFoundTriangle])) {
        return m_lastFoundTriangle;
    }
    
    // 2단계: 인접 삼각형 우선 탐색 (지역성 원리)
    if (m_lastFoundTriangle != -1) {
        for (int neighbor : m_triangles[m_lastFoundTriangle].neighbors) {
            if (IsPointInTriangle(point, m_triangles[neighbor])) {
                m_lastFoundTriangle = neighbor;
                return neighbor;
            }
        }
    }
    
    // 3단계: 공간 그리드 기반 탐색
    uint64 key = m_spatialGrid.GetKey(point);
    auto it = m_spatialGrid.grid.find(key);
    // ...
}

 

최적화 효과

• 3단계 탐색 전략 : 캐시 -> 인접 -> 그리드 순서로 최적화
• 지역성 활용 : 연속된 위치 검색에서 높은 적중률
• 조기 종료 : 각 단계에서 찾으면 즉시 반환

 

3. A* 경로 탐색 알고리즘

3.1 삼각형 기반 A* 구현

bool NavMesh::FindTrianglePath(int startTriangle, int endTriangle, vector<int>& outPath)
{
    priority_queue<PathNode> openList;
    vector<bool> closedList(m_triangles.size(), false);
    vector<PathNode> allNodes(m_triangles.size());
    
    // A* 알고리즘 핵심: F = G + H
    PathNode startNode;
    startNode.gCost = 0;  // 시작점부터의 실제 비용
    startNode.hCost = GetDistance(m_triangles[startTriangle].center, 
                                  m_triangles[endTriangle].center);  // 휴리스틱
    startNode.fCost = startNode.gCost + startNode.hCost;  // 총 예상 비용
    
    while (!openList.empty())
    {
        PathNode currentNode = openList.top();
        openList.pop();
        
        // 목적지 도달 체크
        if (currentNode.triangleIndex == endTriangle) {
            ReconstructPath(allNodes, endTriangle, outPath);
            return true;
        }
        
        // 인접 삼각형들 탐색
        for (int neighborIndex : m_triangles[currentNode.triangleIndex].neighbors)
        {
            float tentativeGCost = currentNode.gCost + 
                GetDistance(m_triangles[currentNode.triangleIndex].center, 
                           m_triangles[neighborIndex].center);
                           
            // 더 나은 경로 발견시 업데이트
            if (tentativeGCost < allNodes[neighborIndex].gCost) {
                // 노드 정보 갱신 및 오픈리스트 추가
            }
        }
    }
}

 

A* 알고리즘 최적화

• 휴리스틱 함수 : 유클리드 거리 기반 예상 비용 계산
• 우선순위 큐 : F값이 낮은 노드 우선 탐색
• 경로 복원 : 부모 노드 추적으로 최종 경로 구성

 

3.2 경로 스무딩 최적화

void NavMesh::SmoothPath(const vector<Vec3>& originalPath, vector<Vec3>& outPath)
{
    outPath.reserve(originalPath.size());
    outPath.push_back(originalPath[0]);
    
    size_t cur = 0;
    while (cur + 1 < originalPath.size())
    {
        int bestNext = cur + 1;
        bool foundValidPath = false;
        
        // 시야선(Line of Sight) 기반 최적화
        for (size_t i = cur + 1; i < originalPath.size(); ++i)
        {
            if (HasLineOfSight(outPath.back(), originalPath[i])) {
                bestNext = static_cast<int>(i);
                foundValidPath = true;
            }
        }
        
        // NavMesh 경계 검사
        if (!foundValidPath && !IsLineOnNavMesh(outPath.back(), originalPath[bestNext]))
        {
            Vec3 safe = GetNearestPointOnNavMesh(originalPath[bestNext]);
            outPath.push_back(safe);
        }
        else {
            outPath.push_back(originalPath[bestNext]);
        }
        cur = bestNext;
    }
}

 

스무딩 기법

• 시야선 검사 : 직선 경로 가능성 판단
• 웨이포인트 생략 : 불필요한 중간점 제거
• 안전성 보장 : NavMesh 경계 이탈 방지

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

 

완벽하게 이동이 구현이 되지는 않았다. 일부 경로에서 벽에 가로막혀 못가는 현상이 종종 있다.

 

 

 

4. NavMeshAgent 이동 시스템

4.1 Agent 컴포넌트

class NavMeshAgent : public Component
{
private:
    shared_ptr<NavMesh> m_navMesh;
    vector<Vec3> m_path;
    uint32 m_currentPathIndex = 0;
    Vec3 m_destination;
    NavMeshAgentState m_state = NavMeshAgentState::Idle;
    
    float m_speed = 5.0f;
    float m_stoppingDistance = 0.1f;

public:
    void SetDestination(const Vec3& destination);
    void UpdateMovement();
    bool HasReachedDestination() const { return m_state == NavMeshAgentState::Arrived; }
};

 

4.2 부드러운 이동 구현

void NavMeshAgent::UpdateMovement()
{
    if (m_path.empty() || m_currentPathIndex >= m_path.size())
    {
        m_state = NavMeshAgentState::Arrived;
        return;
    }

    auto transform = GetTransform();
    if (!transform) return;

    Vec3 currentPos = transform->GetPosition();
    Vec3 targetPos = m_path[m_currentPathIndex];
    float distance = Vec3::Distance(currentPos, targetPos);

    // 현재 웨이포인트에 도달했으면 다음으로
    if (distance <= m_stoppingDistance)
    {
        m_currentPathIndex++;
        if (m_currentPathIndex >= m_path.size())
        {
            m_state = NavMeshAgentState::Arrived;
            return;
        }
        targetPos = m_path[m_currentPathIndex];
    }

    // 이동 처리
    Vec3 direction = targetPos - currentPos;
    direction.y = 0; // Y축 고정

    if (direction.Length() > 0.01f)
    {
        direction.Normalize();

        // 회전 계산 및 적용
        float targetYaw = atan2(direction.x, direction.z) + 3.141592f;
        Vec3 currentRotation = transform->GetLocalRotation();
        Vec3 newRotation = Vec3(currentRotation.x, targetYaw * 180.0f / 3.14159f, currentRotation.z);
        transform->SetLocalRotation(newRotation);

        // 위치 업데이트
        Vec3 newPos = currentPos + direction * m_speed * DT * 2.5f;
        if (m_navMesh)
        {
            newPos = m_navMesh->GetNearestPointOnNavMesh(newPos);
        }
        transform->SetPosition(newPos);
    }
}

 

 

5. State Machine과의 통합

5.1 Monster AI 에서의 활용

void MonsterStateMachine::ProcessAI()
{
    switch (currentState)
    {
    case MonsterStateType::Trace:
        if (hasValidTarget && distanceToTarget <= m_attackRange)
        {
            // 공격 사거리 진입시 NavMeshAgent 정지
            RequestStateChange(MonsterStateType::Attack);
        }
        break;
        
    case MonsterStateType::Attack:
        if (distanceToTarget > m_attackRange)
        {
            // 타겟이 멀어지면 다시 추적
            RequestStateChange(MonsterStateType::Trace);
        }
        break;
    }
}

void NavMeshAgent::SetDestination(const Vec3& destination)
{
    Vec3 startPos = transform->GetPosition();
    Vec3 targetPos = m_navMesh->GetNearestPointOnNavMesh(destination);
    
    // A* 경로 계산
    m_navMesh->FindPath(startPos, targetPos, m_path);
    m_destination = targetPos;
    m_state = NavMeshAgentState::Moving;
}

 

 

5.2 Player입력 처리에서의 활용

void PlayerStateMachine::HandleMovementInput()
{
    if (m_navMeshAgent)
    {
        POINT mousePos = INPUT->GetMousePos();
        Ray ray = CreateRayFromMouse(mousePos, cameraComp);
        
        // NavMesh와의 Ray 교차 검사
        for (auto& obj : CURSCENE->GetObjects())
        {
            auto navMesh = obj->GetFixedComponent<NavMesh>(ComponentType::NavMesh);
            if (navMesh)
            {
                Vec3 hitPoint;
                if (navMesh->RaycastNavMesh(ray, hitPoint))
                {
                    // 유효한 목적지 설정
                    GetGameObject()->GetNavMeshAgent()->SetDestination(hitPoint);
                    RequestStateChange(PlayerStateType::Run);
                    break;
                }
            }
        }
    }
}

 

 

 

 

6. 추격 및 공격 패턴

6.1 알파 몬스터 추격 시스템

class AlphaTrace : public MonsterBehaviour
{
private:
    float m_traceSpeed = 2.0f;
    float m_attackRange = 3.f;
    float m_pathUpdateInterval = 0.5f;
    float m_updateTimer = 0.0f;

public:
    void Update() override
    {
        if (!m_target || !m_owner || !m_navAgent)
            return;

        Vec3 otherObjPos = m_target->GetTransform()->GetPosition();
        Vec3 wolfPos = m_owner->GetTransform()->GetPosition();

        CalcDir(otherObjPos, wolfPos);

        m_updateTimer += DT;
        if (m_updateTimer >= m_pathUpdateInterval)
        {
            m_navAgent->SetDestination(m_target->GetTransform()->GetPosition());
            m_navAgent->SetSpeed(m_traceSpeed);
            m_updateTimer = 0.0f;
        }
    }

    void CalcDir(Vec3 otherPos, Vec3 wolfPos)
    {
        Vec3 dir = otherPos - wolfPos;
        dir.Normalize();

        // 회전 계산 및 적용
        float targetYaw = atan2(dir.x, dir.z) + 3.141592f;
        Vec3 currentRotation = m_owner->GetTransform()->GetLocalRotation();
        Vec3 newRotation = Vec3(currentRotation.x, (targetYaw * 180.0f / 3.14159f), currentRotation.z);

        m_owner->GetTransform()->SetLocalRotation(newRotation);
    }
};

 

6.2 공격 패턴 구현

class AlphaBaseAttack : public MonsterBehaviour
{
private:
    bool m_isAttacking = false;
    bool m_isAttackComplete = false;
    float m_attackTimer = 0.f;
    float m_attackDuration = (36.f / 25.f);
    float m_attackRange = 1.2f;
    float m_skillCoolTime = 0.f;

public:
    void Update() override
    {
        if (!m_isAttacking || !m_target || !m_owner)
            return;

        Vec3 otherObjPos = m_target->GetTransform()->GetPosition();
        Vec3 wolfPos = m_owner->GetTransform()->GetPosition();

        CalcDir(otherObjPos, wolfPos);

        // 공격 타이머 갱신
        m_attackTimer += DT;
        m_skillCoolTime -= DT;
        float distance = Vec3::Distance(wolfPos, otherObjPos);

        if (!m_isAttackComplete && m_attackTimer >= m_attackDuration)
        {
            m_attackTimer = 0.f;

            // 스킬 쿨다운 체크
            if (m_skillCoolTime <= 0)
            {
                static_pointer_cast<Alpha>(m_owner)->PlaySkill(m_target);
                m_skillCoolTime = 12.5f;
            }

            // 플레이어에게 데미지 적용
            static_pointer_cast<Player>(m_target)->Damaged(
                static_pointer_cast<Monster>(m_owner), 
                static_pointer_cast<Monster>(m_owner)->GetMonsterStatus().adPower
            );
        }
    }
};

 

 

 

 

7. 성능 최적화 기법

7.1 계층적 경로 탐색

void NavMesh::ConvertTrianglePathToWorldPath(const vector<int>& trianglePath, 
                                           const Vec3& start, const Vec3& end, 
                                           vector<Vec3>& outPath)
{
    outPath.clear();
    if (trianglePath.empty()) return;

    // 예상 크기로 메모리 미리 할당
    outPath.reserve(trianglePath.size() + 1);

    outPath.push_back(start);

    for (size_t i = 1; i < trianglePath.size() - 1; i++)
    {
        outPath.push_back(m_triangles[trianglePath[i]].center);
    }

    outPath.push_back(end);
}

 

 

결론

1. 삼각형 기반 정밀 내비게이션
   1. 복잡한 3D 지형의 정확한 표현
   2. 인접성 그래프를 통한 효율적인 경로 탐색
   3. 법선 벡터 기반 지형 특성 파악
2. 다단계 성능 최적화
   1. 공간 분할 : O(n) -> O(1) 삼각형 검색 최적화
   2. 캐싱 전략 : 지역성 기반 빠른 삼각형 탐색
   3. 메모리 최적화 : 참조 기반 매개 변수로 불필요한 복사 제거
3. 고급 A* 구현
   1. 삼각형 중심점 기반 노드 그래프
   2. 유클리드 거리 휴리스틱으로 최적 경로 보장
   3. 우선순퀴 큐 기반 효율적인 탐색
4. 지능형 경로 스무딩
   1. 시아선 검사로 불필요한 웨이포인트 제거
   2. NavMesh 경계 준수로 안전성 보장
   3. 적응형 샘플링으로 성능과 정확도 균형
5. 상태 기계 통합
   1. 이벤트 기반 상태 전환으로 반응성 향상
   2. AI와 플레이어 입력 모두 지원