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

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

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

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

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

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

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

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

Здесь один прямоугольник перекрывает другой

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

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

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

Так выглядит поиск пути при низкой стоимости прохода по тайлам пола

Оранжевым выделено пространство поиска, в котором алгоритм A* ищет оптимальный путь

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

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

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

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

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