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

Вернемся к нашей задаче, нам нужно интеллектуально генерировать карты для IPhone/IPad игры типа «Марио», для начала мы рассмотрим генерацию карты в пределах поля 128х128 кубов.

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

Что мы имеем:
— Карта состоит из 128x128 блоков, каждый блок размером 32х32 пикселя;
— Карта хранится в виде массива 128х128, где:

• 0 — пустой блок;
• 1 — земля, персонаж может перемешаться по этому блоку и может его взорвать;
• 2 – камень — блок, который нельзя взорвать;
• 3 — ящик с драгоценностями;
• 4 — шипы, при падении на которые игрок умирает;

Генерация уровней простым путем или метод «рандома»

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



strong>Формула генерировала следующие элементы игровой карты:

1. Этажи: вся карта делилась на условные этажи, расстояние между этажами определялось функцией «Rand».
2. Проемы: между этажами генерировалось случайное количество проходов случайной ширины.
3. Шум: на этажах образовывались случайные блоки.
4. Комнаты: на каждом этаже формировалось случайное количество прямоугольных комнат с одним, двумя выходами или без выходов.
5. Беговые дорожки: для того, чтобы игрок мог разогнаться во время бега, на каждом этаже генерировалось случайное количество прямых дорожек для бега, над некоторыми их них случайно отрисовывался «потолок» случайной высоты.

Минусы генерации уровня методом «рандома»

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

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

Требования, которым должен отвечать алгоритм

• Для данной игры главный герой должен пробраться из точки А в точку В.
• Во время продвижения по уровню игрок не должен застрять или наткнуться на тупик.
• Необходимо наличие пространства для полетов на реактивном ранце.

Генерация уровней с помощью использования пути

Как же генерировать карты? По шаблонам! А шаблоны в себе будут содержать более мелкие шаблоны (подшаблоны).

Для начала давайте разделим наше игровое поле на 64 квадрата, 8х8, для каждого из этих квадратов мы в дальнейшем будем подгружать значения из шаблона, давайте назовем этот квадрат «комнатой». Итак, теперь карта у нас состоит из 8х8=64 комнат.

Суть игры состоит в том, чтобы пробраться из точки A (точка входа) в точку B (точка выхода), перемещаясь при этом из одной комнаты в другую. В данном случае, точка входа находится в верхнем ряду комнат, а точка выхода — внизу карты.

Итак, для начала нам нужно проложить маршрут (путь), по которому игроку следует двигаться. Для этого мы разобьем наши комнаты на типы:

• 0: Комната, которая не находится на пути основного маршрута.
• 1: Комната, из которой гарантированно есть выход слева и справа.
• 2: Комната, из которой гарантированно есть выход слева, справа и внизу.
• 3: Комната, из которой гарантированно есть выход слева, справа и вверху.

Данный алгоритм генерации пути напоминает устройство машины Тьюринга, у нас есть управляющее устройство (головка записи-чтения), которая перемещается по матрице комнат. Число возможных состояний управляющего устройства конечно и точно задано, состояния соответствуют типам комнат.

• Для начала мы помещаем первую комнату в верхнем ряду, тип комнаты может быть 1 или 2, но для начала мы выставляем тип 1.
• Затем мы должны решить, в каком направлении мы должны двигаться, для этого мы берем наугад число от 1 до 5, если это число 1 или 2 — то двигаем наш путь влево, если 2 или 3 — тогда вправо, если это число 5 — тогда мы двигаемся вниз, при этом меняя тип самой первой комнаты с 1 на 2 (теперь у стартовой комнаты есть выход внизу).
• Если при движении наш путь «упирается» в границы экрана слева или справа, то мы меняем направление на противоположное. Стоит отметить, что каждый раз, когда мы двигаемся вниз, мы должны перезаписать тип текущей комнаты с 1 на 2 (так как у этой комнаты добавляется выход снизу).
• После перемещения в следующую комнату, мы проверяем, из какой комнаты мы только что переместились. Если из комнаты с типом 2 — то теперь наша комната может иметь снова тип 2 (с очередным выходом вниз) или тип 3 (выход сверху, слева и справа). Так как комнаты типа 2 и 3 имеют выходы слева и справа — то мы можем повторять наш алгоритм вновь и вновь.
• Если мы уже находимся в нижнем ряду, и алгоритм предлагает нам двигаться еще ниже, то мы просто размещаем выход из комнаты и завершаем алгоритм.

