В игре заточка меча с первого на второй уровень стоит 10 золота и имеет шанс 90% (золото тратится, в случае неудачи меч не изменяется). Заточка со второго на третий уровень стоит 20 золота и имеет шанс 80% (золото тратится, в случае неудачи меч понижается на 1 уровень). Таким же образом меч можно улучшить с третьего до четвертого: заточка стоит 40 золота и имеет шанс 70%. И так далее (с каждым уровнем цена повышается в два раза, а шанс уменьшается на 10%). Золото тратится в любом случае при каждой попытке, в случае неудачи меч понижается на один уровень (но не ниже первого).

Рассчитайте среднюю стоимость улучшения меча до седьмого уровня.


«Заточка» игровых предметов — краеугольный камень геймдизайна традиционных ММО. Это и теоретически бесконечная самовоспроизводящаяся геймплейная петля, и неограниченный источник мотивации для игрока, гонящегося за самым лучшим снаряжением, и эффективный способ вывода излишков ресурсов из игровой экономики. Правильно отбалансировать количество итераций «заточки» предмета и объем затрачиваемых на него ресурсов — достаточно нетривиальная проблема. Приведенная выше задача не первый год кочует по около-геймдевным формумам и пабликам, а также встречается в реальных тестовых заданиях на должность геймдизайнера.

Самым правильным и традиционным решением данной задачи будет приведение ее к уравнению из теории вероятности. Теория вероятности — это раздел высшей математики. Высшая математика — это сложно. Высшая математика дается далеко не всем. Но как же быть тем, в чьей голове генерируются дюжины идей по построению взаимодействий между людьми и системой, между людьми и людьми, между людьми и уникальными, неповторимыми игровыми мирами? Есть ли шанс профессионально заниматься геймдизайном для тех, у кого одним из ключевых аргументов для поступления на факультет востоковедения было полное отсутствие математики как явления в программе обучения? Давайте обратим свой взгляд на Machinations.io Будем смотреть и разбираться.

Machinations.io — это профессиональный инструмент геймдизайнера для построения блок-схем игровых механик, прототипирования и простейшего визуального программирования. Этот инструмент не даст нам тех быстрых, четких и изящных ответов, какие могли бы предоставить выверенные формулы теорвера. Однако Machinations.io может предоставить в наше распоряжение кое-что более ценное для игродела — полноценный прототип работающей игровой механики «заточки» меча, сделанный на коленке за пять минут. По нему можно будет проследить весь тернистый путь меча к желанному седьмому уровню, на практике увидеть необходимое количество итераций, объем затраченных ресурсов, а затем масштабировать весь процесс на сколь угодно большое (в платной версии утилиты) количество мечей.

Для начала быстро взглянем, как устроен интерфейс утилиты:

Теория MMO: Machinations.io и экономика вокруг точильного камня

Главное рабочее пространство представляет собой линованный лист бумаги, хорошо знакомый всем, кто работает с инструментами для составления блок-схем, вроде Draw.io.

В поле 1 расположились привычные инструменты управления и заголовок нашего документа.
В поле 2 находятся все инструменты machinations.io
В поле 3 расположены инструменты управления ходом симуляции
В поле 4 находится меню настройки параметров выбранного элемента.

Начало начал любой игровой механики в machinations.io — это источник ресурса. В нашем случае ресурсом станет меч, который будет проходить итерации «заточки». Для того, чтобы в выстраиваемой нами системе мог появиться этот самый меч, мы берем из поля 2 элемент source (источник ресурса) и размещаем его на рабочем поле.

Для того, чтобы поступление мечей в механику было контролируемым, в поле 4 выставляем его свойство в значение OnStart. В таком положении источник выдаст нам один меч на старте симуляции и более не будет предпринимать никаких действий.

Следующим действием установим место, или если угодно — «инвентарь», куда поступит выданный нам меч.

Берем из поля 2 элемент pool и размещаем его на рабочем поле. От элемента source проводим дорожку к элементу pool.

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

Теория MMO: Machinations.io и экономика вокруг точильного камня

«Кликабельная» гифка с процессом.

