Как работает алгоритм «туннелирования» для генерации игровых уровней

Частный пример генератора локаций.

Разработчик Билли Брандстеттер в своём блоге описал процесс создания генератора уровней для собственной игры: алгоритм последовательно генерирует новые комнаты и соединяет их с остальными.

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

Финальный результат
Финальный результат

По словам Брандстеттера, его генератор работает на основе алгоритма «туннелирования». Его идея заключается в том, что каждая новая комната соединяется с другой через туннель. Так, шаг за шагом, на уровне появляется всё больше и больше комнат, которые обязательно должны быть связаны друг с другом.

Весь процесс создания уровня

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

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

Два соединённых прямоугольника
Два соединённых прямоугольника
Здесь один прямоугольник перекрывает другой
Здесь один прямоугольник перекрывает другой
Комната из четырёх прямоугольников
Комната из четырёх прямоугольников

Во время генерации уровня комнаты не могут перекрывать друг друга, а расстояние между помещениями можно настраивать.

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

Чтобы сделать локацию более разнообразной, можно изменить стоимость тайлов пола и стен — если разница между ними высокая, то алгоритм будет проходить по тайлам пола. Если же она будет низкой, то A* будет часто пересекать стены.

Так выглядит поиск пути при низкой стоимости прохода по тайлам пола
Так выглядит поиск пути при низкой стоимости прохода по тайлам пола
Оранжевым выделено пространство поиска, в котором алгоритм A* ищет оптимальный путь
Оранжевым выделено пространство поиска, в котором алгоритм A* ищет оптимальный путь
Так выглядит пространство поиска, когда стоимость прохода по ячейкам пола равна 30, а по тайлам стены — 100. Можно увидеть, что оранжевая зона значительно расширилась
Так выглядит пространство поиска, когда стоимость прохода по ячейкам пола равна 30, а по тайлам стены — 100. Можно увидеть, что оранжевая зона значительно расширилась

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

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

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

Дополнительные примеры работы алгоритма
9898
23 комментария

Скоро дизайнеры уровней потеряют работу....

Ответить

Да ладно, это достаточно древний подход генерации ещё с первых рогаликов.

18
Ответить

Комментарий недоступен

3
Ответить

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

Ответить

о да, потеряют изза того что умели уже кучу лет

Ответить

Комментарий недоступен

2
Ответить

По идее отдельным вложенным слоем, префабы размещать по паттерну внутри объема.
Обычно от "стенок" идут.

2
Ответить