Генерация подземелий в Diablo 1

Diablo 1 — это классический roguelike 1996 года в жанре hack and slash. Это была одна из первых успешных попыток познакомить широкие массы с roguelike, которые до этого имели нишевую графику в виде ASCII-арта. Игра породила несколько сиквелов и множество имитаций. Она известна своей тёмной, мрачной атмосферой, сгущающейся по мере спуска игрока в подземелья, располагающиеся под городом Тристрам. Это была одна из первых для меня игр с процедурной генерацией карт, и возможность генерации столь правдоподобных уровней просто потрясла меня.

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

Благодарю Дэвида Бревика и команду Blizard North за создание такой потрясающей игры, а также galaxyhaxz и команду Devilution за их удивительную работу по восстановлению читаемого исходного кода проекта.

Введение

Diablo — это игра, состоящая из изометрических тайлов. Игра состоит из 4 этапов, каждый из которых имеет 4 уровня. Этапы игры: Cathedral, Catacombs, Caves и Hell. Есть также несколько фиксированных уровней, например город Тристрам, которые я не буду рассматривать в статье. В Diablo есть отдельные процедуры генерации уровней для каждого из 4 этапов, поэтому я сначала расскажу об их особенностях, а затем рассмотрю по отдельности работу каждого из этапов.

Меня интересовало только то, как генерировались уровни. Чтобы узнать о квестах, монстрах и т.д. я рекомендую прочитать Jarulf’s Guide To Diablo and Hellfire, в котором эти аспекты описаны исчерпывающе подробно.

Общие особенности

Хотя для каждого этапа есть свой генератор уровней, у всех них есть общие особенности.

Подземелья и тайлы

Каждый уровень игры генерируется так, чтобы заполнить сетку размером 40 x 40 тайлов. Ось X соответствует юго-востоку, а ось Y — юго-западу.

Эти тайлы используются только для задач генерации уровней. После создания уровня каждый тайл подразделяется на 4 «фрагмента подземелья», которые рендерятся на экране.

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

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

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

Многоэтапный процесс

Каждая процедура генерации подземелья разделена на два этапа. «Предварительная генерация» вообще не имеет дела с выбором тайлов. Она просто генерирует массив, в котором помечены проходимые тайлы, тайлы, в которых есть двери, и некоторые другие высокоуровневые детали. На втором этапе эта заготовка подземелья преобразуется в массив тайлов, после чего выполняется генерация и вносятся изменения с учётом этих тайлов.

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

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

Готовые фрагменты

Готовые фрагменты — это заранее созданные блоки уровня, которые просто вставляются в случайно сгенерированный уровень. Они используются для большинства квестов игры. На каждом уровне может быть только один готовый фрагмент, расположение которого на каждом этапе выбирается по отдельности.

Butcher’s Den — один из первых готовых фрагментов, встречающихся в игре.

Мини-наборы

Мини-наборы — это ещё один способ вставки в уровень заранее созданного контента. Это небольшие кусочки, обычно размером примерно 3×3, случайным образом вставляемые в подземелье. Существует простая схема сопоставления паттернов, благодаря которой они появляются только в «правильных» местах. Часто они кодируются дополнительными требованиями, например, мини-наборы нельзя располагать близко друг к другу, они не могут накладываться на готовые фрагменты, и так далее. Некоторые мини-наборы выполняют поиск и замену всегда, а другие делают это с фиксированной вероятностью.

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

Тематические комнаты

Тематические комнаты — это небольшие пространства, ограниченные стеной и дверью. Обычно в них случайным образом расположены некие заранее заданные объекты. Например, в библиотеках всегда есть книжный шкаф с двумя свечами по бокам, несколько случайных подставок для книг и монстры. Логова монстров содержат множества монстров и случайный предмет, и так далее.

На уровнях этапа Сathedral генератор создаёт подходящие комнаты, которые распознаются при помощи заливки и используются повторно. На других этапах алгоритм находит открытые пространства, в которых для создания комнат рисуются стены и дверь.

Каждый тип тематических комнат имеет определённые требования к размеру и этапу, на котором он генерируется.

Замены тайлов

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

Сопоставление паттернов и «исправления»

Как сказано выше, в качестве механизма поиска и замены, исправляющего недочёты генератора, используются мини-наборы. Но на большинстве этапов есть процедуры, которые обнаруживают и исправляют более специфические проблемы. Я не буду вдаваться в подробности, потому что их просто куча. Достаточно сказать, что Diablo довольно забагована, и ближе к релизу стало очевидно, что проще будет добавить распознавание конкретных проблем, чем устранять их фундаментальные причины.

