AI-Map в X-Ray: теория, практика, ошибки

[Malandrinus 611]

Хочу добавить немного информации по организации AI сетки на уровне формата файла. Думаю, что это может дать представление о принципиальных ограничениях.

- Сетка внутри файла представляет собой линейный массив из всех узлов. Они нумеруются от нуля. Самих узлов может быть теоретически 2 в степени 32, но реально намного меньше, а главное - размер сетки в плане диктуется ещё одним ограничением, которое будет понятно далее.
- Положение отдельного узла задаётся двумя целыми числами: 16 бит для координаты Y по высоте и 24 бита на две упакованные координаты XZ в плане. Назовём эти числа NY и NXZ. Для перевода этих чисел в реальные геометрические координаты (X,Y,Z) в заголовке файла записаны следующие данные:
Размер уровня (точнее сетки) по вертикали, назовём HY
размер элемента сетки по горизонтали (узел сетки квадратный), назовём DXZ
размеры сетки уровня в виде бокса, заданного вектором двух вершин. Назовём их (X0,Y0,Z0) и (X1,Y1,Z1). При этом размер по вертикали HY всегда совпадает с размером, полученным из вычитания этих двух векторов Y1-Y0 (т.е. имеется избыточность данных). Размеры бокса в плане X1-X0 и Z1-Z0 должны быть кратны элементу ячейки в плане DXZ.
Алгоритм перевода упакованных числе в координаты такой:
По вертикали всегда имеем максимально возможное число уровней 65536 (два байта), и соответственно минимальный шаг по вертикали будет
DY = HY / 65536
Положение вертекса по вертикали будет соответственно
Y = Y0 + DY * NY    или, что тоже самое
Y0 + NY * HY / 65536

Для получения координат по горизонтали надо распаковать 24 бита NXZ. Поступаем так:
Сперва вычисляем количество вертексов по X и Z (точнее размер бокса в вертексах, самих вертексов может быть меньше):
СX = (X1 - X0) / DXZ
СZ = (Z1 - Z0) / DXZ
Теперь как-бы принимаем, что все позиции вертексов в плане упорядочены в набор горизонтальных строк и пронумерованы сквозным образом примерно как показано на картинке:

24-х битное поле NXZ - это и есть номер сквозной нумерации. Для получения координат надо выделить номер строки NX и столбца NZ.
NX - это по сути номер строки, соответственно:
NX = результат целочисленного деления NXZ / CZ

NZ - это позиция внутри строки и соответственно:
NZ = остаток от деления NXZ / CZ

Теперь сами координаты получаем просто:
X = X0 + NX * DXZ
Z = Z0 + NZ * DXZ

Теперь что следует из такого алгоритма. Самое главное, что размеры сетки в плане "в ячейках" имеет ограничение, а именно:
NX * NZ <= 16777216 (2 в степени 24)
При этом не важно, насколько реально в плане уровень покрыт сеткой, важно именно расстояние между наиболее удалёнными точками сетки. Для примера, сетку уровня можно вписать в плане в квадрат 4096х4096 ячеек или в прямоугольник 8192х2048 или в прямоугольник 5592х3000 и т.д. Вот это и накладывает ограничения на максимальный размер уровня, а точнее той его части, что покрыта сеткой и соответственно доступна для неписей.

Кто-нибудь может подсказать, можно ли при компиляции задавать размер ячейки? Обычно он 0.7. Соответственно, для такого размера ячейки и квадратной в плане области сетки максимальные геометрические размеры будут 4096*0.7 = 2867.2 игровых метра.

К этому можно добавить, что вертексы в этом массиве отсортированы по возрастанию всех трёх координат для того, чтобы движок мог их искать бинарным поиском.

 

Изменено 18 Февраля 2015 пользователем malandrinus