На данном этапе мы сформировали путь движения для персонажа, теперь просто заполняем все незатронутые алгоритмом комнаты нулями (0 — комната, которая может и не иметь выходов вообще).

Параметры алгоритма

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

Если на первом пункте алгоритма выбирать случайное число от 1 до 7, при выпадании числа от 1 до 3 — двигаться влево, при числе от 4 до 6 — вправо, а при числе 7 — вниз, то во время генерации на каждом этаже будет больше комнат типа «1», это сделает путь более запутанным. Случайное число от 1 до 3, по аналогии сделает путь менее извилистым.

Отображение пути на карте

На данных скриншотах я замостил непутевые комнаты типа «0» для лучшего отображения пути.

Шаблоны

Каждая комната представляет из себя 16х16 квадратов, всего у нас 4 типа комнат, для каждого типа комнат шаблоны будут находиться в отдельном .plist файле:

room0.plist
room1.plist
room2.plist
room3.plist

Для начала определим ограничения для наших типов комнат, комнаты типа 1 не имеют выходов снизу и сверху, а значит независимо от шаблона, выходы сверху и снизу для комнат типа 1 можно сразу «закрыть». Для комнат типа 2 мы «закрываем» выход снизу, а для комнаты типа 3 — выход сверху.



Каждый раз для каждой комнаты типа 1 программа выбирает любой шаблон из файла room1.plist,
и для этого шаблона в 50% случаев делает зеркальное отражение слева-направо.

Рассмотрим пример шаблонов для комнат типа 1:



При составлении карты из шаблона мы пользуемся следующими правилами:

• 0 — пустой блок;
• 1 — земля, персонаж может перемешаться по этому блоку и может его взорвать;
• 2 – камень — блок, который нельзя взорвать;
• 3 — ящик с драгоценностями;
• 4 — шипы, при падении на которые игрок умирает;
• 7 — «подшаблон» — блок высотой 3 и шириной 5.
• 8 — 75% вероятность того, что здесь будет земля. 25% — вероятность пустоты.
• 9 — 50% вероятность того, что здесь будет земля.

Маскировка шаблонности

Если собирать карту из шаблонов, то на больших картах будут повторяющиеся участки с блоками, наша задача сделать карты в рамках одного шаблона непохожими друг на друга.
Для этого, помимо зеркалирования шаблонов по горизонтали, мы вводим цифры 8 и 9 в шаблонах, которые при вероятности 75% и 50% соответственно, заменяются на единицу (блок земли). Если наша ГЗЧ (головка записи-чтения) натыкается на цифру 7 — то этот участок шаблона заменяется на «подшаблон», который считывается по схожим с шаблоном правилам.

Подшаблоны

Подшаблоны также введены, чтобы сделать два одинаковых шаблона непохожими друг на друга. В шаблонах присутствуют цифры 7 — если алгоритм натыкается на цифру 7, то он заполняет шаблон любым «подшаблоном» из файла boxTemplate.plist

Примеры подшаблонов:

00100
01110
00100

11111
01110
00100

00100
11111
00100

Для подшаблонов также в 50% случаев делаем зеркальное отражение слева-направо.

Я пытался избежать создание графического редактора карт, но для отрисовки шаблонов мне все равно пришлось его реализовать. Чем больше шаблонов и подшаблонов вы добавите в игру, тем более разнообразно будут выглядеть ваши карты.

Результат использования «подшаблона»

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


На видео можно посмотреть, как генерация уровней выглядит на практике:

Перспективы

• Количество шаблонов напрямую влияет на качество уровня, так что добавление новых шаблонов сильно улучшит геймплей.
• Для более разнообразных карт можно сделать «подшаблоны» в «подшаблонах».
• Меняя масштаб мира и точки входа и выхода — можно генерировать бесконечную карту, динамически формируя блоки на пути персонажа и кэшируя пройденные участки.

Если вас заинтересовала данная тематика, дайте знать, я раскрою тему более детально.

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

Напишите в комментариях, какие еще игры с хорошей генерацией уровней вы знаете.

Все ошибки по данной статье присылайте, пожалуйста, в личные сообщения.