Gamedev
Murrmy

Процедурная генерация для рогаликов: Миллионы, миллионы, миллионы pixel shop!

Видеоверсия этой статьи

Вы когда-нибудь играли в Daggerfall? В классические рогалики? В Dwarf Fortress? Вам было интересно, как именно создаются в них здания, города или даже миры? Если да, то этот цикл (надеюсь) статей для вас!

Лапки вверх, с вами Мурмия!

Я принимаю участие в разработке Python-библиотеки для процедурной генерации roguelike-карт. После моих первых принятых в основной код генераторов карт я решила записать видео- и текстовые туториалы, которые подробно объясняют процесс работы кода.

Давайте начнем!

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

Благодаря исключениям ТАКОЕ не сгенерируется никогда.

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

Тип магазина может быть следующим:

  • С едой
  • С драгоценностями

  • С одеждой

  • С оружием

  • С броней

  • С зельями

  • С инструментами

  • С магическими предметами

Если тип стены, пола или магазина не указан, то он выбирается случайным образом.

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

Как работает эта функция?

Создаем новую пустую комнату. Причем так как мы УЖЕ проверили весь магазин на корректность размеров и материалы, для этих комнат ничего проверять не надо. Расставляем на карте выход из магазина, масляную лампу, прилавок и кучку монет (эти объекты генерируются в каждом магазине). После этого определяем словарь, в котором мы выбираем для каждого типа магазина определенные типы предметов.

Что у нас будет на этот момент.

Далее немного магии:

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

  • Кладем предмет в эту клетку
  • Добавляем координату в список
  • Выходим из цикла
Картинка для тех, кто знает клингонский.

Зачем вообще такие сложности? Допустим нам надо разместить на площади в пять на пять клеток двадцать предметов. Если мы каждый раз будем случайно выбирать клетку и класть в нее предмет, то у нас будет две проблемы:

Первая: будет много пустых клеток

Вторая: будет много клеток с двумя, а то и более предметами.

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

Описанным выше алгоритмом мы создаем витрину с товарами около дальней стены торгового зала. Потом так же раскидываем по магазину еще несколько предметов и кошку и возвращаем из функции карту торгового зала, которую записываем в отдельную переменную.

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

  • Создаем комнату
  • Делим ее пополам
  • Создаем стены: теперь у нас две комнаты
  • Создаем двери
  • Расставляем по спальне кровать, факел и сундук
  • В зависимости от типа магазина, случайно раскидываем по складу определенные товары
  • И возвращаем карту

Мы опять попадаем в главную функции генерации магазина. Вклеиваем в него СНАЧАЛА торговый зал, а потом склад со спальней. Почему важен порядок? Дверь из торгового зала в склад была создана на карте со складом, так что если вклеить сначала склад, а потом торговый зал, то дверь просто исчезнет. Дальше при желании мы можем создать экстерьер магазина и перевернуть здание. Это даст нам в пару раза больше разнообразия с минимальными усилиями.

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

Ссылка на исходный код генератора: воть. Также можно быстро и в красивом виде посмотреть, какие именно видео генерируются, в этом видео.

А с вами была Мурмия, всем спасибо, всем пока!

{ "author_name": "Murrmy", "author_type": "self", "tags": [], "comments": 26, "likes": 52, "favorites": 137, "is_advertisement": false, "subsite_label": "gamedev", "id": 261096, "is_wide": false, "is_ugc": true, "date": "Wed, 18 Nov 2020 18:23:00 +0300", "is_special": false }
0
26 комментариев
Популярные
По порядку
Написать комментарий...
9

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

Ответить
1

А можно вообще не заморачиваться и сделать что-то вроде такого:
(пара минут, сейчас накидаю)
upd: а хотя не накидаю, там в статье есть naïve method, для текущих задач сойдет

Ответить
1

Спасибо за ссылку на алгоритм, я изучу его и скорее всего переделаю свой код😄

Ответить
2

Не за что, успеха со своим рогаликом)

Ответить
4

Магазин-магазину рознь конечно, но валяющиеся по всей площади вещи - выглядит не очень. Да и лучше уж пресетом тогда делать их, имхо)
Я все же ждал алгоритмов "лабиринта" и связанных между собой уровней
( ಠ ͜ʖಠ)

Ответить
3

валяющиеся по всей площади вещи - выглядит не очень

Классика (см. правую часть карты)

Ответить
2

Вы когда-нибудь играли в Daggerfall?

Вам было интересно, как именно создаются в них здания, города или даже миры? 

Только в Даггерфоле были псевдорандомная генерация. Немного похожа на vaults в ADOM.
https://dtf.ru/games/210962-dyavolskaya-lapsha-posobie-po-vyzhivaniyu-v-daggerfolle

Ответить
1

А то, что на пути к столу лежит снаряжение это ок?

Ответить
1

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

А не проще хранить список пустых клеток? Если клетка заполнилась, то эта ячейка с координатами удаляется. Тогда не придется запускать бесконечные циклы, а только один цикл на количество предметов. 

# заполняем массив координатами:
Coord = 0
For i in range(room_array.len):
Room_array[i] = coord
Coord +=1

#Размещаем предметы
For i in range(items_amount):
Rand_array_element = random(0, room_array.len)
Coord = room_array[rand_array_element]
Put(item, coord)
Delete(room_array[rand_array_element])

Как-то так.

Предмет если подбирается, то координата возвращается в массив.

Ответить
1

Проще. Сначала генерируем n штук уникальных координат , после яего массив с коорлинатами по порядку отдаем предметам. Это стнадартная задача по работе с массиве   которую человек видит сразу после темы про массивы.  Учебнач задача по принципу  вроде - закинуть на шахматное поле фигуры с случайном порядке. 

Ответить
0

Так я это и написал...

Ответить
0

Для начала - в цикле (For i in range(items_amount):) не меняется значение переменной Coord, а это одна из главных идей ее алгоритма
Вернее, у тебя непонятно в псевдокоде, куда именно помещаются предметы случайные - видно, что ты выбираешь случайный предмет, но расположение - неслучайное, т.е. предметы будут лежать подряд.

Ответить
1

Есть массив, в котором хранятся все свободные координаты. Далее идёт цикл по предметам: берется случайное элемент массива (от 0 до длины массива координат); из этого элемента извлекается координата и присваивается предмету; элемент с координатой удаляется из массива (а значит следующий предмет ее не сможет получить). 

Ответить
1

А, так окей да.

Ответить
0

Не уверен что это тот самый случай, но я сталкивался при примерно таком построении алгоритма с проблемой, когда после удаления элемента из массива, i выходил за его пределы.

Ответить
0

Там один цикл идёт в рамках размера массива, другой в рамках количества предметов. Если между итерациями цикла не вносить изменения в объекты, то выход за пределы невозможен. Ну и если количество предметов помещается в комнате.

Ответить
1

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

Ответить
0

Это я понимаю, меня там другое сбило - не вижу старой версии коммента, не могу сказать сейчас, что именно

Ответить
0

Делаю ASCII рогалик на Java. У меня алгоритм генерирует комнаты разных форм, однако без внутренней структуры. Идея в том, что мы ставим точки в случайных координатах и ищем их пересечение, после чего проводим линии, ставим углы и дальше ставим точки. Строим уровень с левого верхнего угла, вниз против часовой стрелки.
Примеры можно посмотреть у меня в твиттере по ссылке.

#gamedev #indiegame
Версия 0.0.5. Наконец-то добавил боевую систему. Теперь можно раздавать мобам и получать соответственно. Также, у оружия и брони есть разные характеристики, влияющие на бой. Кстати, каждый моб управляется в отдельном потоке для независимости действий. https://t.co/JClCKNmpJu
Ответить
1

Нескромный вопрос: проект для души или для самообразования в разработке?

Ответить
5

Я препод в вузе и после того, как мне поставили в нагрузку предмет по Java, пришлось изучать язык. Благо я до этого работал с решётками, поэтому более менее легче разобраться. И ничего лучше не помогает освоить язык, как игровой пет-проект))
Показываю студентам время от времени игровой код для объяснения интерфейсов, потоков и других штук. Им нравится, а на реальных примерах становится понятно зачем использовать те или иные вещи в языке.

Ответить
0

А, тогда оке, не буду допытываться "а точно ли было нужно для этого использовать потоки", "а вы как именно с ними работаете" итд итп

Ответить
3

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

Ответить
0

А то, что все предметы раскиданы по углам, а не мешают проходу, получилось случайно, или где-то для этого есть пара строчек кода? Чтобы какая-нибудь кровать или кошка не перегородила проход в спальню/склад.

Ответить

Комментарии

null