Tasdia

Tasdia는 인공 세계관 사트의 지도를 관리하기 위해 제작된 지도 관리 소프트웨어이다. 시간에 따른 지형의 변화, 시간에 따른 국가 점유상태의 변화 등 세계관에 대한 이해와 관리를 편하게 하기 위해서 계획되었다.

API

지도: Map

속성	타입
id	int
description	str
area_layers	list[AreaLayer]

GET /api/map

GET /api/map/{id}

영역 레이어: AreaLayer

속성	타입
id	int
description	str
metadata	dict[int, AreaData]
tree	QuadTree
deltas	list[AreaDelta]

GET /api/map/{map.id}/area

POST /api/map/{map.id}/area/new

• 필요: description

GET /api/map/{id}/area/{id}

POST /api/map/{id}/area/{id}/new

지도에 변경사항이 생겼을 때에 area에 변경사항을 등록한다.

• 필요: delta
• 필요: time

GET /api/map/{id}/area/{id}/data

POST /api/map/{id}/area/{id}/data/new

• 필요: color, #RRGGBB 형태
• 필요: description

GET /api/map/{map.id}/area/{id}/tree

AreaData

AreaData는 영역 레이어에 나타난 자료들에 대한 세부적인 정보를 제공한다. 영역 레이어 tree의 각각 영역은 서로 구분되는 정수만을 가지고 있는데, AreaData가 해당 정수를 두고 무슨 의미를 가지는지 나타내는 역할을 하는 것이다.

속성	타입
id	int
description	str
color	tuple

AreaDelta

속성	타입
time	float
delta	QuadTreeDelta

기능적 구현

사분트리: QuadTree

QuadTree는 해당 분기의 최하위 트리가 아니더라도 값을 가진다. 이것은 구현의 편의를 위한 것이다. 이 문서에서 트리의 구조를 설명할 때에 자식이 없는 트리는 A와 같이 한 글자만을 이용해 나타내고, 자식이 있는 트리는 A(1234)와 같이 자식을 괄호 안에 나열하여 나타낸다. 따라서 A(B(1234)CDE)는 1, 2, 3, 4를 자식으로 가지고 있는 트리 B와, 자식이 없는 트리 C, D, E를 A가 가지고 있음을 나타낸다. O는 최상위 트리를 나타내는 것으로 한다.

QuadTree에서 다른 어떤 QuadTree를 나타내기 위해서는 다음 몇 가지 방식을 사용할 수 있다.

1. 가족 주소: family path

가족 주소는 어떤 최상위 트리를 기준으로 각각 몇번째 자식들을 따라가야 원하는 트리가 있는지를 나타낸다.

예를 들어서, O(A(BCDE)FGH)와 같은 구조의 트리가 있다고 했을 때, D의 가족 주소는 O에 대하여 [0, 2]이다. 이는 O의 0번째 자식의 2번째 자식이 D이기 때문이다.

2. (이진) 주소: (binary) path

이진 주소는 가족 주소의 주소 값을 이진수로 나타낸 것이다. 가족 주소 [0, 2]의 이진 주소는 [(0, 0), (1, 0)]이다.

3. 위치: position

위치는 최상위 트리에 대해 찾고자 하는 자식 트리를 상대적인 위치 값을 사용하여 나타낸 것이다. 이때, 트리를 나타내기 위한 위치 값은 x값, y값을 함께 사용한다.

어떤 트리가 최상위 트리로부터 n대손이고, 해당 트리의 오른쪽(인덱스가 1, 3), 또는 아래쪽(인덱스가 2, 3)에 위치하는 트리를 나타내기 위해서는 해당 트리의 위치에 n을 더하여 나타낸다.

예를 들어, O(A(BCDE)FGH)에서 D의 위치는 (0, 2)이다.

다음 표는 최상위 트리를 포함하여 3대로 이루어진 트리의 위치를 나타낸다.

0, 0	2, 0	1, 0	3, 0
0, 2	2, 2	1, 2	3, 2
0, 1	2, 1	1, 1	3, 1
0, 3	2, 3	1, 3	3, 3

