Структуру, о которой ниже пойдёт речь, знали в древней Индии за тысячу лет до самого Фибоначчи и переоткрыли в 1988 году двое математиков, при этом весь граф целиком строится из строк, состоящих только из цифр 1 и 2, или если мы вычтем единицу, то получим 0/1 и бинарный вид.
Берём любую конечную строку из цифр 1 и 2, например такую «11212» и складываем цифры 1 + 1 + 2 + 1 + 2 = 7 и получаем ранг этой строки. Теперь простой вопрос: сколько существует строк заданного ранга? Строку такого же ранга можно получить двумя способами, либо дописав цифру 2 к строке ранга r-2, либо дописав цифру 1 к строке ранга 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 объявляются результаты четырёх операций:
вставить цифру 1 где‑нибудь левее самой левой единицы, а если единиц в строке вообще нет, то в любое место.
заменить самую левую единицу на двойку.
удалить самую левую единицу.
заменить на единицу любую двойку, слева от которой нет ни одной единицы.
Эти операции разбиваются на две взаимно обратные пары: первая отменяется третьей, вторая отменяется четвёртой, поэтому граф можно считать неориентированным, но обычно его рисуют ориентированным, направляя каждое ребро от меньшего ранга к большему. Из этих же правил получаются интересные свойства строк: у строки 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} новыми буквами ломало схему и снижало интерес у фокус‑групп, то есть все должно работать в пределах одного типа врагов. Хотите другой тип врагов? Делайте ему свою фибоюнговину и расставляйте по уровню. Формально это естественное поведение такого алгоритма, и эта единичка для врага любого типа просто двигает сложность, но...
Но это дает дизайнеру возможнось размещать врагов в любом месте уровня, опираясь на данные из предыдущих стычек и точек спавна, не переставляя заново всё, что стоит дальше по коридору. Еще это дает правильный прогресс сложности, такой граф градуирован и длина любого пути равна разности рангов, а обходных путей не существует, что было доказано математиками. Значит переход между двумя соседними сегментами кривой всегда раскладывается в известное число «добавил‑убрал врага», и дизайнер если следует правилам не может случайно перепрыгнуть ступеньку слоужности.
И наконец становится возможно уровень сложности нормально посчитать не привлекая санитаров. Дизайнер описывает верхнюю раскладку и точку схождения, а всё промежуточное вычисляется на простом питоновском скрипте. И сложная боевая система уровня становится числами раскладки бюджета с врагами, позволяя сделать три разных прохождения одной стычки, одинаковым по сложности и разным по ощущению.
Фибоначчи, Юнг и деревья навыков
Работая уже в другой студии, над другим проектом в совершенно другом жанре я обнаружил, что дизайнер дерева технологий использует подозрительно похожую схему для настройки цены развития. Оговорюсь, что это не то отображение дерева технологий или развития персонажа в игре, которое вы видите на экране. Это такой лист с деревом технологий, нарисованным лесенкой что у вас как игрока получилась сбалансированная карта развития персонажа, и более‑менее стабильные билды или сборки или равносильные рассы. А если такую лесенку не нарисуете зараенее, то у вас получатся возможно интересные особенности у каждой рассы или билда, но сбалансировать их станет сложно и придется вводить дополнительные элементы или механики.
Ветка A ■ ■ ■ ■ □ □ Ветка B ■ ■ ■ □ □ Ветка C ■ ■ □ □ Ветка D ■ □ Состояние = (4, 3, 2, 1), ранг 10. Закрашенное всегда образует лесенку, невозрастающую сверху вниз.
Решетка юнга позволяется разложить технологии в сетку, где строка это ветка развития, а столбец глубина внутри неё. Дальше мы вводим правило, что клетку (мощную технологию) можно взять, только если уже взяты клетка слева и клетка сверху. Множество допустимых состояний исследования при таком правиле в точности совпадает с множеством диаграмм Юнга, помещающихся в эту сетку. То есть вопросы «как сбалансировать две рассы» и «сколько ещё надо добавить, чтобы получить сбалансированные билды» теперь решаются арифметикой над массивом, без обхода графа зависимостей, к чему это я... Если у вас в игре две расы врагов, посчитать такие таблицы можно на бумаге, но в AoE2 сейчас около пятьдесяти рас, и у каждой свое дерево технологий, которые должны балансироваться с другими. Сбалансировать такое руками? Наверное можно...
Для баланса игры это хорошо, потому что не будет скрытых особеннстей, а для реиграбельности скорее плохо, потому что все пути получаются одинаковой длины в конечном счёте взаимозаменяемы, и тогда ощущение выбора приходится создавать другими средствами. Оговорюсь, что в виде кода эти таблицы (дерево технологий) ни в одном известном мне проекте так не генерируется. И в Age of Empires 2, и в Stellaris граф технологий сделан руками, причём Stellaris поверх него ещё и накидывает случайные технологии, что от решёточной детерминированности максимально далеко. Речь именно об инструментах и о том, как устроено пространство создания таких деревьев технлогий, а не о рантайме.
Зачем всё это
Вопрос естественный и игроку наверное не нужный. Со стороны выглядит как коза с баяном, взяли, понимаешь, разработчики строки из двух цифр, навесили на них четыре произвольных на вид правила и радуются, что получилось что‑то стройное.
Но вся эта конструкция интересна как в ней вылезли числа Фибоначчи, правда они вылезают примерно везде, где что‑то считается. Еще она интересна, что четыре простых правила могут порождают интересный дизайн уровня и боевки достаточный, чтобы не давать расслабляться игроку и при этом не ломать прогрессию сложности.
Дизайнеры уровней и дерева технологий пришли к этому методом проб и ошибок, хотя надо было всего лишь погрузиться в теорию частично упорядочных множеств и тразитивных сокращений с диаграммами Хассе. Но про Хассе они точно не знают, я спрашивал...
Patrick139
Каждый год такие "открытия". Для полноты надо приложить еще картинку с голым мужиком