Процедурная генерация уровней для игр-головоломок

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

Здорово было бы найти способ заставить компьютер сэкономить вам время и решить проблемы, о которых я сказал выше… И именно тут на помощь приходит процедурная генерация!

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

Fruit Dating — правила и особенности

Не так давно мы выпустили игру Fruit Dating для устройств iOS (также она доступна для Android и даже для невыпущенного (на момент релиза игры) Tizen). Это игра-головоломка с простыми правилами. Её цель — соединять пары фруктов одного цвета, проводя пальцем по экрану. Перемещение пальца соответствует наклону игрового поля в нужном направлении. Когда игрок пытается выполнить свою задачу, на его пути встают различные препятствия, такие как камни, машины и другие фрукты. Все подвижные объекты перемещаются в одном направлении. На картинках ниже показан первый уровень, в котором для соединения фруктов требуется 3 хода.





Со временем добавляются новые особенности:

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

Вы наверно уже заметили, что уровень состоит из плиток; это упрощает работу, потому что каждый уровень может быть представлен как маленькая сетка. Её максимальный размер 8x8 плиток, но всегда есть неподвижная граница, так что «полезная» область не больше 6x6 плиток. Этого может показаться мало, но доказано, что для такого поля можно создать достаточно сложные задачи.

На основании базовых правил (так как дополнительные возможности были добавлены позднее) я начал создавать свой генератор. Сначала я конечно подумал, что кто-то в мире уже решил похожую проблему, так что я начал искать в интернете процедурную генерацию уровней головоломок. Оказалось, что этот вопрос рассматривался не очень широко. Я нашёл всего лишь несколько полезных для меня статей. В основном они были посвящены генерированию/решению уровней для Сокобана. Например:

Раз и два.

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

Инструмент для решения головоломок

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

а) из исходного положения вы можете начать двигаться в любом направлении (влево, вправо, вверх, вниз);
б) из следующего положения можно снова продолжить в любом направлении;
в) в любом положении проверяется соединения фруктов, с поля удаляются совпавшие фрукты и продолжается пункт б), пока на поле не останется несколько фруктов.

Как видите, это простой брутфорс-подход. Итак, количество возможных положений на поле было: 4, 4*4 = 4², 4*4*4 = 4³,… 4ⁿ. На 10 ходу получалось более миллиона комбинаций поля, а на 25 ходу — 1125899906842624 комбинаций. Ну хорошо, тогда мы можем ограничить максимальное количество ходов, скажем до 10, и нас не будут интересовать более сложные уровни, но здесь скрывается другая опасность. Некоторые из головоломок могут быть созданы или сгенерироваться таким образом, что игрок, сделавший в начале несколько плохих ходов, не сможет завершить уровень. Или же в некоторых уровнях может возникнуть зацикленность состояний на поле. Если алгоритм разветвляется в таком направлении слишком рано, уровень может быть помечен как нерешаемый, даже если есть более короткие ветви с более простым решением. Также если алгоритм нашёл решение, нет никаких гарантий, что оно самое короткое — нужно завершить все ветви, чтобы найти кратчайшее решение. Кроме того, на поле часто возникают такие состояния, что один ход в определённом направлении ничего не изменяет. Посмотрите на третью картинку в части «Fruit Dating — правила и особенности» — ничего не изменится, если мы сдвинемся влево.

Поэтому правила изменились:

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

Также есть и другие правила, например, проверка совпадения фруктов и прекращение всего процесса при нахождении решения; кроме того, позже возникли другие правила, связанные с дополнительными возможностями, но базовый инструмент для решения я описал. Он быстро обрывает целые ветви без решения. Кроме глубины решения, он также проверяет родительские положения, сохранённые для каждого состояния на поле, так что в конце можно легко напечатать решение. Давайте рассмотрим это на примере первого уровня игры:


