Четырёхмерный лабиринт с видом от первого лица

Существует более 30 игр с дополнительным пространственным измерением (список на википедии), которые разнообразными способами визуализируют и пытаются сделать доступной для понимания наличие четвёртой координаты. Но среди тех игр, с которыми я ознакомился, не нашел для себя такой, которая сочетала бы в себе следующие факторы:

• вид от первого лица

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

• простая и привычная графика, с текстурами и освещением

• отсутствие лишних геймплейных элементов и бóльшая направленность игры на исследование четырёхмерного мира

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

Сечение vs. проекция

Для начала, надо немного сказать о способах визуализации 4D пространства. Среди них можно выделить два основных — сечения и проекции, которые проще всего проиллюстрировать на аналогии с 3D:

Сечения куба в 2D:

Проекция куба в 2D:

Сечения тессеракта (аналога куба в четырёх измерениях) в 3D*:

*на самом деле это конечно же тоже 2D проекции 3D объектов, но опустим это для простоты

Проекция тессеракта в 3D:

С точки зрения информативности и представления структуры объекта, проекции однозначно лучше, однако у этого способа есть фатальный недостаток — переизбыток информации делает любую хоть сколько-нибудь сложную сцену очень трудной для восприятия. Например, проекция простого 4D коридора превращается в непонятный для неподготовленного человека набор линий (скриншот из игры 4D Maze Game):

Именно по этой причине был выбран способ визуализации 3D сечениями, который, в свою очередь, тоже далеко не идеален, так как значительная часть объекта остается за пределом поля зрения. Для понимания искажений объектов, вызванных этим, лучше всего снова воспользоваться аналогией с обычным трёхмерным пространством, мысленно заменяя 4D на 3D, а двумерное изображение 3D сечения — на одномерную полоску, получаемую плоским срезом:

А вот так выглядят двумерные проекции 3D сечений тессеракта. Принцип искажений аналогичен предыдущему примеру:

Далее эти эффекты демонстрируются на конкретных элементах лабиринта.

Текстуры

У каждого тессеракта есть 8 гиперграней, каждая из которых имеет свою 3D текстуру (16x16x16 точек), по аналогии с кубом, который состоит из 6 граней с 2D текстурами. Каждая гипергрань окрашена в свой цвет, соответствующий направлению, куда она повернута видимой стороной.

Привычные нам грани куба, образованного 3D сечением тессеракта:

После поворота тессеракта в плоскости ZW на 90 градусов видимые гиперграни +-Z поменялись соответственно на +-W:

Анимация вращения тессеракта сразу по всем шести плоскостям

Так как у каждой текстуры есть небольшая черная граница по краям, то иногда возникает странная на первый взгляд ситуация, когда 3D сечение выравнивается ровно по этим границам, и всё становится однотонным:

Освещение

В каждой комнате лабиринта есть источник света, который может быть и не виден в текущем 3D сечении, из-за чего кажется, что блоки освещаются из ниоткуда:

Анимация поворота в плоскости XW, с источником света на гиперграни -Y

Скрытые проходы

Игроку нужно постоянно помнить о том, что некоторые стены комнаты могут быть не видны из его текущего 3D сечения, и поэтому поворот в дополнительном измерении может помочь обнаружить новые проходы:

Анимация последовательности поворотов, сначала в плоскости ZW, а затем в YW

Генерация мира

Лабиринт генерируется методом рекурсивного бэктрекинга (к слову, есть отличная визуализация этого алгоритма):

1. Весь лабиринт заполняется стенами, самая дальняя от нуля комната становится текущей
2. Текущая комната помечается как посещенная
3. До тех пор, пока текущая комната имеет непосещённых соседей:
    3.1. Случайным образом выбирается любой из непосещённых соседей
    3.2. Убираются стены между текущей комнатой и выбранной соседней
    3.3. Выбранная комната становится текущей и повторяется п.2

Затем для каждой комнаты выбирается случайная стена и на неё ставится источник освещения, свет от которого распространяется рекурсивно поблочно во всех направлениях, уменьшая свою интенсивность на единицу на каждом блоке. Свет распространяется до тех пор, пока интенсивность не уменьшится до нуля, либо не встретится блок с интенсивностью большей, чем текущая, либо не встретится непустой блок.

Рендеринг

Поскольку готовых движков для отображения четырёхмерных объектов не существует (или по крайней мере я не нашел таких), то написал свой программный рендерер. Производительность не ставилась в приоритет, поэтому был выбран простой для реализации метод рендера — рейкастинг, который можно описать всего несколькими основными шагами:

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

• Для каждого луча в цикле выполняется последовательный проход по нему с шагом в один блок

• Если на очередном шаге встретился непустой блок:

  • Вычисляется индекс грани и соответствующая ей 3D текстура, а так же степень её освещенности

  • По расстоянию до блока определяется координата в текстуре, из которой и получаем цвет пикселя; возвращаем его и прерываем цикл

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

Производительность такой реализации «в лоб» без всяких оптимизаций получилась ожидаемо крайне низкая, но в небольшом разрешении её хватило для получения комфортных FPS (на AMD Ryzen 5 2600 в 1280x720 и с использованием всех ядер выдаёт в среднем 60 FPS).

Скриншоты

Заключение

В конечном итоге, получилась не столько полноценная игра, сколько демонстрация четырёхмерности в интерактивной форме. Если в дальнейшем её развивать, то можно ускорить рендер, реализовав рейкастинг на шейдерах (либо вообще избавиться от лучей и использовать вместо них алгоритмы растеризации). Также можно добавить генерацию более естественных структур, объекты произвольной формы, разнообразные цели и игровые механики и запилить четырёхмерный майнкрафт, чего уж мелочиться.

Скачать: исходный код, исполняемый файл для windows

Полезные ссылки:

• основы рейкастинга: 1, 2

• подробная статья про визуализацию 4D объектов

Автор: IronLynx

Источник