지난 포스팅에서는 NavMesh기술로 구현할 수 없는 3D 공간상에서의 네비게이션을 주제로 선정하는 과정을 다뤘습니다. 이번 포스팅에서는 그렇다면 어떻게 3D 공간상의 네비게이션을 구현할지에 대한 조사결과를 작성하도록 하겠습니다.
구글링
먼저 구글링을 통해서 어떻게 3D 길찾기를 구현하는지 검색해봤습니다.
3d pathfinding 이라는 단어를 키워드로 검색한 결과입니다. 여러 글들을 찾아 읽어본 결과 Voxel단위로 공간을 분할해서 A* 알고리즘을 적용하는 방법이 있었습니다.
Voxel?
Voxel은 Volume + Pixel의 합성어로 부피를 가진 픽셀이란 뜻을 가집니다. 3D 공간을 같은 크기의 정육면체로 나눈 단위라고 할 수 있습니다. 이러한 복셀을 그래픽렌더링에 채용한 유명한 게임으로는 마인크래프트 가 있습니다
Voxel 3D 길찾기 원리
공간을 Voxel단위로 나누게 된다면 어떻게 3D 길찾기를 계산할 수 있는것인지에 대해 적어보도록 하겠습니다.
2D격자 구조에서 최단거리를 빠르게 찾을 수 있는 알고리즘으로는 A*알고리즘이 있습니다.
A* 알고리즘은 (현재Node 까지의 거리)(현재상태) + (목적Node 까지의 거리)(휴리스틱)의 값의 합이 최소가 되는 노드를 취해가면서 목적지까지의 최단경로를 빠른 시간에 검색하는 알고리즘입니다. 이러한 A*알고리즘은 Start지점부터 End지점까지의 탐색 공간이 격자화되어 그래프를 구성하게 되면 적용이 가능한데, Voxel로 공간을 분할하게 되면 2D와 마찬가지로 3D공간상에서도 A*알고리즘을 적용할 수 있습니다.
특정 Voxel과 인접한 8개의 이웃복셀들에 대해서 A*알고리즘에 필요한 상태값과 휴리스틱값을 계산하면서 최단경로를 검색하게 됩니다.
언리얼 플러그인
위와 같은 개념을 확보하고 바로 개발에 들어가기 전에 이미 누군가가 개발한 언리얼 플러그인이 존재하지 않을까? 라는 의문이 들어서 추가로 검색을 진행했습니다. 그 결과 다음 플러그인을 발견하게 되었습니다.
https://www.unrealengine.com/marketplace/en-US/product/customizable-pathfinding
이번 포스팅에서는 Voxel로 3D 네비게이션이 가능함에 관한 이야기와 언리얼에 존재하는 무료 플러그인을 찾아보는 과정에 관한 이야기를 다뤘습니다. 다음 포스팅에서는 찾은 플러그인을 실제로 써보고 어떻게 구현에 활용할 것인지에 대한 고민과정을 적어보도록 하겠습니다
