Главная » Хабрахабр » Процедурная генерация уровней

Процедурная генерация уровней

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

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

Под катом много текста и "жирных" гифок. Внимание!

Вводная

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

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

Большинство, конечно, про генерацию классических лабиринтов или про генерацию рельефа (кстати, результаты очень впечатляющие), что не подходит для 3D-шутера. Я просмотрел свою базу знаний по геймдеву, и выписал в отдельный документ ссылки на статьи по процедурной генерации. Но некоторые были близки к тому, что мне нужно (звёздочкой я отметил те, которые мне показались наиболее подходящими):

Я решил начать с последних двух — они просто реализуются, и дают хорошие результаты.

Структура генератора

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

  1. Генерация изначальной геометрии (на выбор — или "BSP", или планировка помещений).
  2. Очистка от мусорных секций (таких секций, которые не могут существовать в игре).
  3. Построение соединений.
  4. Очистка от мусорных подграфов (таких групп секций, которые соединены между собой, но нет соединения с оставшимися секциями).
  5. Очистка от излишних соединений (построение остовного дерева, ссылка дана на минимальное остовное дерево, т.к. там есть картинка, но для генератора нет нужны именно в минимальном).
  6. Рандомизация соединений — восстановление обратно некоторых удалённых соединений (для более "человеческого" вида уровня), а также превращение некоторых других в проходы между секциями (что "сливает" несколько секций в одну, более сложной формы).
  7. Генерация секретных комнат.
  8. Генерация "сценария" (где будет начальная и конечная секция, и какой путь надо будет пройти, чтоб из начальной дойти в конечную).
  9. Оптимизация соединений.
  10. Создание дверей и окон.
  11. Выбор действия, которое надо будет выполнить в этой секции (нажать на переключатель, поднять ключ или найти секретную стену).

Есть ещё где-то 12 пунктов, но они пока не доделаны (когда доделаю, напишу про них отдельный пост).

Генерация изначальной геометрии: "BSP"

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

Изначально создаём прямоугольник, размером со всё игровое поле: Алгоритм достаточно прост.

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

Рекурсивно проделываем тоже самое для новых прямоугольников:

И ещё раз и ещё раз, до некоторого предела:

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

Но не каждая с каждой, а несколько хитро, из-за того они хранятся в "BSP"-подобной структуре (для более подробных деталей смотрите оригинальный алгоритм). Потом комнаты соединяются коридорами.


Коридор, соединяющий фиолетовую и белую секции.

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

Кроме того, если комната (на рисунке — бирюзовая) пересекает коридор, то она должна делить его на две разные секции (поэтому один и тот же коридор может отрисовываться разными цветами):

И вот что получается в итоге:

Дальше начинается фаза пометки мусорных клеток:

Это из-за того, что сектор обязательно должен быть окружен стенами (как минимум по 1 клетке с каждой стороны), и в нём как минимум должна быть одна клетка свободного пространства: Как я уже писал, никакой сектор не может быть меньше, чем 3x3 клетки.

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

Вместо этого, для каждой помеченной клетки ищется тот сектор, к которому она может примкнуть (соблюдая правило 3x3):


Если клетку так и не удаётся отнести к какому-либо сектору, она удалятся (но не в этом случае — тут всё хорошо).

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

Генерация изначальной геометрии: планировка помещений

Этот алгоритм несколько сложнее предыдущего, но тоже не rocket science. За основу была взята другая статья.

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

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

В свободном пространстве случайно раскидываются точки роста комнат (минимальный размер комнаты — 3x3):

Комнаты перебираются по очереди, чтоб не было пересечений. Начинается первый этап роста комнат — для каждой комнаты выбирается наибольшая сторона, которая ещё может расти, и она растёт на 1 клетку (если есть несколько сторон с одинаковой длиной — случайная из них).

Затем комнаты преобразовываются в полибоксы:

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

В результате получается полностью заполненное пространство:

Далее полибоксы отрисовываются в виде растра, и (как и в случае "BSP"-генератора) начинается этап пометки "мусорных" клеток:

И присоединения их к существующим секторам:


Тут не удалось присоединить все клетки — лишние были удалены.

Результат обратно превращается в полибоксы:

Очистка от мусорных секций

Иногда возникают такие секции, внутри которых не соблюдается правило 3x3:

