Давайте сделаем рогалик (Строим подземелье)

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

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

Каждый уровень подземелья, это на самом деле сетка из квадратов, называемых тайлами, которая изначально заполнена «камнями» или, попросту говоря, непроходимыми участками местности. В этом пространстве камней мы вырезаем комнаты, тайлы которых помечены как проходимые, как правило это пол, но также это может быть вода, трава, лава или любой другой тип местности. Мы добавляем комнаты случайным образом, на основе одного из нескольких алгоритмов (или сочетании алгоритмов), пока не достигнем желаемого количества комнат. Как только все комнаты созданы, мы должны соединить их прихожими, это как правило узкие коридоры, помеченные как проходимая местность. После того, как все комнаты связаны между собой, у нас есть подземелье. Затем мы можем заполнить подземелье предметами, монстрами — всем тем, что нам необходимо в игре.

Так что мы можем разбить алгоритм на несколько шагов:

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

Есть некоторые вещи, которые мы должны иметь ввиду:

  • Процесс должен быть достаточно быстрым (никто не хочет ждать 5 минут, пока строиться уровень).
  • Количество комнат должно быть разумным. Если игроку нужно будет исследовать сотни комнат, то скука наступит раньше, чем он найдет лестницу вниз, к следующему уровню.
  • В каждую комнату должен быть доступ. Нет ничего хуже. Чем обнаружить, что выход на следующий уровень находится в комнате, в которую игрок не может попасть.

Возникает законный вопрос, какой алгоритм мы будем использовать для создания комнат? Ответ: есть множество алгоритмов. Я выделю некоторые из наиболее популярных методов, а затем подробно объясню метод, который мы будем использовать в Подземелье Судьбы.

Содержание

Метод проб и ошибок

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

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

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

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

Метод комната-коридор

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

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

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

Вы начинаете с разбиения уровня на 2 региона случайных размеров, вертикально или горизонтально. После разбиения информация о каждом регионе сохраняется в узлах дерева, один узел на каждый регион. Затем выберите один из полученных регионов и разбейте его снова сохраняя два новых региона в ветви дерева выбранного региона для разбиения. В результате у вас получиться бинарное дерево. Продолжайте этот процесс до тех пор, пока не получите желаемое количество комнат. Как только дерево будет построено, в конечных узлах (листьях) будут содержаться регионы в которых необходимо создать комнаты.

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

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

Существует очень хороший пример метода двоичного разбиения пространства на вики RogueBasin.

Метод лабиринта

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

Сеточный метод

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

Есть несколько преимуществ при использовании данного метода. Он работает достаточно быстро, так как вы выбираете случайным образом целый регион, а не точку на карте. Сетка позволяет использовать заранее заготовленные макеты для комнат, как и использовать различные настройки для генерации полностью случайных лабиринтов или городов. Поскольку каждый регион имеет одинаковые размеры, то легче будет создать комнаты не прямоугольных размеров, и можно быть уверенным, что они будут «соответствовать». Метод позволяет легко создавать и использовать шаблоны комнат подготовленные заранее и загруженные с диска. Т. к. каждый регион в сетке одинакового размера, вы можете разрабатывать сложные шаблоны комнат, которые несомненно будут вписываться в уровень.

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

Сеточный метод в деталях

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

map.bi

'Минимальный и Максимальный размер комнаты
#DEFINE roommax 8
#DEFINE roommin 4
#DEFINE nroommin 20
#DEFINE nroommax 50
'Признак пустой ячейки.
#DEFINE emptycell 0
'Размер уровня
#DEFINE mapw 100 'ширина карты
#DEFINE maph 100 'высота карты

'Размер ячейки сетки (ширина и высота)
Const csize = 10
'Количество ячеек сетки по высоте и ширине карты.
Const gw = mapw \ csize
Const gh = maph \ csize

'Координаты.
Type mcoord
    x As Integer
    y As Integer
End Type

'Размер комнаты.
Type rmdim
    rwidth As Integer
    rheight As Integer
    rcoord As mcoord
