Math Wizardry - Formula for selecting the best spell

Question

Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cooldown time, and a cast time.

Cooldown time: the amount of time (t) it takes before being able to cast that spell again. A spell goes on "cooldown" the moment it begins casting.

Cast time: the amount of time (t) it takes to use a spell. While the wizard is casting something another spell cannot be cast and it cannot be canceled.

The question is: How would you maximize damage given different sets of spells?

It is easy to calculate the highest damage per cast time. But what about in situations where it is better to wait then to get "stuck" casting a low damage spell when a much higher one is available:

For example,

1) 100 damage, 1 second cast time, 10 second cool down.

2) 10 damage, 4 second cast time, 0 second cool down.

So, in this case you would cast #1, #2, wait. Cast #1

Answer 1

It is worth noting that, in extreme special cases, this problem degenerates to the Knapsack Problem, which is NP-complete to solve exactly. To see this, imagine that there is one spell, henceforth called the Megaspell, which does a very, very large amount of damage, has zero casting time, and has some positive cooldown $n$. If all the other spells do much less damage than the Megaspell, it will clearly be optimal to cast the Megaspell every $n$ seconds and then optimize the cooldown time with the weaker spells.

Now, assume all the other spells also have cooldown $n$. If one optimizes a given $n$-second downtime with these spells, then the same spell-sequence will also be possible in the next $n$-second downtime, and so we can assume the solution is $n$-periodic.

The problem then reduces to optimizing the $n$ available seconds with the lesser spells, each of which may only be cast once. If one replaces casting time with 'weight' and damage with 'value', one recovers the Knapsack Problem for maximum weight n.

Answer 2

I don't have an answer, but I just want to point out that the greedy algorithm fails. That is, if we choose to cast, at any point, the available spell which maximizes $\frac{ \text{damage} }{ \text{cast time} }$, we don't actually maximize our damage output because of cooldown. Consider the pair of spells $(300, 5, 12)$ and $(50, 3, 0)$ (where the three numbers are damage, cast time in second times, and cooldown time in seconds): the greedy algorithm suggests the casting schedule

• Cast spell 1 ($300$ damage, $5$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Repeat

which gives about $32.1$ damage per second. However, the casting schedule

• Cast spell 1 ($300$ damage, $5$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Cast spell 2 ($50$ damage, $3$ seconds),
• Wait $1$ second,
• Repeat

gives about $33.3$ damage per second. So a correct algorithm must take into account which spells are about to finish cooling down.

Answer 3

How about this algorithm? At each moment your decision is which spell to cast next. Having decided, if the cool down time for that one has expired, then go ahead and cast it. If not, wait until it has expired, then cast it. To make the decision, rank the spells in damage/time where time is from now to completion (including any cool down time left). Then see if you can fit in one of the other spell without delaying the best one. Taking Qiochu's example, at the start spell 1 is 300/5=60 dam/sec and spell 2 is 50/3=16.7dam/sec. Having cast spell 1, it is now 300/17=17.6 dam/sec, still better than 2. But we can get 2 done twice before 1 is available, so we should do that. The question would be whether you can change the parameters so that you should use the weaker spell even though it will delay the strong one by just a little bit.

Answer 4

Let's rephrase to: what's the maximal damage that I can cause in, say, 100 seconds? The constraints then become:

1. Can't spend more than 100 seconds casting
2. Can't cast a single spell more than $\frac{100}{cast\ time + cool\ time}$ times

Let $n_i$ be the number of times I cast spell i. I want to maximize $\sum_i n_i damage_i$ subject to $\sum_i n_i cast_i < 100$ and each $n_i(cast_i + cool_i) < 100$.

This can be rewritten to a linear programming problem as follows:

1. The first constraint is $[cast_0 \dots cast_m] [n_0 \dots n_m]^T<100$
2. The other constraints are $[0 \dots (cast_i + cool_i) \dots 0] [n_0 \dots n_m]^T < 100$

EDIT: My assumptions are

1. You cannot cast two spells at the same time. Constraint #1 ensures that this is true.
2. You can only cast a spell once every $cast + cool$ period. Constraint #2 ensures this is true. (Note that this does not say you cannot cast a different spell in this period; only that you cannot cast the same spell in this period.)

Answer 5

I was able to solve the problem with a computer algorithm but am still not certain how it can be done mathematically. It was pointed out by @Greg Muller that the knapsack problem is applicable but I just don't have the mathematical prowess to apply it. If someone could show how that can be done please do.

Will share my logic here, hopefully it is useful to someone out there.

The first step is to determine the spell with the most damage per cast time.

This spell becomes the "baseline" spell since it will guarantee the highest damage per second. Meaning, you should always cast this spell if the following 2 conditions are met: 1) The baseline spell is available (not on cooldown). 2) You are not currently casting a spell.

So it then becomes a matter of filling in other spells while the baseline spell is on cooldown. Between (cast time) and (cooldown - cast time). However, some overlapping can occur (rule 2 above is false).

It then becomes a matter of recursing through all non-baseline spells to find all sequences of spells which do not violate the 2 rules.

For spells which DO overlap you must penalize them for potential damage the baseline spell could have done (up to its maximum damage).

Take for example, 2 spells

1: 300 damage, 3s cast time, 10s cooldown

2: 290 damage, 3s cast time, 3s cooldown

The most damage comes from the sequence 1 - 2 - 2 - 2. Which causes an overlap of 2 seconds into a potential #1 cast. However, this is still beneficial since if you dont cast the third spell (ie. 1 - 2 - 2) you will do 880 damage with 1 second to spare. If you cast the extra #2 spell you will do 1170 - 2 second of #1 which is 200. So 970 damage is your relative damage.

This algorithm is significantly faster than other algorithms which look for sequences that match a target goal: ie. time limit or damage.