Можно попытаться такие секции "восстановить", но я пошёл по более простому пути, и просто их удаляю:

Построение соединений

Соединения создаются с обеих сторон — если секция A соприкасается с секцией B, то будет соединение из A в B и из B в A. Для каждой секции ищутся её соседи, и в местах соприкосновения таких секций создаются соединения. В результате получается двунаправленный граф.

Очистка от мусорных подграфов

Иногда, в результате очистки от мусорных секций, получается не один граф, а несколько независимых, как в этом примере:

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

Очистка от излишних соединений

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

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

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

Рандомизация соединений

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

Но уровень, в котором нет ни одного лишнего соединения тоже не выглядит очень человечным, поэтому вносится некий хаос:

  1. Некоторые удалённые рёбра восстанавливаются.
  2. А некоторые превращаются в проходы.

Дальше те секции, между которыми образовались проходы, "сливаются" в одну:

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

Генерация секретных комнат

На графе выбираются такие сектора, у которых есть только одно соединение:

Затем этот массив обрезается случайным образом (но так, чтоб в нём остался хоть один элемент). Если таких секторов будет несколько, то они все собираются в массив, и сортируются по "площади". Эти сектора и станут секретными комнатами:

Генерация "сценария"

такие, которые ближе к "краю" графа): Вначале выбираются сектора, с минимальным количеством свободных соединений (т.е.


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

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

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


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

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

Далее этому списку секторов назначается номер сценария (просто число, на этом этапе оно ничего конкретного не значит), а соединения на границах этого списка секторов помечаются как закрытые этим сценарием.

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

Дальше выбирается очередной сектор, составляется список, и этот список помечается новым сценарием:

где-то внутри секции с красным сценарием будет находиться ключ или переключатель, который откроет проход к секторам с синим сценарием. Обратите внимание на маленькие синенькие точечки внутри красных квадратиков — так отрисовывается scenario opener — т.е.

Так продолжается до тех пор, пока не останется свободных секторов:

Этот сектор будет тем сектором, в котором игрок начнёт игру. Самому последнему сектору не присваивается сценарий, а только scenario opener.

Для этого уровня:

  • Игрок начинает в стартовом секторе, где-то там находит "открывашку" к желтому сектору, идёт туда.
  • В желтом секторе открывает голубой сектор, идёт туда.
  • В голубом секторе открывает зелёный, идёт туда.
  • В зелёном секторе открывает фиолетовый, идёт туда.
  • В фиолетовом открывает красный.
  • В красном — синий.
  • Где и находит переключатель конца уровня.

Схематически это можно показать так:

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

Оптимизация соединений

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

Создание дверей и окон

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

  • Вначале выбирается точка на соединении, желательно ближе к центру.
  • Затем в этой точке размещается либо дверь, либо окно (а если это соединение к секретной комнате, то секретная стена).
  • Если размещается дверь, то она может быть от 1-й до 3-х клеток размером (одна — обычная дверь, две или три — толстая гермодверь, которая открывается после нажатия на какой-нибудь переключатель).
  • Дальше соединение разбивается на две части — часть перед выбранной точкой, и часть после. И, если либо перед, либо после осталось место, то функция вызывается рекурсивно.

Чтоб уровень выглядел более интересно, на разных шагах разная вероятность размещения двери или окна:

  1. На первом шаге обязательно размещается дверь, т.к. что толку от соединения, если там одни окна.
  2. На втором шаге c большей вероятностью (75%) размещается окно, чем дверь.
  3. Если есть третий шаг (например, соединение длинное), то на нём обязательно размещается окно.
  4. В случае 4-го шага дверь либо окно размещаются равновероятно.
  5. Если соединение экстра длинное, генератор возвращается ко второму шагу.

Выбор действия

Хоть это и не имеет отношения к генерации, но на этом шаге меняется визуализация — теперь окантовка сектора красится в цвет сценария:

Так же заметьте, что вместо двери у секретной комнаты (тёмно-серая слева) нарисована стенка — всё правильно, это секретная стенка.
Стартовый сектор — светло-серый, конечный — синий.

Далее выбираются те сектора, в которых можно разместить ключи:

Выбираются они достаточно просто:

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

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

В остальных секторах будут переключатели.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

OpenSceneGraph: Групповые узлы, узлы трансформации и узлы-переключатели

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

«Монстры в играх или 15 см достаточно для атаки»

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