두 개 이상의 2D 객체가 충돌하는지 감지하는 방법을 잘 알고 있지만 충돌 여부를 결정하는 방법에 관심이 있습니다. 이전 프로젝트에서는 다른 모든 객체 (O (n ^ 2) 수준의 어리 석음)에 대해 모든 객체 검사를 수행했으며 유동적이지 않은 게임 플레이를 만들었습니다.
다양한 포럼에서 Quadtrees, B-Trees 및 기타 생각할 수있는 다른 종류의 트리 또는 구조를 환영합니다.
충돌을 점검해야하는지 결정하는 가장 효율적인 구조는 무엇입니까?
답변
2D 게임의 경우, 2D 객체가 맵의 한쪽면에 매우 많은 분포를 갖지 않는 한 균일 한 그리드가 거의 항상 진행됩니다. 메모리 복잡도는 간단하고 (맵의 크기에 비례) 합리적으로 분포되어 있으며 O (1) 조회 시간과 평균 log (numberOfObjects / (행 * 열)) ^ 2 개의 교차 테스트 셀당 수행됩니다. 객체가 이동 한 셀만 검사하여 정적 지오메트리를 훨씬 효율적으로 만들 수 있습니다. 즉석에서 균일 한 그리드를 쉽게 수정할 수 있으며 (트리 기반 솔루션보다 훨씬 덜 고통스럽고) 구현하기가 더 쉽습니다. 2D 게임에서 사용하지 말아야 할 유일한 시간은 균일 한 그리드의 메모리 요구 사항이 너무 커지는 경우입니다 (예를 들어 레벨이 희소하지만 거대한 공간 시뮬레이션).
답변
Box2D 및 Chipmunk와 같은 2D 물리 엔진은 공간 해시 맵을 많이 사용합니다.
참조 http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#CollisionDetection을 참조. 다람쥐 데모에는 정말 좋은 공간 해시 시각화 도구가 포함되어있어 기술이 어떻게 작동하는지 명확하게 알 수 있습니다.
답변
세계에 하나의 “긴”치수 (X라고 함)가있는 경우 다른 객체와 비교하여 객체를 정렬 된 목록으로 유지할 수 있습니다.이 목록은 이동하면서 다시 정렬 할 수 있으며 충돌 감지는 X 축에서 겹칩니다.
또 다른 가능성은 활성 / 수동 개체 목록을 유지하고 수동 개체 (아직 움직이지 않는)를 신경 쓰지 않는 것입니다.
이들이 화면에서 플레이어가 볼 수있는 중간 크기의 물체라면 모든 것과 모든 것이 그렇게 나쁘지는 않을 것입니다.
그 외에도 Darcy와 함께 일관된 그리드가 좋습니다.