타일링 된 2D 맵의 영역에 많은 수의 객체가 "영역 효과"를 갖는 게임을 작성하고 있습니다.중첩 된 공간 영역에 대한 효과적인 데이터 구조
필수 기능 :이 영역 효과
는 어떤 데이터 구조를이에 가장 적합한 것이 잠재적으로 큰 (예를 들어 1000 개 * 1000 타일) 될 수 있을까?
당신이 정말로 영역 효과의 많은 동시에 발생해야합니까 제공, 그들은 임의의 형상을 갖는 것, 내가 이런 식으로 할 거라고 : 새로운 효과를 생성 할 때
화려한 컴퓨터 과학에 의존하지 않는 일부 무력 솔루션 :
1000 X 1000가 너무 크지 않다 - 단지 MEG. 컴퓨터에는 매력이 있습니다. 2 차원 배열을 가질 수 있습니다. 바이트의 각 비트는 '영역 유형'일 수 있습니다. 더 큰 '영향을받은 영역'은 다른 비트 일 수 있습니다. 합리적인 양의 영역이 있다면 멀티 바이트 비트 마스크를 사용할 수 있습니다. 그 말도 안되면 배열 요소 포인터를 겹치는 영역 형식 개체 목록에 만들 수 있습니다. 그러나 그런 다음 효율성을 잃게됩니다.
키 인덱스 (예 : key = 1000 * x + y)에서 해시 테이블 키를 사용하여 스파 스 배열을 구현할 수도 있습니다. 그러나이 속도는 여러 번 느려집니다.
물론 멋진 컴퓨터 과학 방법을 코딩하는 데 신경 쓰지 않는다면 대개 더 잘 작동합니다!
많은 수의 효과 유형이 있으므로 아마 일종의 목록이어야합니다. 그러나 하나의 "최대 10 제곱의 거리"효과가 441 개의 다른 목록을 생성하거나 업데이트해야하는 잠재적 인 문제가 있습니다 ....? – mikera
일반적으로지도의 밀도에 따라 다릅니다.
모든 타일 (또는 타일의 주요 부분)에 적어도 하나의 효과가 포함되어 있다면 규칙적인 격자 - 타일의 간단한 2D 배열을 사용해야합니다.
맵이 빈약하고 빈 타일이 많으면 쿼드 트리 또는 R 트리 또는 BSP 트리와 같은 일부 spatial indexes을 사용하는 것이 좋습니다.
좋은 생각 - 아마도지도가 약 10-20 %의 면적 효과로 덮여 있기 때문에 공간 색인 유형 접근이 더 좋을 것입니다. – mikera
공간 색인을 사용하면 사용되지 않는 타일에 대한 메모리를 낭비하지 않아도됩니다. 그러나 대부분의 이러한 인덱스는 정적 데이터를 저장하도록 설계되었습니다. 모든 "영향 영역"이 맵을 따라 이동할 수 있다는 것을 이해 했으므로 항상 공간 인덱스를 다시 작성/업데이트해야합니다. 이로 인해 상당한 오버 헤드가 발생할 수 있습니다. –
각 영역 효과의 알려진 최대 범위가있는 경우 선택한 2D 구조를 사용하고 일반적인 2D 충돌 테스트에 최적화 된 실제 소스 만 저장할 수 있습니다.
그런 다음 타일에 대한 효과를 검사 할 때 최대 범위 내의 모든 효과 소스에 대해 (데이터 구조에 최적화 된 충돌 감지 스타일)을 확인한 다음 정의 된 테스트 기능을 적용하기 만하면됩니다 (예 : 원, 거리가 상수보다 작은 지 확인, 사각형 인 경우 x 및 y 거리가 각각 상수 내에 있는지 확인하십시오.
작은 (< 10) 개의 "필드"모양이있는 경우 미리 계산 된 최대 범위 내에서 각 효과 필드 유형에 대해 고유 한 충돌 감지를 수행 할 수도 있습니다.
감사 Kylotan - 빠른 액세스를 보장하는 가장 포괄적 인 접근 방법 인 것 같습니다. 내가 이런 식으로 일을 끝낼 수도 있지만 타일 당 저장소에 대해 quadtree 형식의 접근 방식을 사용하고 목록 단위의 중복을 피하기 위해 타일 단위 목록을위한 영리한 캐시를 사용하는 것일 수도 있습니다. – mikera
어떤 이점이 있는지 이해하지 못합니다. 쿼드 트리에서 얻을 수 있습니다. 타일 맵은 일반적으로 (정의에 따라) 위치에서 타일까지의 2D 해시입니다. 일반적으로 빠른 검색 시스템이없는 경우 쿼드 트리 만 필요합니다 (예 : 타일이 아닌 연속적인 세계의 경우). – Kylotan