충돌 연산 최적화

 

Dynamic AABB Tree

---

 문제점 

O 내가 구상하고 있는 게임은 스타크래프트 유즈맵 느낌의 디펜스 게임을 제작하기 위해서는 100개 이상의 오브젝트들이 필요했고 서로 충돌처리를 해서 시야를 감지하고 밀어내는 과정이 필요했다.

O 원래 엔진의 구조 충돌연산구조는 단순 비교로 n^2의 시간복잡도를 가지고 있었다. 물론 오브젝트를 타입별로 나눠서 충돌을 체크했지만 그래도 같은 오브젝트의 개수가  100개 이상이 되면 프레임이 정말 떨어지는 문제점이 있었다.

 

 해결방안

O N^2 Broadphase가 아닌 Dynamic AABB Treef를 적용해서 연산을  최적화하자

O CollisionManager를 N^2에서 Dynamic AABB Tree로 리팩토링 해보자 

 

 해결과정

O  Dynamic AABB Tree 참고 사이트

Dynamic AABB Trees (box2d.org)

게임 물리학: 브로드페이즈 – 다이내믹 AABB 트리 | Ming-Lun "Allen" Chou - 한국 | 周明倫 (allenchou.net)

O  Dynamic AABB Tree  이해하기

 AABB Tree는 자식노드가 없거나 2개인 경우만 존재하는 이진트리이다.  가장 가벼운 연산인 AABB를 기반으로  노드는  확장한 AABB와 실제 Collider를 가지는 구조로 구성된다. 정렬 방법으로는 노드의 AABB의 넓이를  계산하여 더 작은 넓이 증가량을 가진 쪽으로 삽입한다. 2D에서는 넓이를 사용하지만 3D에 가면 부피나 면적도 사용가능하다.  핵심은 트리 구조로 정렬 후에  충돌하지 않는 노드의 자식들의 충돌 연산을 하지 않아도 되기 때문에 연산량 최적화가 가능하다.

O CollisionManager에 적용하기

 먼저 AABB Tree 클래스를 만들고 CollisionManager가 AABB Tree를 가지고 충돌을 처리하는 방식으로 구조를 작성하였다.  고민한 부분은 오브젝트 타입에 따라서 충돌체크를 하기 위해서는 트리를 가짓수만큼 만드는 방법은 콜라이더가 Node* 를 가져야 하므로 트리가 많아지면 복잡해지고 확장한 AABB를 갱신할 때 트리 개수만큼 재삽입이 발생하므로 비효율적인 구조라고 판단해서 모든 오브젝트들을 한 개의 Tree로 관리하는 대신에 충돌처리를 할 때 오브젝트의 타입을 확인해서 처리하였다. 

 

결과

O 기존의 N^2의 연산에서는 100개 이상의 충돌체를 사용하기 어려웠는데 Dynamic AABB Tree로는 200개 이상의 연산에서도 잘 작동하게 되었다.