Одним из самых распространённых «исправлений» было «устранение блокировок» (lockout): оно проверяло, можно ли пройти по всему подземелью, и запускало генерацию заново, если это не так.

Квесты

Большинство квестов создавалось при помощи готовых фрагментов, но в некоторых использовалась и собственная логика. Например, Zhar the Mad генерирует тематические комнаты-библиотеки, вход в Poisoned Water генерируется мини-набором, а Anvil of Fury имеет специфичный код генерации уровня. Не буду вдаваться в подробности, но код переполнен подобными проверками для квестов.

Cathedral

Собор — это, наверно, самый знаковый из этапов Diablo. Он характеризуется длинными рядами готических арок, тесными комнатками и множеством узких мест в виде дверных проёмов. Давайте посмотрим, как он создавался.

Заготовка подземелья

Первое, что делает алгоритм — рисует «сердцевину» карты. Он случайным образом выбирает до трёх комнат размером 10×10 в заранее определённых позициях вдоль центральной оси X или Y. Вдоль оси также рисуется широкий коридор, соединяющий комнаты. Если на уровне есть готовый фрагмент, то он всегда располагается в центре одной из таких комнат. Эти центральные комнаты подземелья помечаются как непригодные для размещения новых стен, чтобы они всегда оставались большими открытыми пространствами.

Все остальные комнаты генерируются рекурсивной техникой «почкование» (budding) в функции под названием L5roomGen, которая инициируется в каждой из этих комнат, и выбором оси.

Функция L5roomGen

• Ей передаётся прямоугольник исходной комнаты, от которой нужно начинать почкование, а также предпочтительная ось.
• С вероятностью 1/4 меняется предпочтительная ось.
• Выбирается случайный размер новой комнаты, по 2, 4 или 6 тайлов с каждой стороны.
• Для каждой стороны исходной комнаты вдоль выбранной оси (т.е. ЮВ/НЗ для X, ЮЗ/СВ для Y):
  • Прямоугольник новой комнаты выравнивается относительно центра края исходной комнаты
  • Выполняется проверка того, что до этого там не было ничего нарисовано и мы не достигли конца карты. Для стен требуется граница в один тайл.
  • Если проверка завершилась успешно, то рисуется комната.
• Для каждой отрисовываемой комнаты рекурсивно вызывается L5roomGen, которой передаётся новая комната и ось, противоположная использованной ранее.

В конечном итоге эта процедура начинает с нескольких комнат вырезанных внутри «твёрдых» тайлов, а затем многократно приклеивает новые прямоугольники для вырезания новых проходимых областей. На этом этапе все «комнаты» открыты с одной стороны, потому что каждая новая комната размещается непосредственно рядом с предыдущей, без пропусков для размещения стен.

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

Подземелье

Пока алгоритм располагал только тайлы «тверди» и пола. Нам нужно заменить их настоящими тайлами стен. Для этого Diablo использует алгоритм marching squares, который я описывал в предыдущей статье.

Однако игра использует необычную его вариацию. Тайлсет собора содержит стены, но они всегда расположены на дальнем краю тайла. Поэтому существует тайл со стеной на северо-восточной грани, но нет тайлов со стеной на юго-восточной грани. Для создания стен на других сторонах нужно найти «твёрдый» тайл, имеющий дополнительную стену, выходящую наружу от границы тайла. Звучит странно, но на самом деле это очень удобно для сортировки стен по глубине.

Чтобы справиться с этим, Diablo на этапе marching cubes пропускает некоторые стены:

Дополнительные стены добавляются позже, на этапе «исправлений». Думаю, эта простая процедура больше всех влияет на «стиль» собора. Поскольку противоположные стены прикреплены к твёрдым тайлам, то в случае наличия двух комнат, разделённых одним тайлом стен, противоположная стена просто не будет создана. Это означает, что разделители между комнатами «тоньше», чем можно обычно получить в разрешении, при котором выполняются marching squares.

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

Затем генератор случайным образом добавляет разделяющие стены. Разделяющие стены всегда проходят прямо вдоль оси от одной стены до другой. Они начинаются с углов, благодаря чему области красиво разделяются на комнатки. В 25% случаев стена является серией арок, в 25% случаев — это серия арок с перекрывающей вход решёткой, а во всех остальных случаев — это сплошная стена. В случае решёток и сплошных стен где-нибудь вдоль разделяющей стены случайным образом добавляется дверь или арка, чтобы пространство было проходимым.

