Рекурсивная генерация уровней

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

Введение

Эта статья содержит некоторые из моих мыслей относительно генерации уровней в roguelike- играх. Это вдохновлено алгоритмом использованным в Alphaman'е, для генерации зданий, некоторыми статьями, прочитанными в Roguelike News и, что немного странно, форматами входных файлов Bison и Yacc. Идеи могут показаться немного сложными и трудными для осуществления, но я надеюсь, что так или иначе статья окажется полезной.

Обзор

Идея в том, чтобы описывать уровень в форме наподобие BNF (Backus-Naur Form), причём для описания обычно используются свободные от контекста грамматические формы.

Для людей естественно описывать большие и сложные объекты через более простые. Так, мы можем описать уровень. Например: уровень может являться: лабиринтом (maze), темницей/подземельем (dungeon), пещерой (cave), замком (castle), и т.п... лабиринт является набор связанных коридоров и перекрёстков. коридор является вертикальной или горизонтальной линией тайлов пола, окруженной стенами с каждой стороны и открытой, по меньшей мере, в одном направлении. перекрёсток является одним тайлом пола со стенами вокруг, открытым по меньшей мере в двух направлениях. темница/подземелье - набор комнат, перекрёстков и коридоров. комната может являться: хранилищем (vault), малым хранилищем (minor vault), обычной комнатой (ordinary room). и т.п...

Некоторые из правил здесь не выполняются. Например, мы хотели бы обеспечить, чтобы каждое место уровня было досягаемо. Это не очень легко сделать, так что мы не будем пытаться описывать любой тип уровня, как в примере выше. Мы только попытаемся описать (а потом сгенерировать) несколько специфичный тип уровня, создаваемый делением комнат. Здания Alphaman'а.

Мы используем алгоритм аналогичный использованному в Alphaman'е. Сначала я опишу оригинальный алгоритм. Он довольно простой:

1. Начнём с большой пустой комнаты.

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

2. Выберите ось (горизонтальную или вертикальную) и точку внутри комнаты (подальше от стен). Давайте предположим, что мы выбрали горизонтальную ось и точку отмеченную '1'.

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X......1........X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

3. Сделаем стену, проходящую вдоль выбранной оси, пересекающую выбранную точку, ограниченную стенами комнаты и с дверью в точке '1'.

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X######+########X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

4. Вы получили две новые комнаты. Повторим процедуру с теми из них, которые достаточно велики.

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X###########+###X
X...............X
X...............X
X...............X
X...............X
X######+########X
X.........#.....X
X.........+.....X
X.........#.....X
X.........#.....X
X.........#.....X
XXXXXXXXXXXXXXXXX

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

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

Добавление коридоров

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

1. Начнём с большой пустой комнаты.

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

2. Выберите ось (горизонтальную или вертикальную) и точку внутри комнаты (подальше от стен). Давайте предположим, что мы выбрали горизонтальную ось и точку отмеченную '1'.

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X......1........X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

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

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X###############X
X......1........X
X###############X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

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

XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X####+######+###X
X......1........X
X###+###########X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX

5. Вы получили две новые комнаты. Повторим процедуру с теми из них, которые достаточно велики.

XXXXXXXXXXXXXXXXX
X...............X
X###+###########X
X...........2...X
X#####+#####+###X
X...............X
X...............X
X####+######+###X
X......1........X
X###+#####.#####X
X........#3#....X
X........#.+....X
X........+.#....X
X........#.#....X
XXXXXXXXXXXXXXXXX

Результат выглядит не так плохо, в особенности если окончательно оставленные комнаты достаточно велики (в примере не слишком много места). Но есть другая проблема - как заполнить комнаты подходящим содержимым (то есть предметами и монстрами)? Как убедиться что комнаты соединены с некоторой логикой?

Определения уровней