Шаг 2 — это построение собственно итераций заточки меча. Тут начинаются основные хитрости.

Выбираем на боковой панели инструмент «Gate» (шлюз) и размещаем его на поле. Предназначение этого элемента — распределять ресурсы по развилкам дорожек. Наша задача — настроить его так, чтобы он брал «меч» 1 уровня, «подсчитывал» стоимость его заточки и с 90% вероятностью превращал его в «меч» 2 уровня.

Прокладываем дорожку из «инвентаря» с мечами 1 уровня к шлюзу. Затем заходим в параметры шлюза и выбираем там способ распределения — «случайный» (distribution — random). Из шлюза выводим 2 дорожки, на каждой из которых прописываем процентную вероятность того, что ресурс последует по ней. Как сказано в задаче — 90% шанс, что меч заточится до 2 уровня и 10% вероятности, что вернется обратно на 1 уровень. Важно понимать, что если забудем про дорожку с «провалом» заточки, то с 10% вероятностью наш «меч» просто испарится.

И третий важный трюк — научить схему считать стоимость заточки.

Располагаем на поле еще один источник ресурсов. Он будет генерировать стоимость в золотых монетах каждый раз, когда «меч» будет проходить через рандомизатор. Для этого устанавливаем свойства источника на «пассивные» (иначе он будет генерировать ресурсы по своему желанию) и подключаем его с помощью пунктирной стрелки state connection («соединение состояния») к рандомизатору. На стрелке указываем правило, согласно которому, как только на нашем импровизированном точильном камне количество мечей становится равным 1 (=1), источник золотых монет должен будет сгенерировать стоимость заточки, равной 10.

Теория MMO: Вторая кликабельная гифка.

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

Следующий этап конструирования симуляции во многом дублирует предыдущий. Главным отличием будет неудачный исход заточки. В случае провала, меч не вернется на 2 уровень, а откатится еще на 1 уровень вниз. Ну и стоимость заточки с каждым этапом возрастает, а шанс на успех — падает.
Теория MMO: Machinations.io и экономика вокруг точильного камня

Растут ставки и количество задействованных элементов на схеме.

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

Теперь нужно «научить» алгоритм логике действий в ситуациях, когда меч успешно наточен до 7 уровня и когда мечей накопилось столько, что можно подводить статистически достоверные итоги стоимости.

Первым делом, после заточки «меча» до 7 уровня, вместо привычного пула мы располагаем шлюз. В этот раз не рандомизирующий, а простой. Его задача — регистрировать прохождение ресурса и посылать сигнал новому сделанному нами источнику «мечей», что пора пускать в работу следующее изделие. Если не прибегать к такой сигнальной системе, а просто пускать в процесс заточки «мечи» непрерывно один за одним, то есть риск, что одновременно в одном рандомизаторе окажутся 2 меча, а стоимость «считается» только с одного.
И последним шагом мы задействуем элемент End Condition («Условие остановки»). Располагаем его на поле, а рядом с ним — пул с законченными изделиями. Пунктирная стрелка, соединяющая пул с «выключателем» подаст сигнал об остановке симуляции, когда будет готово 1000 «мечей».

Теория MMO: Machinations.io и экономика вокруг точильного камня

Магия рутинной и кропотливой работы не только достроила за кадром схему до впечатляющих размеров, но и добавила цветовую кодировку, а также поясняющие надписи.
Кто заметит на гифке ошибку — тот молодец ;)

Ну что ж, все готово! Еще раз перепроверяем все шаги, настраиваем условия симуляции (скорость, количество шагов и прочее) и жмем на запуск!

Теория MMO: Machinations.io и экономика вокруг точильного камня

«Мечи» точатся, «монеты» считаются. Кружочки бегают по дорожкам, задействованные условия и алгоритмы подсвечиваются и мигают. Любишь игры про автоматизацию? Оглянись вокруг! Разве здесь не прекрасно?

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

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

26 комментариев

avatar
Не знаю, как работает рандомизатор в БДО, но точить я зареклась… Меня теория хаоса не то, что не любит, просто ненавидит.
  • 0
