How do I pick the most beneficial combination of items from a set of items?

I'm designing a piece of a game where the AI needs to determine which combination of armor will give the best overall stat bonus to the character. Each character will have about 10 stats, of which only 3-4 are important, and of those important ones, a few will be more important than the others.

Armor will also give a boost to 1 or all stats. For example, a shirt might give +4 to the character's int and +2 stamina while at the same time, a pair of pants may have +7 strength and nothing else.

So let's say that a character has a healthy choice of armor to use (5 pairs of pants, 5 pairs of gloves, etc.) We've designated that Int and Perception are the most important stats for this character. How could I write an algorithm that would determine which combination of armor and items would resul开发者_开发百科t in the highest of any given stat (say in this example Int and Perception)?

Targeting one statistic

This is pretty straightforward. First, a few assumptions:

• You didn't mention this, but presumably one can only wear at most one kind of armor for a particular slot. That is, you can't wear two pairs of pants, or two shirts.

• Presumably, also, the choice of one piece of gear does not affect or conflict with others (other than the constraint of not having more than one piece of clothing in the same slot). That is, if you wear pants, this in no way precludes you from wearing a shirt. But notice, more subtly, that we're assuming you don't get some sort of synergy effect from wearing two related items.

Suppose that you want to target statistic X. Then the algorithm is as follows:

• Group all the items by slot.
• Within each group, sort the potential items in that group by how much they boost X, in descending order.
• Pick the first item in each group and wear it.
• The set of items chosen is the optimal loadout.

Proof: The only way to get a higher X stat would be if there was an item A which provided more X than some other in its group. But we already sorted all the items in each group in descending order, so there can be no such A.

What happens if the assumptions are violated?

• If assumption one isn't true -- that is, you can wear multiple items in each slot -- then instead of picking the first item from each group, pick the first Q(s) items from each group, where Q(s) is the number of items that can go in slot s.

• If assumption two isn't true -- that is, items do affect each other -- then we don't have enough information to solve the problem. We'd need to know specifically how items can affect each other, or else be forced to try every possible combination of items through brute force and see which ones have the best overall results.

Targeting N statistics

If you want to target multiple stats at once, you need a way to tell "how good" something is. This is called a fitness function. You'll need to decide how important the N statistics are, relative to each other. For example, you might decide that every +1 to Perception is worth 10 points, while every +1 to Intelligence is only worth 6 points. You now have a way to evaluate the "goodness" of items relative to each other.

Once you have that, instead of optimizing for X, you instead optimize for F, the fitness function. The process is then the same as the above for one statistic.

If, there is no restriction on the number of items by category, the following will work for multiple statistics and multiple items.

Data preparation:

• Give each statistic (Int, Perception) a weight, according to how important you determine it is
  Store this as a 1-D array statImportance
• Give each item-statistic combination a value, according to how much said item boosts said statistic for the player
  Store this as a 2-D array itemStatBoost

Algorithm:

In pseudocode. Here assume that itemScore is a sortable Map with Item as the key and a numeric value as the value, and values are initialised to 0.
Assume that the sort method is able to sort this Map by values (not keys).

//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)