# Turn Based Event Algorithm

I'm currently working on a small roguelike in XNA, which sees the player in a randomly generated series of dungeons fending off creeps, as you might expect. As with most roguelikes, the player makes a move, and then each of the creeps currently active on screen will make a move in turns, until all creeps have updated, and it return's to the player's go. On paper, the simple algorithm is straightforward:

Player takes turn
Turn Number increments
For each active creep, update Position
Once all active creeps have updated, allow player to take next turn

However, when it comes to actually writing this in more detail, the concept becomes a bit more tricky for me. So my question comes as this: what is the best way to handle events taking turns to trigger, where the completion of each last event triggers the next, when dealing with a large number of creeps (probably stored as an array of an enemy object), and is there an easier way to create some kind of engine that just takes all objects that need updating and chains them together so their updates follow suit?

I'm not asking for code, just algorithms and theory in the direction of objects triggering updates one after the other, in a turn based manner.

Edited: Here's the code I currently have that is horrible :/

        if (player.getTurnOver() && updateWait == 0)
{
if (creep[creepToUpdate].getActive())
{
creep[creepToUpdate].moveObject(player, map1);
updateWait = 10;
}
if (creepToUpdate < creep.Length -1)
{
creepToUpdate++;
}
else
{
creepToUpdate = 0;
player.setTurnOver(false);
}
}
if (updateWait > 0)
{
updateWait--;
}

• Is there a reason you can't make a List<Creep> and simply iterate through it? – chaosTechnician Jul 10 '12 at 16:35
• because the objects have to update in order, not all at once - basically, the next creep is only allowed to update once the last creep has updated - there must be a visible wait time while each moves/makes an attack – GamersIncoming Jul 10 '12 at 17:01
• Of course you can still iterate with visible wait time. You just keep pointer to where you're at in the list. Update one, then update the graphics, update the next, then update graphics, etc. until you're done with all the creeps. However, if you really have 1000 creeps, having a visible wait time might be a bad idea. – MichaelHouse Jul 10 '12 at 18:38
• So, like @Byte56 said, keep a List<Creep> and int creepIndex doing only one iteration per draw/update loop. That's what it looks like you're more or less doing above so I'm not sure what the problem is. – chaosTechnician Jul 10 '12 at 22:42
• Ok I fixed it, just me being stupid, I had this nested in another for loop which I had overlooked which was slowing the whole thing up. Thanks for all the help. – GamersIncoming Jul 11 '12 at 15:45

Here's something I did for a similar "small roguelike", and it wound up working pretty well, and perhaps you will have success with it.

To make this clearer, I must first talk about the concept of "turns".

My Roguelike was based (loosely) upon the board game HeroQuest, which involved the typical dice rolling, moving figures, etc.

I didn't want to have my game like that. I wanted the player to move a square and I wanted the creatures to move appropriately. However, I did still want the idea of a particular amount of movement for the player equating to a differing amount of movement for the creatures.

So, I kept track of the fractional turn of the creatures. If a creature has a movement rate of 8 squares per turn, then each time he moves he increments his fractional turn by 0.125. If he moves 10 squares per turn, he increments only by 0.1.

And this can be used for any activity done by the creature. If a creature may attack 1 time per round, then when he attacks add 1 to the fractional turn. If a creature may attack 2 times per round, then add 0.5.

On the threshholds (where the fractional turn goes from a 0 point something to a 1 point something, like perhaps going from 0.95 to 1.05), then this triggers an "end of turn" event for the creature, where health recovery, mana recovery, or whatever else you want to have happen for the creature.

At any time, picking the creature to move next is quite simple. Whoever has the lowest fractional turn value gets to move next. When the player is next to move, then wait for user input. You could easily adapt a priority queue to use for this purpose, where the lowest fractional turn is the priority.

A small caveat: I had multiple areas in the game, so not everything was loaded at the same time. If everything is loaded at once, it doesn't matter what the turn values are, because less is still less, but if a player leaves an area and the creatures in it are no longer updated, when the player arrives again he will have a much larger turn value than the other creatures, and they will get a lot of opportunity to beat him to a pulp.

This is how I mitigated that: when a player leaves the area, subtract his turn value from all of the turn values of all of the creatures in it. When he arrives in an area, add his turn value to all creatures in it. This way between visits the areas have a relative value to the player that can be restored later.

• I like this idea, but I currently have 1000 creeps spread over the whole map. Looping through and checking if each is visible (and therefore if it should be updated) and then incrementing the counter to check for the next creep to update takes far too long. What would be the quickest way to completely ignore creeps that are inactive? – GamersIncoming Jul 10 '12 at 18:27
• I think you still want to update the creeps that are not visible, you would just have instantaneous movement for those that are not visible. Further, updating 1000 creeps shouldn't be the slow. Have you actually tried or are you speculating? – MichaelHouse Jul 10 '12 at 18:37
• If I were to just run through them all using a for loop it would obviously be instant. However in order to not update everything in one pass (as a for loop would) I'm instead using a variable creepNumber which I increment each pass when the last creep[creepNumber] is finished updating. I'll edit my first post to put the code in to show what I'm doing and why it's horribly inefficient (I just can't get my head around another way). – GamersIncoming Jul 10 '12 at 18:47
• @GamersIncoming "What would be the quickest way to completely ignore creeps that are inactive?" you ask? Spatial Partitioning. – chaosTechnician Jul 10 '12 at 22:39