avatar
Ох! За один только инструмент плюс!)
Эт вам не таблички в Google Docs)) Хотя, на самом деле, если сильно упороться, то можно многое на их «движке» сделать)
  • +2
avatar
Что-то я подумал и немного залип насчет переноса этого всего в реальную игру. Это все классно, но как быть уверенным в том какая именно функция аппроксимации генерации случайных числе используется в их реализации? Ведь если я напишу уже в игре что-то свое, то получи другой результат, причем может даже сильно отличающийся. (или я просто плохо искал?)
Комментарий отредактирован 2020-12-15 22:09:25 пользователем William_Godwin
  • 0
avatar
Понятно, что в программировании используются псевдо-случайные числа, вместо настоящих случайных, и распределение может быть разным.
Самый простой способ проверить, который мне приходит в голову — забить простенькую задачку на рандомизацию в тулзе, в экселе и в движке, получить выборку с достаточно большого количества чисел и сравнить результаты.
Ну или напрямую у разрабов спросить, какой ГПСЧ они используют)
Я таким вопросом пока не задавался, меня радует сама возможность проверять гипотезы без глубокого знания матана или движка.
Комментарий отредактирован 2020-12-15 22:21:09 пользователем Panzercult
  • +3
avatar
За 10 минут набросал в Экселе, получил результат 2783,53. В браузере на моём ноуте тормозит, не стал ждать до конца. Интересно, ответ верный?
Комментарий отредактирован 2020-12-15 23:08:53 пользователем Beagle
  • 0
avatar
Достаточно близко к тому, что показывает симуляция)
На 1000 шагов у меня получилось произвести 33 меча, средняя стоимость — 2886 монет.
Есть способы запустить 100 параллельных симуляций по 1000 шагов каждая, но обрабатываться они будут около часа. Зато и ответ выйдет точнее.
  • +1
avatar
У меня точное теоретическое значение, формулы там примитивные, больше логика нужна, чем теория вероятности. Могу написать решение.
Комментарий отредактирован 2020-12-15 23:18:53 пользователем Beagle
  • 0
avatar
Я примерно в курсе насчет формул, но может кому еще из читателей будет интересно. Так что в любом случае пиши ;)

У меня точное теоретическое значение
Твое точное теоретическое, против моего неточного практического. И в том и в другом есть свой смысл.
  • 0
avatar
В реальности всегда будет статистический разброс вокруг теоретического значения. Но знать его полезно.

Решение:

Цена меча 2 уровня: 10 золота: 0,9 = 11,(1) золота.
Однократно приведу обоснование: из 10 мечей 1 уровня мы изготовим 9 мечей 2 уровня и затратим 100 золота, цена меча = 100: 9, то же, что и 10: 0,9.
Начиная с 3 уровня к цене изготовления будем добавлять цену меча (цена меча 1 уровня была равна нулю, в условиях задачи это следовало явно указать, а то ответ был бы иным)

Цена меча 3 уровня: ( 20 + 11,(1) ): 0,8 = 38,(8) золота минус 0,2 единицы мечей 1 уровня при неудаче, которые пока ничего не стоят.

Цена меча 4 уровня: ( 40 + 38,(8) ): 0,7 = 112,7 золота минус 0,3 единицы мечей 2 уровня, которые стоят 0,3 * 11,(1) = 3,(3) золота. Итого 112,7 — 3,(3) = 109,37 золота.

Цена меча 5 уровня: ( 80 + 109,37 ): 0,6 = 315,61 золота минус 0,4 единицы мечей 3 уровня, которые стоят 0,4 * 38,(8) = 15,(5) золота. Итого 300,05 золота.

Цена меча 6 уровня: ( 160 + 300,05 ): 0,5 = 920,11 золота минус 0,5 единиц мечей 4 уровня, которые стоят 0,5 * 109,37 = 54,68 золота. Итого 865,42 золота.

Цена меча 7 уровня: ( 320 + 865,42 ): 0,4 = 2963,56 золота минус 0,6 единиц мечей 5 уровня, которые стоят 0,6 * 300,05 = 180,03 золота. Итого 2783,53 золота.
Комментарий отредактирован 2020-12-15 23:49:48 пользователем Beagle
  • +4
