Случайные лабиринты и сапёр от третьего лица, инопланетные жуки и алгоритм Брезенхема

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

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

Игра получилась на удивление иргабельной, извините за тавтологию. Интересное сочетание экшена/аркады и паззла/адвенчуры. Разрешите рассказать вам о паре алгоритмических задач, возникших при генерации уровней. Сами алгоритмы простые. Однако интересно именно то, что их можно использовать в игре.

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

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

На поле расставлены ловушки. Каждое число показывает количество ловушек в восьми клетках вокруг него. Ловушки можно вычислить, как в игре «Сапёр». Однако в отличии от последней разминировать ничего не нужно. Главное — не попасться в ловушку! Цели каждого уровня могут быть разными: собрать все монеты, прибить всех инопланетных жуков, разрушить все лазеры и т.д. Таким образом, ловушки — это часть ландшафта, местность, которую надо учитывать при исследовании уровней инопланетного храма.

Что будет, если просто случайно раскидать по полю ловушки и монеты? Вот так, например:

Обозначения на схеме: «@» - персонаж, «$» - монета, «x» - ловушка. Перемещая персонажа по полю, на этом уровне необходимо собрать все монеты. Но случайное расположение ловушек заблокировало проход в правую часть поля. Уровень невозможно пройти.

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

Генерируем случайный лабиринт. На стенах случайно расставляем ловушки, а в проходах — монеты.

Такой способ гарантирует доступ ко всем монетам, минуя ловушки. При этом сам лабиринт игроку не виден. Он не обязан ходить по дорожкам. На картинке сверху, например, можно сразу же взять монету, сдвинувшись на две клетки вправо.

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

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

Главное же требование к структуре лабиринта: он должен быть связанный. В каждую клетку дорожки должна быть возможность попасть из любой другой клетки-дорожки.

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

1. Начинаем с ячейки, на которой стоит курсор в начале игры. Закрашиваем ее. Закрашенные клетки будут дорожкой лабиринта.

На каждом шаге:

2. Выбираем случайное направление (вверх, вниз, вправо, влево) по которому свободны две ячейки по прямой.

3. Если такое направление нашлось, то двигаемся на эти две клетки, закрашивая их.

4. Если тупик, то откатываемся назад до того момента, пока не встанем на ячейку, где еще есть варианты направлений движения.

5. Если больше вариантов нет — все, лабиринт построен!

Вот эта анимация хорошо иллюстрирует алгоритм построения:

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

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

А теперь давайте добавим на уровень жуков!

Жуки — это микро-боссы, которые перемещаются по своим траекториям. Они слепые в отличие от большого босса. Жуки не видят, где находится игрок. Однако если на них наткнуться, то проиграешь.

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

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

Забавно, но для расчета клеток по которым двигаются жуки можно использовать алгоритм Брезенхэма. В Википедии он отлично объясняется с примерами:

https://ru.wikipedia.org/wiki/Алгоритм_Брезенхэма

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

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

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

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

Однако можно генерировать и случайную форму уровня, а также наличие и расположение жуков, лазеров, воды, предметов и т.д. Сделал в игре режим «Челлендж», в котором такой новый случайный уровень генерируется каждый день. Причем, этот уровень одинаковый для всех игроков по всему миру.

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

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

Игру ASCIILL вынес из основной игры и оформил в виде отдельного проекта. Очень уж прикольно получилось. Вы можете посмотреть на игру вот здесь: https://store.steampowered.com/app/1878770/ASCIILL/

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

Благодарю за прочтение. Пока!