I didn’t really mean to do another Tetris post this soon, but circumstances have occasioned it. This will be of little interest to anyone not involved in Nullpomino‘s development.

The Dilemma

As described by Zircean, there was an effort to create a game engine for Nullpomino 8 that was based on milliseconds rather than frames. This effort was abandoned, since the team determined that what they had was essentially the same as a frame-based approach. Zircean wrote a blog post about why frames were the superior method, and after discussing it with him at length over IRC, I came to the conclusion that the previous effort was off target, and further that a time-based approach can work and could be  desirable. I’d like to note here that I somewhat prefer the frame approach myself, but this is entirely a matter of subjective judgement and not of capability or difficulty of implementation. I hope to describe here the advantages of, and techniques behind, implementing a time-based approach.

The “Millisecond” Engine Is Actually “Event Based”

When I said the previous effort was off-target above, this is what I meant. The idea was to make an engine that processed the game using milliseconds as a unit rather than frames (1/60th of a second). They ran into trouble when they tried to use time as the base unit, but process inputs as if they were processing frames. This resulted in various dilemmas that were unresolvable without using the same solutions as in the frame engine, and this then led to the (mistaken) conclusion that a “millisecond” engine was essentially the same as a frame engine.

Rethink the Process

The trouble with all that is that it was premised on the wrong idea of how the engine ought to work. If we step back a moment and think about it, what we want from the engine is quite simple. We want to receive a specific input sequence and output the exact same results every time. Thinking about the “processing order” of rotations versus shifts and so on is not only overcomplicating things, but it is unnecessary. Since we are basing the engine on events in time, all the information we need is right there where we can use it: in the timer. From here on in, I’m going to refer to the “millisecond” engine concept as event-based, since that’s what it properly should be.

The key insight to be had is that it doesn’t matter how many spaces a piece moves during one processing unit, or when it does what and how. We have, in the timestamps, all the information necessary to reproduce an input sequence no matter which actual inputs get calculated in what groupings. All we want to do every time we update the gamestate is make the gamestate what it should be at this particular moment in time. By disregarding the idea of how many inputs happen per update—or how many updates happen per input—we can arrive at a solution.

How to Make Event-based Tetris Work

There are a number of things we want to be able to do, all traditionally based on frame counts, which we must convert into time. The first thing we need to do is simply timestamp all the inputs. Using a high resolution timer should give us plenty of fine-grained data to work with. Simple subtraction can give us durations. The timestamps themselves can give us the ordering of the inputs. Simple!

Take delayed auto-shift (DAS), for example. In Tetris, when you press and hold a key, there is a delay. After that delay expires, the piece moves at a specific rate (auto repeat rate – ARR). This might be expressed in frames as 8 DAS / 1 ARR for a delay of 8 frames and a repeat rate of 1 shift per frame. Since frames directly translate to time, we can equate this to 133 1/3 milliseconds of DAS and one shift per 16 2/3 milliseconds. Normally, when the system is running fast enough, we would then update the game state once every time it is necessary: once when the key is pressed, and once every time the piece auto-shifts. If something causes a system slowdown, however, we have a problem. What if the piece should have moved twice in the amount of time between two updates?

Well, there’s always division. During the update, we know how long it has been since the last update was triggered. We can divide this by the repeat rate and know exactly how many spaces the piece should have moved. Then we put it there and we’re done. This means the game always runs in realtime, even if something keeps it from updating the screen at full speed.

What if something else happens during that time? Well, that’s fairly easily dealt with as well. I started simple but it gets a little more complicated. What we really have to do is go over the “timeline” of the input sequence in order for the amount of time that passed between the last update and this update. If, say, a player rotates the piece while it is auto-repeating, that will be reflected in the timestamp. Rather than calculate directly where the piece should be, we must follow the sequence in time—shift, rotate, shift—to generate the correct output. That’s not really very hard, but it does mean we can’t use the nice nifty math trick.

One option, here, is to have something throw out shift events into the input sequence. This enables us to process the input without any special case stuff. I like this method. In fact, it coincides nicely with separating the input receiver from the actual game logic. Since our desire is to timestamp the inputs as accurately as possible, we might go so far as to have the input handler run in a separate thread, so that slow processing of game logic or blocking function calls or whatever may be don’t interfere with our ability to timestamp the input sequence as accurately as possible. In such a paradigm, it would be fairly easy to have the input receiver then be in charge of keeping track of DAS and ARR timings and sending out shifts into the engine as appropriate.

But What About Synchros?

(A synchro is when two inputs are given within the same frame, relying on the order of the game engine’s processing of inputs to achieve a result that otherwise couldn’t be achieved.)

Well, there’s a simple solution to that, too. You decide that any keys pressed within a specific duration of time after another key are “pressed at the same time” and process accordingly. Here is where your order of operations comes in, but that’s just fine. There needs to be an order of operations, and there is already a standard to that. It doesn’t make the fundamental system not work.

Sychros actually become easier since they begin precisely at the time of the first keypress, rather than being grouped by frame timings. And the synchro delay becomes customizable, and could therefore be used as a tuning setting similar to how DAS currently is. It’s worth noting that for this to work right, you must know whether or not any other keys were pressed during the synchro’s time window. This means that engine updates must happen that much after an input is given, creating an input lag. If you don’t care about synchros, you could reduce that to 0 and have a game that’s just that much more responsive. Or, if you wanted to practice or play around with them, you could increase it to something you can perform consistently at the cost of the added delay.

