Генерация подземелий — от простого к сложному

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

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

В итоге у нас получится генератор подземелий со следующими свойствами:

• Комнаты будут соединены коридорами.
• Топологически подземелье будет иметь форму дерева. Добавить циклы будет элементарно, но уже в качестве домашнего задания.
• Будет настраиваться количество комнат, их размер, «уровень ветвления».
• Подземелье будет располагаться на клеточной сетке (состоять из квадратных клеток).

Весь код можно найти на github.

Кода в посте не будет — все используемые подходы легко описываются словами.

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

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

Общий подход

Поскольку мы не пишем «боевой» код, то многие вещи можно упростить:

• Подземелье размещаем на клеточном поле. Все координаты будут целочисленными. Математики вообще мало будет.
• Визуализировать будем с помощью matplotlib. Да, с помощью библиотеки рисования графиков.
• Код будет писаться «в лоб», лишь бы работал.
• Результаты работы генератора будем выводить в отдельном окне с помощью pyplot.show, и писать на файловую систему. Для включения/отключения этих фич добавим опции командной строки.
• Код будем писать в одном файле. Так проще смотреть дифы и, в целом, строк не много будет.

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

План следующий:

1. Учимся создавать и описывать одну клетку комнаты. Назовём его блоком.
2. Учимся создавать случайные комнаты из блоков.
3. Настраиваем генератор комнат, чтобы исключить некрасивые и / или сложные комнаты.
4. Учимся генерировать две комнаты и расставлять их рядом.
5. Учимся соединять комнаты коридором.
6. Наводим лоск.

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

Шаг 1: подготовка окружения

Символический шаг:

• Создадим файл requirements.txt со списком необходимых нам пакетов.
• Создадим заготовку для генератора, умеющую парсить аргументы командной строки с помощью argparse.
• В README.md добавим информацию о настройке виртуального окружения и запуске генератора.

Github tag: step-1.

Шаг 2: первый блок

Чтобы работать с блоком подземелья, нам необходимы:

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

Размер блока, как и размер клетки, примем равными единице и даже не будем его выносить в константы.

Для позиции и блока сделаем отдельные классы с говорящими названиями: Position и Block.

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

Точка будет представляться через кортеж (x, y), отрезки и ломаные линии через списки точек.

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

При формировании границ блока, мы примем, что его позиция указывает на левый нижний угол.

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

Идеально :-)

Github tag: step-2.

Шаг 3: несколько блоков

Шаг 3.1: хоть какая комната

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

1. Состоит из блоков.
2. Неразрывна — то есть представляет именно одну комнату, а не несколько островов из блоков.

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

1. Создаём комнату из одного блока.
2. Добавляем к комнате блок, примыкающий к её случайно выбранной стене.

Давайте попробуем. Для этого создадим класс Room, описывающий комнату. В нём будем хранить список блоков.

Метод Room.expand будет добавлять к комнате один случайный блок.

Метод Room.allowed_new_block_positions будет возвращать список доступных клеток для новых блоков. Находить свободные позиции мы будем просто:

1. Класс Position научим возвращать множество соседних позиций.
2. Соседние клетки всех блоков комнаты объединим в одно множество.
3. Из этого множества удалим клетки самих блоков, останутся только свободные клетки.

В Room добавим метод, аналогичный Block.geometry_borders. Пока он будет просто возвращать границы всех блоков.

Получится что-то такое:

Не ахти что, но для начала сойдёт.

Github tag: step-3.1

Шаг 3.2: границы комнаты

Нам надо убрать внутренние стены.

Во-первых, это некрасиво.

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

Для этого наведём порядок в стенах. От них нам необходимы:

1. Позиция.
2. Положение: внешняя (настоящая) или внутренняя (прозрачная).
3. Направление: с какой стороны от стены комната, а с какой внешний мир. Будем считать, что направление обозначает куда стена смотрит из комнаты. Соответственно, направления у нас 4: LEFT, UP, RIGHT, DOWN.

Выделим стены в отдельный класс Border. Каждый блок будет иметь 4 стены. Метод Block.geometry_borders теперь будет не самостоятельно создавать отрезки, а получать их от (внешних) стен.

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

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

Чтобы упростить работу с координатам. Добавим методы:

• Position.point — возвращает текущие координаты позиции.
• Position.move — возвращает копию позиции, сдвинутую на указаное расстояние по осям X и Y.

