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

Всем привет.
Хочу поделится информацией базовых принципах хранения и обработки геоданных, а также о том, как это связано с координатной сеткой.
Сразу скажу, я пишу этот мануал в разделе PTS сервера, но он одинаково справедлив(кроме описанной структуры хранения геоданных!) для любой сборки.

0 t$ {1 F# o7 u) t0 {* a) R3 jОбщая структура и описание:
. m5 L) J# T! }9 }4 v5 BИгровой мир в L2 описывается тремя координатами. XYZ.
Ось X это направление Запад-Восток(Уменьшение координаты X - это движение на Запад, следовательно увеличение X - движение на Восток)
& z+ [" m9 f. b/ e% D" d, MОсь Y это направление Север-Юг(Уменьшение координаты Y - это движение на Север, следовательно увеличение Y - движение на Юг)
  _  _6 b' o" a3 W7 qОсь Z это высота. Из-за особенностей хранения гео-данных на PTS сервере, высота ограничена диапазоном 16 битного значения (От -16384 до 16383)
& A1 u" g! x9 m
Координатная сетка очень плотно связана с геодатой. Далее в тексте, если специально не указано иное, то следует считать, что описания даются в плоскости XY.
. o$ G' Q% Q; C! ?2 iИгровой мир делится на Регионы. Обычный Регион представляет из себя квадрат, с размерами 32768 x 32768 точек
1 k, P& ~& g0 w  F5 V9 N) SРегион в свою очередь делится на 65535 Блоков(сетка 256х256). Таким образом, размер одного Блока 128 x 128 точек.
* |* G3 c1 C0 z* ^3 ^" p9 kБлоки бывают трех основных типов(Плоский, Комплексный и Мультислойный). В чем их отличие и особенности я объясню ниже.
Комплексные и Мультислойные Блоки делятся еще на более мелкие элементы - Ячейки. Один Блок вмещает в себе 64 Ячейки в виде сетки 8 х 8. Следовательно одна Ячейка представляет из себя квадрат 16 х 16 точек.
2 ^" v* k6 }5 dМельчайшим объектом мира L2 является Точка. Каждая Точка имеет координаты XYZ.

