Хабрахабр

[Перевод] Генератор подземелий на основе узлов графа

image

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

Введение

Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм

Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.

(a)

(b)

(с)

(d)

На рисунках (с) и (d) показаны схемы, сгенерированные из входного графа (a) и строительных блоков (b).

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

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

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

Разные формы для разных комнат

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

Две схемы, сгенерированные из входного графа, в которых с комнатой номер 8 связана особая форма комнат.

Явно указываемые позиции дверей

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

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

(a)

(b)

На рисунке (b) показана простая сгенерированная схема с формами комнат из рисунка (a). Рисунок (a) иллюстрирует различные типы размещения дверей — у квадратной комнаты есть 8 чётко заданных позиций дверей, а в прямоугольной комнате используется длина и расстояние от углов.

Коридоры между комнатами

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

(a)

(b)

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

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

Примеры

Несколько схем, сгенерированных из разных наборов строительных блоков и со включенными коридорами.

Несколько схем, сгенерированных из разных наборов строительных блоков со включенными и отключенными коридорами.

Во второй части поста я расскажу о внутренней работе алгоритма.

Я делаю это потому, что несмотря на возможность использования этого алгоритма непосредственно в Unity (он написан на C#), удобство работы с ним далеко от идеала. Также я работаю над плагином Unity для процедурной генерации подземелий, в который будет включён этот алгоритм. На создание шаблонов комнат без GUI уходит очень много времени, а для преобразования выходных данных алгоритма в используемое внутри игры представление нужно очень много кода.

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

Скриншоты плагина Unity (проект находится в процессе разработки)

Часть 2. Реализация алгоритма

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

Мотивация

Прежде чем переходить к реализации, я хочу показать результат того, что мы будем делать. В показанном ниже видео демонстрируется 30 разных схем, сгенерированных из одного входного графа и одного набора строительных блоков. Алгоритм всегда останавливается на 500 мс после генерации схемы, а затем пытается сгенерировать следующую.

Your browser does not support HTML5 video.

Как это работает

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

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

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

Пространства конфигураций

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

(a)

(b)

На рисунке (a) показано пространство конфигураций (красные линии) свободного прямоугольника относительно закреплённого Г-образного многоугольника. Пространства конфигураций. Рисунок (b) показывает пересечение (жёлтые точки) пространств конфигураций подвижного квадрата относительно двух закреплённых прямоугольников. Оно определяет все местоположения центра квадрата, при которых два блока не пересекаются и касаются друг друга.

Мы выбираем на подвижном блоке опорную точку и рассматриваем все локации в $\mathbb^2$, такие, что при перемещении многоугольника так, что его опорная точка располагается в этой локации, и подвижный, и закреплённый блок касаются друг друга, но не пересекаются. Для вычисления пространства конфигураций одного закреплённого и одного свободного блоков используется следующий алгоритм. Чтобы получить пространство конфигураций подвижного блока относительно двух или более закреплённых блоков, вычисляется пересечение отдельных пространств конфигураций (рисунок (b) сверху). Множество всех таких точек образует пространство конфигураций двух блоков (рисунок (a) сверху).

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

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

Инкрементная схема

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

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

Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null;
}

Псевдокод, демонстрирующий инкрементный подход к нахождению правильной схемы.

На каждой итерации алгоритма (строки 6 – 18) мы сначала берём последнюю схему из стека (строка 7) и вычисляем, какую цепь нужно добавить следующей (строка 8). Показанный выше псевдокод демонстрирует реализацию инкрементной схемы. Следующим шагом мы добавляем к схеме следующую цепь (строка 9), генерируя несколько развёрнутых схем, и сохраняем их. Это можно сделать, просто сохранив номер последней цепи, добавленной к каждой частичной схеме. Мы называем эту ситуацию поиском с возвратом, потому что алгоритм не может расширить текущую частичную схему и должен вернуться назад и продолжить с другой сохранённой схемой. Если этап расширения оканчивается неудачей, но в стек не добавляется новых частичных схем, и алгоритму нужно продолжать с последней сохранённой частичной схемой. Также поиск с возвратом является причиной того, что мы всегда пытаемся сгенерировать несколько расширенных схем (строка 9). Обычно это необходимо, когда не хватает места для соединения дополнительных цепей к уже составленным в схемы вершинам. Процесс завершается, когда мы сгенерируем полную схему, или стек опустеет. В противном случае нам бы не было к чему возвращаться.