You Can’t Reproduce TGM Like That

True. But the last section leads right into this one. When you think about it, you will realize that the synchro delay is basically creating a frame. In the usage described above, the frames can have a variable duration, and they don’t have to come back-to-back or at any particular rate. But they could. All you have to do to create a frame-based engine out of this event-based system is to force the synchro delay to always be active at the desired rate. If one were to specify the synchro delay not as an offset but an absolute time, then one could force the engine to run exactly in realtime as well. This would not make the previous usage any more complicated – it just means that rather than say “update the engine in 16ms” you say “update the engine at this specific time”.  This is basically a logical distinction, since that’s how you’d program it anyway.

So, at the end of each update, when you are running in frame-mode, you simply schedule another update for when it Should Have Been. This may make some updates faster or slower than others by miniscule amounts, but that’s what we want in this case – a game that runs at a 1:1 rate with real time and responds to the inputs as though they were accurately entered in said realtime.

There is a corner case presented here, however. What happens if you manage to record two frames’ worth of inputs between one update and the next? In our event-based system, we would simply calculate the sequence in order and produce the result of where the piece Should Be right now. But it is remotely, minutely possible that there should exist a particular grouping of those inputs – some in one pseudo-frame and some in the other. Fortunately, timestamps offer us a simple solution to that situation as well. We can either call the update twice, with different time offsets, or we can ensure that our update code knows when to utilize this ‘chunking’ behavior. The timestamps give us the information we need to arrange the inputs in their proper places.

Instant DAS

A concept that exists in fan games but not really in Official Tetris Games, instant DAS therefore has no real authoritative method of operation. The idea is that the piece moves as far as possible in a single frame when auto-repeating. In Nullpomino 7, this is handled in a logical but unnatural way: each shift between “here” and “there” is processed as if it was a separate frame. This essentially speeds up time – a piece will fall farther than it should have in the same amount of time, because gravity is calculated each time it moves, and it’s moving at an “infinite” rate.

This behavior was chosen for a reason, of course. TGM is all about restricting your possible moves and knowing what you can use and when. If this behavior wasn’t implemented, certain exploits would be possible – such as moving a piece over a hole it should not have been able to cross.

There is no helping that no matter how instant DAS is implemented, it is an exception to the normal rules of how the game should operate. So-called “frame compression” is a fairly elegant solution, if you ignore all the components of processing a frame that must be ignored for it to behave reasonably. It may be that with better structuring, that problem becomes less, but it can’t be ignored that no matter how you do it, it’s a special case—therefore, it can be said that one special case is not really any better or worse than any other. This leads into how instant DAS must be handled in an event-based model.

Instead of repeating a frame but ignoring certain aspects, what you have to do instead is repeat an input sequence and add certain aspects (such as gravity) to that processing. One is pretty much the inverse of the other. I don’t believe either is likely to be better or worse than the other.

That’s a Bunch of Words

Well, yeah. I tried to cover all the bases, and I expect I missed some things. I hope I’ve managed to describe how an event-based model could work just fine for a Tetris game, why it’s no more difficult than a frame-based game, and how the characteristics of frame-based games that people might care about can be reproduced in an event-based model.

Why Should We Do It Like That, Though?

Efficiency. That’s really all there is to it. The fewer updates you perform, the less CPU you use. The less CPU you use, the better. By only updating the display as necessary, you might only need to render 2-10 screen updates per second rather than 60. Consider large multiplayer games and the benefit becomes even greater. Not having a CPU-burning game loop is nice, too. Allowing programs in the background time to run will help keep them from interrupting the game when it really does need the clock cycles. And finally, it can enable a tighter, more responsive play interface. I can’t say that anyone would be able to discern 1-frame differences between one paradigm and the other, but we can certainly all “feel” when a game seems more or less responsive. By reacting exactly when you input a sequence, we can remove just another little bit of interference and get just a little bit closer to the ideal. And for all that, it doesn’t really cost us anything except thinking a bit differently.

Other Notes

Since the idea is to update the game screen as infrequently as possible, it could be beneficial to separate things like timers, status displays, meters, and so on from the code that updates the actual gamestate and draws the fields. If you don’t do that, then having a constantly-updated countdown timer that runs at a resolution of 1ms would pretty much defeat the entire point. This separation could also go hand-in-hand with a framework for displaying arbitrary items in an arbitrary arrangement on the game screen—which would certainly make changing the interface around or adding new things nice as well. That might be worth some thought.

Post filed under Tetris.

3 Comments

  1. I made an event-based tetris clone ages ago, before nullpo was popular. It basically creates timers when you hold down left/right, and when the timers expire, instant-das occurs. Events are fired everytime the user presses keys to manipulate pieces, and there is an underlying game state model with an encapsulating visual model on top. Due to the fact that it uses (i think) windows timers, the accuracy is up to 16ms (i think there are other timers around that i could plug in to increase accuracy to 1ms)

    Draws are only used when the visual data changes. I.e. when instant dassing, there are 4-5 different states in the hidden model. Also timers/gui are only updated when input is pressed. This saves on draw() calls etc making the game more reliable etc.
    http://users.tpg.com.au/onged/40L.rar

  2. also note that that clone uses software rendering, which is vastly inferior to graphics card (opengl etc). It still manages to be lightweight yet play smoothly.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>