Как выбрать наиболее выгодную комбинацию предметов из набора предметов?

Question

Я разрабатываю часть игры, в которой ИИ должен определить, какая комбинация брони даст лучший общий бонус к характеристикам персонажа. Каждый персонаж будет иметь около 10 характеристик, из которых только 3-4 важны, и из этих важных, некоторые будут важнее других.

Броня также повышает 1 или все характеристики. Например, рубашка может дать +4 к внутренним характеристикам персонажа и +2 к выносливости, в то время как пара брюк может иметь силу +7 и ничего больше.

Итак, скажем, у персонажа есть здоровый выбор брони (5 пар брюк, 5 пар перчаток и т. Д.) Мы определили, что Int и Perception являются наиболее важными характеристиками для этого персонажа. Как я мог бы написать алгоритм, который бы определял, какая комбинация брони и предметов приведет к наивысшему значению любой характеристики (скажем, в этом примере Int и Perception)?

Answer 1

Ориентация на одну статистику

Это довольно просто. Сначала несколько предположений:

• Вы не упомянули об этом, но, вероятно, можно носить не более одного вида брони для определенного слота. То есть нельзя носить две пары брюк или две рубашки.

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

Предположим, что вы хотите нацелить статистику X. Тогда алгоритм будет следующим:

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

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

Что произойдет, если предположения будут нарушены?

• Если предположение одно не соответствует действительности, то есть вы можете носить несколько предметов в каждом слоте - тогда вместо выбора первого предмета из каждой группы выберите первый Q (s) предметов из каждой группы, где Q (s) - количество предметов, которые могут быть помещены в слот s .

• Если предположение два неверно - то есть элементы do влияют друг на друга - тогда у нас недостаточно информации для решения проблемы. Нам нужно было бы точно знать, как предметы могут влиять друг на друга, иначе мы должны были бы попробовать каждую возможную комбинацию предметов с помощью грубой силы и посмотреть, какие из них имеют наилучшие общие результаты.

<Ч />

Статистика таргетинга N

Если вы хотите нацелиться на несколько характеристик одновременно, вам нужен способ сказать, «насколько хорошо» что-то. Это называется фитнес-функция . Вам нужно будет решить, насколько важна статистика N по отношению друг к другу. Например, вы можете решить, что каждое +1 к Восприятию стоит 10 очков, в то время как каждое +1 к Интеллекту стоит только 6 очков. Теперь у вас есть возможность оценить «добротность» предметов относительно друг друга.

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

Answer 2

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

Подготовка данных:

• Дайте каждому статистику (Интеллект, Восприятие) вес, в зависимости от того, насколько важным он для вас определен Сохраните это как 1-D массив statImportance
• Дайте каждой комбинации предмет-статистика значение, в зависимости от того, насколько этот предмет повышает статистику игрока
  Сохраните это как двумерный массив itemStatBoost

Алгоритм:

В псевдокоде. Здесь предположим, что itemScore является сортируемой картой с Item в качестве ключа и числовым значением в качестве значения, а значения инициализируются равными 0.
Предположим, что метод sort способен сортировать эту карту по значениям (не ключам).

//Score each item and rank them
for each statistic as S
  for each item as I
    score = itemScore.get(I) + (statImportance[S] * itemStatBoost[I,S])
    itemScore.put(I, score)
sort(itemScore)

//Decide which items to use
maxEquippableItems = 10 //use the appropriate value
selectedItems = new array[maxEquippableItems]
for 0 <= idx < maxEquippableItems
  selectedItems[idx] = itemScore.getByIndex(idx)