Вопросы Теги

Как я выбираю самую выгодную комбинацию объектов от ряда объектов?

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

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

Так скажем, что символ имеет здоровый выбор брони использовать (5 пар штанов, 5 пар перчаток, и т.д.) Мы определяли тот Интервал, и Восприятие самая важная статистика для этого символа. Как я мог записать алгоритм, который определил бы, какая комбинация брони и объектов привела бы к самой высокой из какой-либо данной статистики (скажите в этом Интервале в качестве примера и Восприятии)?

6
задан John Feminella 24 April 2010 в 12:22
поделиться

2 ответа

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

Это довольно просто. Во-первых, несколько предположений:

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

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

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

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

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

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

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

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

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

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

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

7
ответ дан 10 December 2019 в 00:35
поделиться

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

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

  • Присвойте каждой статистике (Int, Perception) вес в зависимости от того, насколько она важна.
    Сохраните это как 1-мерный массив 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)
3
ответ дан 10 December 2019 в 00:35
поделиться
Другие вопросы по тегам:

Похожие вопросы: