Привет, Pikabu! С моего первого поста прошло всего несколько дней, но, на удивление для меня, кому-то стало все-таки интересно что творится под капотом страшной фразы "генерация подземелий" и как изнутри выглядит её код говнокод. Поэтому передаю привет моим трём подписчикам:
и начинаю свой рассказ про то как потратить полтора месяца блуждая по массивам. Материала получилось много, поэтому с коротким промежутком выпущу две части, чтобы ничего не упустить и не запихать все в одну кашу.
Первое, что приходит на ум при придумывании очередного велосипеда на тему создания подземелий - это наспаунить кучу квадратов и соединить их палками. А что, круто же? Комнаты есть, туннели - есть, бегай да собирай бонусы. Вот так и думал мой препод, для которого левел дизайн это "расставь алмазик в трех местах = три разных уровня". Помимо того, что это не так уж и просто сделать, такой подход еще и выглядит отчасти убого, ведь алгоритм объединения отдельных комнат туннелями в таком случае будет примитивным - соедини две ближних и получишь "змейку" из квадратов. Пара дней сидения за гуглом и спешным транслейтом ангельского языка на русский привели меня к статье на хабре, в которой примерно был описан алгоритм неплохой генерации, но на Юнити. Однако, цитировать его слово в слово я не буду, ведь:
так что, опишу то, что изменил под себя и как это выглядит на нашем деревенском GMS2.
Начало простое и логичное. Алгоритм последовательной генерации квадратов налагает на себя одну большую проблему - эти квадраты необходимо разместить так, чтобы они друг друга не касались. Да, можно поступить по топорному - пусть алгоритм ищет пустое место и тыкает туда комнату, размер которой будет рандомным. Вроде и не пересекается, вроде и недалеко друг от друга. Однако, если нам понадобится:
а) определенное количество основных комнат
б) определенный размер комнат
то мы выстрелим себе в ногу, потому что нам либо придется писать кучу условий на проверку свободного места (и в случае нехватки либо распределять заново либо удалять лишнее), либо сидеть и надеяться, что без этих условий рандом сжалится и ни разу не улетит в бесконечный цикл, наткнувшись на место, в которое нужно воткнуть комнату но не нельзя уместиться в минимальный размер.
Решение здесь такое же простое и ленивое - зачем думать над условиями, если программа сама может решить твою проблему? Существует такое понятие как "флокирующее поведение". Это поведение объекта (именуемого агентом) в условии присутствия других таких же объектов. У него существуют несколько ограничений, связывая которые можно получить различный тип поведения, от преследования до убегания. В моем случае, генерируем случайное количество комнат на плоскости со случайным размером в радиусе определенной окружности, определяем вектор каждой комнаты до ближайшего соседа, и просто разворачиваем его в обратную сторону. Иными словами:
Таким образом, расположенные рядом на очень близком расстоянии объекты, разлетаются друг от друга в противоположных направлениях. В итоге, мы получаем гарантированное "несовпадение" по координатам в независимости от размера комнат. В коде это выглядит примерно так:
"если я касаюсь какого-то выродка - посмотреть в его сторону и бежать в противоположную со скоростью 10"
Разбежавшись, комнаты занимают свои позиции и переводят дух. Теперь их ждет вторая стадия - необходимо определиться, кто здесь главный и с кем из соседей этот главный хочешь скорешиться. Забыл упомянуть, как это все хранится: каждая комната это обычный объект GMS2, имеющий координаты, спрайт, а также возможность добавления кода. Для того, чтобы дальше работать с ними как с совокупностью, а не раздельным сбродом, я добавляю id каждого объекта в специальный одномерный массив. Массив хранится в еще одном объекте, который отвечает здесь вообще за всю тусовку связанную с генерацией - obj_dungeonGenerator. Вон сидит, сидит палит
Комнат получается много, поэтому нужно отсечь лишние и взять нужные. Под нужными я понимаю те, которые имеют определенный размер, например, больше среднего. "Лишние" комнаты, однако, совсем не лишние. Почему? Взгляните сюда:
Зеленые квадраты - это нужные комнаты, а красные линии - потенциальные соединения между ними. И знаете что меня напрягает? Вот этот шакал:
Т.е, в некоторых случаях мы получим ситуацию, при которой может сгенерироваться гигантский туннель, незаполненный абсолютно ничем, но счастливо соединяющий нужные нам комнаты. Напоминает "я сделяль", и нас это категорически не устраивает. Игрок, бегущий по такому пространству, быстрее плюнет на игру чем дойдет до соседней комнаты. Чтобы этого избежать можно не идти далеко за грибами - просто берем и включаем в список нужных комнат те, которые умудрились попасть на эту линию. Выходит что-то вроде:
Однако, это еще не конец истории. Окунемся немножко в теорию вероятностей чтобы было понятно о чем речь. В ненавистной мной ТВ (из-за тотального её непонимания когда я сидел на её парах) существует понятие равномерно распределения. Оно используется в любимой нами функции radom(), random_range() и прочих прочих. Согласно термину: "В теории вероятностей случайная величина имеет дискретное равномерное распределение, если она принимает конечное число значений с равными вероятностями." Это значит, что рандомно задавая размер комнаты, мы, каждый раз, можем равновероятно получить как большую, так и среднюю или малую комнату в нашем диапазоне. Как это нам мешает? Такое распределение создает ситуацию, в которой все комнаты получаются примерно одинакового размера. Поэтому, на моменте отбора нужных комнат получится, что мы отберем 10 самых больших, но на фоне останутся, фактически, такие же комнаты, только чуууть меньше или больше. Из этого следует, что в качестве туннелей мы получим не линию из маленьких комнат, а совокупность больших инвалидов, которые уместились по соседству. В своей игре я хочу иметь понятие "основной" и "дополнительной" комнаты - в первой будут сундуки и плюшки с сильными мобами, во вторых - прочая мишура для тира, которую можно пробежать и забыть, не сильно при этом скучая. Поэтому я беру на вооружение так называемое Геометрическое распределение. Оно отличается вероятностью появления каждого последующего события, т.е., чем дальше от начала отсчета "событие", тем меньше вероятность его появления. Таким образом, мы получим маленькое количество больших, и большое количество маленьких комнат, что играет нам на руку - первые в основные, вторые - на мясо. В итоге этого выглядит примерно так (на скрине еще старое, равномерно распределение, но прикрепляю его чтобы видно было дело, а не рисунки с пэинта):
На нем видно окружность, из которой выползли уже готовые комнаты, а также их разделение на основные и дополнительные. Однако, многие посмотрят на скриншот и спросят:
А это еще одна отдельная история. Получив равномерно распределенные по пространству и геометрически распределенные по размерам комнаты мы, по сути, ничего и не сделали - это просто набор объектов, хоть и располагающихся так, как нам нужно. Следующая задача - это сформировать из них массив, каждая ячейка которого будет отвечать за свое место в пространстве и то, что в нем находится - стена, пол, дверь или же пропасть. Благодаря этому массиву в будущем мы сформируем карту тайлов, которые и отрисуют нам графику (с ними, кстати, я недавно разобрался), а не цифры. Чтобы его сделать я отсортировываю все комнаты по х-координате и y-координате и выбираю самые крайние по четырем направлениям.
Получив их, я вычитаю самую верхнюю координату по Y из самой нижней, и самую правую из самой левой по X, получая, тем самым, размер всего занятого комнатами пространства. Дело осталось за малым - делим эти дистанции на размер нашей сетки (я выбрал 16 пикселей, т.к. всю графику буду рисовать именно в этом стиле) и, вауля, у нас получилась матрица определенного размера и с определенной шириной ячейки, однако, она все еще пустая.
Пробегаемся вложенным циклом по этому двумерному массиву с таким условием: "если по координатам этой ячейки ничего нет - кладем туда #, если есть главная комната - кладем 2, если дополнительная - кладем 1", а затем, пробегаем второй раз с другим условием: "если рядом с единицой или двойком в матрице есть # - заменяем его на +", получая тем самым заполненную матрицу с расположением комнат, стен, а также пустых пространств.
Итак, что мы имеем в конце всего этого сложного действа? Во-первых, массив комнат, к каждому элементу которого мы можем отдельно обратиться в случае необходимости. Во-вторых - готовую матрицу, в которой хранится расположение комнат и стен, и, которая, поможет нам при отрисовке тайлов стен и пола. Таким образом, мы подготовили платформу для последующего объединения комнат в граф и создания связей при помощи туннелей, о которых я расскажу в следующем посте.
P.S. имхо, получилось скучнее и нуднее, чем я ожидал, поэтому заранее извиняюсь за слог. В следующий раз попытаюсь вещать более лаконично и грамотно, а то так даже мемасики не спасут положение. Отметьте в комментариях что непонятно или чего недостаточно, пишу такое, отчасти, в первый раз, так что постараюсь уточнить все, что смогу