Процедура заливки обнаруживает потенциальные тематические комнаты.

Размещаются лестницы для соединения с другими уровнями. Если их разместить невозможно, то попытка генерации подземелья начинается заново.

Что касается расстановки мини-наборов, «исправлений» и замен, то их я не буду рассматривать подробно. Я больше всего люблю мини-набор PANCREAS1, имеющий вероятность 1% размещения на тайле пола кучи окровавленной плоти. В конце для украшения подземелья по нему расставляется 5-10 объектов ламп.

Catacombs

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

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

Заготовка подземелья

Процедура создания заготовки подземелья для катакомб достаточно уникальна. На всех остальных этапах есть единственное булево значение, обозначающее наличие или отсутствие пола (плюс набор битов для дополнительных деталей). Catacombs хранят заготовку подземелья в виде ASCII-карты, почти как классические roguelike. И это не особо удивительно, учитывая признание Дэвида Бревика о том, что он черпал вдохновение для Diablo из Angband.

Генератор основных комнат — это снова рекурсивный алгоритм, но на этот раз рекурсивное разделение. Функция CreateRoom вызывается для всей области подземелья размером 40×40 минус 1 тайл границы.

Функция CreateRoom

• Функции CreateRoom передаётся прямоугольник, обозначающий область, внутри которой нужно генерировать комнаты. Также функции передаются подробности об исходной комнате (изначально null)
• Если область оказалась слишком узкой, выполняется выход из функции.
• Выбирается случайный размер для комнаты в пределах от 4 до 9 тайлов по каждой из сторон с учётом максимального размера области, в которой нужно расположить комнату.
• В области выбирается случайная позиция для размещения комнаты.
• Комната отрисовывается на ASCII-карте. На рисунке символом '.' обозначаются тайлы пола, символом '#' — окружающая стена, а буквами 'A', 'B', 'C' и 'E' — четыре угла.
• Если у комнаты есть исходная комната:
  • Выбирается случайный тайл на ближайших краях исходной и новой комнат.
  • Эта информация записывается в список коридоров, который будет использован позже.
• Вырезаются оставшиеся части области, за исключением текущей комнаты, создавая четыре прямоугольника.
• Размер каждого прямоугольника уменьшается на два тайла, чтобы создать пространство между комнатами, а затем рекурсивно вызывается функция CreateRoom, в качестве области для которой используется этот прямоугольник, а в качестве исходной — созданная комната.

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

После вызовов CreateRoom получается ASCII-массив, похожий на показанный ниже (спасибо nomdenom за извлечение его из кода):

                                         
                                         
                                         
                                         
                                 A##B   
                                 #..#    
         A####B                  #..#    
         #....#                  #..#    
         #....#                  C##E    
         #....#                          
         C####E                 A#####B  
                                #.....#  
                                #.....#  
          A########B            #.....#  
          #........#            #.....#  
          #........#            C#####E  
          #........#   A#B               
          #........#   #.#               
          #........#   #.#               
          #........#   #.#               
          #........#   #.#               
          #........#   #.#               
          C########E   #.#               
                       #.#        A#B    
                       C#E        #.#    
                A####B            #.#    
                #....#            #.#    
                #....#            #.#    
                #....#            #.#    
                C####E            #.#    
                                  #.#    
                       A#####B    C#E    
                       #.....#           
                 A###B #.....#           
                 #...# #.....#           
                 C###E #.....#           
                       C#####E           

В данном случае «корневой» комнатой, созданной изначально, была самая нижняя.

Затем применяется собранная ранее информация о коридорах. Между каждой записанной парой точек проводится линия. Когда она пересекает стену, записывается 'D', а когда она пересекает твёрдый тайл, то используется ','. Коридоры имеют случайную ширину: 1, 2 или 3. Угловые тайлы используются для помощи в навигации.

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