End Type

'Информация о комнате
Type roomtype
    roomdim As rmdim  'Высота и ширина комнаты.
    tl As mcoord      'Квадрат комнаты (задается 2 углами)
    br As mcoord
End Type

'Структура ячейки сетки.
Type celltype
    cellcoord As mcoord 'Позиция ячейки.
    room As Integer     'Индекс комнаты. Это индекс в массиве комнат.
End Type

Dim Shared rooms(1 To nroommax) As roomtype    'Массив комнат.
Dim Shared grid(1 To gw, 1 To gh) As celltype  'Массив ячеек сетки.
Dim Shared As Integer numrooms                 'Кол-во комнат на карте.


Тип mcoord задает координаты x и y точки в массиве карты уровня. Rmdim — задает размеры комнаты. Поле coord указывает на центр комнаты. Нам это нужно для подпрограммы построения коридоров, в которой мы хотим, чтобы коридоры соединялись с комнатами в центре одной из стен. Это упростит построение коридоров и избавит нас от хитрых математических формул, если комната не будет прямоугольной. Определение roomtype содержит информацию о комнате, ее ширину, высоту, центр, а также координаты верхнего левого угла комнаты и нижнего правого. На самом деле нам не обязательно знать координату правого нижнего угла комнаты (как в прочем и левого верхнего (примечание переводчика)), но это упростит код путем предварительного расчета прямоугольника комнаты. Тип roomtype используется для создания массива rooms, который будет содержать список всех комнат на карте.

Тип celltype описывает регион (ячейку), нашей сетки. Он содержит расположение региона на карте и индекс комнаты в этом регионе из массива комнат. Идентификатор комнаты нужен для того, чтобы мы знали, в каком регионе находится та или иная комната. Двумерный массив grid содержит все регионы, он задает нашу сеть. Количество ячеек в сетке задаются двумя рассчитанными константными значениями Const gw = mapw \ csize для задания ширины и Const gh = maph \ csize высоты сетки. Константы mapw и maph задают ширину и высоту нашего уровня в тайлах карты, csize задает размер ячейки сетки в тайлах. В нашем случае csize=10, что на карте размером 100x100 дает нам сеть 10 на 10 ячеек. Максимальный и минимальный размер комнаты задаются константами roommax=8 и roommin=4, которые определяют занимаемое комнатой место в регионе, что даст нам рамку непроходимых блоков вокруг комнаты.

И, наконец, переменная numrooms будет содержать количество комнат на нашем уровне. Будут еще какие то значения для задания минимального и максимального количества комнат на карте в диапазоне от 20 до 50. Это даст нам от 20 до 50 комнат на уровень, более чем достаточно для одного уровня подземелья. Так как мы используем не более 50% сетки, то генерация уровня будет проходить достаточно быстро.

Инициализация сетки

Первое что нужно сделать, это инициализировать нашу сетку.

map.bi