Вот что мы можем сделать. Мы не только будем делить на две аналогичные комнаты. Мы должны назвать эти комнаты и обеспечивать некоторые правила их разделения. Например, для научного уровня в научно-фантастической roguelike-игре (scientific level in sf roguelike):

  • уровень может быть: (положим здесь некоторую вероятность), научным уровнем (be a scientific level);
  • научный уровень (scientific level) должен быть: по крайней мере большего РАЗМЕРА, но больше чем на РАЗМЕР; (be at least SIZE large, but not larger than SIZE;)
  • научный уровень (scientific level) может состоять: из двух научных секций (scientific sections), разделенных (горизонтально или вертикально) научным холлом (scientific hall);
  • научный холл (scientific hall) может быть: очень широким коридором, с большими дверями по концам и по меньшей мере одной дверью с каждой стороны; там может быть несколько растений или статуй; там может быть несколько научных охранников (scientific guards); там может быть может быть немного научных монстров (scientific monsters); там даже может быть немного научных учёных (scientific scientifists);
  • научная секция (scientific section) может состоять: из двух научных секций (scientific sections) разделенных (горизонтально или вертикально) научным коридором (scientific corridor);
  • научный коридор (scientific corridor) может быть: широким коридором с открытыми входами по концам и по крайней мере одной дверью с каждой стороны;
  • научная секция (scientific section) должна быть: по крайней мере большего РАЗМЕРА, но больше чем на РАЗМЕР; (be at least SIZE large, but not larger than SIZE;)
  • научная секция (scientific section) может состоять: из двух научных лабораторий (scientific labs) разделенных (горизонтально или вертикально) научным коридором (scientific corridor);
  • научная лаборатория (scientific lab) должна быть: по крайней мере большего РАЗМЕРА, но больше чем на РАЗМЕР; (be at least SIZE large, but not larger than SIZE;)
  • научное лаборатория (scientific lab) может состоять: состоите из двух научных лабораторий (scientific labs) разделенных научной стеной (scientific wall);
  • научная стена (scientific wall) может быть: стеной с дверью посередине;
  • научная лаборатория (scientific lab) может быть: быть комнатой с кафельным полом (tiled floor); там может быть несколько научных артефактов (scientific artifacts); там может быть может быть немного научных монстров (scientific monsters); там даже может быть немного научных учёных (scientific scientifists);

Построение уровня

Теперь, давайте посмотрим как сделать произвольный уровень исходя из такой информации. Сначала, мы хотим сформировать уровень. Итак, мы смотрим определения и видим как наш уровень может стать научным уровнем (scientific level) с такой-и-такой вероятностью. Но также могут быть и другие определения уровня, так что мы должны выбрать (произвольно) определение уровня. Давайте предположим, что мы выбрали научный уровень (scientific level). Мы видим, что он должен быть таким-и-таким большим, поэтому мы обеспечим пустую начальную комнату данного размера. Теперь мы смотрим в определение и видим как мы должны разделить наш уровень на два научным холлом (scientific hall) и с каждой стороны поместить по научной секции (scientific section). Итак, мы выбираем точку, выбираем ось, помещаем наш коридор в середине и научные секции (scientific section) с каждой стороны. Будет неплохо обращать внимание на минимальный размер каждой из секций при выборе точки для разделения уровня. Затем, мы должны сделать наши научные секции (scientific sections). Посмотрев определения, мы увидим, что у нас есть два варианта. Итак, мы произвольно выбираем один из них. Мы можем или разделить эти секции на меньшие, или в научные лаборатории (scientific labs). В некоторых точках, мы должны делать второе, поскольку может не найтись места, чтобы разместить научную секцию (scientific section) (которая предполагается больше чем лаборатория). Мы продолжим вниз дерево элементов уровня (level features), пока не придем к 'атомам', которые не состоят из других элементов и которые мы можем генерировать используя другие алгоритмы. Иногда может возникнуть потребность в алгоритме, чтобы 'сохранять' (to 'back up') неправильные решения, поскольку они могут и не дойти до атомов (because there is no way it can get to the atoms). Это обусловлено ограничениям размера. Это недостаток и я не знаю как убедиться что уровень когда-нибудь будет завершён. Но я верю, что это каким-то образом можно решить. Представление уровня

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

The Sheep



Автор: Radomir "The Sheep" Dopieralski.
Источник: неизвестен.
Перевел: Дмитрий О. Бужинский, 26.02.2006.