Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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. alt text

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

share|improve this question
    
Why would I do 1-3-1 in this situation? Why not 1-2-1? Why not 1-2-3-1, which is more efficient than 1-3-1-X if 1-3-1 alone won't kill the target? –  user744 Nov 15 '10 at 21:03
    
@Joe Wreschnig: Thanks for pointing that out. Was a mistake in my example. Simplified it now to just 2 cases. –  aaronfarr Nov 15 '10 at 21:15
    
But now the greedy solution isn't 1221 unless your greedy algorithm sucks. Picking 121 still gives higher DPS when you do a greedy selection including the remaining cooldown time. I think you're inventing a problem where there is none. –  user744 Nov 15 '10 at 22:54
1  
Greedy, as in choose the highest available dps spell whenever possible. Disregarding other logic ie. waiting. –  aaronfarr Nov 15 '10 at 23:06
1  
You should link to the dupe at math.stackexchange.com/questions/10414/… –  Sparr Nov 16 '10 at 5:43
show 3 more comments

6 Answers 6

up vote 23 down vote accepted

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.

share|improve this answer
add comment

This is a specialized combinatorial optimization problem. As the number of spells increases, the difficulty in finding the optimal combination/pattern of spells increases significantly. Heuristics similar to those used for the knapsack problem would be valuable in solving this problem.

share|improve this answer
add comment

You need to think in terms of 'damage per unit of casting time' (DPCT) - for example, a fireball with a 3 second cast and doing 3000 damage would do 1000 DPCT.

If you had to wait 3 seconds for the cooldown before casting it, that would reduce it to 500 DPCT (3000 damage, divided by 6 seconds total, including the waiting)

So you just need to determine the damage-per-cast-time of each spell, including any remaining wait for the cooldown. Pick the one with the highest DPCT, Wait if necessary, then cast it. Repeat until the boss is dead :)

share|improve this answer
    
the problem is that DPCT can be very misleading. Say for example we add 2 more spells to the mix Fireball: 3000 damage, 3 second cast, 6 second cooldown, DPCT: 1000 Spell #2: 20 damage, 4 second cast, 4 second cooldown, DPCT: 5 Spell #3: 3 damage, 3 second cast, 3 second cooldown, DPCT: 1 (remember, cooldown begins the moment the spell is cast) Even though Spell #3 has a lower DPCT it will result in higher DPS (1-3-1-3...) than Spell #2 (1-2-1-2...). –  aaronfarr Nov 15 '10 at 22:30
add comment

Using your example, you'd probably want the two spells to be closer in effectiveness, but possibly give you a different advantage. Having a short casting time (or no casting time for that matter) would be very useful, so then it may be worth using even if it does less damage and takes longer to use again.

You could always impose another element into the equation. Mana/Magic Points can serve this purpose, by allowing the player to determine whether the use of those points is worth the benefit.

Overall though, as bluescrn said, the DPCT (or DPS as its called in many games that are highly tuned and discussed by players seeking the best mix) is really the main element you will want to have balanced, especially if you have any sort of tech/skill trees that allow different players to progress with different skills, yet with the ability to do similar amounts of damage at their given position in the game.

share|improve this answer
add comment

Figured out this algorithm which works well for my purposes.

People brought up some great points. Giving it ultimate goal parameters would allow normal search algorithms to do their thing. ie. do optimal damage in t seconds, do x damage in optimal time.

My algorithm simply returns the sequence of spells with the highest DPS. It is a fast algorithm as it cuts down on the size of the set you are traversing, does not require knowledge of other search tree techniques.

The first step is to identify the spell with the highest 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.

share|improve this answer
add comment

You could do a simple "security level" style switch case.

This is just off the top of my head so beware logic errors beyond my tired state's level of thought, but I hope this can get you started.

Assuming your time is done in block integers -

// after casting spell
int remainingTime = (coolDown - castTime);
switch(spellJustCast)
{
  // assuming the cast method will have some input validation for whether the spell
  // is off cooldown or not, pass the time as a parameter
  case 3 : castSpell1(remainingTime);
           castSpell2(remainingTime);
           break;
  case 1 : castSpell2(remainingTime);
           castSpell3(remainingTime);
           break;
  case 2 : castSpell1(remainingTime);
           castSpell3(remainingTime);
           break;
  default: System.out.println("Debug!");
           break;
}

Some of the method calls are unnecessary due to your spell times, but there's always room for updates this way.

Edit: I just realised, you would need to reset the remaining time after the new spell was cast, probably best to make it a class attribute/field and set it from a call within the castSpell methods.

share|improve this answer
    
I really have no idea what you're trying to get at here, but no modern game engine has functions like castSpell1 and castSpell2. –  user744 Nov 15 '10 at 22:56
    
@Joe Wreschnig I meant them as being his own methods in his custom game classes, this is just an abstract example, not a detailed one. –  kymully Nov 16 '10 at 8:20
1  
Right, that's not how spells work in modern engines. There's one castSpell function that takes an object whose fields are read from a file. Such a switch statement would be impossible to maintain in any real engine, and some kind of planning algorithm is required. –  user744 Nov 16 '10 at 9:33
    
@Joe Wreschnig I understand. I was merely giving a way in which to solve the problem. This example is written in java, not intended for an engine or specific framework. But if it can't be implemented as you say, my answer is void. –  kymully Nov 16 '10 at 10:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.