avatar
И, ради прикола:
8 уровень — 10806, 9 уровень — 58203, 10 уровень — 597904 золота. Дальше вероятность улучшения равна нулю. А сколько времени займёт расчёт до 10 уровня в Machinations.io?
Комментарий отредактирован 2020-12-16 00:08:38 пользователем Beagle
  • 0
avatar
цена меча 1 уровня была равна нулю, в условиях задачи это следовало явно указать, а то ответ был бы иным

Думаю, он был добыт в бою, а не куплен или произведен за деньги)

А сколько времени займёт расчёт до 10 уровня в Machinations.io?

Примерно столько же. Но у machinations перед формулами есть одно преимущество: наглядность и, если можно так выразиться, эмоциональность. Это когда меч последовательно «точится» на каждой итерации схемы, ты смотришь как он пробегает по дорожкам, как начисляются «монетки» в стоимость процесса, болеешь за этот меч. И вот он успешно добрался до предпоследнего уровня, остался один шажок, и тут рраз, и случается череда неудач и меч шаг за шагом откатывается по уровням до самого дна и заточка начинается заново. Игра, она же не только про математику, она еще и про эмоции. В таблицах и формулах эмоций не будет. А в такой наглядной и динамичной схеме — будут. Поэтому, если надо быстро — можно и формулами пользоваться. А если надо наглядно, то лучше брать и смотреть на процесс и прислушиваться к ощущениям.
  • +1
avatar
Слушай, я решал не так как Beagle, и у меня, начиная с 4-го уровня, получаются другие результаты. 107.94 вместо 109.37. Можешь запустить симуляцию подольше и рассудить?
  • 0
avatar
Симуляция каждый раз даёт разное значение. Напиши свою формулу, обсудим.
  • 0
avatar
Я сначала вообще в матричном виде решал.

Тут уже можно делать симуляцию. На питоне:

import numpy as np

p1 = np.array([1, 0, 0, 0, 0, 0])
A = np.array([
    [0.1, 0.2, 0,   0,   0,   0  ],
    [0.9, 0,   0.3, 0,   0,   0  ],
    [0,   0.8, 0,   0.4, 0,   0  ],
    [0,   0,   0.7, 0,   0.5, 0  ],
    [0,   0,   0,   0.6, 0,   0.6],
    [0,   0,   0,   0,   0.5, 0  ],
])
c = np.array([10, 20, 40, 80, 160, 320])

R = 0
p = p1
for i in range(1000):
    R += c.dot(p)
    p = A.dot(p)
print( R )

Получается 2335.71 золота.

Можно посчитать и точное значение.

Код на питоне:

import numpy as np
from numpy.linalg import eig, inv

p1 = np.array([1, 0, 0, 0, 0, 0])
A = np.array([
    [0.1, 0.2, 0,   0,   0,   0  ],
    [0.9, 0,   0.3, 0,   0,   0  ],
    [0,   0.8, 0,   0.4, 0,   0  ],
    [0,   0,   0.7, 0,   0.5, 0  ],
    [0,   0,   0,   0.6, 0,   0.6],
    [0,   0,   0,   0,   0.5, 0  ],
])
c = np.array([10, 20, 40, 80, 160, 320])

S, U = eig(A)

R = c.dot(U).dot(inv(U).dot(p1)/(1-S))
print®

Получаются те же 2335.71 золота.
  • +3
avatar
Допер. Смотри, точим 10 мечей 3 -> 4, тратим 10 * (40 + 38.(8)) золота, получаем 7 мечей-4 и 3 мечей-2. Пусть C(4) — цена меча-4. Тогда

10 * (40 + 38.(8)) = 7 * С(4) + 3 * 11.(1)

откуда

C(4) = 10 * (40 + 38.(8)) / 7 — 3/7 * 11.(1) = 107.94
  • +2
