미로를 나타내는 데이터 구조

Question

매번 미로의 구조가 바뀔 때마다 (일부 문은 닫히고 일부 문은 열립니다 .HP4에서 Triwazard와 같은 것) 동적 미로 게임을 작성하고 있습니다. 누구든지이 데이터 구조가 가장 적합 할 것이라고 제안 할 수 있습니까?

Answer 1

미로는 사각형 그리드입니까? 다른 것?

유용한 정보 (패스 또는 객체)가 어느 정도 포함되는지에 따라 다릅니다.

사각형 격자이고 대부분의 격자 사각형에 SOMETHING이 포함되어있는 경우 좋은 데이터 구조는 배열의 각 요소가 1 행을 나타내는 2D 배열 (배열 배열)이고 내부 배열의 각 요소는 1 셀 이 행에는 해당 셀에 속한 데이터가 들어있는 객체 (이웃 셀을 이동할 수 있으며 셀에 포함 된 것, 거기에 문자가 있음)가 있습니다.

그러나 미로가 사각형이 아니거나 큰 미로의 셀 대부분이 실제로 유용하지 않은 경우 (예 : 통과 할 수없는 블록 인 경우) 좋은 데이터 구조는 그래프입니다.

그래프의 모든 꼭지점은 통과 가능한 셀입니다. 가장자리는 이동할 수있는 셀 쌍을 나타냅니다 (일부 문이 단방향 일 경우 방향 그래프로 만들 수 있음). 모든 정점/셀은 해당 셀에 대한 정보가 포함 된 개체입니다 (예 : 물리적 미로에서의 위치, 그리기 등).

array-of-array 구조의 장점은 그리기가 쉽고 처리가 간단하다는 것입니다 (모든 이동은 색인에 있거나 색인 해제 된 것입니다). 벽 추가/제거는 인접한 두 셀의 배열 요소에서 데이터를 변경하는 것만 큼 쉽습니다.

그래프 구조 이점은 미로 통과가 매우 희박한 경우 훨씬 적은 공간을 차지한다는 점입니다 (예 : 필드의 1/100 만 통과). 이것은 랜덤 (예 : 직사각형이 아닌 그리드) 지오메트리를 나타낼 수있는 유일한 구조이며 처리는 매우 간단합니다. 벽에 추가/제거는 그래프에 가장자리를 추가하는 것만 큼 쉽습니다.