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

Aristo · 3 Дек 2023

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

Общая структура и описание:
Игровой мир в L2 описывается тремя координатами. XYZ.
Ось X это направление Запад-Восток(Уменьшение координаты X - это движение на Запад, следовательно увеличение X - движение на Восток)
Ось Y это направление Север-Юг(Уменьшение координаты Y - это движение на Север, следовательно увеличение Y - движение на Юг)
Ось Z это высота. Из-за особенностей хранения гео-данных на PTS сервере, высота ограничена диапазоном 16 битного значения (От -16384 до 16383)

Координатная сетка очень плотно связана с геодатой. Далее в тексте, если специально не указано иное, то следует считать, что описания даются в плоскости XY.
Игровой мир делится на Регионы. Обычный Регион представляет из себя квадрат, с размерами 32768 x 32768 точек
Регион в свою очередь делится на 65535 Блоков(сетка 256х256). Таким образом, размер одного Блока 128 x 128 точек.
Блоки бывают трех основных типов(Плоский, Комплексный и Мультислойный). В чем их отличие и особенности я объясню ниже.
Комплексные и Мультислойные Блоки делятся еще на более мелкие элементы - Ячейки. Один Блок вмещает в себе 64 Ячейки в виде сетки 8 х 8. Следовательно одна Ячейка представляет из себя квадрат 16 х 16 точек.
Мельчайшим объектом мира L2 является Точка. Каждая Точка имеет координаты XYZ.

Как хранятся и обрабатываются геоданные на PTS сервере:
Для хранения геоданных, PTS-сервер использует бинарные файлы, в формате X_Y_conv.dat, где X и Y это номера Региона.
Т.к бинарные файлы подразумевают хранение данных в виде массива байт, то для получения каких-то данных, в большинстве случаев происходит сбор чисел больших диапазонов из определенного количества байт.
Первые 18 байт каждого файла геоданных содержат так называемый Заголовок:
0 байт - X региона
1 байт - Y региона
2-5 байты остались для меня загадкой, я подозреваю что это два 16 битных значения, но их смысл не понятен, т.к они не изменяются.
6-9 байты образуют 32 битное значение, которое хранит в себе количество Ячеек в регионе.
10-13 байты образуют 32 битное значение, которое хранит в себе количество НЕ Мультислойных блоков в регионе
14-17 байты образуют 32 битное значение, которое хранит в себе количество ПЛОСКИХ блоков в регионе.

Дальше хранится информация о самих блоках региона по порядку от 0 до 65534 позиции.
Для удобства восприятия, я буду считать восемнадцатый байт файла региона как нулевой по индексу.
0 и 1 байты хранят 16 битное значение, которое указывает на тип блока.
0x00 - Это Плоский блок. Размер данных 4 байта.
0x40 - Комплексный блок. Размер данных 128 байт.
ВСЕ остальные это Мультислойный блок(В этом случае, тип также указывает еще и на размер блока: [Тип * 2 + 64 * 2 + 2]

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

0 - Движение через ячейку запрещено.
1 - E (1 << 0) Движение на Восток X+
2 - W (1 << 1) Движение на Запад X-
3 - WE (W | E) X+ || X-
4 - S (1 << 2) Движение на Юг Y+
5 - 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+
14 - NSW (N | S | W) (Y- || Y+) && X-
15 - NSWE (N | S | W | E) X- || X+ || Y- || Y+

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

Вернемся к блоку. Что в нем хранится? Каждый тип Блока хранит данные по своему. Разберем их поочереди.
Плоский Блок - Т.к этот тип блока не делится на Ячейки, то значение проходимости общее для всех координат блока(и на PTS это всегда 15, т.е Плоский блок всегда проходим. Плоский блок НЕ ХРАНИТ NSWE). Мы знаем, что размер Плоского блока - 4 байта. Это два 16 битных значения. Каждое значение содержит в себе высоту этого блока в формате ( byte1 << 8 | byte0 & 0xff) & 0x0fff0)
Комплексный Блок - Т.к этот блок разделен на 64 ячейки, а общий размер блока 128 байт, то мы легко вычисляем, что каждая ячейка блока содержит два байта, которые в свою очередь собираются в 16 битное значение.
Как из одного значения получить NSWE и высоту? Для этого нужно использовать следующую формулу:
Высота - ( ( byte1 << 8 | byte0 & 0xff) & 0x0fff0) >> 1 (т.е фактически деление пополам исходного значения)
NSWE - ( ( byte1 << 8 | byte0 & 0xff) & 0x0F) (т.е фактически мы берем младшие разряды числа)
Мультислойный Блок - Представляет из себя по сути Комплексный блок, но каждая ячейка которого может содержать как одно, так и несколько значений-слоев(в каждом значении будет зашифрована собственная высота и NSWE)

