Spatial Index

분류: 분류 번역, 분류 설계패턴

이 글.. 시작은 했는데.. 참 까다롭네요... 만만치 않은 글입니다.. 도와주세요.. 2001/02/20 22:40, gryu

다른 것은 다 해석이 되어 있어서 제가 해석을 좀 해 봤는데, 맞는지 모르겠네요 ^^;; () 로 친 부분이니 확인 좀 해 주세요... 2001/02/21/ 03:53, PaRang

수고하셨습니다.. 저도 조금 손을 댔습니다 2001/02/21 14:05, gryu

제가 손댄김에 하는데까지 해봤습니다. 좀 이해못할 말들도 있네여. 2001/02/22 05:48, zho

zho님.. 제 마음에 드는 번역 스타일입니다^^; 이 글은 오래 걸릴 줄 알았는데 생각보다 금방 끝나겠네요... gpgiki 만세! - 2001/02/22 15:44, gryu
- 감사...사전식 단순직역을 좋아하시는군여...^^;... 전 의역을 하고 싶은데 실력이 모자라서...쩝... 2001/02/23 00:41, zho

슬슬 정리에 들어갑시다 - 2001/02/26 15:37, gryu

오랜만에 손을 댔습니다.. 일단 원문을 모두 삭제했구요.. 이 글은 이제 거의 완료된 것으로 봐도 좋겠습니다... 2001/04/04 00:26, gryu

공간적 색인 [1]

의도:

모델 데이터베이스 안에서 위치에 의한 검색 속도를 증가시킨다.

문제:

거의 모든 게임들은 위치나 영역에 의해 모델 데이터베이스를 빠르게 검색할 필요가 있다.

그러한 공간적 검색의 예를 몇 가지 들어보면:

렌더링에서 제외시킬 객체들을 식별하는 경우(컬링)
플레이어가 어느곳을 지나쳤는지의 여부를 판단
마우스로 클릭한 곳에 어떠한 UI 버튼이 있는지를 판단
물리적인 충돌 검출
어떠한 폭발에 의해 피해를 입는 객체들을 판단

해결책:

공간적 색인은 공간적 질의를 빠르게 해 준다. 공간적 색인은 주어진 공간적 키로 데이터베이스의 연관된 값들에 빠르게 접근할 수 있도록 한다. 공간적 색인은 질의의 속도를 빠르게 하기 위해 데이터베이스로부터 정보를 캐싱할 수도 있다. 데이터베이스의 값을 직접 돌려줄 수도 있고, 아니면 데이터베이스의 실제 값에 접근할 수 있는 키를 돌려줄 수도 있다. 공간적 색인의 구현 방식은 다양하겠지만, 대부분 세계를 검색 공간으로 축소하기 위해 공간적으로 나누든지, 객체들을 공간적으로 분류 하든지, 공간적 질의를 빠르게하기 위해 참조들 사이의 시간적 또는 공간적 결합성을 사용하든지, 또는 이러한 모든 기법들의 몇 가지를 조합한 것이다.

색인은 연관된 모델 데이터베이스와 동기화되어 있어야 한다. 일반적으로 공간적 색인은 모델 데이터베이스의 프레임웍 내에서 구현된다.

공간적 색인은 종종 하나의 최적화된 뷰 패턴으로 간주되며 뷰 코드와 아주 밀접하게 연관된다. 색인은 보통 뷰에 의해서는 읽히기만 하지만, 모델에 의해서는 읽고 쓰기가 가능하기 때문에, 아마도 뷰 코드 보다는 모델 코드쪽으로 보다 많이 속하게 될 것이다.

구조

지금은 없음

예:

다음이 흔히 볼 수 있는 공간적 색인들이다.

BSP(이진 공간 분할) 트리
스레드 방식의 충돌 해소를 수반한 X와 Y 해시들
개별적인 공각적 색인들을 연결하는 포털들
옥트리

문제점과 위험:

개념 상의 혼란: 데이터베이스 색인은 데이터베이스가 아니고, 그 역도 마찬가지이다. 하나의 데이터베이스는 여러 개의 색인들을 가질 수도 있고, 하나도 갖지 않을 수도 있다. 색인은 개념적으로 데이터베이스 자체와는 구별되는 것이며, 데이터베이스에 대한 질의의 속도를 올리기 위해 쓰이는 하나의 추가적인 데이터 구조일 뿐이다. 예를 들어서, 하나의 책은 하나의 키워드 색인과 하나의 목차, 하나의 그림 색인을 가질 수도 있고 아니면 하나도 갖지 않을 수도 있다. 이러한 각 예제에 있어서, 책의 내용(text)은 데이타베이스이다. 우리는 책의 한 페이지를 찾기 위해서 사용하는 키의 종류에 따라 다른 색인을 사용한다. 목차의 경우 키는 개념이다. 키워드 색인에 있어서 그것은 하나의 낱말일 것이고, 그림 색인에 있어서는 하나의 그림일 것이다. 이와 마찬가지로, 하나의 게임은 렌더러를 위한 하나의 객체 데이터베이스와 그에 연관된 하나의 공간적 색인, 충돌 감지를 위한 또 다른 공간적 색인, 그리고 AI가 서로 다른 적들에 기반한 질의를 할 수 있도록 하는 "종류 색인" 등 여러 가지 색인들을 가질 수 있다.

커플링(Coupling): 공간적 색인들은 그들의 연관된 데이타베이스에 너무 강하게 연결되는 경향이 있으며, 그러면 융통성과 재사용성이 감소될 수 있다. 색인이 특정 서브시스템에 지나치게 최적화되면 다른 서브시스템에 덜 유용하게 될 수 있다. 예를들면, 만약 공간적 색인이 렌더러에 고도로 최적화되고 연결되어 있다면, AI 서브시스템이 가장 가까운 적유닛을 효과적으로 찾기 위해 공간적 색인을 사용할 때에는 문제가 있을 수 있다.

동기화(Synchronization)와 복제(duplication): 색인에 있어서 키는 데이타베이스의 값들과 동기화된 채로 있어야 한다. 성능 향상을 위해 색인이 캐쉬된다면 동기화가 어려울 수도 있다. 유닛이 데이타베이스에서 움직인다면, 공간적 색인에 캐쉬된 데이타를 갱신시키거나 무효화시켜야 한다. 데이타베이스로부터 색인을 분리하는 것은 동기화문제를 발생시킬 수 있다. 데이타는 데이타베이스로부터 색인으로 자주 복제되기 때문에, 자원을 소비한다(메모리와 데이타를 동기화시키기 위한 추가 부담 둘 다).

용례 및 참고자료:

Hanan Samet 의 The Design and Analysis of Spatial Data Structures (Addison-Wesley, 1990) 를 볼것. 또한 MPotentially Visible Set 라고 불리는 퀘이크의 공간적 색인을 설명한 Mike Abrash의 글이 Blue's News 사이트 http://www.bluesnews.com/abrash 에 공개되어 있다. PVS는 실질적으로는 또다른 공간적 색인인 BSP 를 참조하는 공간적 색인이다.

References

[1] See http://www.gamedev.net/gdpatterns/viewpattern.asp?id=19