Алгоритм для процедурного 2D-карты со связанными путями

26

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

Я ищу лучшие решения, чем у меня сейчас.

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

Ниже моя текущая реализация. В настоящее время номера не имеют выходов или выходов в 2, 3 или 4 направлениях.

Генерация комнат подземелья

Настройка: установите текущую комнату в верхнюю левую комнату.

  1. Получите действительный тип комнаты для комнаты (где действительный тип комнаты - это тип, в котором нет выходов из темницы и у которых есть выходы, которые соответствуют выходам из комнаты выше и комнаты слева. Необходимо только проверить выше и осталось из-за шага 2 ниже).
  2. Положите комнату и продвиньте координату X на один шаг. Если x-координата превышает ширину подземелья, установите x-координату на 0 и продвиньте y-координату на один шаг. Если у-координата превышает высоту подземелья, все готово.
  3. Повторите с # 1.

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

Проверка, все ли номера подключены

Настройка: Создайте двумерную карту целых чисел, представляющих пути, и инициализируйте записи значением «необработанное» (еще не пройденное), -1. Установите целочисленный индекс начального пути, который отслеживает текущий путь, равным 1. Установите текущую комнату в верхнюю левую комнату, добавив ее в стек комнат для проверки.

  1. Если в стеке есть комнаты для проверки, выведите его, чтобы установить индекс пути комнаты к текущему индексу пути. Если в стеке нет комнат, увеличьте индекс пути и попробуйте получить комнату, продвигая столбец за столбцом, строку за строкой, пока мы не получим комнату, которая еще не была обработана. Если нет места, мы закончили.
  2. Проверьте, есть ли выход в комнату слева. Если он добавил, добавьте левую комнату в стек, если его там еще нет.
  3. Повторите шаг 2 для направлений вниз, вправо и вверх (поскольку мы используем стек, что означает, что комнаты перемещаются по часовой стрелке, начиная с верхнего направления).
  4. Повторите с шага 1.
  5. Если число индексов пути больше единицы, есть отключенные комнаты.

Если есть отключенные комнаты, я затем группирую комнаты по их индексу пути, получаю индекс наибольшего пути и соединяю все остальные комнаты с этими комнатами. Это незавершенная работа, но мой (текущий, "грубый") план - пройти каждую комнату в группе комнат (кроме первой), чтобы проверить, есть ли горизонтальный или вертикальный путь к группе комнат biggeset, и если так, создайте горизонтальный / вертикальный путь там, вставляя / обновляя комнаты между ними. Промыть и повторить. Безобразно, да, но это то, что не будет заметно с точки зрения визуального шаблона, поэтому оно работает в этом смысле.

user1323245
источник
1
Вы проверили "Dungeon Generation" на PCG вики ? Это отвечает на ваши вопросы?
congusbongus
@congusbongus Полезное чтение наверняка. Этот генератор донжонов, связанный с этой страницей, просто потрясающий. Спасибо.
user1323245

Ответы:

33

Один из лучших и наиболее используемых алгоритмов, которые я когда-либо видел, - это создание подземелий с использованием Binary Space Partitioning.

Лучшее общее объяснение, которое я прочитал, - это найденное в «Хрониках Дорина» (прикреплено в конце для целей резервного копирования), потому что объясняет процедуру, не входя в код, оставляя реализацию читателю.

Два других учебника на ту же тему с кодом можно найти по адресу


Построение дерева BSP

Мы начнем с прямоугольного подземелья, заполненного клеточными стенами. Мы собираемся рекурсивно разделять это подземелье, пока каждое подземелье не будет иметь размер комнаты. Разделение подземелья использует эту операцию:

  • Выберите случайное направление: горизонтальное или вертикальное разделение
  • Выберите случайную позицию (x по вертикали, y по горизонтали)
  • Разделите подземелье на два подземелья

введите описание изображения здесь

Теперь у нас есть два подземелья A и B. Мы можем применить одну и ту же операцию к ним обоим.

