Геодата и координатная сетка. Основы.

Всем привет.
5 ~: ?3 B& i2 {$ o) j6 S$ c& vХочу поделится информацией базовых принципах хранения и обработки геоданных, а также о том, как это связано с координатной сеткой.
Сразу скажу, я пишу этот мануал в разделе PTS сервера, но он одинаково справедлив(кроме описанной структуры хранения геоданных!) для любой сборки.

Общая структура и описание:
7 n4 C+ r0 W) sИгровой мир в L2 описывается тремя координатами. XYZ.
9 |8 M: g; x5 B9 V7 @) d$ nОсь X это направление Запад-Восток(Уменьшение координаты X - это движение на Запад, следовательно увеличение X - движение на Восток)
; v) K9 J  D- }( L: ^2 YОсь Y это направление Север-Юг(Уменьшение координаты Y - это движение на Север, следовательно увеличение Y - движение на Юг)
4 h& r5 l0 s0 ^% O$ ?Ось Z это высота. Из-за особенностей хранения гео-данных на PTS сервере, высота ограничена диапазоном 16 битного значения (От -16384 до 16383)

Координатная сетка очень плотно связана с геодатой. Далее в тексте, если специально не указано иное, то следует считать, что описания даются в плоскости XY.
Игровой мир делится на Регионы. Обычный Регион представляет из себя квадрат, с размерами 32768 x 32768 точек
6 P6 C: }! w1 x. `, ^6 [Регион в свою очередь делится на 65535 Блоков(сетка 256х256). Таким образом, размер одного Блока 128 x 128 точек.
0 j  r& o4 b0 O3 F( E! G7 ]Блоки бывают трех основных типов(Плоский, Комплексный и Мультислойный). В чем их отличие и особенности я объясню ниже.
0 C7 j/ j7 e" |* m5 d# o( ZКомплексные и Мультислойные Блоки делятся еще на более мелкие элементы - Ячейки. Один Блок вмещает в себе 64 Ячейки в виде сетки 8 х 8. Следовательно одна Ячейка представляет из себя квадрат 16 х 16 точек.
Мельчайшим объектом мира L2 является Точка. Каждая Точка имеет координаты XYZ.

Как хранятся и обрабатываются геоданные на PTS сервере:
7 Y4 o0 ^, D" P" g& s! b4 mДля хранения геоданных, PTS-сервер использует бинарные файлы, в формате X_Y_conv.dat, где X и Y это номера Региона.
Т.к бинарные файлы подразумевают хранение данных в виде массива байт, то для получения каких-то данных, в большинстве случаев происходит сбор чисел больших диапазонов из определенного количества байт.
Первые 18 байт каждого файла геоданных содержат так называемый Заголовок:
. E& ~0 C1 G4 _, m( i# P0 байт - X региона
5 R6 D& d4 L3 ?# |0 [" C- Q1 байт - Y региона
1 q/ g& H" v- S# C. h+ a0 _2-5 байты остались для меня загадкой, я подозреваю что это два 16 битных значения, но их смысл не понятен, т.к они не изменяются.
3 d5 `9 `. P" a' ?0 [2 j, x9 [6-9 байты образуют 32 битное значение, которое хранит в себе количество Ячеек в регионе.
& W# S. H3 {6 N6 J10-13 байты образуют 32 битное значение, которое хранит в себе количество НЕ Мультислойных блоков в регионе
14-17 байты образуют 32 битное значение, которое хранит в себе количество ПЛОСКИХ блоков в регионе.

Дальше хранится информация о самих блоках региона по порядку от 0 до 65534 позиции.
Для удобства восприятия, я буду считать восемнадцатый байт файла региона как нулевой по индексу.
0 и 1 байты хранят 16 битное значение, которое указывает на тип блока.
0x00 - Это Плоский блок. Размер данных 4 байта.
( f3 r/ Y8 l7 I7 V2 d0x40 - Комплексный блок. Размер данных 128 байт.
* c( j- {) u, N& B0 LВСЕ остальные это Мультислойный блок(В этом случае, тип также указывает еще и на размер блока: Тип * 2 + 65)

Как и какая информация хранится в Блоке?
Для этого нужно небольшое отступление. В мире L2 за возможность движения в определенном направлении, сквозь Ячейку, отвечает еще одна ее характеристика, условно обозначенная как NSWE. Это битовая маска в диапазоне от 0 до 15 включительно.
Что она означает? Это аббревиатура состоящая из первых букв сторон света: North South West East

/ F+ D2 E0 v# e: D7 ?4 u5 S0 - Движение через ячейку запрещено.
1 - E (1 << 0) Движение на Восток X+
2 - W (1 << 1) Движение на Запад X-
3 - WE (W | E) X+ || X-
: x( W* _; e+ j1 f' P8 x& {) [4 - S (1 << 2) Движение на Юг Y+
$ N) y3 v! z1 a1 U5 n/ Y7 v5 - SE (S | E) X+ && Y+
6 - SW (S | W) X- && Y+
7 - SWE (S | W | E) (X- || X+) && Y+
8 - N (1 << 3) Движение на Север Y-
7 N& f  p5 d1 {0 T  y9 - NE (N | E) X+ && Y-
10 - NW (N | W) X- && Y-
9 [2 U  s7 l8 p7 u7 R1 S11 - NWE (N | W | E) (X- || X+) && Y-
) Y) K  e: S0 k- U* v$ k( Q* b12 - NS (N | S) Y- || Y+
13 - NSE (N | S | E) (Y- || Y+) && X+
0 d' U3 s9 U: U) [; K" K5 n& N/ R8 U14 - NSW (N | S | W) (Y- || Y+) && X-
15 - NSWE (N | S | W | E) X- || X+ || Y- || Y+

$ {& d. d: C% z2 _7 h9 p/ wТ.е условно, если у вас персонаж стоит в координате 12345, 6789, а вы кликаете в координату 12345, 9876 (т.е Y+) то пройти вы сможете только через те Ячейки, NSWE значение которых удовлетворит выражению:
4 I: K2 q$ `4 i0 J, V(NSWE & S) == S
' z8 v5 C+ w! y1 H
1 `; Z" `$ i5 `' n0 F3 ZВернемся к блоку. Что в нем хранится? Каждый тип Блока хранит данные по своему. Разберем их поочереди.
* t2 z: C" G0 s1 w! f7 GПлоский Блок - Т.к этот тип блока не делится на Ячейки, то значение проходимости общее для всех координат блока(и на PTS это всегда 15, т.е Плоский блок всегда проходим. Плоский блок НЕ ХРАНИТ NSWE). Мы знаем, что размер Плоского блока - 4 байта. Это два 16 битных значения. Каждое значение содержит в себе высоту этого блока в формате ( byte1 << 8 | byte0 & 0xff) & 0x0fff0)
! h) b! a8 K) `5 ]& MКомплексный Блок - Т.к этот блок разделен на 64 ячейки, а общий размер блока 128 байт, то мы легко вычисляем, что каждая ячейка блока содержит два байта, которые в свою очередь собираются в 16 битное значение.
. C; m6 d8 b% V' m4 v. SКак из одного значения получить NSWE и высоту? Для этого нужно использовать следующую формулу:
# t9 Q$ J8 N2 [" f: W7 s; v' fВысота - ( ( byte1 << 8 | byte0 & 0xff) & 0x0fff0) >> 1 (т.е фактически деление пополам исходного значения)
NSWE - ( ( byte1 << 8 | byte0 & 0xff) & 0x0F) (т.е фактически мы берем младшие разряды числа)
/ _6 D3 W: o% L" R& U3 A. TМультислойный Блок - Представляет из себя по сути Комплексный блок, но каждая ячейка которого может содержать как одно, так и несколько значений-слоев(в каждом значении будет зашифрована собственная высота и NSWE)
: Z, q9 Z+ q4 ^5 z! `6 {
Как соотнести мировые координаты и конкретный блок в мире L2:
1 s# L3 g, X4 n
Центр мира L2 с координатами 0, 0 ВСЕГДА находится в квадрате 20_18. Следовательно этот регион мы можем обозначить как Нулевой Регион.
ZERO_R_X = 20;
/ K5 l8 C" F( ~3 r: D6 N, EZERO_R_Y = 18;
Из загруженных гео-данных, мы можем узнать минимальные и максимальные индексы Регионов. (R_X_MIN, R_Y_MIN, R_X_MAX, R_Y_MAX)
$ @1 C8 \# h% Y% i5 P5 L3 {Как мы помним - размер региона по каждой стороне 32768
$ R* O# D6 U- o$ |. D! F+ D0 n7 ?
0 [3 a/ d0 F( ^) {! P) W, Q8 |  M2 kИмея эти данные, мы можем расчитать координаты противолежащих углов Карты Мира по формулам:
- d! P* y8 D1 Q; E3 p+ OWORLD_MAP_MIN_X = (R_X_MIN - ZERO_R_X) * 32768
WORLD_MAP_MIN_Y = (R_Y_MIN - ZERO_R_Y) * 32768

WORLD_MAP_MAX_X = ((R_X_MAX - ZERO_R_X) + 1) * 32768
( M: S* ?. x+ E. z% cWORLD_MAP_MAX_Y = ((R_Y_MAX - ZERO_R_Y) + 1) * 32768

Вот расчет для High-Five карты мира:
; R2 Z, l( J% z. }WORLD_MAP_MIN_X = (11 - 20) * 32768 = -294912
WORLD_MAP_MIN_Y = (10 - 18) * 32768 = -262144
WORLD_MAP_MAX_X = ((26 - 20) + 1) * 32768 = 229376
WORLD_MAP_MAX_Y = ((26 - 18) + 1) * 32768 = 294912

Т.е карта ХФ представляет из себя прямоугольник с вершинами в точках (-294912, -262144) и (229376, 294912)
+ |) y- L+ @* F! d2 |  I
Теперь самое важное: Как получить блок(или даже ячейку) из координат?
: R3 J' r" x$ Y2 R5 l7 \Вот пошаговые действия для координат XY:
1 k) F8 |9 t  S+ n& l& @% h
Шаг 1) Восстановим координаты региона из мировых
/ i& q5 Z4 Z" r% o+ m, AREGION_X = (x - WORLD_MAP_MIN_X >> 4) >> 11
REGION_Y = (y - WORLD_MAP_MIN_Y >> 4) >> 11

2 O  u! H# z# p4 E3 |  mШаг 2) Определим позицию блока по X и Y внутри региона
1 \# u$ e6 T7 D' {& `( X1 t, SBLOCK_X = ((x - WORLD_MAP_MIN_X >> 4) >> 3) % 256
BLOCK_Y = ((y - WORLD_MAP_MIN_Y >> 4) >> 3) % 256
* Z7 S# p) {/ p3 h) W
Шаг 3) Если искомый блок не плоский, то мы можем получить так же и ячейку.
- `0 f! |9 m9 ?+ h* K6 v1 OCELL_INDEX = (((x - WORLD_MAP_MIN_X >> 4) % 8) << 3) + (((y - WORLD_MAP_MIN_Y >> 4) % 8) % 8)