Наш результат:

Github tag: step-3.2

Для интереса, давайте создадим комнату побольше, например из 100 блоков… У-у-упс…

Комнаты-то могут быть с дырками.

Шаг 3.3: убираем дырки

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

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

Решений может быть несколько:

• Найти дырки и добавить на их место блоки. Это увеличит размер комнаты в блоках, что сделает генератор менее предсказуемым (мы хотим, чтобы он создавал комнаты сугубо заданного нами размера).
• Поменять алгоритм генерации… Ну нет, он простой и мне нравится.
• Считать такие комнаты «ошибочными» и при их возникновении, пересоздавать. Это наш путь.

Добавим метод Room.has_holes, которые будет проверять комнату на наличие дырок.

Идея проверки:

1. Определим прямоугольник, в который вписывается комната.
2. Сформируем множество всех клеток этого прямоугольника.
3. Добавим во множество первое кольцо клеток вокруг его границ (чтобы обеспечить связанность пустых областей по разные стороны комнаты).
4. Удалим из множества клетки, занятые блоками.
5. Поиском в ширину (или в глубину), начиная от случайной клетки множества, определим все доступные из неё клетки.
6. Если множество найденных клеток совпадает и исходным, значит дырок нет.
7. Если мы не добрались до каких-то клеток, значит дырки есть.

Попробуем снова создать большую комнату. Генератор проработает дольше, так как будет создавать несколько комнат, но в итоге создаст правильную. Например, такую:

Github tag: step-3.3

Шаг 4: Две комнаты

Шаг 4.1: Подготовка

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

• Они пересекаются, так как каждая комната у нас строится начиная с позиции (0, 0).
• Нельзя понять где какая комната и какие стены к какой комнате относятся.

Пересечение пока трогать не будем. Сначала озаботимся базовыми вещами:

1. Нам нужна сущность, которая владеет комнатами. Назовём её Dungeon.
2. Нам нужна цветовая дифференциация комнат, чтобы в случае ошибок  хотя бы примерно видеть в чём проблема.

Цвета для комнат будем выбирать случайные и тёмные, поскольку светлые цвета на белом фоне не будут видны. Для этого хорошо подойдет интервал RGB от #000000 до #999999.

Чтобы лучше видеть пересечения стен, сделаем границы комнат полупрозрачными. Смешение цветов будет выделять проблемные места. Например, так:

Github tag: step-4.1

Шаг 4.2: Убираем пересечения

Чтобы комнаты не пересекались, одну из них необходимо сдвинуть куда-нибудь.

Поскольку у нас пока нет ни дверей ни коридоров, то двигать можно куда угодно. С другой стороны, разумно соблюсти несколько условий:

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

Попробуем для одной из комнат перебирать возможные позиции, пока не найдём ту, в которой она не пересекает вторую комнату. Искать будем от некоторой «центральной» точки, по спирали, проверяя сначала клетки на расстоянии 1, потом на расстоянии 2 и так далее.

Так как мы на клеточном поле, то расстояние у нас будет Манхеттенское.

За центральную точку возьмём (0, 0). Переставлять будем вторую. Когда у нас появятся двери, мы сможем переделать этот подход и искать точки не от центра комнаты / подземелья, а от дверей.

Итого. Нам необходимы:

1. Функция points_at_circle, возвращая все точки на заданном расстоянии от центральной.
2. Метод Room.is_intersect, проверяющий пересекаются ли комнаты
3. Методы *.move во всех классах от Room, до Position (в котором он уже есть), которые будут двигать нашу комнату (и все её части) в новое место.

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

И вот наши комнаты уже стоят порознь.

Github tag: step-4.2

Шаг 5: коридоры

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

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

Но.

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

Во-вторых, мало кому нужны «просто комнаты». Обычно, для каждой комнаты устанавливаются дополнительные ограничения, которые могут влиять на её форму, расположение и количество входов. Поэтому необходимо уметь расставлять комнаты с учётом положения дверей.

Этим мы и займёмся.

Шаг 5.1: реализация «в лоб»

Что нам необходимо для коридоров:

