algorithm - Spell casting - How to optimize damage per second

Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cool down time, and a cast time. Pretty standard RPG stuff.

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. 
   

   Fireball: 3000 damage, 3 second cast time, 6 second cool down.

   
   


2. 
   
   

   Frostbolt: 20 damage, 4 second cast time, 4 second cool down.

   
   


3. 
   

   Fireblast: 3 damage, 3 second cast time, 3 second cool down.

   
   

In this case your damage per second is higher if you chose to go for the lower DPCT spell (fireblast) instead of the frostbolt. So we must consider consequences of choosing a spell.

In the following example are cases of "over casting" and "waiting".

Answer

All AI is search!

When you get into the guts of AI it's amazing how much of it is really search.

• state: the remaining cooldown of all available spells.


• fitness: total damage done


• cost: total time taken


• branches: any known spell. If spell is still in cooldown just add that value to its cast time.


• goal: total health of target. The goal has to be a finite amount of damage, so in the case of an unknown target, pick the largest possible health.
  Alternatively, the goal could be spend less than 50 seconds and the search would find the maximal damage that could be done in 50 seconds.

Plug these parameters into a Uniform Cost Search (UCS) and presto, guaranteed optimal battle plan. Even better if you can come up with a heuristic, search with A*, or IDA* and you'll get the same answer much faster.

Some more advantages to using UCS is it can find optimal cast order for much more complicated situations than the one you provided with only 3 variables. Some other aspects that could easily added:

• damage over time


• refresh spell to reduce cooldown of other spells


• haste spell causing other spells to cast faster.


• damage booster causing other spells to do more damage.

UCS is not omnipotent. It cannot model the benefits of protection spells. For that you'll have to upgrade to alpha-beta search or minimax.

Also it doesn't handle area-of-affect and group fights very well. UCS can be tweaked to give reasonable solutions in these situations, it is not guaranteed to find the optimal solution.