Turn Update Mechanics

I was implementing a turn system and wanted to write down some things before I forget. I initially worked off the reference for Nethack to understand how the turn system determines which monsters can act during a turn. It’s basically an update loop where each monster is given energy equal to its speed. Only monsters with energy >= 12 can act in a turn. Having 24 energy means you can act twice, 36 thrice. Your max accumulated energy is based on your speed. A speed between 0-12 means your max energy is 12. 13-24 speed has 24 max energy. And 25-36 speed has 36 max energy.

Basic Energy Loop

This isn’t too hard to implement, but I don’t like how we’re calculating the enery every turn. I want the option of having a large number of active entities and while this is a pretty simple system, I’d rather not repeat it over 1000s of entities 30-60 times a second.

let actingMonsters = [];

for (const it of monsters) {
    it.energy += it.speed;
    if (it.energy >= 12) actingMonsters.push(it);
}

for (const it of actingMonsters) {
    update(it);
}

Turn Patterns

I noticed that it looks like the moves in a turn should be simple to predict if you stick to integer speed values. And it kind of is. Over 12 turns. Speeds of 13-24 behave the same as 1-12, except the number of moves in a turn is increased by a base move of 1. A speed of 16 is just like a speed of 4. 16 has one move on turns 1, 2, 4, 5, 7, 8, 10, 11 and two on 3, 6, 9, 12, where 4 would have zero and one, respectively.

My initial though was to just create a full list of monster order over 12 turns. By keeping track of the different start and stop points, you can just iterate over the list. The disadvantage of this list is it needs to be recalculated every time the speed of an enemy is changed. If that is infrequent, then we’re saving a lot by not calculating energy levels each turn.

The big disadvantage of this is that this list can become quite big as the number of entities grows. Say you had four monsters with speeds [1, 3, 5, and 11]. The list would be [ 3, 2, 3, 1, 3, 2, 3, 3, 3, 1, 2, 3, 3, 2, 3, 3, 0, 1, 2, 3 ] where each number is the index of the former list. There are twenty items in that second list. The worst case are speeds like 9-11 which need to be added to the list once for almost each of the twelve turns being tracked. Just based on averages, we’d expect this list to be 6.5x the number of entities. Classic memory.vs.cpu tradeoff.

Using Repeating Cycles

A quick scan of that Speed-Turns table shows other cycles like 2, 3, 4, 5, 6, and 12. I thought I could maintain lists based on those cycles, but speed from 7-11 don’t fit nicely into these cycles. You’d still end up with a complicated structure for tracking all the monster turns and I doubt it would end up much smaller than the previous method.

Looks like precomputing turn order is a dead end, but I’ll revisit when I get a better sense of how expensive the turn energy computation is. Maybe instead of allowing all speeds from 1-36, I can stick to just those that are cyclic. 1, 2, 3, 4, 6, 12, 13, 14, 15, 16, 18, 24 …

Randomized Turn Order based on Weighted Probabilities

The main reason I wanted to precompute the turns was then it’d be possible to do things like statically assign which monsters go first in a round. The idea was to sum up all the monster speeds and compute a weighted distrbution