[게임 프로그래밍 패턴][20]공간 분할

개요

공간 분할은 위치를 가진 객체를 위치에 따라 자료구조에 정렬하여 사용하는 패턴이다. 충돌이나 공격같이 서로 가까운 객체들을 찾아 처리해야 할 때나 특정 위치나 근처의 객체를 빠르게 찾아야 할때 성능을 개선할 수 있다.

가장 간단한 방식은 고정 크기로 나눈 그리드 셀들에 해당 셀의 영역에 있는 객체를 링크드 리스트로 저장해두는 방법이다. 서로 특정 거리보다 인접한 객체들끼리 처리하고자 한다면 그 거리를 포함하는 인접 셀에 있는 개체들끼리만 거리 검사를 하여 처리하는 식으로 사용하면 된다. 

각 셀들에 어떤 객체가 들어있는지가 항상 관리되어야하기 때문에 객체 생성시나 이동시 특정 셀에 넣거나 옮기는 처리가 필요하다.

 

 

인접 셀 처리

포지션이 완전히 같은 객체들에 대해 처리한다고 하면 같은 셀에 있는 객체들끼리 검사하여 처리하면 된다. 하지만 충돌이나 거리 검사등은 인접한 셀에 들어있는 객체끼리도 상호작용 할 수 있기에 같이 검사해야한다. 이는 다음과 같이 처리할 수 있다. 충돌 검사를 처리하며 한칸 인접한 셀에 있는 객체끼리는 닿지만 두칸 이상 떨어진 셀들 안의 객체는 충돌하지 않는다고 가정하자.

각 셀의 객체들에 대해 다음을 수행한다. 우선 셀안의 객체들끼리 충돌 검사를 수행한다. 그후 셀안의 각 객체마다 인접한 셀들의 모든 객체들에 대해 충돌 검사를 수행한다. 이때 주변 8칸 모두에 대해 검사하면 다른 셀에 있는 객체들의 쌍마다 두번씩 검사가 일어난다. 이를 방지하기 위해 한 셀의 인접한 8칸들에서 각 대칭 부분 중에서 하나의 부분씩만에 대해 검사를 하면 된다. 즉 

x	x
x	o
x

 

o 셀에 대해서 x셀들의 객체들에 대한 충돌 검사를 수행하면 된다. 이렇게 하면 인접한 셀들의 각 객체 쌍에 대해 한번씩 충돌 검사가 일어난다.

 

 

개선된 공간분할

실제 게임엔진들에서는 좀더 개선된 공간 분할 기법들을 사용한다. 객체들의 수나 분포에 따라 분할 정도나 분할 형태를 조절하는 등의 개선방식을 사용한다.

쿼드트리의 경우 하나의 공간에서 시작하여 공간에 객체가 정해둔 개수보다 많다면 공간을 네개로 나눈다. 그리고 그렇게 나눠진 각 공간 역시 정해둔 개수보다 많으면 그렇지 않을때 까지 4칸으로 나눈다. 3차원의 경우 8개로 나누는 옥트리가 된다.

그외에 위와 비슷하게 공간을 두 공간으로 재귀적으로 나누며 분할 영역도 고정이 아닌 객체의 분포에 따라 적절히 나누는 k-d트리나 이진 공간, BVH등의 기법이 있다. 

 

 

 

 

참고서적

게임 프로그래밍 패턴