Структуру, о которой ниже пойдёт речь, знали в древней Индии за тысячу лет до самого Фибоначчи и переоткрыли в 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=01 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 поверх него ещё и накидывает случайные технологии, что от решёточной детерминированности максимально далеко. Речь именно об инструментах и о том, как устроено пространство создания таких деревьев технлогий, а не о рантайме.
Зачем всё это
Вопрос естественный и игроку наверное не нужный. Со стороны выглядит как коза с баяном, взяли, понимаешь, разработчики строки из двух цифр, навесили на них четыре произвольных на вид правила и радуются, что получилось что-то стройное.
Но вся эта конструкция интересна как в ней вылезли числа Фибоначчи, правда они вылезают примерно везде, где что-то считается. Еще она интересна, что четыре простых правила могут порождают интересный дизайн уровня и боевки достаточный, чтобы не давать расслабляться игроку и при этом не ломать прогрессию сложности.
Дизайнеры уровней и дерева технологий пришли к этому методом проб и ошибок, хотя надо было всего лишь погрузиться в теорию частично упорядочных множеств и тразитивных сокращений с диаграммами Хассе. Но про Хассе они точно не знают, я спрашивал…
ссылка на оригинал статьи https://habr.com/ru/articles/1076886/