1. Научиться отмечать стены, имеющие дверь (вернее, имеющие возможность её поставить).
2. Научиться отмечать стены, через которые уже есть проход в другую комнату (чтобы не соединять одну дверь с двумя и более комнатами).
3. После создания комнаты, сразу размечать в ней несколько (случайных) позиций для дверей.
4. При добавлении комнаты в подземелье, выбирать две случайные двери (одну незанятую в подземелье, другую — в новой комнате), соединять их коридором и искать позицию новой комнаты не от центра координат, а от выбранной двери

По сути, добавить пару флагов и поменять аргументы вызова функций. Для простоты, пока будем рисовать коридоры условно — прямой линией от двери до двери.

Отмечать двери будем более жирными полупрозрачными линиями.

Иии… Как-то не очень у нас получается.

Github tag: step-5.1

Шаг 5.2: улучшаем коридоры

Почему текущий вариант выглядит плохо:

1. Логика расположения комнат учитывает геометрическую близость дверей, но не учитывает длину коридора. Для примера посмотрите на зелёную и светлобордовую комнаты слева посередине: двери близко, но сам коридор надо вести в обход.
2. Идея выбирать случайные двери для соединения создаёт ощущение «искусственности». Человек бы соединял более оптимальным способом. Тем более, при генерации больших подземелий. возникнут проблемы с использованием дверей из внутренних частей подземелья.

Чтобы исправить эти косяки:

1. Выбор случайных дверей, заменим на полный перебор их сочетаний.
2. Научим комнаты поворачиваться на  90, 180, 270 градусов.
3. Вместо проверки прямого манхэттенского расстояния, будем проверять длину минимально возможного коридора.

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

1. Для максимально допустимого расстояния между дверями. (от 1 до допустимой границы).
2. Для каждого из возможных сочетаний дверей.
3. Для каждой из клеток на текущем допустимом расстоянии от двери подземелья.
4. Для каждого возможного поворота новой комнаты.
5. Если текущее положение комнаты ничего не пересекает и путь от двери до двери не больше текущего допустимого расстояния, то выбираем текущее положение комнаты.

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

В данном месте будет очень уместна известная инструкция по рисованию совы.

Но я уверен, что вы разберётесь и получите примерно следующий результат.

Github tag: step-5.2

Шаг 6: наводим лоск

Мы почти закончили. Осталось сделать наше подземелье привлекательнее.

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

Сами коридоры будем отображать толстой чёрной линией с уменьшенным z-индексом, чтобы её концы скрывались под остальной графикой.

Отображение дверей сделаем опциональным и выключим по-умолчанию.

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

Для заливки нам потребуется знать линию, очерчивающую контур заливаемой области. Разрозненных отрезков будет недостаточно. Чтобы собрать такой контур из имеющихся у нас отрезков, возьмём случайный отрезок в качестве первого сегмента и будем искать следующий отрезок такой, чтобы он начинался в точке окончания первого отрезка. Поскольку контуры наших комнат не пересекаются, а сами комнаты не содержат дырок, для каждого отрезка найдётся только один парный. Реализовано это в функции make_countur.

Опции генерации расширим, разделив жёстко задаваемое количество блоков и дверей на интервалы. Это сделает наши подземелья разнообразнее.

Github tag: step-6.

Что можно делать дальше

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

Оптимизация

Как вы могли заметить, я совершенно не занимался оптимизациями. Вплоть до того, что вместо двухмерных массивов использовал множества координат. Если имеете опыт работы со сложными алгоритмами, у вас, возможно, даже глаз подёргиваться начал или какая-нибудь похожая реакция возникла. Простите :-)

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

Хорошими кандидатами станут:

• find_path
• Room.has_holes
• Dungeon.room_positions_bruteforce

Замыкание комнат в циклы

Подземелье без возможности ходить по-кругу — не самое интересное подземелье.

Попробуйте добавить дополнительные коридоры, чтобы сделать его запутанней.

Дифференциация комнат

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

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

Дифференциация дверей

Двери тоже могут быть разными.

Попробуйте добавить «цвета» для дверей и соединять только двери одинаковых цветов.

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

Усложнение правил расположения комнат

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

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

Уход от клеточного поля

Тут есть несколько интересных вариантов.

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

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

Примерно как на этих картинках с черепами и рыбами:

Подробнее об этом можно узнать, начав с чтения про гомологию и книгу On Growth and Form.

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

В-третьих. Можно и полностью отказаться от клеток, так как они нужны нам только для упрощения проверок и генерации формы комнат. Логика генерации при этом не изменится.