First of all, a disclaimer: I’m a bit embarrassed about writing this entry because I feel like this isn’t a hard problem so I should just know how to do it. I’m also embarrassed because my solution to the problem is probably any combination of wrong, inefficient, overly complex, and laughably stupid. But I guess if it works, it works.
If you know a better way to do this, I’d love to hear it.
The Problem
In a turn-based game where there are multiple actors, how do you predict and list the order in which the actors will take their turn when that order is dependent on each actor’s individual “speed” statistic, especially if an actor could have multiple turns before another if the first was “fast” enough and the second was “slow” enough.
For example, in a Tactics RPG such as Final Fantasy Tactics or Phantom Brave, it is useful to see which units will get their turns soon so you can either target them specifically in the hopes of defeating them before they take their turn or so you can prepare to survive an attack from them.
I’ll try to explain the problem I’m talking about using a sort of racing analogy. Say there is a circular race course around which there are vehicles driving laps. Each vehicle begins at the “starting line” and moves at a constant rate the entire time. The vehicles aren’t really racing each other. They are just driving in circles around the course repeatedly. (And for the sake of this example they magically don’t have to worry about pesky realities such as having to avoid each other to prevent collisions.)
Such a “race” would be boring because given how long the course is and how fast each vehicle is moving, you would be able to predict the order in which the vehicles would cross the starting line and begin a new lap. The results would be known before it even started, and are not that hard to manually calculate, though it could be time consuming depending on how many you want to list.
For example. If the track were 100 units long, and there were only two vehicles on the track–vehicle “Bob” traveling at 100 units per minute and the other, “Sally,” traveling at 50 units per minute–then we could list the order as: Bob, Bob, Sally, Bob, Bob, Sally, Bob, Bob, Sally, etc. This is if we awarded a “tie” to the fastest vehicle. That is, if both vehicles finish a lap at the same time, the vehicle that was traveling fastest at the time it crossed the line will be put on the list first, with the slower vehicle put on the list immediately thereafter.
But how do you generalize that out to make it work for any number of vehicles moving at individual (but not necessarily unique) speeds on a track of any length? In other words, take this specific example and come up with a more general theory that would work in any other scenario where there is at least one vehicle (but potentially hundreds or thousands or more vehicles) moving around the track, each at its own but not necessarily different speed?
A Partial Solution
To bring this back to the problem of predicting which actors would get to take their turns in which order, I’ll spell out how the racing analogy relates. Basically, each vehicle on the track can be thought of as an actor, each with their own “speed” statistic. The length of the track can be thought of as a kind of “ready meter” that each actor has and fills up in increments of their speed stat. Once the ready meter has become full, that actor gets to take a turn.
Since this is computer programming, these meters can’t technically all fill up simultaneously. That is, we have to go to one actor, and allow it to add a little bit to its ready meter, then go to the next and let it add a little to its ready meter, and so on, and after all the actors have taken a single turn to add that little bit to their ready meter, we compare them and see who is full.
If multiple actors’ ready meters are full, we award the turn to the one that is most full (e.g. if one actor’s meter is 115% full and the other is only 100% full then the one that is 115% full gets to go first). If multiple actors’ meters are full and at the same level, then we award the turn to whichever one has the fastest speed. If multiple actors’ meters are full and at the same level and have the same speed, then we award the turn in the same order as the list of actors is already sorted (since we have to iterate through them one by one to compare them) which may have somewhat random results depending on the sorting method used. And of course once a turn is awarded to an actor, we subtract the amount of the meter from them and let them fill it up again. (This means that if an actor had overfilled its meter to 115% before it got a turn, after the subtraction it would still have the extra 15%.)
So a partial solution would be to find out how many turns into the future you wanted to list and then just let a computer do what computers do best and run the numbers following those rules and let the computer build the list manually that way. You could do that and in a matter of perhaps a few seconds at most (depending, I suppose, on how long the “race course” is, to use the analogy) you could have a list of the next few thousand (or tens or hundreds of thousands of) turns.
Aside from the fact that it feels like a clunky hack, if your game or match isn’t likely to last that many turns before winning or losing conditions are met then it works, right?
Well, maybe. Partially. Sort of. Yes and no.
The Problem With the Partial Solution
It does work if the vehicles are always in the race and always going at the same speed. But this is a game, remember? Continuing with the analogy, what if the vehicle gets a temporary (or permanent) speed boost (or slowdown) partway through the race? Suddenly the list is invalidated beyond that point in time. What if a vehicle crashes into a siderail or is otherwise disabled and is no longer a part of the race? Once again, the pre-generated list is invalidated, since that vehicle will no longer be finishing any laps.
And if all you did was create the list and then just go down the list and say, “Okay, first you, second you, third you,” etc., then eventually when Bob’s name comes up on the list but Bob is no longer in the game, you’re going to have a problem. This particular problem isn’t that hard to deal with. You could just remove all future references to Bob and move everyone else up the line to fill in the blank spots. If you’ve pre-generated the list far enough out then you should still have a long enough list of turns to last you through the game.
But what about if Sally is still in the game but suddenly she is now moving three times as fast? Then you’ve got a big problem. How big? Potentially fairly big. Again, if all you did was create the list and then just go down the list one by one to see whose turn it is, then suddenly Sally gets a speed boost, how will you know what the new order will be? How can you recalculate it from that point on? You can’t just start the calculation over with the new speeds. Bob may have been 99% full when Sally got the boost, which means he might still go next, or at least soon. But if you start them all at 0% and have them fill up with the new speeds, it will mess up the order
What to do about this?
My Solution
Again, this probably isn’t the best solution, or even a very good one, but this is the solution I’ve come up with. And since I haven’t implemented it yet, it might not even work, but I think it will.
Basically what I’ll do is determine which actor gets the current turn, and then keep and use that information (including the current status of each actor’s ready meter) to predict the next X turns (however many I want to display–a relatively small number) assuming everything stays the same.
And if, during the course of the current turn, one or more actors is removed from the game or changes speed, I will recalculate the next X turns using the current “ready meter levels” and the new speeds.
But It’s Still Not Great
Like I said, it’s not a great solution. In fact, there are some inefficiencies I can identify right away.
Since I’m only keeping track of the “ready meters” for the current turn, this means I will need to recalculate X turns after every turn so that I can display the future order. In other words, if I want to display the next 10 turns in a list, then I have to calculate 10 turns each turn. This means that (assuming the order hasn’t changed due to changes in speed or removal from the game) I am basically throwing away and recalculating the same order for 90% of the list each turn.
It’s nice and simple to just create a First In, First Out (FIFO) list that only stores the name/id/reference to the actors that get to move. It makes it so a simple array can handle the future order prediction/display stuff.
On the other hand, if I made each entry in the list store a bit more information, such as the how full the “ready meter” is for each actor at that time in the list, then when I popped the actor off the top of the list and needed to figure out which actor to put on the bottom of the list, I could simply calculate only that one. Additionally, I would only have to throw away and recalculate the entire list when one or more actors speed changed or were removed from the game.
That sounds pretty efficient, except now that’s a lot more data to store for each turn. Before the list would essentially just look like:
- Bob
- Bob
- Sally
- Bob
- Bob
- Sally
- Bob
- Bob
- Sally
- Bob
But with this revised method that stores more data, it would look more like:
- Bob (100), Sally (50)
- Bob (100), Sally (100)
- Sally (100), Bob (0)
- Bob (100), Sally (50)
- Bob (100), Sally (100)
- Sally (100), Bob (0)
- Bob (100), Sally (50)
- Bob (100), Sally (100)
- Sally (100), Bob (0)
- Bob (100), Sally (50)
And that’s with only two actors. Now imagine what the list would look like with twenty or fifty actors. I guess that’s still not too bad. Even with 50 actors I’d only need to store 1,000 pieces of data for the list. That would be a lot to process for a human, but for any computer made in the 21st century it could be iterated through pretty fast. And really you’d only iterate through one item in the list at a time to calculate the next thing in the list, with 50 actors that’s only 100 values, namely the actor’s name/id/reference and corresponding fullness of the “ready meter.” Super easy for a modern CPU.
Okay, so I think I’ve convinced myself that this idea would work pretty well for my needs, even if it’s not the best solution.
Very interesting question/subject matter. This is why programming is fun, trying to solve problems like this.
I think you described the nature of the problem pretty well.. You want to make a turn based order of play, but you have speeds expressed as arbitrary values. The perfect example is a board game where you have cars on a track with a fixed number of spaces on the board, but car speed is in miles per hour. And your goal is a system that assigns turn order — AND MOST IMPORTANTLY you want to capture the idea that if car X is twice as fast as car Y, it should get twice as many turns.
Your solution sounded like it was on the right “track” to me, though i got lost a little bit. However i believe there is a more elegant solution that would look something like this:
For each agent, you will keep track of its current turn “meter”, which will start at 0.
Now on each turn you “normalize” the speeds of the agents to make them scale from 0 to 1; you do this by simply dividing all agent speeds by the speed of the fastest agent (this preserves the relative speeds which is all we care about).
TURN LOOP BEGIN:
For each agent, ADD the agent’s normalized speed (which will range from 0 to 1) to their current meter value.
Sort agents by current meter values.
Iterate through list of agents. If agent has more than 1.0 in their meter, they take their turn and SUBTRACT 1.0 from their meter. If not, they are skipped.
REPEAT TURN LOOP
I contend that this will get you what you want. I think intuitively the way to think about it is that it tries to convert the relative speeds into “fractions of a turn”. So that the fastest player is always taking one full turn per round. Other players take virtual “fractional turns” — not moving but building up until they can be spent for a full turn.
Another way to think of it is to imagine player A is twice as fast as player B. So on each round we give player A 2 chips, and player B 1 chip. And it costs 2 chips to move. So on each turn player A spends his 2 chips to play, and player B must *SAVE UP* chips so he can move every other turn. That’s essentially what we are doing here.
@mouser: Thanks for the response.
Your solution does indeed sound more elegant than the one I came up with. Now I just need to prototype it and see how it works in action.