Binding of Isaac и её ремейк Binding Of Isaac: Rebirth — одни из самых любимых для меня игр. Они относятся к жанру roguelite twin stick shooter и очень похожи на Enter the Gungeon.

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

Хоть мне и пришлось провести декомпиляцию, а также освежить свои покрывшиеся пылью знания о Flash (когда-то я написал собственный декомпилятор Actionscript), мне ещё и очень повезло: разработчик Isaac Флориан Химсл и один из основных разработчиков Rebirth Саймон Парзер с радостью ответили на мои вопросы. На самом деле, Флориан даже недавно записал видео с описанием алгоритма. На его канале можно также узнать подробности разработки его новой игры Squid Invaders.

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

Базовый алгоритм

Разработчики Isaac активно вдохновлялись играми серии Zelda в 2D и генерировали карты, похожие на их подземелья.


Это набор квадратных комнат, соединённых краями друг с другом. Некоторые комнаты являются особенными — на каждом этаже всегда есть лавка , комната сокровищ и босс ; кроме того, случайным образом выбираются несколько других особых комнат. За исключением секретной комнаты , в подземелье нет петель.

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

Первую версию Isaac разработали менее, чем за 3 месяца, поэтому Химслу приходилось невероятно эффективно использовать своё время. Фундаментальный дизайн игры изящен и прост. Сначала генерируется план этажа (уровня). Затем некоторые комнаты выбираются в качестве особых. Потом из соответствующего пула выбирается интерьер каждой комнаты.

План этажа

Isaac генерируется на сетке размером 9?8. Для удобства ячейки обозначаются числами — единицами обозначают позицию по X, десятками — позицию по Y. Это означает, что можно двигаться вверх, вниз, влево и вправо, просто прибавляя +10, -10, +1 и -1. Ячейки с позицией по X, равной 0, не используются (всегда пусты), и это значит, что большей части кода не нужно беспокоиться о границах карты. То есть верхняя левая ячейка карты имеет обозначение 01, а нижняя правая — 79.

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

Сначала по формуле random(2) + 5 + level * 2.6 определяется количество комнат. Т.е. уровни начинаются с 7 или 8 комнат, и каждый раз увеличиваются на 2 или 3 комнаты.

Затем игра помещает начальную комнату (ячейка 35) в очередь. Далее она циклически обходит очередь. Для каждой ячейки в очереди она циклически обходит 4 основных направления и делает следующее:

• Определяет соседнюю ячейку, прибавляя к текущей ячейке +10/-10/+1/-1.
• Если соседняя ячейка уже занята, то игра ничего не делает.
• Если сама соседняя ячейка имеет более одного заполненного соседа, то игра ничего не делает.
• Если на уровне уже достаточно комнат, игра ничего не делает.
• Игра ничего не делает с вероятностью в 50%.
• В противном случае игра помечает соседнюю ячейку как содержащую комнату, и добавляет её в очередь.

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

В случае, если на картах требуется больше 16 комнат, начальную комнату периодически снова помещают в очередь, чтобы стимулировать рост.

Так как описанный выше алгоритм начинается с единственной комнаты и многократно расширяется наружу, он, по сути, является исследованием в ширину (breadth first exploration). Ограничение, не позволяющее добавить комнату, если уже есть два соседа, разделяет комнаты на отдельные коридоры, которые никогда не объединяются в петли.

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

Особые комнаты

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

Затем указывается положение секретной комнаты. Эти комнаты добавляются в план этажа; они являются одними из немногих исключений из правила, запрещающего располагать комнаты рядом с несколькими уже существующими. На самом деле, алгоритм наоборот, предпочитает их размещать их так. Генератор случайным образом ищет пустую ячейку, находящуюся рядом с не менее чем тремя комнатами и не рядом с любой из конечных комнат. Если он не находит её спустя 300 попыток, то слегка ослабляет критерий поиска, а после 600 попыток ослабляет его ещё больше. Эта процедура гарантирует, что секретная комната всегда будет размещена на уровне, но обычно они зажаты рядом с перекрёстками, то есть рядом с ними всегда много комнат.

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

Обычные комнаты

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

Комнаты случайным образом выбираются из пула. Информация о комнатах содержит и структуру (ямы, огонь, камни и т.п.), и монстров. И те, и другие подвержены случайным вариациям, например, появлению монстров-чемпионов и красных каминов.

Для обычных комнат существует три пула: лёгкий, средний и сложный. Первый этап главы выбирает из простых и средних комнат, а второй — из средних и сложных. Первая глава (Basement) содержит в пулах 174 обычных комнат. «Альтернативные главы», например, Cellar, которая случайным образом может заменить Basement, имеют немного отличающийся набор комнат.

Проклятие лабиринта

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

• На 80% больше обычных комнат (максимум 45)
• Для особых комнат используются только 6 дальних конечных комнат
• Уровни выбирают комнаты из пулов простых, средних и сложных комнат.
• В план этажа случайно добавляются дополнительные обычные комнаты с логикой размещения, как у секретных комнат.

Демо

Я создал на Javascript упрощённый пример генератора, чтобы можно было с ним поэкспериментировать. Полный код можно найти здесь, а работающий пример — в оригинале статьи.

Rebirth

Binding of Isaac: Rebirth — это ремейк оригинального Binding of Isaac, созданный компанией Nicalis, которая в то время была известна своими портами VVVVV и Cave Story. Игру портировали на C++ и переделали все звуки и графику. За годы существования игра получила множество DLC, добавивших новых предметов и врагов к и так уже достаточно впечатляющему списку оригинала.

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


С полным набором DLC (на момент написания статьи это Afterbirth+) в игре есть 11 больших комнат: 2?2, 2?1, L-образные и узкие коридоры в разных вариантах поворота.


Типичная L-образная комната, в три раза больше обычной комнаты. Она была реализована Саймоном Парзером благодаря аккуратной модификации исходного кода Химсла.

Вместо обхода в цикле всех направлений алгоритм обходит все выходы из комнаты. В комнате размером 2?2 их может быть до восьми.

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

Если для комнаты не хватает пространства, то алгоритм пытается вставить другого кандидата. При успешной вставке больших комнат есть вероятность 95%, что они будут удалены из пула.

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

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


В Isaac пропасти обычно пересекать невозможно

Вывод

Генератор уровней Isaac — не самый сложный из тех, которые я видел, но несмотря на такой малый объём кода, работает он невероятно хорошо. Вероятно, именно поэтому его так часто пытаются воссоздать. Его простота позволяет вносить изменения и расширения, и мы видим это на примере Rebirth. Невероятный результат.

Также можно заметить, что эта игра продолжает тенденцию, в соответствии с которой план этажа генерируется отдельно от деталей комнаты. В своих статьях о Diablo 1 [перевод на Хабре] и Enter the Gungeon [перевод на Хабре] я говорил, почему такой подход может быть очень мощным.

При декомпиляции кода я не нашёл каких-то особо интересных подробностей. Самое интересное, о чём я могу сказать — расположение комнаты сокровищ хранится в переменной с именем «boner» — вероятно, сокращение от Bonus Room. Также в коде присутствуют тонкости относительно незначительных побочных эффектов различных предметов, но эту тему я оставлю анализаторам.

Далее вы можете посмотреть серию видео Химсла о внутреннем устройстве игры или даже сыграть в Isaac и увидеть все уровни вживую. Я слышал, что новый DLC Repentance выйдет в этом году. Также я рекомендую сыграть в другие игры главного дизайнера Эдмунда Макмиллена (особенно в Super Meat Boy).