I'm currently developing a plugin for World of Warcraft in LUA to help optimize a recently introduced part of the game, namely Garrison missions.
A Warcraft Garrison (basically a player fortress) has a place where you can assign your followers to go on an mission for you. If these missions succeed, your followers get some experience and you get a small reward, ranging from a bit of money to powerful equipment for you or your followers. A garrison has 20-25 followers and has about 25-30 missions to choose from per day.
A mission has the following attributes:
- A level between 90 and 100, inclusive.
- (for level 100 missions) An equipment level between 615 and 645, in steps of 15.
- between 1 and 3 slots to send followers with.
- between 0 and 6 mission threats. There are about 10 categories of threats, the names of which are irrelevant. What is relevant is that a follower can have 1 or 2 abilities that can counter these threats. A mission can have the same threat twice.
- A zone type where this mission occurs.
- an enemy type which this mission is fighting against.
- A duration.
A follower has the following attributes:
- the race of the follower.
- A level between 90 and 100, inclusive. followers of equal or higher level contribute more to mission success. A follower that is one level beneath the level of the mission is less effective, but still has an effect. A follower 2 or more levels below the level of the mission does not have an influence on the mission success and cannot counter any threats.
- (Starting at level 100) An equipment level between 600 and 655, inclusive. Like normal level, followers of equal or higher equipment level are more effective.
- 1 or 2 abilities that are counters for mission threats. A countered threat increases the chance at success. if all threats are countered with followers of equal of higher level, a mission has a 100% chance of success. A follower can have 2 abilities that counter the same threat.
- 1, 2 or 3 traits that can give minor chance of success bonuses in specific mission conditions. These don't give as much bonus chance as a full counter, but are useful to optimize for. A trait can counter a zone, a duration or an enemy type. They can also give a bonus for having a specific type of follower on the same mission, or even give an always-on chance of success bonus.
What I understand from some brief chatting with Gamedev.SE, this is basically the Bin Packing problem, with the missions being the packages and the followers being the bins. However, in this case, the bins can combine and are different sizes.
The algorithm I'm looking for aims to do the following in the least amount of time:
- Maximize the amount of missions with 100% chance of success;
- Maximize the individual chance of success of each mission that doesn't have 100% chance;
I could probably bruteforce it, but I'm hoping for a somewhat more sophisticated solution.
What algorithm should I use for this?