Roguelike timing systems.

[Destroid]

Hi, I'm very new to designing roguelikes (and pretty new to gamedev in general) and was hashing out a few ideas, and one of them was the timing system.  In the end I thought a good system to do RL timing would be to have an array store all of your actors, and each engine tick step through the array to see if any actor is ready to act.  Readyness will be measured by a cooldown timer (or timers) that when they reach 0, the actor may take an action, filling it's cooldown back up again to an appropriate amount.

Then at one stage I looked over the time system section at roguebasin, and reading the systems there left me more confused than enlightened.  They talk about ordered queues and the like, but I really don't understand the benefits of having such a thing, versus (what I perceive to be) the simpler system outlined above.  Is there something I'm missing?  Is my system a variant on a standard but I'm just not getting it?  Or is there a good reason to re-order actors, or use a queue?

[Darren Grey]

Either method is fine.  The queue thing can be faster on the CPU (not a worry) and maybe has design advantages, but it's probably better to stick to something that you understand.

[Omnomnom]

The benefit of a queue is you can jump efficiently to the actor whose turn is next, you don't have to scan through all the actors and find the one with the lowest cooldown. But I suspect the performance difference is irrelevant on modern computers unless you plan on having thousands of actors.

I went with a queue and I regret it now because it took so long to implement and it just makes things more complicated.  If I was starting again I would go with the array approach and only switch to a queue IF the array approach wasn't performing. I am betting the array approach will be fast enough. I suspect the processing of the actors actions takes a lot more processing time than working out who acts next anyway.

[Destroid]

Great to know, thanks!

[Z]