avatar
Ты прав, я потерял деление цены сломанных мечей на шанс апгрейда. Поскольку их цена после пересчёта выросла, цена улучшенных мечей уменьшилась, и исправление накапливающейся ошибки уменьшило ответ. Ошибся я оттого, что сначала написал формулу без учёта цены сломанных мечей, т.к. она была равна нулю, а когда ввёл этот член, он не попал под скобки. Похоже, что Panzercult в симуляции сделал ту же ошибку.
Вот уточнённые данные.

2 — 11,11111111
3 — 38,88888889
4 — 107,9365079
5 — 287,3015873
6 — 786,6666667
7 — 2335,714286
8 — 8083,492063
9 — 37474,60317
10 — 327594,6032
Комментарий отредактирован 2020-12-16 22:25:26 пользователем Beagle
  • +1
avatar
Вот сейчас не понял в чем ошибка заключается.
Можно объяснение для гуманитария?
  • 0
avatar
Общая формула по вычислению цены меча вытекает из уравнения:
(Цена апгрейда уровня N) + (цена меча уровня N-1) = (Вероятность апгрейда уровня N) * (цена меча уровня N) + (1 — (Вероятность апгрейда уровня N)) * (цена меча уровня N-2).
Если словами: за цену ковки и меча, который куёшь, получаешь меч следующего уровня с указанным шансом и при неудаче меч предыдущего уровня. В цифрах для 4 уровня:
(40 + 38.(8)) = 0,7 * С(4) + 0,3 * 11.(1)
Теперь надо выразить цену меча С(4), преобразовав уравнение.
Перносим 0,3 * 11.(1) в другую часть с минусом:
(40 + 38.(8)) — 0,3 * 11.(1) = 0,7 * С(4)
Делим обе части на 0,7
(40 + 38.(8)) / 0,7 — 0,3 * 11.(1) / 0,7 = С(4)
Моя ошибка заключалась в том, что 0,3 * 11.(1) не было поделено на 0,7, отчего величина члена уравнения с ценой сломанных мечей снижалась, а цена улучшенных мечей при этом повышалась. После устранения ошибки цена меча 7 уровня упала почти на 450 золота.
Комментарий отредактирован 2020-12-17 19:15:31 пользователем Beagle
  • 0
avatar
Просил же для гуманитариев(
В симуляции у меня задействован пошаговый алгоритм, а не обобщенное уравнение. Не вижу (пока?) в алгоритме шага, в который могла бы закрасться подобная ошибка.
Комментарий отредактирован 2020-12-18 08:10:41 пользователем Panzercult
  • 0
avatar
Похоже у тебя всё верно, просто разброс итогового значения от рандома большой. Надо генерить по 10 000 и 100 000 мечей, чтобы увидеть дрейф результата к теоретическому.
  • 0
avatar
Да, 33 меча не показатель.
Сейчас попробую прям много-много мечей наточить.
  • 0
avatar
Ну или напрямую у разрабов спросить, какой ГПСЧ они используют)

Блин, ну да, вообще логично)
  • 0
avatar
Мне кажется, отличия в нормальных генераторах столь незначительны, что на общее представление о процессе не повлияют. Ну а разницей в третьем или четвертом знаке после запятой вполне можно пренебречь )

Инструмент действительно классный! И заметка оформлена замечательно. Особенно порадовали гифки :)
  • +2
avatar
Неа нельзя. Это как раз те самые проблемы при вычислениях с плавающей точкой о которой я писал в последней заметке. Ну, точнее как… В некоторых задачах можно, но может потом обнаружится, что результат вычислений вы будете использовать где-то еще. Есть вычисления, которые производятся, например каждые 25ms, а с более сложной логикой вообще может оказаться, что количество операций на столько большое, что вам вообще иногда выдают так называемый NaN, что может приводить к undefined behaviour.

Это вообще добольно насущная проблема просто потому, что компьютеры считают как бы совсем не так как мы) И проблемы часто возникают даже там, где их интуитивно не ждешь, например просто при умножении и сложении.)
Комментарий отредактирован 2020-12-15 23:30:32 пользователем William_Godwin
  • 0
avatar
Надо подумать
Комментарий отредактирован 2020-12-15 22:44:59 пользователем Beagle
  • 0
avatar
Полезная и забавная тулза. Спасибо. 8)
  • 0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.