Как соотнести мировые координаты и конкретный блок в мире L2:

Центр мира L2 с координатами 0, 0 ВСЕГДА находится в квадрате 20_18. Следовательно этот регион мы можем обозначить как Нулевой Регион.
ZERO_R_X = 20;
ZERO_R_Y = 18;
Из загруженных гео-данных, мы можем узнать минимальные и максимальные индексы Регионов. (R_X_MIN, R_Y_MIN, R_X_MAX, R_Y_MAX)
Как мы помним - размер региона по каждой стороне 32768

Имея эти данные, мы можем расчитать координаты противолежащих углов Карты Мира по формулам:
WORLD_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
WORLD_MAP_MAX_Y = ((R_Y_MAX - ZERO_R_Y) + 1) * 32768

Вот расчет для High-Five карты мира:
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)

Теперь самое важное: Как получить блок(или даже ячейку) из координат?
Вот пошаговые действия для координат XY:

Шаг 1) Восстановим координаты региона из мировых
REGION_X = (x - WORLD_MAP_MIN_X >> 4) >> 11
REGION_Y = (y - WORLD_MAP_MIN_Y >> 4) >> 11

Шаг 2) Определим позицию блока по X и Y внутри региона
BLOCK_X = ((x - WORLD_MAP_MIN_X >> 4) >> 3) % 256
BLOCK_Y = ((y - WORLD_MAP_MIN_Y >> 4) >> 3) % 256

Шаг 3) Если искомый блок не плоский, то мы можем получить так же и ячейку.
CELL_INDEX = (((x - WORLD_MAP_MIN_X >> 4) % 8) << 3) + (((y - WORLD_MAP_MIN_Y >> 4) % 8) % 8)

Я не педагог и не писатель. Заранее прошу прощения за сумбур в изложении.

space2pacman · 17 Фев 2025

Поправка

ВСЕ остальные это Мультислойный блок(В этом случае, тип также указывает еще и на размер блока: Тип * 2 + 65)

Не Тип * 2 + 65

А (Тип + 65) * 2

0x4F = 79
В красном квадрате 17 блоков (17 * 16 байт) = 272
В нижнем еще 16 байт
272 + 16 = 288

Формула: (Тип + 65) * 2
(79 + 65) * 2 = 288

Aristo · 17 Фев 2025

space2pacman написал(а):
Поправка

Не Тип * 2 + 65

А (Тип + 65) * 2

Посмотреть вложение 84477

0x4F = 79
В красном квадрате 17 блоков (17 * 16 байт) = 272
В нижнем еще 16 байт
272 + 16 = 288

Формула: (Тип + 65) * 2
(79 + 65) * 2 = 288

структура мультиблока следующая.
2 байта - заголовок.
128 байт - метадата 64 ячеек(т.е по 2 байта на количество ячеек на XY)
+ по 2 байта на каждую ячейку(на каждый слой).

Минимальный размер мультислойного блока: 2 байта заголовок + 128 байт метадата + 130 байт дата(63 ячейки по 1 слою(2 байта дата ячейки) на индекс и минимум 1 на 2 ячейки(2 байта дата ячейки х2). Итого 196 байта данных + 2 байта заголовок(64 ячеек(65 слоев), в заголовке 65).
Максимальный размер мультислойного блока: 2 байта заголовок + 64 байта метадата + 32 640 байт дата(64 ячейки по 255 ячеек(510 байт на ячейку)). Итого 32 704 байта данных + 2 байта заголовок в котором(64 ячейки(16320 слоев) в заголовке 16320)

Фактически ячейки пишутся последовательно:
[short][short;{short0},{short1}],[short;{short0},{short1}{short2},{short3},{short4}],[short;{short0}]

Т.е у меня опечатка в мануале, что там Тип * 2 + 65, когда правильно 64*2 + (cell_count * 2)

Т.е фактически цикл парса мультиблока выглядит вот так:

1) Читаем заголовок. Видим например 0x4F(79).
2) Получаем 79 ячеек.
3) Считываем метадату 0 ячейки(2 байта(short): Получаем например 2. Это значит что там 2 слоя по 2 байта. Вычитываем 4 байта даты.
4) Читаем метадату ячейки 1(2 байта(short)): Получаем например 5. Это означает что эта ячейка содержит 5 слоев по 2 байта. Вычитываем 10 байт даты.
5) Повторять до 63 ячейки включительно.
6) Сверяем количество ячеек фактически в слоях, с ячейками из заголовка и видим, что их количество совпадает. Заголовок нам нужен по сути только для идентификации типа сектора, чтобы корректно его считать.