Из исходного положения ходы разветвляются на четыре возможных направления. Пометим их как 1-1, 1-2, 1-3, 1-4. Алгоритм всегда стремится переместиться в следующем порядке: вправо, вверх, влево, вниз. Поскольку для дальнейшего изучения сохраняемых состояний нужно применить стек, первое продолжающее состояние передаётся в стек последним (в нашем случае 1-4). Снова первым ходом является сдвиг вправо (2-1) и поскольку это новое состояние, оно записывается в стек. Следующим становится сдвиг вверх, который приводит к состоянию 2-2. Мы уже были в этом состоянии в первой итерации. Поэтому мы применяем правило г) и обрываем эту ветвь — в стек ничего не записывается. Далее идёт попытка хода влево. Он приводит к новому состоянию (2-3) и оно помещается в стек. Последний ход — сдвиг вниз, но в нём нет различия между 1-4 и 2-4, поэтому мы ничего не помещаем в стек (правило б)… нет нового состояния = ничего не делаем). Теперь верхнее состояние стека — это 2-3. Из него мы перемещаемся вправо и попадаем в состояние 3-1, которое равно состоянию 2-1. Но в 2-1 мы были на второй итерации, так что обрываем эту ветвь. Затем мы двигаемся вверх, фрукты оказываются на соседних плитках, и поскольку это была единственная пара, игра завершается.

Алгоритм работает, хотя он может и не найти кратчайший путь. Он просто берёт первое найденное решение. Чтобы исправить это, я сначала ограничил максимальное количество ходов равным 30. Если решение не находится, я считаю уровень непроходимым. Если решение находится, допустим на 15 ходу, я снова запускаю «решатель» с максимальной глубиной решения 14 (15 — 1). Если решение не находится, то 15 — это кратчайший путь. Если решение найдено например на 13 ходу, я запускаю инструмент с максимальной глубиной 12 (13 — 1). Я продолжаю процесс, пока возвращается какое-нибудь решение. Последнее возвращённое решение является кратчайшим решением.

Генератор

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

Фаза генерирования состоит из двух частей:

• генерирование стен
• генерирование объектов на поле

Генерирование стен всегда начинается с рисования неподвижной границы поля:


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


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


По картинке видно, что каждая следующая часть стены короче, так что можно быть уверенным, что в какой-то точке стена закончится.

Поскольку все стены начинаются от границы поля, то каждая отдельная плитка была соединена с границей. Для меня это выглядело скучно, поэтому я добавил ещё один этап, на котором генерируются внутренние стены. Внутренние стены не соединены ни с одной имеющейся плиткой. Этап начинается с выбора случайной плитки и проверки того, свободна ли она и плитки в пределах 3x3 от неё. Если это так, то стена БУДЕТ помещена в сетку, и следующая плитка выбирается согласно случайному направлению (это направление случайно выбирается перед тестированием первой плитки). Цикл прерывается, когда условие свободных на 3x3 плиток не выполняется. Обратите внимание на выделенное выше слово «будет». Если вы поместите стену в сетку сразу же и перейдёте к обработке следующей плитки, область в пределах 3x3 никогда не будет свободной, потому что вы только что поместили туда стену. Поэтому я сохраняю все плитки стен во временный массив и одновременно помещаю их в сетку после прекращения цикла.

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

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

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


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

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

Для концов коридоров, окружённых плитками с трёх сторон, я выбрал вес 6 + Random (3). Для плиток в горизонтальных или вертикальных коридорах я выбрал вес 2. Для углов я выбрал вес 3 + Random (3), а для свободных областей — 1.

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

Препятствия (камни, машины, бочки) создаются похожим способом, но отличие в том, что их веса отделены от весов фруктов; также существует определённая случайная плотность препятствий, которая указывает количество препятствий в уровне, если они выбраны.

Кстати, с помощью весов можно делать и другие хитрости. Позже я добавил спящего ёжика и муравьеда (их описания приведены в начале статьи). Не имеет смысла помещать их в середине коридора, поэтому для коридоров их вес = 0.

В этой анимации показано расположение на уровне фруктов и препятствий:


Окончательный сгенерированный уровень показан на статичной картинке ниже. Для решения требуется 6 ходов (вправо, вверх, влево, вниз, вправо, вверх). Отлично, через 1-2 минуту после нажатия на кнопку Generate у нас получился интересно выглядящий уровень, прохождение которого возможно через 6 ходов (никто не будет играть в уровни, для прохождения которых нужно 30 ходов!); к тому же, для его поиска нам не пришлось ни капли мучиться. Но… всегда можно сделать чуть-чуть лучше. И с этой точки в нашей статье мы будем пытаться сделать уровни красивее.

Редактор

Генерирование уровней завершилось в предыдущей части. Наш редактор поддерживает drag&drop, так что можно легко перетаскивать объекты, чтобы получить более высокий уровень симметрии. Например, вот так:


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

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

Окончательный результат

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


Об авторе: Томас Рыхновски (Tomas Rychnovsky) — инди-разработчик небольших мобильных игр для Android, iOS и Tizen.