그리드 용 최적의 고밀도 이진 공간 파티션

Question

캐릭터가 임의로 생성 된지도를 실시간으로 움직이는 게임을 작성했습니다 (흥미로운 데이터 구조 문제입니다.). 지도는 캐릭터 (아마도 20-60 타일) 주변의 원으로 볼 때 생성되므로 데이터가있는 곳, 매우 밀도가 높습니다. 그리고 모두 그리드에 있습니다. 그러나 데이터가없는 곳에는 거대한 생성되지 않은 공간이있을 수 있습니다. 캐릭터는 거대한 원안을 걸을 수 있습니다. 예를 들어, 광대 한 빈 공간 주변에 타일 링을 만들 수 있습니다.

간단한 매트릭스는 엄청난 양의 불필요한 오버 헤드를 발생시키고 많은 공간을 낭비합니다. 하지만 일반적인 BSP는 밀도가 높고 그리드와 유사한 데이터 특성으로 인해 성능이 크게 떨어지는 것처럼 보입니다.

무엇을 제안합니까? 행렬 - quadtrees - 두 가지 하이브리드?

Answer 1

나는 지난 한 달이 태클 있었고, 나는 상당히 좋은 솔루션입니다 무엇을 믿는 함께 올라와있다 :

는 그래도 난 더 우아한 솔루션에 관심이 있어요. 순수한 매트릭스만큼 빠르지는 않지만, 무한하게 확장 될 수있는 이점이 있습니다 (int의 한계 내에서).

기본적으로 쿼터 트리와 같이 위쪽이 아닌 2 차원 공간 파티션입니다. 현재 할당 된 행렬 공간 외부의 점에 쓰면 큰 노드가 생성되어 확장됩니다. 노드의 자식 노드의 대다수가 행렬을 할당 받으면 노드를 모아서 참조를 제거합니다. 즉, 더 잘 정의 된 경계를 사용하면 성능이 향상됩니다. 더 많은 구조가 매트릭스처럼 작동하기 때문입니다.

나는 here 코드를 게시했으며 앞으로 어떤 종류의 데모를 작성하고 더 나은 호스팅 사이트로 이동할 것입니다.

귀하의 의견을 주저하지 말거나 질문이 있으시면 언제든지 알려주십시오.

Answer 2

나는 내가하고있는 게임에서 비슷한 것을 구현할 생각이다. 2D 배열처럼 액세스 할 수있는 사용자 정의 클래스를 만들겠습니다. map[x][y]하지만 기본 데이터 형식은 해시 테이블에 더 가깝습니다. 무언가 같아 data[x.Value.ToString() + "," + y.Value.ToString()]

내 타일은 걷기 쉽고, 치명적이거나, 고의적이지 않으므로 내 게임은 상당히 기본입니다. D