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

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

Общая структура и описание:
' j+ y; g) |+ D8 o& tИгровой мир в L2 описывается тремя координатами. XYZ.
6 @$ \& Q  @+ O1 \/ C; Z3 ]Ось X это направление Запад-Восток(Уменьшение координаты X - это движение на Запад, следовательно увеличение X - движение на Восток)
Ось Y это направление Север-Юг(Уменьшение координаты Y - это движение на Север, следовательно увеличение Y - движение на Юг)
: e+ L) I  p5 F1 c* x9 L- I5 AОсь Z это высота. Из-за особенностей хранения гео-данных на PTS сервере, высота ограничена диапазоном 16 битного значения (От -16384 до 16383)

3 C( k7 r; s' xКоординатная сетка очень плотно связана с геодатой. Далее в тексте, если специально не указано иное, то следует считать, что описания даются в плоскости XY.
5 u7 x( D7 l* X& w% cИгровой мир делится на Регионы. Обычный Регион представляет из себя квадрат, с размерами 32768 x 32768 точек
  L- m7 r+ z* b4 ^% vРегион в свою очередь делится на 65535 Блоков(сетка 256х256). Таким образом, размер одного Блока 128 x 128 точек.
& T9 M; u: i9 `  L7 zБлоки бывают трех основных типов(Плоский, Комплексный и Мультислойный). В чем их отличие и особенности я объясню ниже.
6 _) n- }$ ^5 \" t8 @: S- [; D# LКомплексные и Мультислойные Блоки делятся еще на более мелкие элементы - Ячейки. Один Блок вмещает в себе 64 Ячейки в виде сетки 8 х 8. Следовательно одна Ячейка представляет из себя квадрат 16 х 16 точек.
& r4 C* \8 l/ w- g, E7 l" I% DМельчайшим объектом мира L2 является Точка. Каждая Точка имеет координаты XYZ.

Как хранятся и обрабатываются геоданные на PTS сервере:
Для хранения геоданных, PTS-сервер использует бинарные файлы, в формате X_Y_conv.dat, где X и Y это номера Региона.
# i2 k% K$ E3 |: t- GТ.к бинарные файлы подразумевают хранение данных в виде массива байт, то для получения каких-то данных, в большинстве случаев происходит сбор чисел больших диапазонов из определенного количества байт.
6 s0 o: i+ h5 UПервые 18 байт каждого файла геоданных содержат так называемый Заголовок:
% o. c9 |3 h% y4 H- ?/ Q4 U# E0 байт - X региона
7 v, O/ w1 ^' p/ Z4 p$ |1 байт - Y региона
: [8 ~, K- g( L7 W* V2-5 байты остались для меня загадкой, я подозреваю что это два 16 битных значения, но их смысл не понятен, т.к они не изменяются.
6-9 байты образуют 32 битное значение, которое хранит в себе количество Ячеек в регионе.
10-13 байты образуют 32 битное значение, которое хранит в себе количество НЕ Мультислойных блоков в регионе
14-17 байты образуют 32 битное значение, которое хранит в себе количество ПЛОСКИХ блоков в регионе.
5 L5 i0 [1 f7 J1 _& X- a
Дальше хранится информация о самих блоках региона по порядку от 0 до 65534 позиции.
Для удобства восприятия, я буду считать восемнадцатый байт файла региона как нулевой по индексу.
0 и 1 байты хранят 16 битное значение, которое указывает на тип блока.
0x00 - Это Плоский блок. Размер данных 4 байта.
0 c) X. K3 c# R) h) a. d" H) z0x40 - Комплексный блок. Размер данных 128 байт.
ВСЕ остальные это Мультислойный блок(В этом случае, тип также указывает еще и на размер блока: Тип * 2 + 65)
! a+ P; W' B0 u
  A, f" X5 P: F( V, @Как и какая информация хранится в Блоке?
Для этого нужно небольшое отступление. В мире L2 за возможность движения в определенном направлении, сквозь Ячейку, отвечает еще одна ее характеристика, условно обозначенная как NSWE. Это битовая маска в диапазоне от 0 до 15 включительно.
Что она означает? Это аббревиатура состоящая из первых букв сторон света: North South West East

0 - Движение через ячейку запрещено.
1 - E (1 << 0) Движение на Восток X+
2 - W (1 << 1) Движение на Запад X-
$ r& s! L) U5 @" a* \3 - WE (W | E) X+ || X-
6 E8 r# d+ n$ Z2 l9 o4 - S (1 << 2) Движение на Юг Y+
" ?& r1 C) N+ c. Z5 J5 - SE (S | E) X+ && Y+
6 - SW (S | W) X- && Y+
7 - SWE (S | W | E) (X- || X+) && Y+
8 - N (1 << 3) Движение на Север Y-
9 - NE (N | E) X+ && Y-
10 - NW (N | W) X- && Y-
11 - NWE (N | W | E) (X- || X+) && Y-
12 - NS (N | S) Y- || Y+
13 - NSE (N | S | E) (Y- || Y+) && X+
* \  x  D- G+ W7 x2 C5 J+ B( R4 R14 - NSW (N | S | W) (Y- || Y+) && X-
6 g& u" _$ _( \2 `' i8 x) j% C* d% Q15 - NSWE (N | S | W | E) X- || X+ || Y- || Y+

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

8 }! |5 e8 p: {! v- @8 zВернемся к блоку. Что в нем хранится? Каждый тип Блока хранит данные по своему. Разберем их поочереди.
7 ?5 \( v+ X3 H& R( ?7 A- ^Плоский Блок - Т.к этот тип блока не делится на Ячейки, то значение проходимости общее для всех координат блока(и на PTS это всегда 15, т.е Плоский блок всегда проходим. Плоский блок НЕ ХРАНИТ NSWE). Мы знаем, что размер Плоского блока - 4 байта. Это два 16 битных значения. Каждое значение содержит в себе высоту этого блока в формате ( byte1 << 8 | byte0 & 0xff) & 0x0fff0)
+ U  G) E  t- Y) b% c3 l! N4 t: JКомплексный Блок - Т.к этот блок разделен на 64 ячейки, а общий размер блока 128 байт, то мы легко вычисляем, что каждая ячейка блока содержит два байта, которые в свою очередь собираются в 16 битное значение.
Как из одного значения получить NSWE и высоту? Для этого нужно использовать следующую формулу:
Высота - ( ( byte1 << 8 | byte0 & 0xff) & 0x0fff0) >> 1 (т.е фактически деление пополам исходного значения)
NSWE - ( ( byte1 << 8 | byte0 & 0xff) & 0x0F) (т.е фактически мы берем младшие разряды числа)
Мультислойный Блок - Представляет из себя по сути Комплексный блок, но каждая ячейка которого может содержать как одно, так и несколько значений-слоев(в каждом значении будет зашифрована собственная высота и NSWE)
! g% h+ D; \. U% f6 O' I
, Z7 A" t2 ], OКак соотнести мировые координаты и конкретный блок в мире L2:

6 z& z* k  [. Y, g/ K  @3 q+ b( a; KЦентр мира L2 с координатами 0, 0 ВСЕГДА находится в квадрате 20_18. Следовательно этот регион мы можем обозначить как Нулевой Регион.
, e" Z8 ~5 V8 U& y* t. TZERO_R_X = 20;
ZERO_R_Y = 18;
/ D0 t0 J& u  V+ j0 z# m  \  ZИз загруженных гео-данных, мы можем узнать минимальные и максимальные индексы Регионов. (R_X_MIN, R_Y_MIN, R_X_MAX, R_Y_MAX)
, K. L; i( t. K* J3 b1 Y, vКак мы помним - размер региона по каждой стороне 32768

( ^3 ?6 q# q$ D  y1 m9 h) r& C6 QИмея эти данные, мы можем расчитать координаты противолежащих углов Карты Мира по формулам:
# A9 ]6 E' ]3 V0 j1 ~4 I' X7 nWORLD_MAP_MIN_X = (R_X_MIN - ZERO_R_X) * 32768
0 j: y& I' ^& Z) i5 j% N6 vWORLD_MAP_MIN_Y = (R_Y_MIN - ZERO_R_Y) * 32768
  r7 _9 n5 `% @( I: }$ j
0 Y1 t0 v7 e" Y- K3 |7 Y# lWORLD_MAP_MAX_X = ((R_X_MAX - ZERO_R_X) + 1) * 32768
# Q, J0 M7 d+ }* eWORLD_MAP_MAX_Y = ((R_Y_MAX - ZERO_R_Y) + 1) * 32768
0 `/ G3 K  H1 t: @" C6 `! M
$ T2 y% C$ b' r2 H1 cВот расчет для High-Five карты мира:
8 @: M, \0 N, Q2 Q! ]; f3 U* l6 q3 VWORLD_MAP_MIN_X = (11 - 20) * 32768 = -294912
) p2 |, C2 p* ?0 i9 F$ i+ aWORLD_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
, D# \3 R/ O3 a3 D
: b# ~9 p# L1 ?' B2 X4 Y8 wТ.е карта ХФ представляет из себя прямоугольник с вершинами в точках (-294912, -262144) и (229376, 294912)

Теперь самое важное: Как получить блок(или даже ячейку) из координат?
) v( i( j- ^) S- q% nВот пошаговые действия для координат XY:
* W( [, [' E# ~1 r0 X% V
8 L% y$ X/ L5 C4 ]/ dШаг 1) Восстановим координаты региона из мировых
REGION_X = (x - WORLD_MAP_MIN_X >> 4) >> 11
7 L' q6 y  a' n# Z* W$ T* F8 |REGION_Y = (y - WORLD_MAP_MIN_Y >> 4) >> 11
2 Y6 H* J: |' z. J+ X9 _4 p9 F
Шаг 2) Определим позицию блока по X и Y внутри региона
8 t0 M. Z6 R6 _BLOCK_X = ((x - WORLD_MAP_MIN_X >> 4) >> 3) % 256
# c$ R, p1 g* l! WBLOCK_Y = ((y - WORLD_MAP_MIN_Y >> 4) >> 3) % 256
$ ?- [7 A5 F8 O+ `2 c- O
Шаг 3) Если искомый блок не плоский, то мы можем получить так же и ячейку.
+ D! [  K4 o5 V8 S& |9 t# XCELL_INDEX = (((x - WORLD_MAP_MIN_X >> 4) % 8) << 3) + (((y - WORLD_MAP_MIN_Y >> 4) % 8) % 8)
5 p  a! L# m$ [7 J! m