Проблема, которую нужно решить: создайте случайную 2D карту подземелий для игры на основе тайлов, где все комнаты соединены.
Я ищу лучшие решения, чем у меня сейчас.
Мое текущее решение состоит в том, что я запускаю два алгоритма. Первый генерирует подземелье со своими комнатами. Второй убедитесь, что все комнаты связаны. Мне любопытно, какие другие решения могут существовать. Быстрее и / или проще и т. Д. Скорость на самом деле не является проблемой, но если скорость может быть достигнута без реальных затрат, это хорошо. Более важно то, что я и другие читающие могут научиться различным подходам и решению проблемы.
Ниже моя текущая реализация. В настоящее время номера не имеют выходов или выходов в 2, 3 или 4 направлениях.
Генерация комнат подземелья
Настройка: установите текущую комнату в верхнюю левую комнату.
- Получите действительный тип комнаты для комнаты (где действительный тип комнаты - это тип, в котором нет выходов из темницы и у которых есть выходы, которые соответствуют выходам из комнаты выше и комнаты слева. Необходимо только проверить выше и осталось из-за шага 2 ниже).
- Положите комнату и продвиньте координату X на один шаг. Если x-координата превышает ширину подземелья, установите x-координату на 0 и продвиньте y-координату на один шаг. Если у-координата превышает высоту подземелья, все готово.
- Повторите с # 1.
Затем я проверяю, все ли комнаты подключены. Если они не все подключены, я запускаю второй алгоритм, который не совсем сексуально, но, безусловно, достаточно хорошо с точки зрения планировки подземелий, проходит через комнаты и меняет их так, чтобы все до подключения.
Проверка, все ли номера подключены
Настройка: Создайте двумерную карту целых чисел, представляющих пути, и инициализируйте записи значением «необработанное» (еще не пройденное), -1. Установите целочисленный индекс начального пути, который отслеживает текущий путь, равным 1. Установите текущую комнату в верхнюю левую комнату, добавив ее в стек комнат для проверки.
- Если в стеке есть комнаты для проверки, выведите его, чтобы установить индекс пути комнаты к текущему индексу пути. Если в стеке нет комнат, увеличьте индекс пути и попробуйте получить комнату, продвигая столбец за столбцом, строку за строкой, пока мы не получим комнату, которая еще не была обработана. Если нет места, мы закончили.
- Проверьте, есть ли выход в комнату слева. Если он добавил, добавьте левую комнату в стек, если его там еще нет.
- Повторите шаг 2 для направлений вниз, вправо и вверх (поскольку мы используем стек, что означает, что комнаты перемещаются по часовой стрелке, начиная с верхнего направления).
- Повторите с шага 1.
- Если число индексов пути больше единицы, есть отключенные комнаты.
Если есть отключенные комнаты, я затем группирую комнаты по их индексу пути, получаю индекс наибольшего пути и соединяю все остальные комнаты с этими комнатами. Это незавершенная работа, но мой (текущий, "грубый") план - пройти каждую комнату в группе комнат (кроме первой), чтобы проверить, есть ли горизонтальный или вертикальный путь к группе комнат biggeset, и если так, создайте горизонтальный / вертикальный путь там, вставляя / обновляя комнаты между ними. Промыть и повторить. Безобразно, да, но это то, что не будет заметно с точки зрения визуального шаблона, поэтому оно работает в этом смысле.
источник
Ответы:
Один из лучших и наиболее используемых алгоритмов, которые я когда-либо видел, - это создание подземелий с использованием Binary Space Partitioning.
Лучшее общее объяснение, которое я прочитал, - это найденное в «Хрониках Дорина» (прикреплено в конце для целей резервного копирования), потому что объясняет процедуру, не входя в код, оставляя реализацию читателю.
Два других учебника на ту же тему с кодом можно найти по адресу
источник
Метод BSP, по-видимому, является наиболее популярным методом генерации подземелий, но он не единственный.
Для полноты я объясню генератор, который работал для меня . Я должен признать , что я не помню , где я читал об этом , так что я просто скажу , что это не мое изобретение ( старая статья по Jamis Buck звучит очень знакомо).
Лабиринт с комнатами
Основная идея заключается в том, что подземелье - это лабиринт с комнатами. Итак, первым шагом для этого алгоритма является создание лабиринта :
Следующий шаг - сделать его разреженным (удалить тупики):
Шаг № 3 - добавить несколько циклов (сделать их неидеальными ), но я пропущу изображение, потому что оно едва заметно (мне не нужен был идеальный лабиринт, поэтому я сделал несколько ярлыков алгоритма генерации лабиринта, так что он уже были петли к этому моменту).
Затем для шага 4 нам нужно удалить изолированные клетки:
На данный момент мы закончили с коридорами и готовы добавить комнаты. Для этого мы делаем следующее:
Пока что наше подземелье будет выглядеть так:
Последний шаг - добавить украшения.
Несколько заключительных мыслей
источник