Как хранятся и обрабатываются геоданные на PTS сервере:
Для хранения геоданных, PTS-сервер использует бинарные файлы, в формате X_Y_conv.dat, где X и Y это номера Региона.
Т.к бинарные файлы подразумевают хранение данных в виде массива байт, то для получения каких-то данных, в большинстве случаев происходит сбор чисел больших диапазонов из определенного количества байт.
5 s) J% q* X  L! N3 DПервые 18 байт каждого файла геоданных содержат так называемый Заголовок:
0 байт - X региона
6 K0 E0 ~! X4 n- f' J* O1 байт - Y региона
8 E0 O3 l& J8 M7 _5 ?, V2-5 байты остались для меня загадкой, я подозреваю что это два 16 битных значения, но их смысл не понятен, т.к они не изменяются.
6-9 байты образуют 32 битное значение, которое хранит в себе количество Ячеек в регионе.
' J- i, t7 V: H1 \10-13 байты образуют 32 битное значение, которое хранит в себе количество НЕ Мультислойных блоков в регионе
14-17 байты образуют 32 битное значение, которое хранит в себе количество ПЛОСКИХ блоков в регионе.
! M) j; A6 U; \# f) m
/ e' e2 v' k5 a- K/ y- LДальше хранится информация о самих блоках региона по порядку от 0 до 65534 позиции.
Для удобства восприятия, я буду считать восемнадцатый байт файла региона как нулевой по индексу.
/ {* l1 u; V* c5 ?0 и 1 байты хранят 16 битное значение, которое указывает на тип блока.
0x00 - Это Плоский блок. Размер данных 4 байта.
( @9 B  {' J8 ~1 W! S0x40 - Комплексный блок. Размер данных 128 байт.
9 Z0 }% J9 Y6 N1 Q7 qВСЕ остальные это Мультислойный блок(В этом случае, тип также указывает еще и на размер блока: Тип * 2 + 65)
5 y4 `! o  |2 I+ V
Как и какая информация хранится в Блоке?
& d1 a. o9 n; _! A3 @3 Q! }: B! lДля этого нужно небольшое отступление. В мире L2 за возможность движения в определенном направлении, сквозь Ячейку, отвечает еще одна ее характеристика, условно обозначенная как NSWE. Это битовая маска в диапазоне от 0 до 15 включительно.
7 J0 U! u; e  LЧто она означает? Это аббревиатура состоящая из первых букв сторон света: North South West East

0 - Движение через ячейку запрещено.
6 g% K0 |6 B. h0 G; |: E1 - E (1 << 0) Движение на Восток X+
2 - W (1 << 1) Движение на Запад X-
3 - WE (W | E) X+ || X-
+ L! u# C# c) l$ b: t7 w: f4 - S (1 << 2) Движение на Юг Y+
6 S9 g' ~" Z! I: |! O5 - SE (S | E) X+ && Y+
) ^3 u- b6 n3 z7 N7 N) D6 - SW (S | W) X- && Y+
7 - SWE (S | W | E) (X- || X+) && Y+
8 - N (1 << 3) Движение на Север Y-
% E2 j7 w3 T: B9 - NE (N | E) X+ && Y-
10 - NW (N | W) X- && Y-
11 - NWE (N | W | E) (X- || X+) && Y-
3 N* d6 i$ x2 p6 i' v7 \) s$ C2 {12 - NS (N | S) Y- || Y+
% p: \! r1 T! q& L" I13 - NSE (N | S | E) (Y- || Y+) && X+
14 - NSW (N | S | W) (Y- || Y+) && X-
15 - NSWE (N | S | W | E) X- || X+ || Y- || Y+

Т.е условно, если у вас персонаж стоит в координате 12345, 6789, а вы кликаете в координату 12345, 9876 (т.е Y+) то пройти вы сможете только через те Ячейки, NSWE значение которых удовлетворит выражению:
0 t3 l: _/ Y/ |( ^: s  ?(NSWE & S) == S

8 O5 }% V1 Y( WВернемся к блоку. Что в нем хранится? Каждый тип Блока хранит данные по своему. Разберем их поочереди.
Плоский Блок - Т.к этот тип блока не делится на Ячейки, то значение проходимости общее для всех координат блока(и на PTS это всегда 15, т.е Плоский блок всегда проходим. Плоский блок НЕ ХРАНИТ NSWE). Мы знаем, что размер Плоского блока - 4 байта. Это два 16 битных значения. Каждое значение содержит в себе высоту этого блока в формате ( byte1 << 8 | byte0 & 0xff) & 0x0fff0)
: y( ?4 k# |6 O# IКомплексный Блок - Т.к этот блок разделен на 64 ячейки, а общий размер блока 128 байт, то мы легко вычисляем, что каждая ячейка блока содержит два байта, которые в свою очередь собираются в 16 битное значение.
  G9 {* H. d  E* q2 r) j+ \& }# e) TКак из одного значения получить NSWE и высоту? Для этого нужно использовать следующую формулу:
: S. f  r. t' V7 W+ r: L3 hВысота - ( ( byte1 << 8 | byte0 & 0xff) & 0x0fff0) >> 1 (т.е фактически деление пополам исходного значения)
. B' g) w' G8 ?/ ZNSWE - ( ( byte1 << 8 | byte0 & 0xff) & 0x0F) (т.е фактически мы берем младшие разряды числа)
Мультислойный Блок - Представляет из себя по сути Комплексный блок, но каждая ячейка которого может содержать как одно, так и несколько значений-слоев(в каждом значении будет зашифрована собственная высота и NSWE)

, u  X3 b+ G9 h5 ?* z) I5 ?$ vКак соотнести мировые координаты и конкретный блок в мире L2:
- ?5 R$ e$ Y$ c& u
Центр мира L2 с координатами 0, 0 ВСЕГДА находится в квадрате 20_18. Следовательно этот регион мы можем обозначить как Нулевой Регион.
ZERO_R_X = 20;
ZERO_R_Y = 18;
$ n; F; o( a3 b6 I$ g3 NИз загруженных гео-данных, мы можем узнать минимальные и максимальные индексы Регионов. (R_X_MIN, R_Y_MIN, R_X_MAX, R_Y_MAX)
Как мы помним - размер региона по каждой стороне 32768
' ?- d* K$ w/ W( e2 S6 p
Имея эти данные, мы можем расчитать координаты противолежащих углов Карты Мира по формулам:
7 Q* K9 y. x, W* V- D% x( `WORLD_MAP_MIN_X = (R_X_MIN - ZERO_R_X) * 32768
WORLD_MAP_MIN_Y = (R_Y_MIN - ZERO_R_Y) * 32768
4 Z+ U5 T4 F0 r! x
WORLD_MAP_MAX_X = ((R_X_MAX - ZERO_R_X) + 1) * 32768
WORLD_MAP_MAX_Y = ((R_Y_MAX - ZERO_R_Y) + 1) * 32768

6 q% _% P/ u1 c7 G# ]Вот расчет для High-Five карты мира:
WORLD_MAP_MIN_X = (11 - 20) * 32768 = -294912
, ~+ w( ^) X9 n, s5 ^# r! ~WORLD_MAP_MIN_Y = (10 - 18) * 32768 = -262144
* N4 r, o  a- ^WORLD_MAP_MAX_X = ((26 - 20) + 1) * 32768 = 229376
$ w1 b3 V0 C8 m8 I( w9 |5 M5 S4 NWORLD_MAP_MAX_Y = ((26 - 18) + 1) * 32768 = 294912
" N5 S' k4 S; S6 ~3 m0 X  H
Т.е карта ХФ представляет из себя прямоугольник с вершинами в точках (-294912, -262144) и (229376, 294912)
7 x. D/ m1 d7 y# z3 W
Теперь самое важное: Как получить блок(или даже ячейку) из координат?
4 g; }4 z) ^, G% fВот пошаговые действия для координат XY:

. F8 ~$ W7 m# {' q; g( zШаг 1) Восстановим координаты региона из мировых
REGION_X = (x - WORLD_MAP_MIN_X >> 4) >> 11
REGION_Y = (y - WORLD_MAP_MIN_Y >> 4) >> 11

Шаг 2) Определим позицию блока по X и Y внутри региона
, G$ E. ^2 a, b  yBLOCK_X = ((x - WORLD_MAP_MIN_X >> 4) >> 3) % 256
BLOCK_Y = ((y - WORLD_MAP_MIN_Y >> 4) >> 3) % 256
. b7 O7 o" h! X# i6 `  }
+ z7 W* n) `, ^! ?Шаг 3) Если искомый блок не плоский, то мы можем получить так же и ячейку.
CELL_INDEX = (((x - WORLD_MAP_MIN_X >> 4) % 8) << 3) + (((y - WORLD_MAP_MIN_Y >> 4) % 8) % 8)