[Roguelike]Determing Initiative?

The way Angband handles this is to have each creature in the game accumulate energy, with 100 energy being required before the creature can perform an action. The amount of energy a creature gets each tick is determined by its speed. Thus, the theoretical maximum speed would be obtained by a creature getting 100 energy every tick. The player by default gets 10 energy per tick (and thus needs 10 ticks before they can take an action). A creature that's twice as fast as that would get 20 energy per tick (needing 5 ticks to get an action). This does mean that you can have multiple ticks go by without anything getting a turn, but it seems to work fine aside from that.

To think of it another way, it's basically similar to the Final Fantasy "active time battle" system, where you can't take a turn until your bar fills, except the game hides all the waiting for you.

Thanks, Derakon. That's good to know.

I'm expecting to have a large number of entities, possibly up to a thousand in the 'busiest' instance, so trying to think of a more efficient method.

Think I might be on the verge of getting the list idea working. Maybe if I store the slowest member I can allow for resets.

Sortlist at beginning: Cat(28/28), Dog(40/40), Human(100/100)
SLOW = 100; (last element's speed)

Cat goes first, then gets shifted into a new position.
Dog(40/40), Cat(28/56), Human(100/100)

Dog goes, gets shifted.
Cat(28/56), Dog(40/80), Human(100/100)

Cat goes again, still less than SLOW value.
Dog(40/80), Cat(28/84), Human(100/100)

Dog goes, value is now > SLOW, gets placed after Human with Value - SLOW.
Cat(28/84), Human(100/100), Dog(40, 20)

Cat goes, value > SLOW, gets placed before Dog (112 - SLOW)
Human(100/100), Cat(28, 12), Dog(40, 20)

Human goes at last, value > slow, gets placed at end of list with (200-SLOW)
Cat(28, 12), Dog(40, 20), Human(100/100)

Actually, I can simplify this by creating a new list, rather than shuffling all elements to the back and having to keep track of the slowest entities. With each actual MOVE I have to search a list for the entities new position, but that should be faster than iterating through every entity multiple times to see if they're ready to move yet.

Any thoughts?

Quote:

Original post by ChaosFollowing With each actual MOVE I have to search a list for the entities new position, but that should be faster than iterating through every entity multiple times to see if they're ready to move yet.

I'm not sure of that. I guess it could depend on whether you have many fast entities.

Another idea, supposing that among your thousands of entities, many will have the same speed and move at the same time: you can use your system, or the accumulating one, but with the difference that each node in that system will not represent one entity, but the a of all entities that share the same values (speed and action time).

The only drawback I see is that you have some housekeeping to do between lists when an entity decides to wait, or has its speed changed. If this happens only to the player and makes things inefficient, you could make it have its own list, so that it does not get mixed with enemies that never need to change.

Quote:

Original post by SriLumpa Another idea, supposing that among your thousands of entities, many will have the same speed and move at the same time: you can use your system, or the accumulating one, but with the difference that each node in that system will not represent one entity, but the a of all entities that share the same values (speed and action time). The only drawback I see is that you have some housekeeping to do between lists when an entity decides to wait, or has its speed changed. If this happens only to the player and makes things inefficient, you could make it have its own list, so that it does not get mixed with enemies that never need to change.

That is a terrific idea, and just what I was looking for. 90% of entities in most cases will be speed 100. The instances of speed-changing should be extremely rare, so it shouldn't cause untoward problems. And as long as I keep the player at the very front or end of their particular list, it should be nice and cohesive.

Cheers!

Hm...

Okay, a few ideas.

1. Assume that everything that happens within a given round is simultaneous (even if it isn't, programmatically) and just sort of ignore who-goes-first on the micro-level. Basically as long as everything only does one thing when it does something, this should work.

In this case, have it so the player always moves first. This way, every thing that happens on screen will appear to happen as a result of player input, further establishing the notion of simultaneousness. Simultanouity. Simultaneity. Whatever.

Oh and only redraw after EVERYONE had moved.

2. Maybe handle speed like this:

A. Each entity has a counter that determines how long till they can move.
B. Initially this counter is equal to their "speed" value.
C. If the counter is equal to zero, the entity may move, and reset the counter. If not, decrease the counter by one.
D. If you want higher speeds to be faster, then start the counter at zero and count up to Speed.

3. So, basically, if everyone's speed is 10, then they'll take a turn every ten iterations of the update loop. I'm not sure how XNA really works in terms of speed but you're essentially just decreasing a variable during idle turns so the pause for turns where nothing happens should be negligible*.

4. If the player's speed is 10 and the enemy's speed is 5, the enemy will update every five iterations and the player every 10. So, the enemy moves twice as fast.

---edit---

Actually, I've been working on a roguelike engine myself over the past few months. The entity behavior is all scripted in lua so I could write up a really simple program to test this idea out tomorrow and put it up for you.

Quote:

Original post by MeshGearFox Hm... Okay, a few ideas.

Thanks for the post. Similar to the Angband variant posted by Derakon, but I'm worried that the crunch-time will be too large for what I have in mind(1,000 or so Entities).

The advantage of several lists sorted by speed means I only iterate each Entity when its their turn to move, which should be considerably faster even if there's twenty different speeds involved in those 1,000+ entities.

Mm, I don't think iterating over a thousand entities each frame will actually cost you all that much. Give it a shot and see how fast it is. It's a simple, known-working solution, after all. You can always simplify it by batching together entities with the same speed (arbitrarily assign them all the same energy).

Quote:

Original post by Derakon Mm, I don't think iterating over a thousand entities each frame will actually cost you all that much. Give it a shot and see how fast it is. It's a simple, known-working solution, after all. You can always simplify it by batching together entities with the same speed (arbitrarily assign them all the same energy).

The main problem is if I have 999 entities with 100 speed(normal), and 1 super-fast entity with 5 speed. If I subtract energy by 5 each loop, that's almost 20,000 iterations of "do I move yet?", where the answer is yes only around 1,020 times.

The actual move itself may require further AI/pathfinding crunch, so the more efficient, the better.

You don't have to iterate over them all each turn. They can precompute the next turn on which they'll be able to move.

You just keep an ordered list of entities. Each tick, you just run down the list until you find someone who can't move.

The trick then is merely keeping the list in order. But entities will only change position in the list when something happens to them -- which will be less than every tick.

Once someone has moved, they take their entry out of the wakeup list, and reinsert it by going down the list until they find someone who will wakeup later than 100/SPEED ticks, and put their entry in front of them.

I would use timestamps.