게임 프로그래밍 패턴 - 공간분할

박승우·2025년 3월 24일

95번째 키워드 '게임프로그래밍 패턴 - 공간분할'이다.

정의

공간분할 패턴은 객체들의 위치정보를 효율적으로 관리하여 프로그램의 성능을 향상 시키고 관리가 용이하게 하는 기법이다.
이를 통해, 객체간의 상호작용을 최적화하여 불필요한 계산을 줄이고 자원을 효율적으로 사용할 수 있게 된다.

사용하게 되면 객체들 간 불필요한 모든 쌍 확인을 피하게 되고, 넓은 범위 충돌감지(Borad-Phase)나
시야 절두체 컬링(Frustum Culling)등을 효율적으로 수행할 수 있게 된다.

사용 범위 및 분야

컴퓨터 그래픽스 : 높은 그래픽 처리를 위해 많은 자원을 요구하게 되는데 자원들을 효율적으로 관리하기 위해 사용
렌더링 최적화 : 게임 개발에서 플레이어의 시야에만 들어오는 객체만 렌더링 하도록 공간을 분할하여 관리
AI 및 경로 탐색 : AI가 경로를 탐색할 때 전체맵을 탐색하는 것 보단 공간분할을 통해 범위를 제한하여 사용

1인칭 슈팅(FPS) 게임에서의 공간 분할

BSP Tree 를 이용한 공간분할이 핵심기술로 도입된 게임은 대표적인 사례료 둠(Doom)과 퀘이크엔진(Quake) 이 있다.

두 개의 프로그램은 이진 공간분할 트리(BSP)를 사전에 생성하여 레벨의 벽과 지형을 분할하였다.
트리는 공간을 두 부분으로 재귀적으로 잘라나가며 최종적으로 볼록(convex)과 구역(subsector)들로 분할을 하게 된다.

최종적으로 분할 된 잎 노드들은 나눌 필요가 없는 작은 볼록공간이 되며 이는 시야에서 보이는 면만 그리도록 최적화 함

이는 렌더링이 복잡한 레벨에서 보이는 면과 보이지 않는 면을 실시간으로 판정하는 문제를 효율적으로 해결한 것이라 한다.

Doom의 첫 레벨인 E1M1을 BSP로 분할한 결과

- 각 색깔 영역이 BSP Tree의 한 서브섹터(leaf Node)에 해당하며, 이를 바탕으로 렌더링 순서 결정

실시간 전략(RTS) 게임에서의 공간 분할

RTS장르는 한 화명에서 수십에서 수백 개의 해당하는 오브젝트들이 상호작용을 하게 되는 장르이다.
한 시야 안에서 플레이어가 수 많은 오브젝트들을 컨드롤 할 수 있끼 때문에 각 연산에 대해서 최적화가 필수가 된다.

유닛 충돌 및 범위 판단 최적화

- RTS 유닛들은 이동중이나 공격할 때 서로 겹치지 않는다거나 아군과 적군을 나눈다거나 서로 상호작용이 되어야하는 등 많은 계산이 필요하게된다.
  유닛의 쌍이 100쌍이라고 했을 때, 100 * 100을 일일히 하게 되면 많은 연산이 되기 때문에 성능이 많이 저하 된다.
  
  
  이를 해결하기 위해서 "격자 그리드"기반 또는 "쿼드 트리" 기반 공간분할을 사용하게 된다.
  유닛들은 자신의 위치에 해당하는 타일이나 셀(공간)안에 속해 있고, 충돌이나 공격 판정시에는 해당 셀과 인접한 셀의 유닛만 검사하면 충분하다.
  
  이렇게 하게 되면 서로 셀이 다른 유닛끼라는 건너 뛰게 되어 불필요한 연산은 줄어들게 된다.