Алгоритм построения подземелий

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Введение

Интересные произвольные карты - одна из вещей, которые делают roguelike-игры уникальными. Они существенно увеличивают удовольствие от игры, поскольку игрок всегда может столкнуться со свежими вызовами и разными проблемами.

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

В этой статье я описал технику, которую я разрабатываю для использования в своей собственной небольшой roguelike-игре Tyrant. Я сомневаюсь, что это совершенно оригинальная идея, но прежде я никогда не видел в точности такой же алгоритм используемый для создания подземелий. Как бы то ни было, он достаточно хорошо работает, так что я решил поделиться этим с миром.

Цели построителя подземелий

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

Базовому подземелью требуется:

  • набор взаимосвязанных комнат, дверей и туннелей
  • вход (лестница вверх)
  • выход (лестница вниз)
  • каждое пространство должно быть достижимо

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

План

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

Вдохновение исходило из мысли: "Если я был жителем подземного мира, как бы я подошёл к построению своего подземелья?" или: "Если я был преступником, как бы я подошёл о строительству своей темницы?"

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

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

Алгоритм

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

  1. Заполните всю карту сплошной землёй
  2. Выкопайте простую комнату в центре карты
  3. Выберите произвольную стену любой комнаты
  4. Решите, какое новое улучшение будете строить
  5. Посмотрите, нет за выбранной стеной комнаты, которую заденет новое улучшение
  6. Если нет, продолжайте. Если есть, вернитесь к шагу 3
  7. Добавьте улучшение по ту сторону выбранной стены
  8. Пока подземелье не закончено, возвращайтесь к шагу 3
  9. Добавьте лестницы вверх и вниз в произвольные точки карты
  10. И, наконец, свободно разбросайте по подземелью несколько монстров и предметов.

Шаги 1 и 2 просты, так как вы только что создали карту. Я обнаружил, что очень полезно написать команду "fillRect", которая заполняет прямоугольную область карты определенным типом тайлов.

Шаг 3 мудрёнее. Вы не можете выбирать произвольные квадраты, чтобы добавить новые улучшения, поскольку по правилам требуется всегда добавлять к существующему подземелью. Это делает соединения наглядными и также гарантирует, что каждый квадрат будет достижим. В Tyrant'е это сделано следующим путём: на карте выбираются произвольные квадраты, пока не найдется квадрат со стеной, совмещённый (горизонтально или вертикально) с пустым квадратом. Это хороший метод, поскольку он дает вам даже возможность приблизительно выбрать любой конкретный квадрат стены.

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

Шаг 5 - более мудрёный, и ключевой во всём алгоритме. Для каждого улучшения вам нужно знать область карты, которую он займёт. Затем вам нужно просканировать область снаружи от выбранной стены чтобы увидеть, не пересечётся ли область с какими-нибудь улучшениями которые там уже есть. Tyrant делает это довольно упрощённым образом - он просто берёт прямоугольное пространство, которое займёт новая характеристика плюс по квадрату с каждой стороны для стен, затем проверяет, будет ли этот прямоугольник полностью заполнен сплошной землей.

Шаг 6 решает добавлять характеристику или нет. Если рассматриваемая область уже содержит что-нибудь ещё кроме твердой земли, тогда программа переходит к шагу 3. Отметьте, что таким образом будет отвергнуто *большинство* новых улучшений. Это не проблема, так как время обработки незначительно. К каждому подземелью Tyrant пытается добавить 300 или около того улучшений, но обычно только 40 или около того проходят этот этап.

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

Шаг 8 просто повторение цикла, чтобы построить больше комнат. Точное количество раз, сколько вы захотите проделать это, будет зависеть от размера карты и разных других причин.

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

Шаг 10 просто создает кучу дополнительных произвольных монстров в случайно выбранных местах, чтобы добавить немного остроты. Tyrant создаёт большинство монстров именно во время генерации карты, хотя он добавляет несколько специальных существ когда сгенерированы отдельные комнаты.

Ну, вот и всё. Это все в "псевдокоде", но если вам нужен специфический пример реализации - напишите мне. В этом случае сможете увидеть специфику на Java...

Пример

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

Обозначения:

# = Пол
D = Дверь
W = Рассматриваемая стена

1. Первая комната

 #####
 #####
 #####

2. Выбираем произвольную стену

 #####
 #####W
 #####

3. Сканируем область для нового коридора (включая пространство по всем сторонам)

 #####**********
 #####W*********
 #####**********

4. Всё чисто, так что добавим новое улучшение

 #####
 #####D########
 #####

5. Выберем другую стену:

 #####     W
 #####D########
 #####

6. Сканируем область для новой комнаты

       ******
       ******
       ******
       ******
       ******
#####  ***W**
#####D########
#####

7. Область в порядке, так что добавим новую комнату. Бросьте в ней ящик (C) для хорошей пометки

        ####
        ###C
        ####
        ####
#####     D  
#####D########
#####

8. Добавим другой коридор как и раньше

             #
             #
        #### #
        ###C #
        #### #
        #### #
#####     D  #
#####D########
#####

9. А теперь, мы пытаемся добавить коридор ко второй комнате.

             #
             #
        #### #
        ###C*******
        ####W******
        ####*******
#####     D  #
#####D########
#####

10. Это терпит неудачу, поскольку сканируемая область уже использована.

             #
             #
        #### #
        ###C #
        #### #
        #### #
#####     D  #
#####D########
#####

11. Причудливое улучшение. Добавим восьмиугольную комнату

             #
             #   ###
        #### #  #####
        ###C # #######
        #### #D#######
        #### # #######
#####     D  #  #####
#####D########   ###
#####

12. За потайной дверью скрывается коридор, зверски заставленный ловушками:

             #
             #   ###
        #### #  #####
        ###C # #######S###T##TT#T##
        #### #D#######
        #### # #######
#####     D  #  #####
#####D########   ###
#####

13. И так, я могу продолжать и продолжать......

Заключение

Ну, вот и весь мой алгоритм. Я надеюсь, что вы найдёте его полезным или по крайней мере интересной перспективой для решения этой частной задачи.

Если вы хотите увидеть результаты прямо сейчас, вы можете скачать разрабатываемую версию Tyrant'а на:

С 18-4-1999, версия игры должна включать как глубокий лесной уровень, так и уровни подземелий, которые были созданы с использованием точно такой же техники.

Удачного программирования, Mike.



Автор: Mike Anderson.
Источник: Dungeon-Building Algorithm, Copyright © 16.04.1999.
Перевел: Дмитрий О. Бужинский [Bu], 19.05.2005.