Suppose you have 1000 monsters (like in ADOM's animated forest), each of them roughly as fast as you (one move per game second), but with a different time offset (the first move of monster number i is at i game milliseconds). If on each game millisecond you are looking for the monster which moves next, you will compare 1000 monsters per game millisecond, which is 1000000 compare operations per each game second. If you are, say, resting for 500 turns, then it will take 500 million operations, which will take roughly a second of real time (depending on the computer and programming language).

Now, the RogueBasin article is misleading. It suggests that you keep the list of actors ordered by time, instead of an unordered one. As you have noticed, there is no obvious benefit in this approach (although it takes 1 operation to find the next actor, it may take 1000 operations to move the actor to its correct position after updating their time, and the two balance each other).

On the other hand, there are effective implementations of priority queue, where the actors form a tree-like structure (instead of an ordered list), and it takes 1 operation to find the next actor, and only ~20 operations to move the moved actor to the right position. Thus, you perform roughly 20 operations on average, instead of 1000. Thus, the number of operations for 500 turns will drop down to (roughly) 10 millions, which will be executed instantly.

As you can probably see, in most cases the simplest approach is sufficient. It is not a problem to have resting take 1 second of real time in extreme circumstances.

[Destroid]

Could this become an issue if you are working in a slower language like python?

[Z]

I expect it to be fast enough in Python... I am not sure.

Which means that you should do as Omnomnom says. Try the simplest possible way. Only when the game starts running too slowly, you should use some kind of profiiling (or intuition) to determine the part which causes problems, and optimize it.

[kraflab]

A binary heap is really simple to implement.  I think I have it as about 50 lines of code.  You just need to know how to insert and how to remove.  It's probably not as hard as you think and since it is a standard you can look at probably tons of examples.  The thing is that a binary heap is the fast option in other parts of your code.  Another place I use it is in the a* pathinding, because a bin heap is faster than other options, such as a list and whatnot.  As Z said, it probably won't make a significant difference in most cases, but if you come from a programming background or are confidant in your ability to learn I would suggest you implement it because why not?

[Snargleplax]

It's hard to imagine actually needing to implement a heap.  Standard libraries for pretty much any language will provide one, almost certainly superior in quality to any handroll.  And yes, I agree it's best to go this route and not shy away from concepts just because they may be new to you.  A heap is a useful abstraction; embracing it will simplify your program (and your reasoning about it) in the long run.

[guest509]

  When I did Sun Crusher I made all objects 'pause' until after the player had taken their turn, then they all were allowed to move. They would then 'pause' again once they'd moved (terrain moved, space stations just fired shots).

 I couldn't figure out how to check that everything had moved, so I just let the player move again after like 1.5 seconds of real time...surely all the objects on the screen had finished by then, right? Wrong. Sometimes enemy shots fired would still be flying, so if the player were quick enough he could dodge them.

  The work around for this was really embarrassing. Every time a bullet object was created it reset a global timer. I figured out the max flight time from one end of the screen to the other, and set the timer to that. The player was paused until that timer went off....So several dozen bullets are firing, resetting a timer over and over...grah!

  There were more completely stupid and noobish work arounds, but I learned a lot, and the game was sort of unique. So it was a success. Just please never ask for the source. Ever.

  I'll never do it like that again. :-)

[requerent]

It's hard to imagine actually needing to implement a heap.  Standard libraries for pretty much any language will provide one, almost certainly superior in quality to any handroll.  And yes, I agree it's best to go this route and not shy away from concepts just because they may be new to you.  A heap is a useful abstraction; embracing it will simplify your program (and your reasoning about it) in the long run.

+1.

The actual usage of advanced data structures, particularly in java, are abstracted among a set of collection classes. They're all convertible between one another and use almost the exact same syntax. I think python does something similar. When at all possible, use standard libraries!



As for the timing- From a conceptual point of view, it might be better to implement equitable discrete timing. That is, all actions take 1 turn and every monster (and player) takes 1 turn.

Then you just take 1 turn for the player, iterate through your monsters and give them each a turn to do something, then poll the player for an action. If you REALLY want 'haste' or 'slow' or timing effects, you can apply that in the update function of a given entity-- add an extra update call or skip every other update call respectively. Missiles can similarly be simplified by describing how many tiles they cover per turn.

Additionally... you can just run updates for each monster and log each tile that is interacted with- you can easily track collisions (esp if you store positions prior to update) in a computationally minimal way.




Some people like to get into physical simulations and initiative timings and what not, but you really don't need to mess with that. The player will rarely experience the work you put into that. A turn-based game, strictly speaking, doesn't ever need to use the timer in the logic component of a game-loop.

Bind your game logic to the User-Interface. What information is relevant in the UI is all the player should care about. Similarly, it's all the coder should bother implementing. If your work doesn't reflect onto the UI in a way that informs the player to make decisions, then whatever you're doing is irrelevant.

[Destroid]

In my case, the design calls for more sophisticated timing rules than you usually see in a roguelike, with highly variable amounts of time passing per action (dependant on conditions) and multiple independent cooloffs per actor, to separate out the attack and movement steps (and possibly others, but starting small here!).  At the moment I am working on other projects in Actionscript 3, but I wouldn't be shy about learning a different language, although I am by now means an advanced programmer.

[requerent]

In my case, the design calls for more sophisticated timing rules than you usually see in a roguelike, with highly variable amounts of time passing per action (dependant on conditions) and multiple independent cooloffs per actor, to separate out the attack and movement steps (and possibly others, but starting small here!).  At the moment I am working on other projects in Actionscript 3, but I wouldn't be shy about learning a different language, although I am by now means an advanced programmer.

AS is awesome- does a lot of work for you, but I'd recommend learning HaXe NME. It's the same syntax as AS only better in every way. They've wrapped the Flash API such that it can target multiple platforms. It's easy and accessible and more powerful- do it. www.haxenme.org.


Why the need for complex timing? How much of a role does it actually play relative to the end user as per your design?

[guest509]

  What? No lols for my complete mess of a timing system? 

[Destroid]

AS is awesome- does a lot of work for you, but I'd recommend learning HaXe NME. It's the same syntax as AS only better in every way. They've wrapped the Flash API such that it can target multiple platforms. It's easy and accessible and more powerful- do it. www.haxenme.org.


Why the need for complex timing? How much of a role does it actually play relative to the end user as per your design?

Pretty central, I'm modelling momentum, while retaining single square movement. This requires variable time.  The player will be interacting directly with this system.


And Jo, that really does sound like a mess