Генерация подземелий или как потеряться в массивах. Часть II.⁠⁠

И снова привет, Pikabu! С момента первых двух постов появились некоторые изменения:

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

В прошлый раз мы остановились на том что создали отдельный одномерный массив, содержащий id каждой игровой комнаты, а также гигантскую матрицу, в которой хранится наша сетка с расположением каждого блока на игровом поле. Что же дальше? А дальше нужно как-то соединить эту байду друг с другом, ведь бегать мы будем между комнатами, а не нарезать круги по одной и той же (логично(нет)).

Одним из удобных графических представлений связей между объектами в 2D плоскости является так называемый Граф:

Граф - это такой абстрактный математический объект, представляющий из себя множество вершин и ребер - соединений этих вершин между собой. Графы бывают разные (и они не обязательно напоминают символ сатаны) - они могут быть взвешенными, ориентированными, двудольными, связными.. В общем, куча их. Так какой же нам выбрать? Давайте подумаем. В нашем подземелье между комнатами будут туннели, и очень желательно чтобы они были как можно меньше (вспомните того шакала из прошлого поста), поэтому дистанция между комнатами - важный параметр. Граф, в котором такой параметр учитывается, называется взвешенным, и у каждого ребра такого графа пишется его "вес". В нашем случае - это дистанция между комнатами, и чем она меньше - тем лучше. Направления, в котором эти комнаты связаны, нам не особо и вперлось - какая разница куда бежать, вправо или влево, вверх или вниз между комнатами? В случае необходимости, мы можем пробежать по туннелю и два раза (мало ли, забыли итем в соседской комнате?). Это значит, что граф неориентированный, т.е., не имеет определенных, залоченных направлений движения. Вот и определились. Теперь нужно подумать, как представить его в коде, а не на бумаге. Можно сделать это структурой, например, где каждый элемент будет вершиной графа, содержащий указатели на все другие вершины.. (фу) Однако, в GMS2 я не особо то и обнаружил возможность нормально реализовать данный метод (или плохо искал). Так что, что мы говорим структурам?

И выбираем матрицу :3

Не зря ведь в заголовке написано "как потеряться в массивах" - надо оправдывать название) Берем наш двумерный массив, пробегаемся по каждой комнате по её id и вызовем функцию GMS distance_to_object(). Запишем значение в соответствующую ячейку, и, вуаля, получим заполненный массив с расстояниями между всеми комнатами. Теперь дело за малым - находим в каждой строке матрицы минимальное значение, не включая элемент, в котором индекс строки совпадает с индексом столбца (очевидно, ведь это путь от себя до себя и он равен 0) и сохраняем отдельно. Теперь у нас есть список наименьших путей, по которому мы сможем соединить между собой все комнаты. Но, думаю, если здесь есть те, кто имеет опыт работы с GMS и уже успели задаться вопросом: зачем заниматься всем этим, заполнять матрицу и искать меньшие значения, если есть чудесная функция instance_nearest(), которая и находит минимальную дистанцию до ближайшего объекта? Отвечу:

А вернее, я буду использовать не только самый короткий путь до комнаты, но и (с долей вероятности) буду искать еще один короткий, не включая предыдущий. Зачем?

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

Итак, самое основное сделано - теперь мы знаем что связать друг с другом и как это сделать. Самое время построить туннели, ведь ради них все и затевалось. Но не так все просто оказалось, нежели я думал. Сначала я взял самое очевидное решение - построить из центра одной комнаты палку вверх, а из центра другой - палку в сторону. И знаете что?

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

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

Что пришло мне на ум - у нас есть матрица игрового поля, почему бы не поработать с ней?

Алгоритм вышел такой:

1) Вычисляем положение наших двух комнат в матрице игрового поля

2) "Вырезаем" часть матрицы, в которой эти комнаты располагаются

3) В строках матрицы, где располагаются наши комнаты, ищем такую, в которой количество пустот минимально. Тоже самое со столбцами

4) Найденную строку и столбец заполняем полностью нулями, что означает для моей матрицы расположение туннеля.

Результат:

Желтые комнаты - основные, которые попытались соединиться. Алгоритм определил путь, по которому лежит минимальное количество пустоты и заполнил его туннелем. Осталась последняя загвоздка - справа внизу вы видите тупики, ведь алгоритм в тупую заполнил строку и столбец массива, не учитывая эту ситуацию. Проблема решилась с первого раза (что удивительно) - в цикле я запустил проверку в массиве на условие: "если рядом с ячейкой тоннеля есть меньше двух "соседей" (клетки комнат или такого же туннеля) - это значит, что это тупик, следовательно, заполни его пустотой".

Финальная версия генерации на данный момент выглядит примерно так:

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

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

P.S. спасибо тем, кто оставлял комментарии по поводу генерации в прошлом посту - появилось пара идей для реализации)