Pull to refresh

Алгоритм генерации головоломок для игры Cut the Rope и Braid

Game development *Algorithms *
Awaiting invitation
Привет, Харбралюди.

Год назад написал алгоритм, генерирующий головоломки для игрушки Cut the Rope. С тех пор им не занимался. Делюсь с вами своим опытом.

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

Если мы задаемся задачей построить подобный генератор для определенного класса игр-головоломок, самое простое решение – «в лоб»:

1. Генерируем уровни
2. Заставляем робота проходить их перебором и каждый раз находить все возможные варианты прохождения
3. Создаем массив для результата и начинаем наполнять его полученными уровнями
4. 3аписываем «прохождение» каждого нового сгенерированного уровня и сравниваем с уже существующими вариантами в массиве: если нет уровней с похожим прохождением, тогда добавляем в массив; иначе – выбрасываем

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

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

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

1. Решения генерируются в виде направленного графа — в виде последовательности действий, которые нужно совершить, чтобы пройти уровень. Помимо этого граф ветвится, поскольку в любой момент у игрока есть выбор, какое действие совершать дальше. Естественно, упрощать подобный алгоритм можно бесконечно. К тому же, графы легко сортируются по длине прохождения, количеству вариантов решения и любым другим критериям.
2. Строим решения согласно полученным графам. Пробегаемся по графу и строим систему уравнений. В зависимости от физики в вашей игре, возможных действий игрока и прочего (к примеру, вид сверху/сбоку или 2D/3D), получаем различные методы записи уравнений. Грубо говоря, это работает так: если согласно решению от платформы A можно допрыгнуть до платформы B, то их местоположение находится определенной зависимости.
3. Решаем уравнения (системы получаются довольно большими и метод решения приходится писать отдельно), получаем множество решений берем самое «красивое» с точки зрения гейм дизайна.

Опять же модифицировать этот алгоритм можно бесконечно. К примеру, можно упростить шаг 2 и строить «приблизительные» уровни, а затем проверять их на соответствие первоначальному графу решений. Или же можно решать системы уравнений на шаге 3 просто до поиска первого решения.

Для каждой игры данный алгоритм будет выглядеть по-своему. Cut the Rope, к примеру, удобен тем, что всякие пузыри и веревки в нем одноразовы; не удобная своей динамичностью – иногда решение состоит в том, чтобы порезать веревку A и до определенного момента успеть порезать веревку B. Для игр же с двумя игроками, подобный алгоритм будет колоссально усложняться, в виду удвоения числа возможных действий на единицу времени. Алгоритм для игры Portal 2 получим вообще что-то запредельное, к тому же с учетом существования уровней к этой игре вроде triplex (советую поискать в google: portal 2 triplex).

Игра Braid использует манипуляции со временем и поэтому генерация уровней для этой игры не будет похожа ни на что другое, в виду сложности пространства решений (привязка действий ко времени; как выглядит эта привязка – материал для еще одной статьи). Однако построить генератор уровней для нее возможно. К сожалению, используя описанные методы, для этого нужно 2-3 года серьезной работы по его написанию, еще куча времени по оптимизации и вычислительные мощности на таком уровне, которого возможно еще не существует.

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

Благодарю за внимание.

image
Tags:
Hubs:
You can’t comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author’s username will be hidden by an alias.