'Инициализируем массивы сетки и комнат
Sub InitGrid
    Dim As Integer i, j, x, y, gx = 1, gy = 1

    'Очистим массив комнат.
    For i = 1 To nroommax
        rooms(i).roomdim.rwidth = 0
        rooms(i).roomdim.rheight = 0
        rooms(i).roomdim.rcoord.x = 0
        rooms(i).roomdim.rcoord.y = 0
        rooms(i).tl.x = 0
        rooms(i).tl.y = 0
        rooms(i).br.x = 0
        rooms(i).br.y = 0
    Next
    'Сколько будет всего комнат
    numrooms = RandomRange(nroommin, nroommax)
    'Создадим немного комнат
    For i = 1 To numrooms
        rooms(i).roomdim.rwidth = RandomRange(roommin, roommax)
        rooms(i).roomdim.rheight = RandomRange(roommin, roommax)
    Next
    'Очимтим массив сетки
    For i = 1 To gw
        For j = 1 To gh
            grid(i, j).cellcoord.x = gx
            grid(i, j).cellcoord.y = gy
            grid(i, j).Room = emptycell
            gy += csize
        Next
        gy = 1
        gx += csize
    Next
    'Добавим комнаты к ячейкам
    For i = 1 To numrooms
        'Найдем пустую ячейку
        Do
            x = RandomRange(2, gw - 1)
            y = RandomRange(2, gh - 1)
        Loop Until grid(x, y).Room = emptycell
        'Центр комнаты
        rooms(i).roomdim.rcoord.x = grid(x, y).cellcoord.x + (rooms(i).roomdim.rwidth \ 2)
        rooms(i).roomdim.rcoord.y = grid(x, y).cellcoord.y + (rooms(i).roomdim.rheight \ 2)
        'Зададим прямоугольник комнаты
        rooms(i).tl.x = grid(x, y).cellcoord.x
        rooms(i).tl.y = grid(x, y).cellcoord.y
        rooms(i).br.x = grid(x, y).cellcoord.x + rooms(i).roomdim.rwidth + 1
        rooms(i).br.y = grid(x, y).cellcoord.y + rooms(i).roomdim.rheight + 1
        'Сохраним индекс комнаты
        grid(x, y).Room = i
    Next
End Sub


Подпрограмма InitGrid вначале очищает массив rooms для того, чтобы мы могли заполнить его новыми комнатами.

map.bi

...
'Очистим массив комнат.
For i = 1 To nroommax
    rooms(i).roomdim.rwidth = 0
    rooms(i).roomdim.rheight = 0
    rooms(i).roomdim.rcoord.x = 0
    rooms(i).roomdim.rcoord.y = 0
    rooms(i).tl.x = 0
    rooms(i).tl.y = 0
    rooms(i).br.x = 0
    rooms(i).br.y = 0
Next
...


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

map.bi

...
'Сколько будет всего комнат
numrooms = RandomRange(nroommin, nroommax)
'Создадим немного комнат
For i = 1 To numrooms
    rooms(i).roomdim.rwidth = RandomRange(roommin, roommax)
    rooms(i).roomdim.rheight = RandomRange(roommin, roommax)
Next
...


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

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

map.bi

...
'Очимтим массив сетки
For i = 1 To gw
    For j = 1 To gh
        grid(i, j).cellcoord.x = gx
        grid(i, j).cellcoord.y = gy
        grid(i, j).Room = emptycell
        gy += csize
    Next
    gy = 1
    gx += csize
Next
...


Просто перебираем все ячейки сетки, сохраняя координаты каждой ячейки на карте и присваиваем значение emptycell параметру Room, что указывает, что в данный момент ячейка пуста. Теперь мы готовы добавить к сетке наши комнаты.

map.bi

...
'Добавим комнаты к ячейкам
For i = 1 To numrooms
    'Найдем пустую ячейку
    Do
        x = RandomRange(2, gw - 1)
        y = RandomRange(2, gh - 1)
    Loop Until grid(x, y).Room = emptycell
    'Центр комнаты
    rooms(i).roomdim.rcoord.x = grid(x, y).cellcoord.x + (rooms(i).roomdim.rwidth \ 2)
    rooms(i).roomdim.rcoord.y = grid(x, y).cellcoord.y + (rooms(i).roomdim.rheight \ 2)
    'Зададим прямоугольник комнаты
    rooms(i).tl.x = grid(x, y).cellcoord.x
    rooms(i).tl.y = grid(x, y).cellcoord.y
    rooms(i).br.x = grid(x, y).cellcoord.x + rooms(i).roomdim.rwidth + 1
    rooms(i).br.y = grid(x, y).cellcoord.y + rooms(i).roomdim.rheight + 1
    'Сохраним индекс комнаты
    grid(x, y).Room = i
Next
...


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

Рисуем комнаты

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

map.bi