После записи всех коридоров ASCII-карта подчищается. Угловые тайлы становятся тайлами стен, а тайлы ' ' по соседству с ',' тоже становятся стенами. Наконец, символы ',' заменяются символами '.'. Так мы получаем показанный ниже план подземелья.

                                         
                                         
                                         
                                         
                                 ####    
                                 #..#    
         ######                  #..#    
         #....#                  #..#    
         #....#                  #D##    
         #....#                  #.#     
         #D####                 ##D####  
         #..#                   #.....#  
         #..#                 ###.....#  
         ##D########          #.D.....#  
          #........#          #.#.....#  
          #........# ###      #.##D####  
          #........# #.###    #.##...#   
          #........###.D.#    #.##...#   
          #........##..#.#    #.##...#   
          #........##..#.#    #.##...#   
          #........##..#.#    #.##...#   
          #........##..#.#    #.##...#   
          ###D#######..#.#    #.##...#   
            #.......#..#.#    #.###D##   
            ###.....#..###    #.# #.#    
            #######D##.#      #.# #.#    
                #....#.#      #.# #.#    
                #....D.#      #.# #.#    
                #....######   #.# #.#    
               ##D####....##  #.# #.#    
               #...........#  #.# #.#    
               ####....###D####.# ###    
                  ######.....##.#        
                 #####.D.....##.#        
                 #...D.#.....D..#        
                 #####.#.....####        
                     #########           

Как видите, эта процедура может оставлять на карте довольно много пустого места. Поэтому следующим шагом генератора является «заполнение пустот». Он ищет любые смежные отрезки стены, к которым можно приклеить дополнительные прямоугольники пола. Прямоугольники могут быть размером не менее 5×5 и не более 12×14.

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

Это даёт нам показанную ниже заготовку подземелья.

   ##########                            
   #........# ###########                
   #........# #.........#                
   #........# #.........#                
   #........# #.........#        ####    
   #........# #.........#        #..#    
   #######..###.........#        #..#    
         #..............#        #..#    
         #..............#        #D##    
         #..............#        #.#     
         #D####.........#       ##D####  
         #..# ###########       #.....#  
         #..#                 ###.....#  
         ##D########          #.D.....#  
          #........#          #.#.....#  
   ########........# ###      #.##D####  
   #...............# #.###    #.##...#   
   #...............###.D.#    #.##...#   
   #...............##..#.#    #.##...#   
   #...............##..#.#    #.##...#   
   #...............##..#.#    #.##...#   
   #...............##..#.#    #.##...#   
   #......###D#######..#.#    #.##...#   
   #......# #.......#..#.#    #.###D##   
   #......# ###.....#..###    #.# #.#    
   #......#########D##.#      #.# #.#    
   #.........#  #....#.#      #.# #.#    
   #.........#  #....D.#      #.# #.#    
   #.........#  #....######   #.# #.#    
   #.........# ##D####....##  #.# #.#    
   #.........# #...........#  #.# #.#    
   #.........# ####....###D####.# ###    
   #.........#    ######.....##.#        
   #.........#   #####.D.....##.#        
   #.........#   #...D.#.....D..#        
   ###########   #####.#.....####        
                     #########       

Подземелье

Повторюсь, катакомбы отличаются от стандартной формулы уровней. Вместо алгоритма marching squares (который назначает тайлы на основании квадратов 2×2 заготовки подземелья) здесь используется собственная процедура сопоставления паттернов, которая рассматривает каждый из прямоугольников 3×3 заготовки подземелья и выбирает для подземелья соответствующий тайл. Паттерны определяют, чем должен быть каждый тайл заготовки подземелья: стеной, полом, дверью, сплошным тайлом, или их сочетанием. Я не совсем понимаю, почему.

Остальная часть функции покажется вам знакомой по Cathedral. На карте размещаются лестницы вверх и вниз, подземелье проверяется на возможность полного прохождения, а также выполняются различные исправления. Как описано в разделе «Общие особенности», вставляются комнаты, а затем множество мини-наборов и замен тайлов.

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

Caves

Уровни Caves заполнены обширными открытыми пространствами и реками лавы. Стены этой области грубы и волнисты. Единственными прямоугольными компонентами здесь являются деревянные помосты, которые очевидно появились позже, чем сами пещеры.

Этот этап — один из самых красивых в игре благодаря анимированной лаве. Чувствуется, что он сильно отличается от предыдущих уровней, составленных из комнат. Поэтому меня весьма удивило то, что основная часть генерации моделируется по принципам этапа Cathedral, а картам придаётся более «пещерный» вид при помощи хитрых трюков.

Заготовка подземелья

Создание уровня пещер начинается с одной случайной комнаты размером 2×2, располагающейся где-нибудь поблизости от центра карты. Затем генератор вызывает для каждого края этого блока процедуру DRLG_L3CreateBlock.

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