введите описание изображения здесь

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

введите описание изображения здесь

Строительство подземелья

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

введите описание изображения здесь

Чтобы построить коридоры, мы перебираем все листья дерева, соединяя каждый лист с его сестрой. Если в двух комнатах есть стены лицом к лицу, мы можем использовать прямой коридор. В противном случае мы должны использовать Z-образный коридор.

введите описание изображения здесь

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

введите описание изображения здесь

Мы повторяем процесс до тех пор, пока мы не соединим первые два подподземелья A и B

введите описание изображения здесь

reefaktor
источник
Может быть ничего не стоит, что этот метод никогда не будет создавать петли, однако я не уверен, есть ли способ обойти это без добавления дополнительных случайных коридоров. Все еще очень хороший ответ, +1
Vality
Это многообещающее начало. Просто нужно найти способ добавить несколько циклов, но я скорее работаю над этой проблемой, чем продолжаю идти по пути, по которому я сейчас нахожусь. Спасибо.
user1323245
2
Ницца ! Мне был интересен идентификатор, поэтому я сделал небольшую попытку. Вы должны быть осторожны при использовании случайных, иначе последуют слишком странные результаты. И мне интересно, не следует ли обрабатывать коридоры прямо во время рекурсивного разбиения, потому что я не вижу простого способа построить коридоры из дерева. В любом случае, для всех, кто интересуется скрипкой, здесь: jsfiddle.net/gamealchemist/xt57zwb8
GameAlchemist
Хотя я нахожу это несколько проблематичным в повторяющейся сеяной процедуре в больших средах. Вероятно, это один из лучших методов, которые я когда-либо видел для такого поколения, если вы генерируете весь свой уровень сразу. Я +1 это
Тот Бездомный Парень
4

Метод BSP, по-видимому, является наиболее популярным методом генерации подземелий, но он не единственный.

Для полноты я объясню генератор, который работал для меня . Я должен признать , что я не помню , где я читал об этом , так что я просто скажу , что это не мое изобретение ( старая статья по Jamis Buck звучит очень знакомо).

Лабиринт с комнатами

Основная идея заключается в том, что подземелье - это лабиринт с комнатами. Итак, первым шагом для этого алгоритма является создание лабиринта :

Лабиринт, созданный с помощью вариации алгоритма Эллера

Следующий шаг - сделать его разреженным (удалить тупики):

Сделать разреженным: удалить тупики

Шаг № 3 - добавить несколько циклов (сделать их неидеальными ), но я пропущу изображение, потому что оно едва заметно (мне не нужен был идеальный лабиринт, поэтому я сделал несколько ярлыков алгоритма генерации лабиринта, так что он уже были петли к этому моменту).

Затем для шага 4 нам нужно удалить изолированные клетки:

Удалить изолированные клетки

На данный момент мы закончили с коридорами и готовы добавить комнаты. Для этого мы делаем следующее:

  1. Генерация набора комнат (ширина и высота)
  2. Для каждой комнаты мы перебираем все возможные места и выбираем лучшее место.
    • Наилучшее местоположение рассчитывается путем добавления веса к условиям (например, смежность с коридором).
  3. Мы размещаем комнаты.

Пока что наше подземелье будет выглядеть так: Номера добавлены

Последний шаг - добавить украшения.

Нарисуйте двери и номера комнат

Несколько заключительных мыслей

  • Я использовал урезанную версию алгоритма Эллера .
  • Различные алгоритмы лабиринта могут привести к различным текстурам. Вы можете предпочесть другой алгоритм. Например, на следующем рисунке показаны различные текстуры, полученные в результате использования алгоритма «Двоичное дерево» (диагональное смещение) и варианта алгоритмов «Рекурсивное деление» (длинные коридоры): Двоичное дерево против псевдо-рекурсивного деления
Roflo
источник
2
Хорошая вещь. Я искал разные способы сделать это, поскольку использование разных алгоритмов для разных уровней может сделать игру еще более универсальной.
user1323245