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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слева — проекция 3D коридора, справа — 4D
Слева — проекция 3D коридора, справа — 4D

Именно по этой причине был выбран способ визуализации 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

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

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 71

    +8
    Осталось написать кубик Рубика в 4 измерениях и тогда мне будет чем заняться между уколами санитарки.
    Впрочем направление интересное. но мне кажется, что игровое направление верное. А просто посмотреть -не очень
      +2
      Уже написан и 4d и 5d
    +2

    Очень интересное направление, особенно для игр в научно-фантастическом сеттинге.
    В "Crysis" был уровень на базе пришельцев, где приходилось как бы "летать" или "плавать". Вот он был бы в разы интереснее, будучи четырехмерным.

      +1

      Первая мысль — это может сделать Antichamber еще большим Antichamber. Если данная игра обошла вас стороной, советую попробовать посмотреть, мне кажется она может дать новых идей.

        0
        Жаль, там очень агрессивные цвета. Интересная игрушка, по после получаса дико болит голова, хоть ни разу не эпилептик.
          0

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

          0
          Под линукс собрать можно или там сильно завязано на винду?
            0
            Завязано на win
              +5
              Завязано не сильно. Изменений нужно не так уж и много. (Если что, я на C++ не писал лет 10, так что сильно не бейте за код).
                0
                Спасибо за pull request, добавлю.
                  +1
                  Спасибо! А как собрать?
                    0
                    Присоединяюсь к вопросу.
                      +3

                      Для начала нужно установить зависимости. В моём случае (Debian) это делается так


                      sudo apt install build-essential cmake ninja-build libglfw3-dev libglm-dev

                      Потом нужно создать каталог для сборки (внутри скачанного каталога проекта), перейти в него, сконфигурировать и собрать проект.


                      mkdir builddir
                      cd builddir
                      cmake ..
                      ninja

                      В результате появится ожидаемый исполнимый файл.

                        +1
                        В manjaro, почему-то, не нужен ninja. сборка выглядит так:
                        sudo pacman -S cmake glfw-x11 glm

                        После установки зависимостей сборки:
                        mkdir builddir && cd builddir && cmake .. && make
                          0
                          Да под Убунтой тоже помогла замена «ninja» на «make».

                          Но, виндовая под вайном идёт гораздо быстрее
                            0

                            Соберите с -O2. Добавьте в конец CMakeLists.txt:


                             target_compile_options(${PROJECT_NAME} PRIVATE -march=native -O2 )

                            Результаты (AMD FX-8320):


                            • Linux, по-умолчанию: ~5 FPS
                            • Linux, O2: ~15-17 FPS
                            • Wine: ~20-30 FPS. Но там начальное положение в лабиринте другое, меньше видно, чем в начальном положении в версии под линукс. Если побродить, есть просадки вроде такие же, до 15-17.
                              0
                              Судя по всему, вы тестировали без включенной многопоточности? Попробуйте включить её в файле config.txt, FPS должно значительно повыситься.
                      0
                      Спасибо!
                      Оно работает!
                      image
                      0
                      Как уже выше написали, зависимость там минимальная.
                      0

                      даешь д()()м в 4D!!!
                      ps: а как будеть лететь ракета кибердемона, прячущегося в складках мерности?!)))

                        0

                        Ракета будет лететь по прямой, но прилетит с неожиданной стороны :)

                          +6

                          По четырехмерной прямой. Для заданной трехмерной проекции это будет прямолинейный отрезок из одной точки пустого пространства в другую точку пустого пространства с изменяющимся сечением снаряда вдоль траектории полета.
                          Это значит снаряд начнет появляться постепенно из какой-то точки трехмерной проекции в виде сечения, двигаясь прямо.
                          Во время полета кусочек снаряда будет расширяться в сечении и станет полноценным снарядом в точке пересечения 4д прямой и нашей трехмерной проекции. Потом так же постепенно начнет исчезать, погружаясь в складку четвертого измерения в виде всё меньшего сечения пока не исчезнет где то в воздухе.
                          Если мы немного отошли в сторону и наша трехмерная проекция не пересекается с траекторией снаряда, то сечение снаряда не достигнет своего полного обьема, а начнет уменьшаться раньше

                            0
                            Это если снаряд четырехмерный. Если он трехмерный то эффекты будут другие.
                            Пересечение произвольно ориентированной в объеме плоской фигуры с плоскостью — отрезок(за маловероятным исключением полного совпадения плоскостей ориентации ) А трехмерного снаряда с техмерной плоскостью — плоская двухмерная фигура. То есть снаряд не сработает.
                              0

                              Вы правы. Я исходил из того, что в 4х мерном простанстве не существует истинно 3х мерных объектов, так же как реальном мире нет плоских обьектов. Даже у тончайших листков бумаги есть толщина, пусть и очень маленькая.


                              Снаряд на сработает.

                              Сработает. Если листок бумаги попадет по человеку с большой скоростью тонкой стороной, то человека разрежет на длину листка.
                              Так же и с трехмерным снарядом, который будет плоским сечением пронзать 3х мерные обьекты в 3х мерной проекции 4х мерного пространства

                                +2
                                Не сработает. Связи между атомами не почувствуют наличия между ними бесконечно тонкой плоскости из ничего. Более того вы его даже не увидите. Закон обратных квадратов взаимодействий (электромагнитных и гравитационных) обусловлен именно трехмерностью нашего пространства. И проекция этих сил из несовпадающей трехмерной плоскости на нашу будет иметь нулевое значение.
                                  0

                                  Мы говорим про реальность или про игру?


                                  В реальности не существует "бесконечно тонкого ничего", а именно обьектов с размерностью меньше самого пространства. Значит 3х мерный обьект должен иметь толщину в 4м измерении, а не "ничего". Именно эта толщина и определяет "срабатывание".


                                  В игре же будет зафиксировано пересечение 3д модели снаряда с 3д проекцией пространства в виде плоской фигуры и пересечение этой плоской фигуры с 3д моделью персонажа в виде отрезка. Факт пересечения и триггерит попадание снаряда по персонажу.


                                  P. S. Увидел дополнение к вашему комментарию про проекцию сил. Кажется, мы говорим о разном. Я имею ввиду цельный 4х мерный мир по аналогии с нашим, а вы ведете речь про параллельно существующие 3д миры, имеющие ориентацию друг к другу в 4м измерении, которое отсутствует в каком либо из самих этих миров.

                                    0
                                    В реальности с цельным 4 мерным объектом есть та же проблема с связностью. Его любое бесконечно тонкое трехмерное сечение имеет массу. Интеграл этой массы по четвертому измерению даст какую-то фигню. Эта фигня должна взаимодействовать с другими такими 4-х мерными по закону обратных кубов… Тут наблюдается слишком много логических проблем именно с физикой и взаимодествиями. Так что я -пас…
                          0

                          Надо сделать это в vr для большего погружения в 4д. Вообще vr — хорошая возможность научиться интуитивно чувствовать 4д мир, но это пока не делают (

                            0

                            Разве VR даёт сильно больше информации, чем проекция 3д проекции 4д мира на 2д монитор?

                              +1

                              В плане субъективного восприятия кажется, что да. Но только "кажется")

                                0

                                Разница есть на самом деле. Можно почуствовать сравнив как выглядят "3д видео" и "360° видео" в шлеме.

                                  0

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

                                    0
                                    Основное достоинство VR бинокулярное зрение и параллакс связанный с микродвижениями головы и тела. Создаётся убедительный эффект погруженности в 3Д сцену.

                                    Я переживал восторг, разглядывая 3Д сцены, которые сам рисовал на обычном мониторе, чувство погружения прямо внутрь «матрицы».
                                    +1
                                    В VR очень неприятно (для некоторых!) когда «пол» меняет положение. Или когда окружение движется не из за перемещения головы, а в результате движения камеры в пространстве игры.

                                    Разработчики, учитывающие этот эффект, делают перемещение на дальние расстояния мгновенным (по типу телепорта). А если перемещать камеру как на движущейся тележке или качелях, то наблюдал дезориентацию, падения, тошноту. Не только на себе, но на десятке людей. Мне хватает нескольких секунд, чтобы словить сильшейшую тошноту, которая потом часами не угасает.

                                    0
                                    В Ubuntu под Wine отлично запустилось
                                      +2

                                      Как же это КРУТО. Спасибо большое!


                                      Пара идей:


                                      • Добавить мини-карту с текущей 3д проекцией и положением игрока в ней — вот оч поможет вестибулярный аппарату. Карта перерисовывается динамически в зависимости от текущей 3д проекции
                                      • Добавить 4-хмерную плоскость к которой игрок всегда будет находится в перпендикулярном положении (а-ля земля)
                                        0
                                        На самом деле интересно было бы развить эти идеи и выработать «правила» 4-мерного игрового мира в форме ограничений на степени свободы, аналогичные 3-мерному. Вы предлагаете добавить гиперплоскость (а-ля земля), ортогональную, полагаю, 4-вектору ускорения свободного падения, которая имеет 3 степени свободы (т.е. игрок по гиперплоскости перемещается в 3-х направлениях, не счиатя «прыжков»). Какими будут ограничения на «повороты головы»? Обычно в 3-д играх направление взгляда задается единичным вектором (имеющим две степени свободы), а поворот плоскости вокруг этого вектора исключается (хотя в реальности он вполне возможен). В 4-д мире направление взгляда, очевидно, должно задаваться так же единичным вектором (уже с 3-мя степенями свободы) и ограничениями на поворот плоскости (но тут уже у 2-плоскости две степени свободы, так что не совсем понятно как это логичнее сделать). При наличии 3-х степеней свободы привычное управление мышкой поворотами «головы» уже становится не вполне удобным и интуитивно понятным. Как быть? Возможно, появятся новые контроллеры?)
                                        Интересно услышать Ваше мнение)
                                        0

                                        Хм, через несколько минут игры бинарник из статьи зарубил виндовый антивирь. Запускал несколько раз, всё было хорошо, но когда попробовал Roll, то сразу удалилось. Странно, на virustotal всего 2 детекта, проактивная защита сработала?

                                          0
                                          Действительно странно. Я даже не представляю, что там может быть подозрительного для антивируса.
                                            0
                                            У нас после апдейтов с 16 декабря такое поведение. ЕХЕ собранные на одной машине (без цифровой подписи), а потом сразу скачанные интернет браузером на другой, детектируются как вирус. Пользы, конечно, от такого антивируса конечно мало.
                                              0
                                              Описание угрозы идёт как Behavior:Win32/DefenseEvasion.WI!ml.
                                              Причём любопытно, но на virustotal антивирус от MS ничего не детектит.
                                            0

                                            интересно, как это будет выглядеть в VR?

                                            0

                                            ого! здорово! спасибо очень круто!
                                            скачал себе несколько таких игр!

                                              0
                                              Новый виток для развития игроиндустрии.))
                                                +5
                                                Так давно ведь. Видео датировано 2014-м.

                                                0

                                                В Задаче Трёх Тел было описание 4-х мерного пространства, интересно с тех пор посмотреть глазами насколько это возможно.

                                                  0
                                                  А меня в своё время очень впечатлило описание пятимерной Вселенной в книге Грега Игана «Диаспора».
                                                  Небольшой отрывок
                                                  В Пилотской Кабине было яблоку негде упасть: отличное окружение, чтобы попрактиковаться в преодолении непредсказуемых препятствий. Орландо обнаружил, впрочем, что большую часть времени молча стоит, очарованный открывающимся видом. Одна стена пентерактового окружения представляла собой сплошное гигантское окно, занятое увеличенным изображением Пуанкаре. Стоять перед нею и с открытым ртом пялиться на звезду было вполне простительно. Перемещение в публичных пятимерных окружениях требовало от Орландо постоянного самоконтроля, куда большего, чем страх ударить лицом в грязь — в строгом смысле слова последней оплошности совершить он физически не мог. Пятимерное тело, снаряженное многочисленными полезными рефлексами, в целом отвечало предполагаемому макросферному стандарту, но полагаться на столь чуждые инстинкты было все равно что управлять роботом-дистантником, чья программа включала так много автономных откликов, что все данные ему инструкции оказывались излишни…
                                                  Он смотрел вниз, в окнопол. В пятимерном окружении самые банальные детали оказывали гипнотизирующее воздействие. Тессеракт окошка состыковывался с тессерактом пола не по прямой, а через объем приблизительно кубических очертаний. Стоило ему подумать об этой гиперповерхности как о нижней части прозрачного окна, как тот факт, что он видел весь этот объем одновременно, обретал успокоительный смысл. Но как только он напоминал себе, что каждая точка куба принадлежит также фронтальной гиперповерхности матового пола, как иллюзия нормальности улетучивалась.
                                                  Пуанкаре с самого начала им не очень-то благоприятствовала. Даже ее очертания решительно противоречили старым представлениям о кривизне и пропорциях небесных тел. Орландо видел краем глаза, что четырехмерный диск звезды занимает лишь треть тессеракта, которому полагалось его обрамлять. Куда меньше места отсекала от прямоугольника вписанная в него окружность, и это побуждало плохо приспособленную к новым условиям часть его личности воображать, что звезда вот-вот улетит в глубь тессеракта, провалившись между восьмеркой точек сцепления. Конечно, этого не происходило. Поскольку полис подошел к звезде на расстояние, вполне достаточное, чтобы рассмотреть ее континенты «невооруженным» глазом, блеск светила слепил Орландо. Границы гигантских слябов кристаллизовавшихся минералов, что плавали по звездной поверхности, превосходили сложностью все формы трехмерных аналогов; ни одна выветренная долина, ни один коралловый риф не были так восхитительно вычурны, как темный скальный силуэт на фоне раскаленного звездного вещества.
                                                  +1

                                                  Блин, я всегда думал что 4 измерение — это t — время. Уххх

                                                    +1
                                                    В некоторых играх это измерение именно так и реализуют.
                                                      0
                                                      Обычно для удобства формул. Но когда говорят о мерности миров, обычно имеют ввиду геометрические мерности. А «который час» можно спросить и у жителя 4d мира.
                                                      +4
                                                      После того как скачал игру....
                                                      … я в своем познании настолько преисполнился, что будто проживаю в миллионах и миллиардах таких же измерений и этот мир мне абсолютно понятен.
                                                        +1
                                                        Интересно, сколько людей научились понимать четырёхмерное пространство и ориентироваться в нём. С помощью этой, либо другой симуляции
                                                          0

                                                          Ну понимать — это понятие растяжимое. Человек и в трехмерном пространстве ориентируется намного хуже, чем в двухмерном.

                                                            +1

                                                            Тогда какой смысл делать такие игры? С тем же успехом можно менять окружению по любым выдуманным законам — зритель/игрок и не заметить разницы.

                                                          +1
                                                          Хочу пакмана в 4D! Новый виток в индустрии
                                                            0
                                                            Главное не надевать шлем виртуальной реальности, а то есть все шансы попрощаться с едой из желудка.
                                                              0

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

                                                              0
                                                              После статьи мне так и не стало понятно значение 4d
                                                                0

                                                                Что Вы имеете ввиду под значением?
                                                                Значение слова? 4d — 4 dimension или 4 измерения пространства, не считая времени.

                                                                  0

                                                                  Это нормально. Мне кажется, никто здесь так и не научился видеть в 4х измерениях, просто не признаются. Смысла в таких играх поэтому не видно, интерес только в технической реализуемости.

                                                                  0
                                                                  Если бы добавили такие игры для виртуальной реальности, было бы круто, а так с монитора сложно всё таки прочувствовать эту реальность
                                                                    0

                                                                    А чем в виртуальной реальности будет проще?

                                                                  0

                                                                  А вы знали, что у лабиринтов в этой игре есть выход, после которого наступает победа?
                                                                  Я уже две недели изучаю/модифицирую код этой игры и постоянно в неё играю, и только сегодня первый раз заметил, что её можно пройти
                                                                  Выглядит как белый квадтрат вместо стены у края лабиринта. А вот что происходит если туда зайти — сюрприз =)


                                                                  Спойлер

                                                                  Используйте F8 что бы ходить сквозь стены и найти выход, прошерстите 3-д пространство по количеству комнат в поперечнике 4-ого пространства (по де-фолту = 3).
                                                                  Я очень удивился когда зашел в этот "портал"

                                                                    0
                                                                    Выход есть всегда :)
                                                                    Используйте F8 что бы ходить сквозь стены и найти выход, прошерстите 3-д пространство по количеству комнат в поперечнике 4-ого пространства (по де-фолту = 3).

                                                                    А можно ещё проще — изменить размер лабиринта, меняя параметр maze_size в config.txt. Например, можно сделать «плоский» лабиринт, если задать maze_size_w = 1 и maze_size_y = 1. В таком виде он очень легко проходится.
                                                                    0

                                                                    Автор, джва года уже такое хочу, не встречал:
                                                                    в двух изменениях точку можно показать перекрестием линий (прицел Робокопа) параллельным осям, в трёхмерном уже трёх линий. Можете сделать гифку или видео с анимацией движения точки пересечения 4 линий внутри прозрачного тессеракта?

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

                                                                        Да, хотелось бы "снаружи", проекцию в 2D как на картинках в статье.

                                                                    Only users with full accounts can post comments. Log in, please.