Minecraft сравнивает массивы за куб

September 14, 2024 Telegram

Коллизии в играх обнаруживаются тяжелыми алгоритмами. Для примера попробуйте представить себе, насколько сложно это для просто двух произвольно повернутых кубов в пространстве. Они могут контактировать двумя ребрами, вершиной и гранью или еще как-то более сложно.

В майнкрафте вся геометрия хитбоксов параллельна осям координат, т.е. наклона не бывает. Это сильно упрощает поиск коллизий.

Я бы такое писала просто. Раз хитбокс блока — это объединение нескольких параллелепипедов, то можно его так и хранить: как список 6-элементных тьюплов. В подавляющем большинстве случаев этот список будет очень коротким. Для обычных кубов его длина — 1, для стеклопаналей может достигать 2, наковальня, о боги, состоит из 3 элементов, а стены могут иметь их аж целых 4. Для проверки хитбоксов на пересечение достаточно перебрать пары параллелепипедов двух хитбоксов (кажется, их может быть максимум 16). Для параллелепипедов с параллельными осями задача решается тривиально.

Но Minecraft JE писала не я, поэтому там реализация иная.

Хитбокс тамошние программисты хранят как массив вокселей (воксель — трехмерный аналог пикселя). Имеется битсет на $W \times H \times D$ элементов, где каждый бит отвечает за свой воксель. Воксели при этом не обязаны быть кубическими: рядом с битсетом хранится массив размеров вокселей по каждой из трех осей. Так, например, блок с вот таким хитбоксом ( $\times 4$ в глубину):

##..
####
####
####

будет храниться как битсет на 4 элемента со значениями

10
11

и размеры вокселей $2, 2$ в ширину, $1, 3$ в высоту и $4$ в глубину.

Даже если два хитбокса оказались каким-то чудом выровнены, для проверки хитбоксов на пересечение битсеты двух хитбоксов проANDить их все равно было бы неправильным, ведь размеры вокселей могут не совпадать, и #. и .# вполне могут пересекаться (а ###. и .###, наоборот, не пересекаться). В 1D правильный метод был бы следующим:

Считаем для каждого из двух хитбоксов префиксные суммы длин вокселей, для примера выше это $0, 2, 4$ . Прибавляем координаты блоков. Это, по сути, координаты границ вокселей.
Объединяем эти два массива в один с сортировкой. Это “интересные” координаты, т.е. координаты, на которых какой-то из двух хитбоксов переходит на другой воксель.
Интервал между любыми двумя соседними координатами гарантированно не пересекает границы вокселей, поэтому теперь можно для каждого такого интервала втупую проверить пересечение.

В 3D нужно провести аналогичный алгоритм по трем осям. Для этого нужно по каждой из осей составить массив интервалов, а затем тремя вложенными циклами перебрать все параллелепипеды на этих интервалах: они гарантированно не будут пересекать границы вокселей. Всего делается $(W_{1} + W_{2} + 2) \times (H_{1} + H_{2} + 2) \times (D_{1} + D_{2} + 2)$ проверок.

Например, стеклопанель может иметь вот такой хитбокс:

.#.
###
.#.

Здесь по двум осям 4 интересных координаты ( $0, 1, 2, 3$ ), а по третьей две ( $0, 1$ ). Кубообразный моб имеет 2 интересных координаты по каждой из осей, поэтому при проверке на коллизию моба и стеклопанели (если более грубая проверка до этого, например, по расстоянию, даст неопределенный результат) цикл сделает $6 \times 6 \times 4 = 144$ итерации. Для сравнения, с моим алгоритмом их было две.

Проверка хитбоксов на пересечение — не единственная полезная операция над ними. У стен, например, есть две модели: соединяющиеся с блоком сверху и не соединяющиеся. Соединять надо, если верхняя грань стены всей своей поверхностью контактирует с нижней гранью блока сверху, т.е. если “хитбокс” верхней грани стены вложен в “хитбокс” нижней грани этого блока. По сути та же задача, только не в 3D, а в 2D, и не пересечение, а вложенность.

Любители абстрактных фабрик абстрактных фабрик в этот момент решили, что раз задача звучит похоже, то и решать ее надо тем же методом, поэтому процедуру проверки на пересечение переделали в общую процедуру проверки, принимающую аргументом предикат. Предикат — это произвольная булева функция от двух аргументов. Для пересечения это $a \land b$ , для невложенности это $a \land \neg b$ . Процедура, соответственно, возвращает true, если хоть в какой-то точке пространстве предикат вернул true.

К сожалению или к счастью, на этом веселье не заканчивается. Поскольку AI мобов при прокладывании пути учитывает хитбоксы, при замене блока на другой (или изменении стейта блока) путь может быть нужно перепроложить. Для оптимизации это нужно делать только тогда, когда старый и новый хитбоксы не совпадают. А как проверить хитбоксы на равенство? Правильно, запустить уже написанную процедуру с предикатом $a \neq b$ .

Теперь пройдемся по всей этой истории в режиме турбо. В исходных кодах хитбоксы на старте императивно высчитываются как объединение нескольких параллелепипедов, что генерирует массив вокселей. При каждом изменении блока эти массивы вычитываются, вычисляется объединение наборов “интересных” координат, по ним запускаются три вложенных цикла, внутри считываются элементы битсета и запускается динамически поданный на вход предикат $a \neq b$ . Где-то здесь еще валяется оптимизация, что два равных (в плане адресов) хитбокса надо всегда считать равными, но для различающихся хитбоксов она не помогает.

Зачем все это надо — выше моего понимания. Я бы хранила массивы параллелепипедов и, ну, сравнивала бы их на равенство. Учитывая то, что хитбоксы зашиты в код и не изменяются датапаками, должно быть возможно заранее гарантировать, что одинаковые хитбоксы всегда разбиваются на одинаковые параллелепипеды, если возможно несколько вариантов. Решение Mojang мне и в голову не пришло. Наверное, я не настоящая программистка.