Algorithm for determining turn order in a turn-based rpg.

You could try using a counter. Instead of measuring how fast a character is you measure how long it takes for him to attack.
Each combat cycle you ask each character if he can attack: if (last cycle number + his attack cycle delay < current cycle ) then he can attack. If need be you can add them to a queue/list in the order they are ready and then deal with them in order.
That way each character will attack whenever he can without waiting for the others.


Edit: changed some words so it made more sense in a turn based environment.

Thanks, I think I understand.

I tried plotting each character's turn on a clock, with the fastest character taking a turn ever ten minutes, the second fast taking a turn every 20, and the third every 25.

You're saying the algorithm would basically be the minute hand going through each minute: 12:01, 12:02, etc. until it found out it was someone's turn right? Am I getting this right, because it's starting to make more sense thinking about it that way.

EDIT: The only problem I'm thinking of is how to figure out what interval the algorithm should progress (what a "clock-tick" should be I guess). I guess you would take the LCD of all the entities in the battle?

That depends on what you want to do though. As far as I know, ATB system is like FF8, not FFT. If you'd like to make one, just have a queue representing for people who are waiting for their turn. Then, every character would have a waiting gauge that would be filled (or depleted, depending on the design) every frame by an amount proportional to the character's speed. Whenever the gauge hits the full/empty point, the Character's put at the end of the queue. Then the beginning of the queue is the character who has the current turn. Once the turn's over the character's removed from the beginning and the next one is taken (that's the way queues work).
You can elaborate from here depending on what you need. If you want the gauges to pause when someone's turn arrives, then just have the while(TurnQueue.IsEmpty()) before filling/depleting the gauge. If you want it to be done instantly (Like in FFT), then it's a little bit more complicated, but still very simple. Pseudocode:

Here, whenever the TurnQueue is empty, the algorithm runs through all the Characters present on the battlefield and determines whoever will be the first one to reach the turn, based on his time LeftToWait and his Speed. Then it reduced everyone's time by this number multiplied by everyone's speed. Then it checks again to see who is done with the waiting to determine whom to add to the end of the queue.

If you choose to integrate it this way, be advised that float opperations are erroneous, and thus the if(Characters.LeftToWait==0.0f) might never tick. Then I would advise using some kind of lambda (i.e. error amount acceptable) and check withing it's bounds (-lambda
And yeah, I know I could have retained the Characters that would have hit the gauge the first when I was testing it, but then I would have to introduce an additional variable to store it, and I wanted to keep the code simple.

Everybody has a counter, every second add a point to their counter. When the points in their counter hits Max speed - their speed they get to go. If you want different moves to have different costs subtract that move from their counter otherwise set it to zero.

put all the characters into an array, then sort that array by the speed value, and there you have your order. of course you can go further and make the players characters take precedence over the cpus or vice versa.

A "charge system" like ATB is not too bad to work with.

Each player has a "charge" which increases over time while in combat. Once the charge equals whatever your "fully charged" value is, then it's his turn to move. The rate at which the charge builds depends on the player's speed.

Each game cycle you update a player's charge based on their speed, and check to see if any players have a full charge. If so, you basically "pause" the combat and prompt them to enter their attack selection.

Another option that could work:

If your speed scores go from 1 to 20, with 20 being the fastest, you can have a derived stat for a sort of inverse "attack rate."

A very simplistic way to do that would be to take 21 and subtract the speed score:

Player 1: 21-20 = 1 "firstattack"
Player 2: 21-12 = 9 "firstattack"
Player 3: 21-1 = 20 "firstattack"

With your "battle progress" starting at 1 at the start of a battle, check each of the players for a nextattack == battleprogress. When a player attacks, increment his nextattack by the amount of firstattack. In this extreme case, Player 1 would attack 9 times for every 1 attack of Player 2, and (Edit) 20 times for every attack of Player 3. Player 2 attacks 2.22 times for each of Player 3's attacks.

Whenever a player is finished with his attack, you can then continue incrementing battleprogress while checking against each players' nextattack until you find whose turn it is next. If you're using C++ you might consider storing each of the players in a container and having a GetNextAttacker() method responsible for incrementing battleprogress and comparing it to the nextattack of each player in the container until it finds a match or reaches the end. If it reaches the end, increment battleprogress and repeat. When it finds a match, GetNextAttacker() returns the player (via reference, pointer, ID, whatever) whose turn it is.

[Edited by - Crowseye on June 19, 2010 6:27:19 PM]

Quote:

Original post by stonemetal Everybody has a counter, every second add a point to their counter. When the points in their counter hits Max speed - their speed they get to go. If you want different moves to have different costs subtract that move from their counter otherwise set it to zero.

This makes sense, but the counter's max couldn't be his speed value, otherwise faster characters would take longer to get to their turns.

There would have to be a delay value that is inversely proportional to speed like someone else was talking about. int delay=math.floor(1/speed*100) or something.

Quote:

put all the characters into an array, then sort that array by the speed value, and there you have your order. of course you can go further and make the players characters take precedence over the cpus or vice versa.

There would be no reason to max out your speed stat if the only benefit it gave you was going first in a battle. The way I'm thinking of it is if you were to fight a really slow boss for an extended amount of time with a super fast character, your Speedy Gonzales would have a significantly higher overall turn count comparatively.

Quote:

Original post by freeworld put all the characters into an array, then sort that array by the speed value

You could end up with a starvation problem if you reordered each time unless they weren't added to the array until they were ready to attack, but then we'd be back at the other suggestions. On the other hand, if you reordered only after everyone attacked then you wouldn't have the "lapping" feature he requested.