Пару недель назад решал задачу связанную с балансом прокачки в некоторой игре ИКС.

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

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

Условие и постановка задачи

Вообще, изначально задача звучала как: “Можно ли как-то улучшить сцену номер 2?” Понятно, что эта формулировка ни разу не задача, это скорее некоторое пожелание заказчика. Для того, чтобы перейти к задаче необходимо представить описание со слов заказчика в виде списка условий, которым должно удовлетворять конечное решение.

После нескольких уточнений стало понятно, что задача может быть сформулирована так -- необходимо определить цены действий в рамках заданной сцены при следующих условиях

  1. Зайдя в сцену игрок имеет фиксированное количество денег равное 70$ и должен иметь возможность сразу произвести первое действие без необходимости решать головоломку

  2. Общее количество действий в сцене фиксировано и равно 12

  3. Вознаграждения за решение каждой головоломки (прохождение уровня) фиксированы (см. таблицу вознаграждений), известны и не могут быть изменены

  4. Уровни проходятся последовательно т.е. следующий открывается только после прохождения предыдущего

  5. Повторное прохождение уровней не допускается 

  6. Не должно возникнуть ситуации, когда игрок может выполнить 2 действия без решения головоломки т.е. после решения Х головоломок игрок должен иметь возможность совершить не более Х действий

  7. Одно и только одно действие должно требовать решения 2 головоломок. Номер это действия можно выбрать произвольно

  8. Необходимо обеспечить игроку пусть небольшую, но свободу выбора последовательности действий

  9. После совершения всех 12 действий у игрока должно остаться фиксированное количество денег равное 55$

Таблица вознаграждений за решение головоломок

Номер уровня

Вознаграждение $

6

130

7

130

8

135

9

135

10

140

11

140

12

140

13

145

14

145

15

150

16

150

17

155

Нумерация уровней в таблице начинается с 6 потому, что в примере рассматривается сцена 2. Соответственно, в первой сцене было 5 уровней

Несмотря на то, что теперь есть весьма внушительный список ограничений, приступить к решению задачи пока что нельзя потому, что условие номер 8 определено слишком абстрактно. Что значит “небольшая свобода выбора”, которая дается игроку?

Учитывая содержательную сторону игры, было принято решение понимать “свободу выбора” в рамках сцены 2 так

  1. Первые 7 действий идут последовательно одно за другим т.е. нет никакого выбора

  2. Далее можно выбрать какое из действий 8 или 9 совершать первым, а какое вторым

  3. После того, как совершены оба действия 8 и 9, можно выбирать в любой последовательности между действиями 10, 11 и 12

Схематично это можно изобразить так:

Пусть действием, которое требует решения двух головоломок, будет действие 9.

Вот теперь все условия полностью определены, можно приступать к решению

Решение

Пусть цены искомых действий будут х1, х2, …, х12.

Тогда первые 7 действий должны удовлетворять следующим условиям в форме неравенств:

x_1<70\\ 70<x_1+x_2<70+130\\ 200<x_1+x_2+x_3<200+130\\ ... \\ 740<\sum_{i=1}^{7}{x_i}<880

То есть

  1. На начало сцены имеем 70$, поэтому цена первого действия должна быть строго меньше этого значения

  2. Цена первого и второго действий вместе должна быть больше 70, чтобы невозможно было сделать сразу оба. Одновременно с этим сумма должна быть меньше значения, которое получается после прохождения следующего уровня т.е. меньше 200 (=70+130)

  3. Добавление в сумму каждого следующего действия сдвигает левую и правую границы неравенства на величину вознаграждения соответствующего уровня

Для действий 8 и 9 необходимо учесть возможность выбора со стороны пользователя т.е. наложить дополнительные ограничения (неравенства). Кроме того, нужно не забыть, что действие 9 требует прохождения двух уровней, а не одного, как все остальные. Эти ограничения выражаются в форме неравенств как

880<\sum_{i=1}^{7}{x_i}+x_8<880+140\\ 880+140<\sum_{i=1}^{7}{x_i}+x_9<880+140+145\\ 880+140+145<\sum_{i=1}^{7}{x_i}+x_8+x_9<1165+145

Первое и второе неравенства этой группы обеспечивают возможность выбора т.е. первым может идти как действи 8 так и действие 9. Также нужно обратить на границы второго неравенства -- они сдвинуты, чтобы учесть то, что 9 действие требует прохождения двух уровней

Последний блок действий 10, 11, 12 также имеет дополнительные ограничения, связанные с возможностью выбора. Они выписываются по аналогии с действиями 8 и 9 т.е. необходимо учесть все возможные комбинации, которых в этот раз не 2, а 6

1310<\sum_{i=1}^{9}{x_i}+x_{10}<1460\\ 1310<\sum_{i=1}^{9}{x_i}+x_{11}<1460\\1310<\sum_{i=1}^{9}{x_i}+x_{12}<14601460<\sum_{i=1}^{9}{x_i}+x_{10}+x_{11}<1610\\ 1460<\sum_{i=1}^{9}{x_i}+x_{10}+x_{12}<1610\\ 1460<\sum_{i=1}^{9}{x_i}+x_{11}+x_{12}<16101610<\sum_{i=1}^{9}{x_i}+x_{10}+x_{11}+x_{12}<1765

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

1765-\sum_{i=1}^{12}{x_i}=55

В итоге для решения поставленной задачи необходимо решить систему из 18 неравенств с 12 неизвестными, что совсем несложно

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

Вот одно из решений

Номер действия

Цена действия

1

50

2

80

3

120

4

100

5

120

6

150

7

180

8

200

9

280

10

170

11

120

12

140

Заключение

Несколько важных замечаний

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

    1. вознаграждения за уровни не изменяются

    2. количество денег на счету у игрока в начале и в конце сцены фиксированы

  2. Показанный подход можно применять к аналогичным и более сложным задачам