'Поместить данные из сетки в массив карты.
Sub DrawMapToArray
    Dim As Integer i, x, y, pr, rr, rl, ru, kr

    'Добавим первую комнату в массив карты
    For x = rooms(1).tl.x + 1 To rooms(1).br.x - 1
        For y = rooms(1).tl.y + 1 To rooms(1).br.y - 1
            level.lmap(x, y).terrid = tfloor
        Next
    Next
    'Добавим остальные комнаты в массив карты и объединим их
    For i = 2 To numrooms
        For x = rooms(i).tl.x + 1 To rooms(i).br.x - 1
            For y = rooms(i).tl.y + 1 To rooms(i).br.y - 1
                level.lmap(x, y).terrid = tfloor
            Next
        Next
        ConnectRooms i, i - 1
    Next
End Sub


Вначале мы добавляем первую комнату в массив карты, т. к. он уже заполнен у нас значениями стен (непроходимых блоков), то мы просто заполняем необходимые ячейки карты значениями «пол» и у нас получаться комнаты. После добавления первой комнаты, мы добавляем все остальные в цикле и объединяем их коридорами. Именно для соединения комнат между собой мы добавили первую комнату отдельно, чтобы у нас уже были готовы 2 комнаты для вызова подпрограммы ConnectRooms, которая объединит их коридором.

Объединение комнат

Как только в массиве карты у нас есть 2 комнаты, нам нужно объединить их коридором

map.bi

'Объединение всех комнат.
Sub ConnectRooms( r1 As Integer, r2 As Integer)
    Dim As Integer idx, x, y
    Dim As mcoord currcell, lastcell
    Dim As Integer wflag

    currcell = rooms(r1).roomdim.rcoord
    lastcell = rooms(r2).roomdim.rcoord

    x = currcell.x
    If x < lastcell.x Then
        wflag = FALSE
        Do
            x += 1
            If level.lmap(x, currcell.y).terrid = twall Then wflag = TRUE
            If (level.lmap(x, currcell.y).terrid = tfloor) And (wflag = TRUE) Then
                Exit Sub
            Endif
            level.lmap(x, currcell.y).terrid = tfloor
        Loop Until x = lastcell.x
    End If

    If x > lastcell.x Then
        wflag = FALSE
        Do
            x -= 1
            If level.lmap(x, currcell.y).terrid = twall Then wflag = TRUE
            If (level.lmap(x, currcell.y).terrid = tfloor) And (wflag = TRUE) Then
                Exit Sub
            Endif
            level.lmap(x, currcell.y).terrid = tfloor
        Loop Until x = lastcell.x
    Endif

    y = currcell.y
    If y < lastcell.y Then
        wflag = FALSE
        Do
            y += 1
            If level.lmap(x, y).terrid = twall Then wflag = TRUE
            If (level.lmap(x, y).terrid = tfloor) And (wflag = TRUE) Then
                Exit Sub
            Endif
            level.lmap(x, y).terrid = tfloor
        Loop Until y = lastcell.y
    Endif

    If y > lastcell.y Then
        Do
            y -= 1
            If level.lmap(x, y).terrid = twall Then wflag = TRUE
            If (level.lmap(x, y).terrid = tfloor) And (wflag = TRUE) Then
                Exit Sub
            Endif
            level.lmap(x, y).terrid = tfloor
        Loop Until y = lastcell.y
    Endif
End Sub


Предыдущий код выглядит несколько сложнее, чем простой алгоритм Манхэттенского расстояния (Manhattan distance). Мы передвигаемся по массиву уровня из первой комнаты во вторую добавляя коридор по ходу движения. Первое что нам нужно сделать, это получить отправную и конечную точки.

map.bi

...
currcell = rooms(r1).roomdim.rcoord
lastcell = rooms(r2).roomdim.rcoord
...


Сперва мы проверяем, конечная точка находится справа или слева от начальной. Если слева, то мы движемся влево: x-=1, иначе вправо x+=1, пока координата коридора x не совпадет с x координатой конечной точки. Если x координаты равны, то мы ничего не делаем. Как только координаты x совпадают, мы проделываем тоже самое для координаты y. Когда обе координаты совпадают — мы достигли конечной комнаты.

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

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

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

Перевод на русский: Fantik

содержание | назад | вперед