I am trying to make an algorithm that finds the sequence of spell that maximizes the total damage. I understood this situation as a 0-1 knapsack problem with cooldown for each item. However, I couldn't come out with an appropriate algorithm to solve it(except checking all the possible situations).
I have found the exact same question asked 13 years ago, but the answers seemed not enought for me.
This was the original question by aaronfarr
"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?
(my question is also same)
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,
Fireball: 3000 damage, 3 second cast time, 6 second cool down.
Frostbolt: 20 damage, 4 second cast time, 4 second cool down.
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.
(https://gamedev.stackexchange.com/questions/5593/spell-casting-how-to-optimize-damage-per-second)
these are my thoughts for the answers that were written 13 years ago.
try using Uniform Cost Search, A*, IDA* - by deft_code I have googled about those algorithms(Dijkstra Algorithm together), but thoses seemed to focus on the problem with "Start Point" and "End Point". In my case, the goal is to find the sequence of spell that maximizes the total damage and this seems like combination optimize problem which is not appropriate to solve with them.
anserver by aaronfarr himself I think the solution he came out with is a type of greedy algorithm with does not guarantee the right answer. I am looking for an algoritm that guarantees the best answer.
and these are other algorithms I have tried.
Dynamic Programming The problem of Dynamic Programming was that I couldn't take cooldown, cast time into an account. In DP, it seemed impossible to know which spell was used before.
Brute force I tried this solution with DFS. Since the number of spells is about 15~25, this took way more time than I expected. This can be the last resort, but I am hoping for something better.
At any point in time, the state of the wizard include the remaining cast time on any spell that he is casting, and the list of remaining cooldown times.
He only has to make a decision when the remaining cast time is 0, so we only need to consider those states.
The decision that the wizard must make is to wait or to cast one of the spells with cooldown = 0. The only thing it makes sense to wait for is the cooldown of the next spell to cast, so the decision that the wizard must make at any decision point is just the next spell to cast, and he will cast it immediately if the cooldown is 0 or after the cooldown time. The time before the next decision state is the casting time plus remaining cooldown.
So now you can make the graph of states (cooldown lists) and transitions (spell selections), which you can search in various ways, keeping track of DPS.
If you want to find the highest possible continuous DPS, then you need to search for the best cycle in this graph. The simplest way is to start at each reachable state and use DFS to find the best simple path, if any, back to the start. I'm not entirely sure that's what you're looking for, though.