Фибоначчи врагов

4 часа назад Прокомментировать Просмотры: 1

Математическая структура, о пойдет речь далее, была известна в Древней Индии за тысячу лет до рождения Фибоначчи, а в 1988 году её переоткрыли два математика. Примечательно, что весь этот граф формируется исключительно из комбинаций цифр 1 и 2, либо через вычитание единицы преобразуется в бинарный формат с нулями и единицами.

Возьмем любую конечную последовательность из единиц и двоек, например «11212», и найдем сумму её элементов: 1 + 1 + 2 + 1 + 2 = 7. Это значение называется рангом строки. Возникает закономерный вопрос: каково общее количество строк определенного ранга? Новую строку того же ранга можно получить ровно двумя способами: приписав двойку к последовательности ранга r-2 либо добавив единицу к последовательности ранга r-1. Других вариантов не существует, поскольку наш алфавит ограничен всего двумя символами.

ранг 0: «» → 1
ранг 1: 1 → 1
ранг 2: 11, 2 → 2
ранг 3: 111, 12, 21 → 3
ранг 4: 1111, 112, 121, 211, 22 → 5
ранг 5: … → 8

Обратите внимание на правую колонку: 1, 1, 2, 3, 5, 8. Да, это классическая последовательность Фибоначчи f® = f(r-1) + f(r-2). Единственное отличие заключается в начальных условиях: f(0) = 1 (пустая строка) и f(1) = 1 (единственный элемент «1»). Из-за этого сдвига вся последовательность смещена относительно канонических чисел Фибоначчи ровно на одну позицию, то есть f® = F(r+1).

Аналогичным образом поступали древнеиндийские стиховеды при сочинении метрических текстов, где короткий слог приравнивался к одной единице времени, а длинный — к двум. Такой подход позволял выстраивать изящный ритм и гармоничные языковые конструкции, подтверждая, что в данном контексте числа Фибоначчи появились задолго до самого математика. Любопытно, что же общего между стихосложением, Фибоначчи и деревьями технологий в видеоиграх? Читаем далее…

Красивая теория

Теперь преобразуем полученные комбинации в граф, в результате чего выстраивается весьма изящная топология.

ранг 4:   1111    112     121     211     22
            │      │       │      │ │     ││
            │      │       │      │ └──┐  ││
ранг 3:    111 ────┼───────┼──────┘    21─┘│
            │      12 ─────┼────────────┼──┘
            │       │      │            │
ранг 2:    11 ──────┼──────┼────────────┘
            │       └────  2
            │              │
ранг 1:     \──────  1  ───/
                     │
ранг 0:             ""

Эта структура носит название графа Юнга — Фибоначчи. Каждой строке, включая пустую, в нем соответствует отдельная вершина, а соседями конкретной строки s признаются результаты четырех преобразований:

добавление единицы в любую позицию левее самой первой единицы (если таковых в строке нет, то в любое место).
замена самой левой единицы на двойку.
удаление самой левой единицы.
замена на единицу любой двойки, перед которой нет ни одной единицы.

Данные операции формируют две взаимообратные пары: первая нейтрализуется третьей, а вторая — четвертой. Благодаря этому граф формально считается неориентированным, хотя на схемах его принято изображать ориентированным, направляя ребра от меньших рангов к большим. Эти правила порождают любопытные особенности строк: так, у последовательности 211 имеется ровно два непосредственных предшественника (111 и 21), у строки 22 тоже два (12 и 21), в то время как у строки 121 он всего один.

Математики Фомин и Стенли подробно изучили и зафиксировали эти свойства в своих трудах:

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

""     out=1  in=0
1      out=2  in=1     (вверх: 11, 2 | вниз: "")
11     out=2  in=1     (вверх: 111, 21 | вниз: 1)
2      out=2  in=1     (вверх: 12, 21 | вниз: 1)
21     out=3  in=2     (вверх: 121, 211, 22 | вниз: 2, 11)
22     out=3  in=2     (вверх: 122, 212, 221 | вниз: 12, 21)

Откуда же берется этот дополнительный прирост в единицу? Операция вставки единицы генерирует столько вариантов, сколько позиций находится левее самой левой единицы (то есть количество ведущих двоек плюс один), в то время как четвертая операция, направленная вниз, дает на один вариант меньше. Замена крайней левой единицы на двойку и её удаление привносят по одному варианту и полностью компенсируют друг друга. Фомин назвал граф с подобными характеристиками Y-графом из-за характерного Y-образного ветвления. В свою очередь, Стенли доказал в своих работах, что на любом ранге обнаруживается решетка, сводимая к следующей схеме: 21, 22, 121, 211 и 221.

              221        (ранг 5)
            /  |  \
          22  121  211   (ранг 4)
            \  |  /
              21         (ранг 3)

Устали? Самое время перейти к видеоиграм…

Юнг, Фибоначчи и расстановка монстров

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

Дизайнеры в двух разных шутерах от независимых студий занимались расстановкой противников на локациях, опираясь именно на этот граф. Разумеется, они понятия не имели о диаграммах Хассе или частном случае в виде графа Юнга — Фибоначчи (вряд ли они вообще слышали эти термины). Просто в ходе прототипирования и плейтестов эмпирически выяснилось, что вываливать орды врагов на игрока бессистемно — скучно. Гораздо эффективнее делить уровень на зоны и распределять противников по некой негласной формуле.

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

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

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

Никаких попыток привести бандитов и мощных боссов к единому денежному или силевому эквиваленту не предпринималось, поскольку подобные шкалы неизбежно начинают искажать баланс, а расширение алфавита {1,2} новыми элементами разрушало бы всю систему и портило отзывы фокус-групп. Иными словами, всё должно функционировать в рамках одного типа противников. Нужен другой тип? Создавайте для него собственную фибоначчиеву структуру и расставляйте по уровню. С точки зрения математики алгоритм ведет себя естественным образом, а дополнительная единица для любого типа врагов просто сдвигает кривую сложности, однако…

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

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

Фибоначчи, Юнг и деревья навыков

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

Решетка Юнга позволяет упорядочить технологии в виде сетки, где строка символизирует ветку развития, а столбец — глубину погружения в нее. Далее вводится правило: разблокировка определенной ячейки (мощного апгрейда) возможна лишь при условии предварительного изучения ячеек слева и сверху. Множество допустимых путей исследования при этом в точности совпадает с множеством диаграмм Юнга, укладывающихся в заданную сетку. Иными словами, задачи вроде «как сбалансировать две расы» или «сколько элементов нужно добавить для равенства билдов» решаются простой арифметикой массивов без необходимости обхода графов зависимостей. Если противоборствующих сторон всего две, таблицы можно рассчитать вручную, но в той же Age of Empires II сейчас около полусотни цивилизаций, и у каждой уникальное дерево технологий, требующее идеального баланса с остальными. Попробовать свести это вручную? Задача крайне сомнительная…

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

Зачем это нужно

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

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

Левел-дизайнеры и архитекторы систем прокачки пришли к этому интуитивно, методом проб и ошибок, хотя для этого требовалось лишь заглянуть в теорию частично упорядоченных множеств, транзитивных сокращений и диаграмм Хассе. Впрочем, про Хассе они точно не слышали — я проверял…

Источник