Linear programming in World of Warcraft: a quest of tailoring, skill and gold
Many video games problems can be modeled with math or solved with programming techniques: n-queens, secretary problem and many more are often encountered in-game!
In World of Warcraft, players can have profession skills: enchanting, tailoring, mining and many others that help gamers to raise money to buy in-game objects, to trade or to sell at the auction house.
As for real life, players have to train skills in order to gain proficiency and to craft more powerful (and valuable) objects.
Just to give you an example, as a tailoring beginner apprentice, you can tailor the following objects:
As you can see, every object require a different amount of materials (or different materials, too!).
The problem to maximize the amount of gold received by selling crafted items when a player has some amount of materials available is a typical linear programming problem.
In particular it is a blending model, i.e. a problem where the goal is to find the optimal way to mix some ingredients given some constraints, in order to minimize or maximize an “objective” function (a goal). Relationship between ingredients mixing is expressed as a linear function…and that’s why we call it “linear”.
Let’s consider the following availability: 20 linen cloth and 8 coarse thread.
We want to decide how to mix them in brown linen cloak or brown linen pants in order to maximize our income.
We also know that the first can be sold for 1 gold at the auction house and the latter can be sold for 3 gold (ok, it’s a lot for those two items, but let’s simplify!).
How can we model the problem?
Let’s define xc as the quantity of linen cloak to be crafted and of xb as the quantity of brown linen pants to be crafted.
We can observe the following facts:
- the quantity xc must be integer and greater or equal to zero
- the quantity xb must be integer and greater or equal to zero
- the quantity of linen cloth used must be lesser than the linen cloth availability
- the quantity of coarse thread used must be lesser than the coarse thread availability
We also know that:
- 1 bolt of linen cloth is made up of 2 pieces of linen cloth.
So the problem can be modeled in the following way:
Let’s graph those inequalities!
We can see that the overlapping planes identify a polyhedron and the fundamental theorem of linear programming states that the optimal solution is one of the vertex of that polyhedron.
So that optimum can be one of the following points: (0,0) (0,8) (2,6) (5,0)
How can we say what’s the optimum? Just calculate the value of the max function in all those points!
To optimize the income we’d better produce 5 brown linen pants! ;)
And now…let’s go to quest! 🙌🙌🙌
