나는 많은 양의 동적 엔터티가있는 2D 게임에서 작업 중입니다. 재미있게 보자. 군인이라고 부르 자. 그 중 50000 명이 있다고 가정 해 보자. (나는 무작위로 생각했다. 훨씬 더 많거나 적을 것이다.)).2D 게임 : 다른 엔터티에 대해 x 개의 가장 가까운 엔터티를 찾을 수있는 빠른 (추정) 방법 - 매우 많은 양의 엔터티 매우 동적 인.
모든 병사들은 규칙에 따라 모든 프레임을 움직이고 있습니다. boids/flocking/steering behaviour를 생각해보십시오. 각 군인마다 운동을 업데이트하려면 내가 처리중인 X 병사와 가장 가까운 X 병사가 필요합니다.
너무 많은 오버 헤드없이 이와 같은 계산을 용이하게하기 위해 저장할 공간 계층이 무엇이겠습니까? (모든 엔티티는 모든 프레임을 업데이트/이동하므로 동적 엔티티를 매우 잘 처리해야합니다.)
가장 간단한 방법은 표를 사용하는 것입니다. 그것은 몇 가지 장점이 있습니다
또한 모든 거리 확인을 위해 스퀘어 루트를 수행하지 않도록하십시오. 거리 만 비교하기 때문에 거리의 제곱을 비교할 수도 있습니다.
+1 광장에 대한 조언, 항상 그것을 생각 나게 반갑습니다 – Gnoupi
+1 광장, 많은 사람들이 몰라요 얼마나 확장 성이 실제로 얼마나 큰지, 그리고 그것을 피하는 것이 얼마나 간단한 지) –
넓은 위상 충돌 감지의 경우 쿼드 트리 (2D이므로)와 같은 spatial index 또는 그리드가 수행합니다. 전에 Metanet Software's tutorial에 연결했습니다. 그리드 기반 스키마를 개괄적으로 설명합니다. 물론 게임에서 그리드를 광범위하게 사용할 필요조차 없습니다. 각 액터를 숨겨진 그리드에 저장하고이 액터를 인접한 셀에있는 객체와 충돌 시키십시오.
quadtree는 모든 움직이는 물체에 적합하지 않기 때문에 나무에서 그것을 제거하고 다시 삽입해야합니다. 잠재적으로 값 비싼 작업. 또는 모든 프레임을 다시 트리에 다시 만들어야합니다. – Toad
@reinier : 쿼드 트리를 얼마나 자주 업데이트해야하는지 파악하기 위해 몇 가지 테스트를 해봐야 할 것 같습니다. 이 속도를 늦추고 충돌을 테스트 할 오브젝트 반경을 늘릴 수 있습니다. 틀림없이 빠르게 움직이는 물체는 어쨌든 확대 된 반경에서 벗어날 수 있지만 처음에는 문제가있는 물체입니다. –
동일한 인수가 그리드에 적용됩니다. ^) – Toad
우수한 공간 계층 구조를 선택하는 요점은 테스트가 필요한 객체 만 빠르게 선택할 수 있다는 것입니다. (작은 부분 집합을 발견하면 제곱근은 그다지 해를 끼치 지 않을 것입니다.)
또한 2 차원 공간 인덱싱을 위해 가장 최선의 방법이 무엇인지에 관심이 많습니다. 동적 객체.
Quadtree/kd-tree는 멋지지만 동적 인 삽입에는 좋지 않습니다. KD- 트리가 불균형해질 수 있습니다.
엔티티가 포인트 인 경우 바이너리 검색과 조합하여 두 번 삽입 정렬 된 구조 (X 및 Y 기준)를 시도해보십시오. ..?
필요하지 않은 경우, 왜 그것을 사용합니까? – Toad
가장 유용한 답변을 선택하여 질문을 닫는 것을 잊지 마십시오. – Toad
여기에 reininer의 제안과 유사한 [좋은 알고리즘] (http://wapedia.mobi/en/Flocking_ (behavior))이 있습니다. –
[이 블로그] (http://blogs.msdn.com/devdev/)에는 [한 가지 해결책의 좋은 글이 있습니다] (http://blogs.msdn.com/devdev/archive/2007/06/07/k)가 있습니다. - 네이버 - 이웃 - 공간 - search.aspx) (뿐만 아니라 다른 좋은 articals의 숫자) – BCS