이렇게 하면 자세한 주소를 나타낼 때에 더욱 절대값이 큰 수를 사용하게 되고, 이론적으로는 유리수의 범위에서 무한히 작은 차이까지도 나타낼 수 있다. 이러한 좌표계를 사용하면, 사분트리의 정중앙은 언제나 (1, 1)로 나타난다.

4. 주소 정수: path int

주소 정수는 흔히 생각되는 좌표이다. 정확한 주소 변수 표시를 위해서는 해당 주소 좌표가 몇회 분할을 기준으로 사용된 것인지를 명시해야 하며, 이때 분할된 횟수로 사용하는 수를 단위(unit)라고 한다.

사분트리 차이: QuadTreeDelta

사분트리의 변경사항을 나타내는 사분트리이다.

기본적으로 그 구현은 사분트리와 같으나, 사분트리에 사분트리 차이를 적용하거나 사분트리 차이에 또 다른 사분트리 차이를 적용하는 등의 연산을 제공한다.

사분트리와 구현적으로 차이가 없으므로 클래스도 QuadTree를 사용한다. 단, 이 경우에 변화가 발생하지 않는 부분은 QuadTree.value를 None으로 해둔다.

사분트리 차이는 클라이언트가 변경사항을 만들 때마다 작성되며, AreaLayer에서 편집 시간과 함께 저장된다. 서버에서는 언제나 가장 최신의 지도 정보를 보관하고 있어야 하며, 클라이언트가 과거 정보를 요청하면 해당 시기까지의 사분트리 차이 추적을 시간반대순서로 전송하여 클라이언트에서 차이를 계산하게 한다.

연산

• 적용: apply

사분트리에 사분트리 차이를 적용하면 해당 차이가 적용된 사분트리를 반환한다. 사분트리 $A$ = O(AB(EFGH)CD)에 사분트리 차이 $d$ = 0(0(0B0A)00E)를 적용하면 O(A(ABAA)B(EFGH)CE)를 차이한다.

사분트리 차이에도 사분트리 차이를 적용할 수 있다. 사분트리 차이 $d$ = 0(0(0B0A)00E)에 사분트리 차이 $e$ = 0(C(0AA0)00F)를 적용하면 사분트리 차이 0(C(0BAA)00F)를 얻을 수 있고, 반대로 $e$에 $d$를 적용하면 0(C(0BAA)00E)를 얻는다.

• 추적: trace

사분트리에 사분트리 차이를 추적하면 사분트리 차이에서 변화를 발생시킨 부분만큼을 떼어낸다. 사분트리 $A$ = O(AB(EFGH)CD)에 사분트리 차이 $d$ = 0(0(0B0A)00E)를 추적하면 0(0(0F0H)00D)를 반환한다.

구현

Tasdia의 프로젝트 관리 단위는 지도(map)이며, 지도는 레이어(layer)라고 하는 부품들로 이루어진다.

레이어

레이어는 지형이나 국경, 지명 등을 나타내기 위한 영역 레이어(area layer)와 지점이나 경로 등을 나타내기 위한 메타정보 레이어(metadata layer)로 나누어진다.

레이어에 등록되는 정보는 모두 어떠한 시점을 기반하며, 따라서 시간에 따라 바뀌는 사트의 모습을 알아볼 수 있다.

영역 레이어

영역 레이어는 일정한 영역을 하나의 이름으로 묶어 나타낸 것으로, 바다와 육지의 구분; 국가 영토 등 면적으로 이루어진 정보를 나타낸다.

영역 레이어로 나타낼 수 있는 것에는 다음이 있다.

• 지형
• 등고선도
• 국가 영토
• 도시 영토
• 등

영역 레이어에 만들 수 있는 정보는 영역 데이터(area data)가 있으며, 서로 다른 영역 데이터끼리는 시·공간적으로 서로 겹치지 않는다.

메타정보 레이어

메타정보 레이어는 점이나 선으로 이루어진 정보를 나타낸 것으로, 도시의 위치, 지하철 노선도 등을 나타낼 수 있다.

메타정보 레이어로 나타낼 수 있는 것에는 다음이 있다.

• 지하철 노선도
• 도시 위치
• 여행 경로
• 등