불규칙한 모양의 게임 세계를 표현하기

Question

나는 게임 세계가 불규칙적 인 모양을 가진 프로젝트를 진행 중이다. 이 도형에는 좌표가있는 격자가 있습니다. 게임 세계는 모양의 안쪽에만 있습니다. (다시 한번 생각해 보자.)

게임 세계를 효율적으로 표현하려면 어떻게해야합니까? 나는 많은 세계가 기본적으로 정사각형이며 2 차원 또는 3 차원 배열에서 잘 작동한다는 것을 알고 있습니다. 나는 사각형 인 배열을 사용하는 것처럼 느껴진다. 기본적으로 공간을 낭비하고 배열을 반복하는 데 필요한 시간이 늘어난다. 그러나, 나는 또한 들쭉날쭉 한 배열이 여기에서도 어떻게 작동 할 지 확신하지 못한다. 게임 세계

X 
XX 
XX X XX 
XXX XXX 
    XXXXXXX 
XXXXXXXX 
XXXXX XX 
    XX X 
    X 

편집의

예 모양 : 는 게임 세계는 대부분 각각의 유효한 위치를 통해 강화해야합니다. 그래서 그렇게하는 것이 쉬운 방법입니다.

Answer 1

희박한 표현과 관련된 계산상의 오버 헤드와 복잡성이 있습니다. 따라서 경계 영역이 실제 세계보다 훨씬 커지지 않으면 '낭비 된'공간을 수용하는 것이 가장 효율적입니다. 근본적으로 세계적인 내용에 더 빨리 접근하기 위해 추가적인 메모리 사용량을 거래하고 있습니다. 더 중요한 것은 '낭비 공간'구현을 이해하고 유지하기가 더 쉬우 며, 이는보다 복잡한 구현이 요구 될 때까지 항상 바람직합니다. 필요한 증거가 충분하지 않은 경우 간단하게 유지하는 것이 좋습니다.

Answer 2

목록이나지도와 같은 데이터 구조를 사용하고 유효한 게임 세계 좌표 만 삽입하십시오. 그런 식으로 당신이 저장하는 유일한 것은 유효한 위치이며, 데이터 구조에서 존재하지 않는 것들을 추론 할 수 있기 때문에 게임이 아닌 세계 위치를 저장하는 데 낭비하지 않습니다.

Answer 3

세계를 땅 (또는 물) 패치의 (간접적 인) 그래프로 표시 할 수 있습니다. 각 패치는 정규 형식을 가지고 있으며, 세계는이 패치들의 조합입니다. 모든 패치는 그래프의 노드이며 모든 이웃에 그래프 가장자리가 있습니다.

아마 일반 세계를 가장 자연스럽게 표현한 것일 수도 있지만 (가장 효율적인 것은 아닙니다). 효율성의 관점에서 볼 때 매우 불규칙한 맵을위한 배열이나리스트를 이긴다. 그러나 편차가 거의없는 직사각형 (또는 다른 규칙적인 모양)에 잘 맞는 배열이나리스트는 아닐 것이다.

매우 불규칙한지도의 예 :

x 
x x 
    x x x 
    x  x 
    x xxx 
    x 
    x 
    x 
    x 

이 효율적으로 일정한 모양으로 (두 공간 비율 및 액세스 시간) 장착 할 수있는 실질적 방법이 없습니다. 다음은, 다른 한편으로는, 기본 형상 변환을 적용하여 일정한 모양으로 잘 맞는 (이것은 작은 비트 누락 된 평행 사변형이다)

xxxxxx x 
xxxxxxxxx 
    xxxxxxxxx 
    xx xxxx 

Answer 4

쉬운 일 단지 어레이를 사용하고, 막 마크 비 게임 스페이스 위치에는 몇 가지 특수 마커가 있습니다. 들쭉날쭉 한 배열도 효과가있을 수 있지만 그다지 사용하지는 않습니다.

Answer 5

표현에서 낭비되는 공간을 최소화하기 위해 quadtree을 사용할 수 있습니다. 쿼드 나무는 다양한 입도로 2 차원 공간을 분할하는 데 좋습니다. 가장 정밀한 세분성은 게임 스퀘어입니다. 게임 사각형이없는 전체 20x20 영역이있는 경우 쿼드 트리 표현을 사용하면 배열 표현과 마찬가지로 400 개가 아닌 전체 영역을 나타 내기 위해 하나의 노드 만 사용할 수 있습니다.

