게임 개발에서 최적화를 위해 유용하게 사용되는 쿼드트리 알고리즘을 이해하자.
쿼드트리는 4개의 자식을 가지는 트리 형식의 자료구조를 의미한다. 2 차원 공간을 효율적으로 분할하고 탐색하기 위해 사용되는 트리 구조이다.
용도에 따라 2가지 쿼드트리로 나누어지는데, 점 쿼드트리와 범위 쿼드트리이다.
점 쿼드트리느느 2차원 평면에서 가까운 위치를 효과적으로 찾는데 사용되고,
범위 쿼드트리는 2차원 평면에서 영역을 가진 물체끼리 겹치는지 탐색하는데 사용된다.
게임에서는 주로 범위 쿼드트리를 사용한다.
게임에서 쿼드트리는
2D 평면 공간에서 두 객체의 충돌 처리 감지하는데 쓰인다. 탑 다운 뷰 슈터게임의 시야 판정이나 충돌처리 등에 활용된다.
이 때 사용하는 기초 데이터는 AAB(Axis-Aligned Bounding Box), 월드 축을 따라 정렬된 사각형 데이터를 사용한다.
쿼드트리 자체가 충돌을 감지하는 알고리즘을 의미하는 것이 아니다.
충돌 감지 알고리즘을 수행할 때, 모든 물체를 전수 조사하는 것이 아닌, 대상 물체 근처에 있는 물체만 골라내서 효과적으로 감지하도록 하는 알고리즘이다.