Алгоритм генерации головоломок для игры Cut the Rope и Braid
Ожидает приглашения
Привет, Харбралюди.
Год назад написал алгоритм, генерирующий головоломки для игрушки 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 года серьезной работы по его написанию, еще куча времени по оптимизации и вычислительные мощности на таком уровне, которого возможно еще не существует.
Все это проделал один. Мало с кем говорил и сам никогда не писал серьезных игр. Поэтому мог где-то ошибиться и мне до сих пор неизвестно, созданы ли уже подобные алгоритмы, – думаю, созданы. Если этот алгоритм кому-то может быть полезен – пишите, не стесняйтесь. И если вдруг решите написать что-нибудь подобное, готовьтесь сложностям при оптимизации, сложностям в формализации, и, самое главное, к невообразимой трудозатратности.
Благодарю за внимание.
Год назад написал алгоритм, генерирующий головоломки для игрушки 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 года серьезной работы по его написанию, еще куча времени по оптимизации и вычислительные мощности на таком уровне, которого возможно еще не существует.
Все это проделал один. Мало с кем говорил и сам никогда не писал серьезных игр. Поэтому мог где-то ошибиться и мне до сих пор неизвестно, созданы ли уже подобные алгоритмы, – думаю, созданы. Если этот алгоритм кому-то может быть полезен – пишите, не стесняйтесь. И если вдруг решите написать что-нибудь подобное, готовьтесь сложностям при оптимизации, сложностям в формализации, и, самое главное, к невообразимой трудозатратности.
Благодарю за внимание.