Hello,

I apologize for the lengthy post, but I am trying to be as clear as possible.

I am creating an RPG and encountered a problem that I cannot figure out a mathematical solution to. I would like to implement a turn-based battle system that would include attack speed of players when determining the order of turns, however I cannot figure out an algorithm for this. Here are some examples of what I mean: (attack speed is a decimal value greater or equal to 1)

If player A has attack speed 2 and player B has attack speed 1, then player A will have two turns before player B gets one.
If player A has attack speed 9 and player B has attack speed 3, then player A will have three turns before player B gets one.
If player A has attack speed 3 and player B has attack speed 2, then player A will get one turn, player B - one turn, then player A will get two turns, player B - one turn and it loops from here.
Hopefully I explained this clearly.

My current algorithm works only in 1 on 1 battles: both players have a variable called remainingAttackValue initialized to their attack speed. When player attacks, his remainingAttackValue is decreased by the smaller value of attack speed of these two players. He can have turns until his remainingAttackValue is greater than that smaller attack speed value. Taking the last example from the above situations:

Player A's attack speed = 3, player B's attack speed = 2. Therefore, we will be subtracting the value 2 from the currently attacking unit's remainingAttackValue.

1. A's remainingAttackValue = 3, B's remainingAttackValue = 2. Player A attacks because he has higher attack speed. We subtract 2 from his remainingAttackValue.
2. A's remainingAttackValue = 1, B's remainingAttackValue = 2. Player B attacks, because player A has not enough points in remainingAttackValue.
3. A's remainingAttackValue = 1, B's remainingAttackValue = 0. Noone can make a move, therefore every player has their remainingAttackValue increased by value of attack speed.
4. A's remainingAttackValue = 4, B's remainingAttackValue = 2. Player A attacks. Subtract 2.
5. A's remainingAttackValue = 2, B's remainingAttackValue = 2. Player A still attacks, because he has enough points in remainingAttackValue.
6. A's remainingAttackValue = 0, B's remainingAttackValue = 2. Player B attacks.
7. A's remainingAttackValue = 0, B's remainingAttackValue = 0. Noone can make a move.
8. A's remainingAttackValue = 3, B's remainingAttackValue = 2. And the situation loops.

The problem appears when I have battles that involve more than two players. For example, if I have three players, I can't just pick the smallest value and subtract that because that would lead to some strange cases like player A having attack speed 1, player B -- 50, player C -- 60 and then player C does 60 turns before player B even gets one.

I can't think of any algorithm that would help me determine the turn order in such cases. It is probably something trivial which I just simply cannot figure out. Could you please give me some advice regarding this problem?

Sounds like you could just do something like...

//For each entity
attackDelay = 1 / attackSpeed //OR e.g. (MAX_ATTACK_SPEED + 1 - attackSpeed) -- whatever it is, something which decreases as attackSpeed increases.
nextAttackTime = currentTime + attackDelay

If multiple entities have the same attack time, sort them in order of attackSpeed.

Edit: Thinking about it, I would probably prefer the MAX_ATTACK_SPEED option, to keep everything as ints and not worry about floating point issues and comparisons being more unintuitive.

va=1
vb=5
vc=7
top = max(va, vb, vc)
# All players aim to reach 'top' at their own vX 'speed'.

a=0
b=0
c=0

turns = []
for i in range(30):
    a = a + va
    b = b + vb
    c = c + vc

    # As 'top' is one of vX, at least one will have reached 'top'.
    # If there are several, you may want to decide who really wins.
    # Here I simply use order A, B, C.
    
    if a >= top:
        turns.append("A")
        a = a - top

    if b >= top:
        turns.append("B")
        b = b - top

    if c >= top:
        turns.append("C")
        c = c - top

print(" ".join(turns))

# Output: C B C B C C B C B C A B C C B C B C C B C B C A B C C B C B C C B C B C A B C C B C B C C B C B C A B C C B C

Much along the lines of @Lactose with a different common finish line.

Inspired by the Bresenham algorithm, which decides in integer arithmetic whether X or Y may move a pixel.

When playing fallout i am sure they just made a list of each character based on Sequence, the character with the highest sequence acts first , if two characters have identical sequence i would probably roll vs another stat (say Luck) to decide which one goes first, this could be done at the beginning of each turn or once per battle , you can decide this .

You could do something like Exlated 2nd edition speed rules. Where the Speed of your action reflected how many "ticks" you had to wait before acting again. A magical fast dagger might have a speed of 3, where a massive two-handed war sledge might have a speed of 9. 

So a character 1 uses a dagger and has to add 3 "ticks" to his waitTicks. Character 2 uses a war sledge and adds 9 waitTicks. 

Tick...Tick...Tick... Character 1 now has zero waitTicks and they can act now. Character 2 now has 6 waitTicks.

- Eck