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

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

В закладки

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

Как всё началось (кратко)

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

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

Можно считать это нуль-скриншотом игры. Как видно игра разработана на GameMaker: Studio 2, а ещё что у меня 92 непрочитанных сообщения в Телеграмме.

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

А вот это уже точно первый скриншот именно этой игры

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

А это уже ближе к конкурсной итоговой версии

Генерация уровней

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

(Для изображений-примеров генерации специально был увеличен размер подземелья, на примерах он 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 подземелье, а затем по полученному результату проходимся клеточным автоматом. Получаются такие пещеры, но с более конкретными комнатами.

Непонятные объекты в виде буквы " I " это сталактиты. Л - логика.

Забавно, но 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

{ "author_name": "Станислав Филиппов", "author_type": "self", "tags": ["\u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u043d\u0430\u044f","\u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f","longread","indie"], "comments": 12, "likes": 58, "favorites": 38, "is_advertisement": false, "subsite_label": "indie", "id": 56887, "is_wide": false, "is_ugc": true, "date": "Mon, 01 Jul 2019 16:47:39 +0300", "is_special": false }
Объявление на DTF
0
12 комментариев
Популярные
По порядку
Написать комментарий...
1

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

Я верно понимаю, что вы просто от руки рисовали на простом белом листочке много всякой черно-белой хероборы, потом фотографировали эти рисунки и каким-то образом их резали на спрайты? Не рассажете подробнее, как пачку рисунков с листа превратить в пачку спрайтов с корректным альфа-каналом (ну то есть чтобы то что белое, было бы белым, а то что по краям спрайта, прозрачным)?

Ответить
2

Почти так и делал, да, а если конкретнее, то рисовал спрайты на листочках в клеточку. Затем не фотографировал, а сканировал их (это на самом деле важное отличие), а затем "резал" на спрайты.

А резал я их относительно просто. Т.к. изображения были взяты сканером, но они имели достаточно большое разрешение (но не сказать, что качественное), а в игре используется странное сочетание плоского пиксельно-нарисованного 3д, что давало свои преимущества.
Секрет правильной альфы был таким: брался скан, затем немного корректировались уровни цвета (чтобы сетка на бумаге была менее замета, а чёрный становился темнее). Затем "волшебной палочкой" выбиралась нужное место, где должно быть пусто и удалялось, а уже потом этот скан в высоком разрешении уменьшался до игровых, например, 64х64. Важный момент: чтобы волшебная палочка сработала верно, то сам рисунок должен быть "замкнут" т.к. как при заливке в пейнте - если есть где-то дыра, то результат будет не таким каким нужно.

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

Ответить
1

Спасибо за ответ! Интересная технология для людей, у которых нет графического планшета

Ответить
0

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

Goblet Grotto вдохновлялся что-ли?

Ответить
1

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

Ответить
0

А почему сообщения в телеграме не читаешь? Вдруг там что-то важное.

Ответить
1

Но после скриншота я прочитал эти сообщения. Или нет. Узнайте об этом в статье через год! (нет)

Ответить
0

Ага! Эта одна из тех игр, которая стала вдохновителем меня на этот жанр. Именно жанр, а не конкретно эту игру т.к. у меня было и до сих пор есть желание ещё сделать подобные игры.
В сам Eye of the Beholder не играл толком (разве что прошёл один этаж)

Ответить
–1

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

Ответить
0

а какие щас жанры из свежака?

Ответить
0

)) батл рояль с таким графическим стилем ваще огонь был бы

Ответить

Комментарии

{ "jsPath": "/static/build/dtf.ru/specials/DeliveryCheats/js/all.min.js?v=05.02.2020", "cssPath": "/static/build/dtf.ru/specials/DeliveryCheats/styles/all.min.css?v=05.02.2020", "fontsPath": "https://fonts.googleapis.com/css?family=Roboto+Mono:400,700,700i&subset=cyrillic" }
{"hash":"b159cbb2","params":{"id":"dtfru","service":1,"title":"\u041f\u0440\u044f\u043c\u043e\u0439 \u044d\u0444\u0438\u0440","isLegacy":false}}