2D 환경에서 동적 객체 간의 충돌 감지

Question

2 차원 세계에서 많은 동적 객체가 있다고 가정 해 보겠습니다. 캐릭터, 발사체, 파워 업, 게임에서 찾을 수있는 일반적인 것들. 모두 움직이고 있습니다. 우리는 그들 사이의 충돌을 탐지하려고합니다. 그것을하는 좋은 방법은 무엇입니까?

쿼드 트리를 살펴 봤지만 동적으로 움직이는 객체 간의 충돌을 감지하는 것처럼 보입니다. 객체마다 모든 프레임에서 위치가 바뀌기 때문에 모든 프레임마다 쿼드 트리를 다시 만들어야합니다. 이것은 값 비싼 작업처럼 보입니다.

쿼드 트리 외에이 문제에 대한 다른 방법이 있습니까? 쿼드 트리 방식을 향상시킬 수있는 방법이 있습니까? 결국 모든 프레임에 트리를 다시 만들면 비용이 많이 들지 않을까요?

Answer 1

일반적으로 쿼드 트리를 업데이트합니다 (이전 버전을 폐기하고 새 건물을 만들기보다는). 생각보다 비싸지는 않습니다. 일반적으로 객체는 각 프레임에서 작은 거리 만 이동하므로 대다수는 quadtree의 동일한 노드에 남아 있으며 변경 사항은 거의 없습니다. 최악의 경우에도 모든 항목이 주요 경계를 넘어 이동하여 제거하고 다시 삽입해야하는 경우에도 비용은 O (n 로그 n)입니다. 그러나 모든 항목에 대한 루프가 많아지면이 정도의 비용이 들게되므로 루프가 하나 더 많지 않습니다.