space2pacman · 17 Фев 2025

Aristo написал(а):
структура мультиблока следующая. 02 00 8C E4
2 байта - заголовок.
128 байт - метадата 64 ячеек(т.е по 2 байта на количество ячеек на XY)
+ по 2 байта на каждую ячейку(на каждый слой).

Минимальный размер мультислойного блока: 2 байта заголовок + 64 байта метадата + 130 байт дата(63 ячейки по 1 слою(2 байта дата ячейки) на индекс и минимум 1 на 2 ячейки(2 байта дата ячейки х2). Итого 196 байта данных + 2 байта заголовок(64 ячеек(65 слоев), в заголовке 65).
Максимальный размер мультислойного блока: 2 байта заголовок + 64 байта метадата + 32 640 байт дата(64 ячейки по 255 ячеек(510 байт на ячейку)). Итого 32 704 байта данных + 2 байта заголовок в котором(64 ячейки(16320 слоев) в заголовке 16320)

Фактически ячейки пишутся последовательно:
[short][short;{short0},{short1}],[short;{short0},{short1}{short2},{short3},{short4}],[short;{short0}]

Т.е у меня опечатка в мануале, что там Тип * 2 + 65, когда правильно 64 + (cell_count * 2)

Т.е фактически цикл парса мультиблока выглядит вот так:

1) Читаем заголовок. Видим например 0x4F(79).
2) Получаем 79 ячеек.
3) Считываем метадату 0 ячейки(2 байта(short): Получаем например 2. Это значит что там 2 слоя по 2 байта. Вычитываем 4 байта даты.
4) Читаем метадату ячейки 1(2 байта(short)): Получаем например 5. Это означает что эта ячейка содержит 5 слоев по 2 байта. Вычитываем 10 байт даты.
5) Повторять до 63 ячейки включительно.
6) Сверяем количество ячеек фактически в слоях, с ячейками из заголовка и видим, что их количество совпадает. Заголовок нам нужен по сути только для идентификации типа сектора, чтобы корректно его считать.

Спасибо за подробный ответ. Ведь это же работает (Тип + 65) * 2
Или это может не работать на других блоках где больше данных?

Правильней будет так?
Заходить в мультиблок. Проходит циклом. Считать ячейки. Умножить ячейки на 2 и прибавить 64

Aristo · 17 Фев 2025

space2pacman написал(а):
Спасибо за подробный ответ. Ведь это же работает (Тип + 65) * 2
Или это может не работать на других блоках где больше данных?

Правильней будет так?
Заходить в мультиблок. Проходит циклом. Считать ячейки. Умножить ячейки на 2 и прибавить 64

С какой целью вам знать количество слоев? Эти данные только для валидации нужны по сути, что вы все правильно считали(чтобы сопоставить с данными из хидера), ну и для ускорения процесса парса, когда вы можете читать данные сразу всего блока целиком и асинхронно его обрабатывать.

Ячеек может быть 0, 64 и >64.
0 это условно плоский блок.
64 комплексный блок(это условное разделение, означающее то, что нет дополнительных метаданных и на каждый индекс просто по 2 байта даты(т.е 1 ячейка))
>64 это мультиблок(опять же условное разделение, означающее, что каждый индекс содержит дополнительные 2 байта метаданных, с количеством ячеек в этом индексе, и ячеек может быть больше одной для любого из индексов). Сами ячейки как были 2 байта, так и остались.

space2pacman · 17 Фев 2025

Aristo написал(а):
С какой целью вам знать количество слоев? Эти данные только для валидации нужны по сути, что вы все правильно считали(чтобы сопоставить с данными из хидера), ну и для ускорения процесса парса, когда вы можете читать данные сразу всего блока целиком и асинхронно его обрабатывать.

Ячеек может быть 0, 64 и >64.
0 это условно плоский блок.
64 комплексный блок(это условное разделение, означающее то, что нет дополнительных метаданных и на каждый индекс просто по 2 байта даты(т.е 1 ячейка))
>64 это мультиблок(опять же условное разделение, означающее, что каждый индекс содержит дополнительные 2 байта метаданных, с количеством ячеек в этом индексе, и ячеек может быть больше одной для любого из индексов). Сами ячейки как были 2 байта, так и остались.

