Геодата и алгоритмы поиска путей в Lineage II

Корректная геодата исключает атаки сквозь стены (shoot-through-walls), падения под текстуры и застревания NPC.

Структура геодаты

Мир Lineage II разделен на регионы (квадраты карты от 11_10 до 26_26). Каждый регион содержит:

• Размер региона: 256x256 блоков геодаты.
• Типы блоков:

1. Flat Block (Тип 0): Однородная плоскость, занимает 3 байта (базовая высота Z).

2. Complex Block (Тип 64): 64 ячейки (8x8), каждая хранит локальную высоту и флаги направлений проходимости (N, S, W, E).

3. Multilayer Block (Тип 128): Многослойные мосты, крыши, этажи башен Крумы. Содержит переменное число слоев на ячейку.

Оптимизация Pathfinding (A* & Cell Graph)

Для расчета маршрутов мобов и персонажей используется модифицированный алгоритм A*:

• Ограничение глубины поиска: Не более 350-500 итераций для предотвращения спайков CPU.
• Сглаживание узлов (String Pulling): Удаление избыточных зигзагообразных точек маршрута прямой проверкой видимости canSeeTarget(start, end).