Бумажная генерация

Не являюсь частым писателем на DTF, была лишь одна статья, где я рассказывал о разработке top-down shooter-а и как прошёл её год в Steam.

О чём будет этот пост? Он о нескольких видах реализаций генераций уровней в Dungeon Crawler-е от первого лица "Бумажное подземелье", которое так же более известно как Drawngeon. Кстати, а вы знали, что в этой игре можно съесть свой топор?

Идея и игра появились на конкурсе по разработке инди-игр сайта gamin.me. Забавно, прямо как и игра из прошлой моей статьи!

У меня была необъяснимая тяга к жанру Dungeon Crawler, при этом именно к First Person View представителей. Что забавно, ведь я не играл в такие игры, но хотелось сделать что-то в этом духе.

Выбрал стиль графики, что будет в игре и взял за основу часть старой игры, где была подобная механика. И снова забавный момент-параллель с прошлой игрой\статьей - для той и этой игры я брал свои старые наработки, которые в итоге пришлось полностью переработать.

Итоговая конкурсная игра была очень забагована и имела никакой баланс (спойлер: до сих пор проблема с балансом есть).

Стоит предупредить, что здесь не будет колоссально детальных алгоритмов и\или такого же пошагового руководства\туториала, а некоторые вещи автор (вероятно) не понимает!

(Для изображений-примеров генерации специально был увеличен размер подземелья, на примерах он 32 ячейки, а в игре чаще встречаются 16)

Вообще я уже когда-то писал такие уровни, но в из этого не получилось сделать игру. И вот наконец мои знания снова пригодились. "Снова" от того, что уже писал такую реализацию пару раз и вот снова практически с нуля.

Какую такую? Самую простую! В конкурсной версии было два вида генераций, но конкретно сейчас о BSP-дереве
(или Binary Space Partitioning
(или Двоичное Разбиение Пространства)).

Алгоритм примерно такой:
0. Создаём "комнату" (или же узел дерева) на всю сетку уровня.
1. Если размер комнаты достаточно мал, то завершаем.
2. Смотрим Ширину и Высоту данной комнаты и на основе этого выбираем ось для деления (по X или по Y).
3. Берём комнату и делим её на две части.
2. Получили две дополнительные комнаты, для каждой начинаем этот же алгоритм с шага 1.

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

Комнаты в Бумажном определяются на конкретной сетке уже достаточно просто - берётся узел без потомков т.е. так называемый "лист" и дальше на основе размеров такой комнаты заполняется сетка значением "здесь пусто" оставляя лишь границу в одну ячейку на границе.

В свои предыдущие попытки написать BSP генератор я очень криво реализовывал заполнение коридоров между комнатами. В этот раз кажется исправился и реализация построения тоже рекурсивная, как и сам алгоритм BSP (логично):

Берём комнату, смотрим её потомков и если они есть, то создаём между ними корридор, затем берём комнаты потомков и выполняем тоже самое.

Второй тип генератора: Змейка.

Честно сказать, я не знаю как правильно называется данный алгоритм, но думаю это связанно с "исследователь", но я назвал её "змейка", хотя общего с одноимённой игрой мало.

Этот алгоритм намного проще, чем BSP.
Суть такова: у нас есть сетка подземелья заполненная значением "здесь стена", затем примерно из центра мы "запускаем змею", выбираем точку и ставим значение "здесь пусто".
Далее в цикле сдвигаем точку на 1 клетку в одну из 4х сторон, сторону выбираем по какому-либо правилу и\или через сколько-то ходов.

Конкретно в игре "правило" достаточно простое - случайным образом выбираем направление тогда, когда случайным образом условие скажет "выбирайте!". В коде это примерно так:

if( choose(0, 1) == 1 ) direction = choose(0, 1, 2, 3);

Далее уже добавленные после конкурса генератор, а именно

Генератор Cave (и его виды в игре)

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

В клеточном автомате есть правила по количеству "живых" и "мёртвых" соседей-клеток. На основе этого правила конкретно текущая клетка меняет своё состояние ("живой" или "мёртвый"). На основе этих правил есть так же игра "Жизнь".

Как это используется в Cave-генераторе: каждая ячейка сетки подземелья заполняется случайным образом значениями "1" или "0", а затем несколько раз прогоняется алгоритм клеточного автомата с конкретным правилом от чего простой "шум" в сетке превращается в "пещеры".

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

Второй вид генератора Cave

Смотря алгоритм вдруг запустился процесс Смекалочка.exe. Мы заполняем поле случайным образом, а что если подать что-то на вход клеточному автомату уже подготовленное? Таким образом получился следующий под-генератор - Cave-BSP.

Это практически буквально последовательное скрещивание двух генераторов, о которых написано выше - в начале мы берём и генерируем BSP подземелье, а затем по полученному результату проходимся клеточным автоматом. Получаются такие пещеры, но с более конкретными комнатами.

Забавно, но Cave-генераторы стали основой другого не совсем генератора, а скорее конкретно закодированного вида локаций - Леса.

Генератор для леса

Очевидно в лесу должны быть деревья, но как их ставить? Хотелось расположить их так, чтобы это напоминало лес, но при этом не сильно влияло на производительность, ведь в лесу много деревьев, а это надо обрабатывать и рисовать.

И тогда на выручку снова пришёл клеточный автомат, ну или в рамках игры просто cave-генератор.

Логика генерации леса примерно такая:
Генерируем "пещеру" для уровня, затем генерируем ещё одну пещеру, но в другую сетку. Затем используя вторую сетку-пещеру расставляем в нужных точках деревья и грибы.
Можно сказать, что это просто двухслойная пещера, но с текстурами леса.

И совсем недавно был добавлен ещё один бонусный генератор, так сказать.

Лабиринт

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

Вот только я провозился с этим алгоритмом относительно долго, потому что кто-то (и кто же это мог быть!?) кое-что перепутал в запаковке\распаковке X и Y координат.

Если попытаться описать алгоритм лабиринта, то он такой:
0. Заполняем сетку значениями "здесь стена".
1. Выбираем случайную клетку и добавляем её в список "для визита".
2. Пока список не пустой, то:
2.1. Выбрать случайную клетку из списка.
2.2. Вычислить "дальнего соседа" *
2.3. Если текущая клетка и клетка "дальнего соседа" являются стенами, то:
2.3.1. Отметить эти клетки как "здесь пусто" (и клетки между ними).
2.3.2. "Сканируем" соседние клетки относительно "дальнего соседа" и добавляем в список такие клетки, которые "здесь стена".

* конкретно в реализации с сеткой необходимо проделывать действия не просто с соседними клетками, а на дистанции 2.
В моей реализации в элементом списка был массив из 2х значений: положение текущей клетки и положение клетки из которой пришли в текущую (условный "родитель").

На этом генераторы закончились!

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

Здесь всё намного проще - у некоторых предметов есть min и max значение, а так же уровень и множитель уровня (level_mul). И в итоге характеристики предмета выбираются от min*level_mul до max*level_mul. Ничего необычного, можно было лучше, но тогда для меня и это казалось чем-то уже интересным.

Всем спасибо за внимание, кто прочитал или проскроллил до этого момента!

Это была моя первая попытка в генерации подземелий, предметов, а так же какие-то РПГ элементы с прокачками и подобным. Балансить всё это намного сложнее, чем мне казалось в начале. Да, я знал, что будет непросто отбалансить, но тут прям уух!

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

Было бы полезно почитать ваши комментарии по поводу этой статьи и игры, а так же можете задать вопросы - постараюсь ответить!

Ещё раз спасибо за внимание!

#indie #процедурная #генерация #longread