언리얼에 있는 시스템 분석해보기 시리즈 네비 매쉬(NaviMesh) - 1

언리얼 네비매쉬를 알아보기 전 매핑 방법 등을 간단하게 정리해봤습니다.

1. 언리얼 네비 매쉬 ( NaviMesh ) 한민규

2. 목차 네비 메쉬란 ? 매핑 과정

3. 참고 도서 스퀘어 에닉스의 게임 AI

4. 앞 서 …… 캐릭터에는 Player Character, Non-Player Character Player Character 는 플레이어가 행동을 선택함 ( 다른 NPC 가 보이면 상호작용 , 특정 오브젝트를 위해 길을 선택해 이동 , 공격이 오면 피함 ) 즉 Player Character 는 언제 , 어디서 , 무엇을 , 어떻게 할지 플레이어의 결정에 의해 조작 . NPC 는 모든 결정을 컴퓨터의 로직에 의해 결정 . NPC 의 행동은 PC 와 비슷하다 . 의사결정을 위한 요소들을 선택 .

5. 캐릭터의 움직임 폴리곤 -> 메쉬 + 텍스쳐 + 스켈레톤 + 애니메이션 모델링 , 텍스쳐링 , 애니메이션의 3 단계 PC 조작 -> 캐릭터의 움직임 ( 실제 이동 , 애니메이션 ) NPC ? -> 캐릭터의 움직임 ?

6. AI 엔지니어 데이터를 로직에 전달 . 특정한 행동 및 새로운 데이터 생성 . 캐릭터에 지능을 부여 .

7. 주변의 다양한 상황 , 정보들을 입력으로 받아 처리 . 로직으로 처리한 후 적절한 행동을 출력 . 지적인 인상 : 플레이어가 주는 데이터로 반응하는 NPC 일 경우 지적인 캐릭터로 보일 수 있다 .

8. NPC 가 PC 처럼 행동하기 위해서는 플레이어처럼 다양한 행동에 대한 데이터와 로직이 필요 .

9. 네비 매쉬란 ? NPC 가 물리적으로 이동할 수 있는지 , 없는지 확인 할 방법이 필요 . 환경 인식 – 어떤 것이 장애물인지 ? 매핑 – 장애물을 제외한 지역은 지나갈 수 있음을 표시

10. 매핑에 필요한 과정 복셀화 연결 삼각형 분할 침식

11. 복셀화 복셀 (Voxel)? Volume Pixel 의 줄임말 3 차원의 부피의 최소 단위 왜 복셀인가 ? 모든 폴리곤을 고려하여 매핑을 만들 순 없음 환경을 좀 더 단순화 복셀로 폴리곤들을 단순화 하여 표현 및 계산

12. 볼륨 월드의 어느 부분을 복셀화 할껀지 결정 . 볼륨의 한 모서리 부분부터 일정한 크기로 복셀을 채워간다 . 복셀과 폴리곤들을 비교 복셀 안에 폴리곤이 있으면 마크

13. 복셀의 크기는 작으면 작을수록 정확도↑ 하지만 클수록 계산량 ↓ ½ 작은 복셀로 만들면 계산량은 8 배 네비를 사용할 대상의 반경으로 하는 편이 좋음

14. 큰 복셀 작은 복셀

15. 높이 고려

16. 볼륨안에 안보이는 복셀 복셀을 그대로 사용하여 NPC 에 적용하기엔 아직도 많음 이동은 X, Y 평면에서 거의 이루어지기 때문에 복셀이 전부 필요하진 않음

17. 연결 경사면 인접한 4 개 면의 높이가 설정한 값보다 작을 경우 연결되어 있다고 설정

18. 삼각형 분할 이동 가능한 복셀들을 사용해 메쉬를 생성 . 이 과정의 결과물이 네비 매쉬 “ 델로네 삼각형 분할 ”

19. 과정 세 점을 골라 점 모두를 지나는 원을 그림 . 그린 원 내부에 다른 점이 있으면 그 점은 폐기 . 이 남은 원의 점들로 삼각형을 그림 .

20. X 폐기 행렬식 > 0 : 점 D 가 ABC 의 외접원 안에 있습니다 . ( 바우어 - 왓슨 알고리즘에서 ' 불법 ' 삼각형 ) 행렬식 < 0 : 점 D 가 ABC 의 외접원 밖에 있습니다 . 행렬식 = 0 : 네 점이 모두 하나의 원 위에 있습니다 . ( 특수 처리 필요 )

21. 복셀로 만들어도 고려되야 할 점 아무리 복셀이라 할지라도 너무 많은 삼각형을 생성할 수 있다 . AI 에게 관심있는 삼각형은 NPC 가 걸어 다닐 표면 사용할 점의 수는 줄이고 , 최대한 멀리있는 점을 사용 . 모서리를 사용

22. X O

23. 침식 NPC 가 사용하는 데이터이기 때문에 NPC 의 개별 정보도 적용 . NPC 의 크기 ( 캡슐 반경 ) 네비 매쉬를 모서리에서 조금 떨어져서 처리 .

24. 언리얼 Recast Detour Navigation. https://github.com/recastnavigation/recastnavigation 현재 사용 엔진 대부분 사용 .

25. 끝