사각형 배열에서 겹침을 찾는 가장 빠른 방법은 무엇입니까?

Question

저는 여가 시간에 거의 순전히 학습 경험으로 "게임"을 진행하고 있으며 플레이어 엔티티와 적군 엔티티 간의 충돌 감지가 발생해야하는 시점에 있습니다.

플레이어와 모든 적 모두 기본 클래스 인 Entity을 공유하므로 x, y, height 및 width 속성에 액세스 할 수 있습니다. 이를 사용하여 각 엔티티에 대해 사각형을 만들고 겹침을 찾으려고합니다. 겹치는 부분이 있으면 충돌이 발생했습니다. 이들 개체 (사각형) 중 하나가 교차하는 경우를 결정하는 가장 빠른 방법은 무엇

X Y HEIGHT WIDTH 
------------------------ 
0 0 25  50 
0 50 25  25 
0 100 25  30 
50 200 25  50 
150 250 25  25 
150 50 25  30 

:

그래서, 위의 논리와 함께, 우리는 다음과 같은 데이터는 사각형의 배열에 척 수 다른? 간단하게 배열을 반복하고 각 요소를 서로 다른 요소와 비교하는 것은 충분히 성능이 없습니다 (O (n^2)). 더 좋은 방법이 있습니까?

Answer 1

서로 가까이있는 요소를 빠르게 찾을 수있는 일종의 공간 인덱스 또는 구조를 사용하려고합니다.

일반적으로 사용되는 데이터 구조는 quadtree입니다.