Answer 6

올라온 구조를 사용하십시오. 나중에 언제든지 변경할 수 있습니다. 어레이 사용에 익숙하다면 사용하십시오. 사용하려는 데이터 구조에 대해 걱정하지 말고 코딩을 시작하십시오.

시맨틱 모델로 래핑하는 것처럼 기본 배열에서 멀리 추상화를 작성하십시오. 그런 다음, 프로파일 링을 통해 공간 낭비 또는 필요한 작업을 느리게한다는 것을 깨닫게되면, 문제없이 문제를 해결할 수 있습니다. 필요한 것을 알기 전까지는 최적화를 시도하지 마십시오.

Answer 7

또 다른 방법은 가장자리 목록을 저장하는 것입니다. 즉, 각 직선 가장자리를 따라 선 벡터를 저장하는 것입니다. 이러한 방식으로 포함 여부를 쉽게 확인하고 쿼드 트리 또는 각 버텍스의 간단한 위치 해시를 사용하여 정보 조회 속도를 높일 수 있습니다. 우리는 야구 경기장의 벽을 모델링하기 위해 가장자리 당 높이 구성 요소를 사용하여이 작업을 수행했으며 아름답게 작동했습니다.

Answer 8

O (1) 시간 동안 게임 세계 위치에 계속 액세스 할 수 있고 너무 많은 공간을 낭비하지 않을 수있는 다른 옵션은 키가 좌표가 될 수있는 해시 테이블입니다.

Answer 9

아무도 언급하지 않은 큰 문제가 있습니다. 디스크에 저장하고 메모리에 저장하는 것과 큰 차이가 있습니다.

당신이 말했듯이 게임 세계에 대해 이야기한다고 가정하면 이것은 매우 커질 것임을 의미합니다. 한 번에 전체를 메모리에 저장하지는 않지만 대신 플레이어가 주변을 돌아 다니면서 바로 주변을 메모리에 저장하고 업데이트합니다.

이 주변 지역은 가능한 한 간단하고 쉽고 빠르게 접근해야합니다. 그것은 반드시 배열 (또는 플레이어가 움직일 때 스왑 아웃되는 배열)이어야합니다. 종종 게임 엔진의 많은 하위 시스템에 의해 참조 될 것입니다 : 그래픽과 물리학은 모델 로딩, 드로잉, 플레이어를 지형 위에 두는 것, 충돌 등을 처리 할 것입니다. 사운드는 적절한 발자국 소리를 내기 위해 플레이어가 현재 서있는 지상 유형을 알아야합니다. 등등. 이 데이터를 모든 서브 시스템에 브로드 캐스트하고 복제하는 것이 아니라 전역 배열에 보관하면 원하는대로 100 % 속도와 효율성으로 액세스 할 수 있습니다. 이것은 실제로 물건을 단순화 할 수 있습니다 (그러나 전역 변수의 결과에 유의하십시오!).

그러나 디스크에서는 확실히 압축하려고합니다. 주어진 답변 중 일부는 좋은 제안을 제공합니다. 해시 테이블 또는 채워진 위치 목록 만 같은 데이터 구조를 직렬화 할 수 있습니다. 확실히 옥트리도 저장할 수 있습니다. 어떤 경우에도 디스크에 빈 위치를 저장하고 싶지는 않습니다. 통계에 따르면 공간의 66 %가 낭비 될 것입니다. 물론 최적화를 잊어 버리고 정당한 작업을 할 시간이 있지만 최종 사용자에게 66 %의 비어 있지 않은 파일을 배포하고 싶지는 않습니다. 또한 디스크는 완벽한 랜덤 액세스 시스템 (SSD 제외)이 아닙니다. 기계식 하드 드라이브는 최소한 몇 년 전부터 있어야하며 순차적으로 가장 잘 작동해야합니다. 플레이어가 움직이는 동안 더 가까운 지형을 스트리밍 할 때 읽기 작업이 순차적이되도록 데이터 구조를 구성 할 수 있는지 확인하십시오. 그러면 눈에 띄는 차이가있을 것입니다. 그래도 내 말을 듣지 마라. 나는 실제로 이런 종류의 테스트를하지 않았다.