- PVSM.RU - https://www.pvsm.ru -
Все ошибки по данной статье присылайте, пожалуйста, в личные сообщения.
Я люблю смотреть на звездное небо и размышлять о далеких мирах, но факт бесконечности вселенной с трудом укладывается в моей голове. Согласно теории большого взрыва, наша вселенная непрерывно расширяется и охлаждается из сингулярного состояния, но давайте предположим, что наша бесконечная вселенная постоянно генерируется по определенным правилам, и количество этих правил ограниченно. Можно допустить, что наша вселенная уже сгенерировалась, то есть для каждой точки бесконечной вселенной уже была произведена генерация по конечному числу правил (генерация была произведена бесконечное количество раз), в итоге мы имеем бесконечную сгенерированную вселенную.
Вернемся к нашей задаче, нам нужно интеллектуально генерировать карты для IPhone/IPad игры типа «Марио», для начала мы рассмотрим генерацию карты в пределах поля 128х128 кубов.
Зачем вообще генерировать карту для игры, если можно ее нарисовать в редакторе карт? Разрабатывая iOS игру «танчики», я сделал редактор уровней с возможностью сохранять уровень на моем сервере, я рассчитывал, что игроки сами будут рисовать карты и присылать мне. Но действительность оказалась более суровой, игроки меня завалили тысячами карт, которые, мягко говоря, были непроработанными, недоделанными и просто некрасивыми. Разрабатывая новую игру, я твердо решил, уровень должен генерироваться автоматически и выглядеть, насколько это возможно, сравнимо с уровнями из редактора.
Что мы имеем:
-Карта состоит из 128x128 блоков, каждый блок размером 32х32 пикселя;
-Карта хранится в виде массива 128х128, где:
Для начала я решил реализовать функцию генерации карты простой формулой, включающей функцию рандомизации. Изменяя значения переменных в формуле, я надеялся откалибровать карту до приемлемого состояния.
Формула генерировала следующие элементы игровой карты:
Минусы генерации уровня методом «рандома»
Улучшая сложность формулы для генерации карты можно было бы добиться лучшего результата, но мной было решено двигаться по другому пути.
Требования, которым должен отвечать алгоритм
Как же генерировать карты? По шаблонам! А шаблоны в себе будут содержать более мелкие шаблоны (подшаблоны).
Для начала давайте разделим наше игровое поле на 64 квадрата, 8х8, для каждого из этих квадратов мы в дальнейшем будем подгружать значения из шаблона, давайте назовем этот квадрат «комнатой». Итак, теперь карта у нас состоит из 8х8=64 комнат.
Суть игры состоит в том, чтобы пробраться из точки A (точка входа) в точку B (точка выхода), перемещаясь при этом из одной комнаты в другую. В данном случае, точка входа находится в верхнем ряду комнат, а точка выхода — внизу карты.
Итак, для начала нам нужно проложить маршрут (путь), по которому игроку следует двигаться. Для этого мы разобьем наши комнаты на типы:
Данный алгоритм генерации пути напоминает устройство машины Тьюринга, у нас есть управляющее устройство (головка записи-чтения), которая перемещается по матрице комнат. Число возможных состояний управляющего устройства конечно и точно задано, состояния соответствуют типам комнат.
На данном этапе мы сформировали путь движения для персонажа, теперь просто заполняем все незатронутые алгоритмом комнаты нулями (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:
При составлении карты из шаблона мы пользуемся следующими правилами:
Если собирать карту из шаблонов, то на больших картах будут повторяющиеся участки с блоками, наша задача сделать карты в рамках одного шаблона непохожими друг на друга.
Для этого, помимо зеркалирования шаблонов по горизонтали, мы вводим цифры 8 и 9 в шаблонах, которые при вероятности 75% и 50% соответственно, заменяются на единицу (блок земли). Если наша ГЗЧ (головка записи-чтения) натыкается на цифру 7 — то этот участок шаблона заменяется на «подшаблон», который считывается по схожим с шаблоном правилам.
Подшаблоны также введены, чтобы сделать два одинаковых шаблона непохожими друг на друга. В шаблонах присутствуют цифры 7 — если алгоритм натыкается на цифру 7, то он заполняет шаблон любым «подшаблоном» из файла boxTemplate.plist
Примеры подшаблонов:
00100
01110
0010011111
01110
0010000100
11111
00100
Для подшаблонов также в 50% случаев делаем зеркальное отражение слева-направо.
Я пытался избежать создание графического редактора карт, но для отрисовки шаблонов мне все равно пришлось его реализовать. Чем больше шаблонов и подшаблонов вы добавите в игру, тем более разнообразно будут выглядеть ваши карты.
На данных четырех скриншотах вы видите один и тот же шаблон, который благодаря цифрам 7,8,9 выглядит каждый раз по разному.
На видео можно посмотреть, как генерация уровней выглядит на практике:
Если вас заинтересовала данная тематика, дайте знать, я раскрою тему более детально.
Для составления этой статьи я частично использовал алгоритмы генерации уровней из игры Spelunky, но возможно, существуют игры с более продвинутой генерацией уровней, о которых я не знаю.
Напишите в комментариях, какие еще игры с хорошей генерацией уровней вы знаете.
Автор: megabraza
Источник [1]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/ios-development/88894
Ссылки в тексте:
[1] Источник: http://habrahabr.ru/post/255775/
Нажмите здесь для печати.