쿼드트리 옥트리가 활용되는 예시에 대하여 더 여쭤보고싶습니다.

Question

3D던전 로그라이크 게임을 개발중인 초보 개발자입니다. PCG알고리즘에 부족한 점이 있는 것 같아 수강 하였습니다. 활용된 예시로는 2D플랫포머, 탄막게임에서의 최적화 부분과 3D게임에서 LOD로 부분 렌더링하는것 까지는 이해하였는데 활용된 다른 예시들이 궁금합니다.

이득우 · Answer

공간 분할 알고리즘은 대상(범, 범위)에 따라, 자료 구조에 따라 다양한 구현 방법이 존재합니다. 질문 주신 것처럼 이를 사용하는 분야가 딱 정해져있다고 보긴 어렵습니다. 사실 이 알고리즘은 게임 뿐만 아니라 다른 곳에서도 사용되기 때문이죠. 강의에서 설명하는 공간 분할 알고리즘은 다양한 구현 방법 중 하나의 예시일 뿐입니다. 강의에서 설명하는 쿼드트리나 옥트리는 과거 게임 엔진을 직접 제작할 때 씬을 분석하고 처리하는데 사용되어 왔습니다. 지금은 많은 사람들이 상용엔진 기반으로 게임을 제작하기에 전통적인 활용방식을 사용할 일은 없다고 봐야겠지요. 기본적인 기능은 이미 엔진이 다 알아서 처리해주고 있기 때문이죠. 그래서 게임 콘텐츠를 만들 때 이 알고리즘을 꼭 쓴다고 이야기하기는 애매한 부분이 있습니다. 다만 게임 기획에 따라 구현할 때 공간분할이 필요한 경우가 종종 발생합니다. O(N)으로 해결이 안될 것 같은 문제를 O(Log)로 해결할 일이 발생할 때 예제를 응용해 해결해보면 좋을 것 같습니다.