С целью пропустить этот блок на время теста

Aristo написал(а):
С какой целью вам знать количество слоев? Эти данные только для валидации нужны по сути, что вы все правильно считали(чтобы сопоставить с данными из хидера), ну и для ускорения процесса парса, когда вы можете читать данные сразу всего блока целиком и асинхронно его обрабатывать.

Ячеек может быть 0, 64 и >64.
0 это условно плоский блок.
64 комплексный блок(это условное разделение, означающее то, что нет дополнительных метаданных и на каждый индекс просто по 2 байта даты(т.е 1 ячейка))
>64 это мультиблок(опять же условное разделение, означающее, что каждый индекс содержит дополнительные 2 байта метаданных, с количеством ячеек в этом индексе, и ячеек может быть больше одной для любого из индексов). Сами ячейки как были 2 байта, так и остались.

Правильно ли я понял, что в мультеблоке если к примеру идет 02 00 8C E4 88 E3 это два слоя? Ячейка над другой ячейкой

Если 05 00 00 .... Это 5 слоев и т.д.?

Минимальный размер мультислойного блока: 2 байта заголовок + 64 байта метадата

128 байт - метадата 64 ячеек(т.е по 2 байта на количество ячеек на XY)

64 или 128 все же?

Aristo · 17 Фев 2025

space2pacman написал(а):
Правильно ли я понял, что в мультеблоке если к примеру идет 02 00 8C E4 88 E3 это два слоя? Ячейка над другой ячейкой

Если 05 00 00 .... Это 5 слоев и т.д.?

64 или 128 все же?

Размер мультиблока я считаю вот так у себя:

Java:

IGeoSector.CELLS_IN_SECTOR * 2 * Short.BYTES + (sector_cell_count - IGeoSector.CELLS_IN_SECTOR) * Short.BYTES

Где IGeoSector.CELLS_IN_SECTOR = 64, а sector_cell_count это количество ячеек из заголовка.

space2pacman написал(а):
64 или 128 все же?

128) Сам уже запутался, потому что перестраиваю стуктуру блока на лету для экономии места и храню количество ячеек в 1 байте, а не в 2, как корейцы

Я мультиблок храню для удобства в другом виде: Сначала метадата всех ячеек, а в потом данные всех ячеек. Это позволяет чутка сократить количество запросов к буферу, и скорость чуть выше, т.к данные локализованы лучше в памяти и неплохо кешируются процессором

space2pacman · 17 Фев 2025

Aristo написал(а):
128) Сам уже запутался, потому что перестраиваю стуктуру блока на лету для экономии места и храню количество ячеек в 1 байте, а не в 2, как корейцы

Вернувшись в формуле. На время теста эта формула будет верна (Тип + 65) * 2 ? Или надо все же в блок заходить и считать ячейки.

А что у вас за проект если не секрет?

Aristo · 17 Фев 2025

space2pacman написал(а):
Вернувшись в формуле. На время теста эта формула будет верна (Тип + 65) * 2 ? Или надо все же в блок заходить и считать ячейки.

IGeoSector.CELLS_IN_SECTOR * 2 * Short.BYTES + (sector_cell_count - IGeoSector.CELLS_IN_SECTOR) * Short.BYTES

64 * 2 * 2 + (79 - 64) * 2 = 286
+ 2 байта заголовок = 288

128(метадата) + 79(cell_count) * 2 = 286
+ 2 байта заголовок = 288

(79 + 65) * 2 = 288

space2pacman написал(а):
А что у вас за проект если не секрет?

Нет проекта. Просто разработка эмулятора приватная.

MrKirill1232 · 17 Фев 2025

У меня считается так -

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

Где используется -

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

initial size для Multilevel -

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

В теории, можно самому посчитать вот так:

Java:

MultilevelBlock block;
int blockSize;
for (int xCell = 0; xCell < 8; xCell++)
{
    for (int yCell = 0; yCell < 8; yCell++)
    {
        CellInfo cellInfo = block.getCell(xCell, yCell);
        blockSize = blockSize + Short.BYTES + (cellInfo.getLayers() * (Short.BYTES + Byte.BYTES));
    }
}
return (64 + (blockSize - (256 / 2)))

space2pacman · 17 Фев 2025