Процедура DRLG_L3CreateBlock

• Эта функция получает ребро прямоугольника, т.е. начальную точку, направление и длину.
• Выбирается размер нового создаваемого блока в интервале 3-4 по каждой из сторон.
• Новый блок случайным образом ставится относительно входного ребра.
• Если для отрисовки блока не хватает места, то выполняется выход.
• Блок отрисовывается.
• С вероятностью 1/4 выполняется выход.
• Рекурсивно вызывается DRLG_L3CreateBlock для трёх ребра, кроме того, из которого мы пришли.

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

После создания грубого наброска формы подземелья генератор применяет процедуры эрозии:

• Сначала он находит области тайлов 2×2 с диагонально противоположными сплошными тайлами. С такими формациями часто бывает сложно работать при выполнении marching squares, поэтому один из сплошных тайлов случайным образом заменяется полом.
• Все сплошные тайлы-одиночки, окружённые 8 тайлами пола, заменяются на тайл пола.
• Все длинные и прямые секции стен случайным образом огрубляются заменой 50% стен тайлами пола.
• Повторно устраняются диагонали из сплошных тайлов.

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

Если на ней есть менее 600 тайлов пола, то карта генерируется заново.

Подземелье

Заготовка подземелья преобразуется в тайлы при помощи marching squares. В отличие от Cathedral и Catacombs, тайлсет здесь намного удобнее, и содержит почти все комбинации, необходимые для marching squares. В нём отсутствуют тайлы для диагонально противоположных стен, но они были устранены в фазе заготовки, поэтому никогда не появляются.

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

Добавляются озёра лавы. Алгоритм ищет смежную секцию стен при помощи заливки. Если ему удаётся найти секцию стен/сплошных тайлов меньше 40 тайлов, полностью окружённых тайлами пола, то они заменяются лавой. Если озеро лавы невозможно найти, то генерация подземелья начинается заново.

Стена размером 3×3 превращается в озеро лавы

Затем добавляется несколько лавовых рек. Генератор предпринимает несколько попыток нарисовать реку, начинающуюся с озера лавы и заканчивающуюся в стене. К реке предъявляются следующие требования: она не должна пересекать себя, река имеет длину 7-100 тайлов, и на ней должно быть подходящее место для размещения моста. Тайл моста гарантирует, что вся карта остаётся проходимой. При наличии места на карту может быть добавлено до четырёх рек.

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

Hell

Hell — последний этап Diablo. В нём основной упор делается уже на монстрах, а дизайн уровней уходит на второй план. Этот этап имеет самый маленький тайлсет из всех, и бОльшая его часть используется для огромных лестниц и пентаграмм. Адские уровни обычно состоят из несколкьих квадратных комнат и имеют симметричную схему.

Заготовка подземелья

Генерация Hell начинается со случайной комнаты размером 5-6 тайлов по каждой стороне (больше, если в ней есть готовый фрагмент для квеста), а затем применяется то же рекурсивное почкование, что и в Cathedral. Однако генерация ограничена областью 20×20.

Добавляется вертикальный и горизонтальный коридор, растянутый до края области 20×20.

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

Подземелье

Заготовка подземелья снова преобразуется в тайлы при помощи marching squares. Затем аналогично созданию Cathedral добавляются стены, и как в Catacombs и Caves.

Заключение

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

Вот самые важные для меня уроки:

• Дьявол кроется в деталях: отдельные компоненты не являются безумно сложными, но в сочетании дают нечто замечательное. Представляю, как разработчики корпели над повышением качества, пока уровни не превратились из просто хороших в потрясающие. Количество тайлов и комбинаторная сложность тайлсетов тоже очень высока — невозможно реализовать это без внимания к тому, как соединяются элементы.
• Поиск и замена для сопоставления паттернов — очень мощный инструмент, при помощи которого можно реализовать множество различных эффектов. Он устраняет баги генерации, добавляет вариативности, вставляет заранее созданный контент, управляет эрозией и делает многое другое.
• Разделение генерации подземелья на карту проходимости (заготовку подземелья) и генерацию тайлов — тоже очень удобная техника, как с точки зрения дизайна, так и отладки.
• Если хотите придать разным областям разный стиль, то отличным решением является создание отдельного алгоритма. Большую часть кода можно использовать многократно, и при этом всё равно создавать очень отличающиеся стили.
• Если возникают сомнения, приклеивайте по сторонам элементов больше прямоугольников.

Автор: PatientZero

Источник