Как работает алгоритм «туннелирования» для генерации игровых уровней
Частный пример генератора локаций.
Разработчик Билли Брандстеттер в своём блоге описал процесс создания генератора уровней для собственной игры: алгоритм последовательно генерирует новые комнаты и соединяет их с остальными.
При этом важное значение играет стоимость прохода по разным тайлам — в зависимости от этой характеристики уровни могут получиться совершенно разными.
По словам Брандстеттера, его генератор работает на основе алгоритма «туннелирования». Его идея заключается в том, что каждая новая комната соединяется с другой через туннель. Так, шаг за шагом, на уровне появляется всё больше и больше комнат, которые обязательно должны быть связаны друг с другом.
Особенность этого подхода в том, что в каждой комнате есть лишь вход и выход, а это далеко не всегда интересно с точки зрения геймплея. Для решения этой проблемы Брандстеттер придал каждой ячейке определённую стоимость перемещения: у пола она ниже, а у стен — выше. Именно поэтому в большинстве случаев алгоритм предпочитает создать туннель, передвигаясь по полу, но иногда он «пробивает» стену — так получаются закольцованные карты или комнаты с несколькими проходами.
Другое правило, которого придерживался Брандстеттер: комнаты не должны быть простыми прямоугольниками. Он создаёт комнаты, комбинируя вместе случайное количество прямоугольников — обычно от одного до четырёх. Алгоритм начинает с одного прямоугольника в качестве основы, а затем соединяет его с другими прямоугольниками произвольного размера. При этом они могут накладываться друг на друга.
Во время генерации уровня комнаты не могут перекрывать друг друга, а расстояние между помещениями можно настраивать.
Когда появляется новая комната, она отделена от остальных. Чтобы соединить её с локацией, применяется алгоритм поиска пути A*. Суть этого алгоритма была описана выше — он высчитывает наименьшую «стоимость» пути, а затем генерирует маршрут. После этого вдоль туннеля создаются переходы между комнатами.
Чтобы сделать локацию более разнообразной, можно изменить стоимость тайлов пола и стен — если разница между ними высокая, то алгоритм будет проходить по тайлам пола. Если же она будет низкой, то A* будет часто пересекать стены.
В зависимости от начальной позиции, места назначения и стоимости перемещения этот алгоритм может создавать разнообразные примеры уровней.
По словам разработчика, эту систему можно значительно усложнить, если добавить систему ключей и замков — тогда комнаты будут разбиты на сектора, которые позволят открывать доступ друг к другу.