space2pacman написал(а):
Поправка

Не Тип * 2 + 65

А (Тип + 65) * 2

Посмотреть вложение 84477

0x4F = 79
В красном квадрате 17 блоков (17 * 16 байт) = 272
В нижнем еще 16 байт
272 + 16 = 288

Формула: (Тип + 65) * 2
(79 + 65) * 2 = 288

UPD: 65 не помогло. Видимо от файла к файлу свои какие-то подводные камни. Подставил 64 и все заработало(без мультиблоков, я их пропускаю для теста)

UPD 2: моя ошибка. Я нижни ряд в скриншоте почему-то за 16 байт посчитал а там 14.

Все верно тогда (79 + 64) * 2 = 286
Или (17 * 16) + 14 = 286

Aristo · 17 Фев 2025

space2pacman написал(а):
UPD: 65 не помогло. Видимо от файла к файлу свои какие-то подводные камни. Подставил 64 и все заработало(без мультиблоков, я их пропускаю для теста)

Я надеюсь мы с вами про _conv.dat файлы говорим, а не про l2j?

space2pacman · 17 Фев 2025

Aristo написал(а):
Я надеюсь мы с вами про _conv.dat файлы говорим, а не про l2j?

Да про него. Я в процессе теста конвертировал разные даты из l2j > conv или подставлял оригинальные и искал закономерности.

Теперь понял, что я не так посчитал и все встало на свои места. Без обсчета мультиблока можно его пропускать опираясь на (Тип + 64) * 2

UPD: все же файл влияет. Я пока не помню как его получил но второй файл идеально генерирует 256 на 256 блоков. Подставляю старый и все "едет". Видимо без просчета мультиблока никак.

UPD2: Файл оригинального сервера парсится идеально.
Для файла, который был получен путем конвертирования - формула (Тип + 64) * 2 не подходит.

Aristo · 17 Фев 2025

space2pacman написал(а):
Да про него. Я в процессе теста конвертировал разные даты из l2j > conv или подставлял оригинальные и искал закономерности.

Теперь понял, что я не так посчитал и все встало на свои места. Без обсчета мультиблока можно его пропускать опираясь на (Тип + 64) * 2

Да. Я просто объяснил как формируется размер. Это 2 байта заголовок + 128 байт метаданных и по 2 байта на каждую ячейку.
(Тип + 64) * 2 == (Тип * 2) + (64 * 2) == Тип * 2 + 128

space2pacman · 17 Фев 2025

Aristo написал(а):
Да. Я просто объяснил как формируется размер. Это 2 байта заголовок + 128 байт метаданных и по 2 байта на каждую ячейку.
(Тип + 64) * 2 == (Тип * 2) + (64 * 2) == Тип * 2 + 128

Для конвертируемого файла из l2j я так понимаю не пройдет?
_conv.dat формат имеет одинаковый или могут с погрешностями конвертировать? Есть инфа?

MrKirill1232 · 17 Фев 2025

space2pacman написал(а):
конвертировать? Есть инфа

Полностью рабочий :\
Парси/Сохраняй/Интегрируй

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

space2pacman · 17 Фев 2025

MrKirill1232 написал(а):
Полностью рабочий :\
Парси/Сохраняй/Интегрируй

Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация

Про проект спасибо) Сурсы изучил. Мне ее не только конвертитьвать надо но и подгружать в свой сервер :pandaredlol:

MrThirtyOddSix · 17 Фев 2025

Если сравнить формат L2J, какая будет разница? Я так понимаю что метадаты там не будет, а все остальное будет похоже на cov формат.

space2pacman · 17 Фев 2025

MrThirtyOddSix написал(а):
Если сравнить формат L2J, какая будет разница? Я так понимаю что метадаты там не будет, а все остальное будет похоже на cov формат.

Знаю только размер меньше немного у L2J.

MrKirill1232 · 17 Фев 2025

MrThirtyOddSix написал(а):
Если сравнить формат L2J, какая будет разница? Я так понимаю что метадаты там не будет, а все остальное будет похоже на cov формат.

в conv dat две высоты для flat блоков
в l2d отдельно записывается и просчитывается nswe
та и все

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

Легендарный

Постоялец

Легендарный

Постоялец

Легендарный

Постоялец

Легендарный

Постоялец

Легендарный

Великий мудрец

Постоялец

Легендарный

Постоялец

Легендарный

Постоялец

Великий мудрец

Постоялец

Пляшущий с бубном

Постоялец

Великий мудрец