How to choose the most profitable combination of items from a set of items?

Question

I am developing a piece of the game where the AI ​​needs to determine which combination of armor will give the best overall bonus to the character. Each character will have about 10 characteristics, of which only 3-4 are important, and of those important, some of them will be more important than others.

Armor will also give an impetus to 1 or all statistics. For example, a shirt can give +4 int character and +2 stamina, at the same time, a pair of pants can have a +7 power and nothing more.

So, let's say that the character has a healthy choice of armor (5 pairs of trousers, 5 pairs of gloves, etc.). We indicated that Int and Perception are the most important characteristics for this character. How could I write an algorithm that determines which combination of armor and items would lead to the highest of any given stats (for example, in this example, Int and Perception)?

Answer 1

Orientation of one statistic

It is pretty simple. Firstly, a few assumptions:

• You did not mention this, but it seems that you can only wear one type of armor for a particular slot. That is, you cannot wear two pairs of underpants or two shirts.

• Presumably, the choice of one item of gear does not affect or does not conflict with others (except for the limitation of not having more than one piece of clothing in one slot). That is, if you wear pants, this in no way prevents you from wearing a shirt. But note, more subtly, that we assume that you are not getting any synergy from wearing two related items.

Suppose you want to configure the X statistics. Then the algorithm looks like this:

• Group all items by slot.
• In each group, sort the potential elements in this group by how much they increase X in descending order.
• Select the first item in each group and put it on.
• A set of selected items is an optimal load.

Evidence. The only way to get a higher criterion X is if there were an element A that provided more X than any other in its group. But we have already sorted all the elements in each group in descending order, so this A cannot be.

What happens if assumptions are violated?

• If the assumption is incorrect, i.e. you can carry several elements in each slot, then instead of selecting the first element from each group, select the first Q elements from each group, where Q (s) is the number of elements that can go to s slots.

• If assumption two is incorrect, that is, the elements influence each other - then we do not have enough information to solve the problem. We would need to know exactly how the elements can influence each other, or they are forced to try every possible combination of elements with brute force and see which ones have the best overall results.

---

Targeting Statistics N

If you want to set up multiple statistics right away, you need a way to say “how good” something is. This is called a fitness feature. You will need to decide how important statistics N are relative to each other. For example, you can decide that each +1 to perception costs 10 points, and each +1 to intelligence costs only 6 points. Now you have a way to appreciate the "kindness" of objects relative to each other.

Once you do this, instead of optimizing for X, you will instead optimize function F, the fitness function. This process will be the same as above for one statistic.

Answer 2

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

Data Preparation:

• Give each statistic (Int, Perception) weight, depending on how important you define it. Store it as a one-dimensional array of statImportance
• Give each combination of elements and statistics a value depending on how much the specified element increases the specified statistics for the player. Store this as a 2-dimensional array of itemStatBoost

Algorithm:

In pseudo code. Suppose itemScore is a sortable Map with Item as a key and a numeric value as a value, and the values ​​are initialized to 0.
Suppose the sort method is capable of sorting 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)