Генерация подземелий в The Binding of Isaac — описание работы алгоритма

Рассказ программиста оригинальной игры.

Программист оригинальной The Binding of Isaac Флориан Химсл в 2020 году опубликовал на YouTube видео, в котором рассказал о принципах генерации локаций в игре. Он признался, что некоторые решения были неудачными, поэтому многие вещи пришлось исправлять авторам ремейка. Мы выбрали из его ролика главное.

Генерация уровня начинается с одной комнаты. Затем создаётся соседняя — алгоритм случайно выбирает, с какой стороны она будет примыкать к изначальной. Максимальное количество комнат в локации определяется разработчиком.

Оригинальная комната, с которой начинается генерация локаций. Все комнаты в The Binding of Isaac одинакового размера
Оригинальная комната, с которой начинается генерация локаций. Все комнаты в The Binding of Isaac одинакового размера

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

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

У некоторых комнат есть условия генерации. К примеру, тупиковые залы могут соседствовать только с одной клеткой. Именно в таких «тупиках» находятся торговцы, предметы и боссы.

Светлым выделены тупиковые комнаты, содержащие важные объекты
Светлым выделены тупиковые комнаты, содержащие важные объекты

Единственное исключение — секретные залы, которые могут связать тупиковую комнату с каким-нибудь другим помещением.

Секретная комната, примыкающая к тупиковому помещению
Секретная комната, примыкающая к тупиковому помещению

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

Генерация подземелий в The Binding of Isaac — описание работы алгоритма

В ремейке The Binding of Isaac процесс генерации отличается: например, там есть комнаты разной формы, а местоположение дверей заранее предопределено. Тем не менее весь уровень всё так же размещается на сетке.

Игра собирает уровни из заранее созданного набора комнат. Соответственно, двери разных клеток должны стыковаться друг с другом, а сами залы не должны слишком часто повторяться (некоторые вообще могут появиться только один раз)
Игра собирает уровни из заранее созданного набора комнат. Соответственно, двери разных клеток должны стыковаться друг с другом, а сами залы не должны слишком часто повторяться (некоторые вообще могут появиться только один раз)
Примерно так выглядит структура уровней в The Binding of Isaac: Rebirth. Они значительно больше, чем в оригинальной версии
Примерно так выглядит структура уровней в The Binding of Isaac: Rebirth. Они значительно больше, чем в оригинальной версии

В оригинальной The Binding of Isaac есть комнаты разной сложности — низкой, средней и высокой. И есть два типа подземелий: в одном совмещаются залы низкой и средней сложности, а в другом — средней и высокой.

Генерация подземелий в The Binding of Isaac — описание работы алгоритма

Химсл признался, что в The Binding of Isaac достаточно плохой баланс сложности — его можно было бы улучшить множеством способов. Например, можно было ограничить количество сложных комнат или врагов на уровне. Но в результате сложность напрямую зависит от случайности.

Генерация подземелий в The Binding of Isaac — описание работы алгоритма

По словам разработчика, The Binding of Isaac — это небольшая и неидеальная игра со множеством недостатков. Тем не менее ни один из них не делает её неиграбельной — загрузки не такие уже долгие, а баланс достаточно хорошо работает. А в ремейке многие проблемы исправили и улучшили оригинальную концепцию.

203203
24 комментария

На самом деле поле для генерации локации не такое уж большое, поэтому уровни часто не вписываются в его рамки. Из-за этого генерация начинается заново, а загрузка удлиняется.Так зачем начинать сначала, если можно воткнуть комнату в свободную клетку. И для чего вообще нужны эти рамочные ограничения.
Статья о том, как не нужно программировать лабиринты  ¯\_(ツ)_/¯

19
Ответить

тот же самый вопрос

2
Ответить

Я почему-то уверен, что дело в флеше и его ограничениях

Ответить

писал по этому алгоритму реализацию на godot
https://v001.dev/isaac_map_gen/

16
Ответить
4
Ответить

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

Че, пацаны, Кнут?

16
Ответить

А ещё по теории вероятности сейчас где-нибудь может и не сидеть чувак и не ждать первой загрузки

3
Ответить