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

Не являюсь частым писателем на 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": 56, "favorites": 36, "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 }
0
{ "id": 56887, "author_id": 46318, "diff_limit": 1000, "urls": {"diff":"\/comments\/56887\/get","add":"\/comments\/56887\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/56887"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 64960, "last_count_and_date": null }
12 комментариев
Популярные
По порядку
Написать комментарий...
1

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

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

Ответить
2

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

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

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

Ответить
1

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

Ответить
0

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

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

Ответить
1

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

Ответить
0

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

Ответить
1

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

Ответить
0

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

Ответить
–1

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

Ответить
0

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

Ответить
0

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

Ответить

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fizc" } } }, { "id": 4, "label": "Article Branding", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "cfovz", "p2": "glug" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjog" } } }, { "id": 10, "disable": true, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "disable": true, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-250597-0", "render_to": "inpage_VI-250597-0-1134314964", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=clmf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Баннер в ленте на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudo", "p2": "ftjf" } } }, { "id": 16, "label": "Кнопка в шапке мобайл", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "chvjx", "p2": "ftwx" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvc" } } }, { "id": 20, "label": "Кнопка в сайдбаре", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "p1": "chfbl", "p2": "gnwc" } } } ]