(a) Входной граф

(b) Частичная схема

(с) Частичная схема

(d) Полная схема

(e) Полная схема

На рисунках (b) и (с) показаны две частичные схемы после планировки первой цепи. Инкрементная схема. На рисунке (e) показана полная схема после расширения (с) второй цепью. На (d) показана полная схема после расширения (b) второй цепью.

Это вложение используется затем для получения всех граней графа. Чтобы разделить граф на части, нужно найти плоское вложение входного графа, то есть чертёж на плоскости, в котором рёбра пересекаются только в конечных точках. Поэтому мы пытаемся расположить циклы в начале разложения, чтобы они были обработаны как можно раньше и снизить вероятность необходимости возврата назад на последующих этапах. Основная идея разложения заключается в том, что из циклов сложнее создать схему, потому что у их узлов больше ограничений. Если существуют другие грани, которые можно выбрать, то используется наименьшая из них. Первая цепь разложения образуется наименьшей гранью вложения, а последующие грани добавляются затем в порядке поиска в ширину (breadth-first search). На рисунке 4 показан пример разложения в цепи, который получен в соответствии с этими этапами. Когда граней не остаётся, добавляются оставшиеся нециклические компоненты.

(a)

(b)

На рисунке (b) показан пример того, как можно разложить на цепи рисунок (a). Разложение на цепи. Числа обозначают порядок создания цепей. Каждый цвет обозначает отдельную цепь.

(с) Хорошая частичная схема

(d) Полная схема

(a) Входной граф

(b) Плохой частичный граф

На рисунке (b) показан пример плохой частичной схемы, потому что в ней недостаточно пространства для соединения узлов 0 и 9. Поиск с возвратом. Для генерации полной схемы (d) необходим возврат к другой частичной схеме (с).

Имитация отжига

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

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

$E = e^{\frac{A}{\omega}} e^{\frac{D}{\omega}} – 1$

A — это общая площадь пересечения между всеми парами блоков в схеме. D — это сумма квадратов расстояний между центрами пар блоков, во входном графе являющихся соседями, но не касающихся друг друга. Значение $\omega$ влияет на вероятность того, что имитации отжига разрешено будет перейти к худшей конфигурации; этот параметр вычисляется из средней площади строительных блоков.

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

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

List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if (/* мы уже сгенерировали достаточное количество схем */) { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if (/* newLayout лучше, чем currentLayout */) { currentLayout = newLayout; } else if (/* вероятность, зависящая от того, насколько плоха энергия newLayout */) { currentLayout = newLayout; } } /* уменьшаем вероятность принятия худших схем */ } return generatedLayouts;
}

Это псевдокод метода, отвечающего за создание схемы отдельной цепи с помощью имитации отжига.

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

Бонусное видео

В показанном ниже видео демонстрируются схемы, сгенерированные из того же входного графа, что и в первом видео. Однако на этот раз показан инкрементный подход. Можно заметить, что алгоритм добавляет цепи узлов по одному. Также видно, что иногда присутствуют две последовательные частичные схемы с одинаковым количеством узлов. Это происходит, когда алгоритм выполняет возврат назад. Если первые попытки добавить другую цепь к первой частичной схеме заканчиваются неудачей, то алгоритм пробует другую частичную схему.

Your browser does not support HTML5 video.

Скачиваемые материалы

Реализацию алгоритма на .NET можно найти в моём github. Репозиторий содержит DLL .NET и GUI-приложение WinForms, управляемое файлами конфигурации YAML.

Показать больше

Похожие публикации

Добавить комментарий

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

Кнопка «Наверх»