HOME WORLD FORUMS WIKI VIDEOS
9580 members and stacking!
     Welcome guest, please login or sign up

2 Pages V  1 2 >  
Reply to this topicStart new topic
> Event based tetris discussion
XaeL
post Jun 9 2015, 11:32 PM
Post #1


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



Hi everyone that is interested.

This thread is for discussion of a high performance event-based tetris engine.



Ok so basically I did a bit of testing in LWJGL for seeing how well it could handle event based.

The main loop looks something like:
CODE

        while ( true ) {
            if (canBlit) {
                canBlit = false;
            glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); // clear the framebuffer            
            glfwSwapBuffers(window); // swap the color buffers
            }
            // Poll for window events. The key callback above will only be
            // invoked during this call.
            
            glfwWaitEvents();            
            this.frameCounter ++;
        }


glfwWaitEvents basically tells the CPU to sleep until a keyboard/mouse event occurs.
it calls a callback (mousecallback for mouse, keycallback for keyboard).

I did some timing to figure out the accuracy of these.
Using my 1000hz mouse, i found that the timing of the glfwWaitEvents would get called 1000x a second when moving my mouse around.
Using my 1000hz keyboard, i attempted to mash 8 keys at the same time. I recorded both the gameTimer and the frame counter to figure out if inputs were being parsed on the same frame. For some reason, my keyboard would very frequently send inputs on the same frame.

Either:
1) I am very good at timing keys so that they are in the same 1ms (not likely)
2) my keyboard controller (hardware) only updates once every (~16ms+)

CODE

Key | frame number | engine.time()
A 529 2.696237024989901
; 530 2.71755624919359
S 531 2.7362457393152675
K 531 2.736333115572284
L 531 2.7363843763097337
D 532 2.7710721678369747
F 533 2.820519847953663
J 534 2.8465428273267497


Has anyone got a 1000hz keyboard and/or done testing to see if its possible to get millisecond (or close. not like this 20ms difference) separated inputs?


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
simonlc
post Jun 10 2015, 06:17 AM
Post #2


Tetris Apprentice
Group Icon
Posts: 168
Joined: 31-October 12



What is the engine time printing? Time in milliseconds?

I tried real fast in JS and seemed to get 60 updates per second with the built in mousemove event handler. I'm not really sure how to accurately test a keyboard however.

CODE
var hertzCount = 0;
var hertzCountStart;
document.addEventListener('mousemove', function(event) {
  hertzCount++;
  if (!hertzCountStart) {
    hertzCountStart = performance.now();
  }
  if (performance.now() - hertzCountStart >= 1000) {
    console.log(hertzCount);
    hertzCount = 0;
    hertzCountStart = 0;
  }
});


With the keyboard test, the fastest loop I can make in JS is 250hz, which seemed like my keyboard had an update rate that was closer to 1000hz (maybe truely even driven because I could get multiple keypresses closer than 1ms apart) using the built in event handler, which meant it was faster than any loop I could make.

Although right now I really feel like it's all magic how it works and I wouldn't take the 1000hz keyboard claim as fact for JS yet.

While the mouse test doesn't mean much for tetris, it seems that js can handle a higher input rate than 60hz for keyboards, which is good news. We just need a good way to be able to test this to confirm.
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Jun 10 2015, 06:47 AM
Post #3


Tetris Professional
Group Icon
Posts: 630
Joined: 13-May 15



My post has nothing to do with the posts above. It's related to event-based Tetris though.

One advantage of event-based Tetris is that it knows the order in which you pressed the keys (in contrast to 60 fps frame-based Tetris, for example if you press left 8 ms after drop in NullpoMino, it could happen that it is interpreted as left & drop instead of drop & left). Another advantage should be the atorepeat behaviour (in 60 fps frame-based Tetris, there's a 15 ms range of inaccuracy for DAS; 6 frame DAS can be triggered after 85 ms to 100 ms, depending on the fraction of the first frame the player pressed down the key).

But how does an event-based game know how long you pressed the key? I programmed a Tetris game in Java and ended up using javax.swing.Timer. When I put repeat delay (DAS) to 80 ms, it felt the same as 90 ms. I verified this suspicion by triggering a timer 1000 times in a row and counting the needed time (with System.currentTimeMillis): It was the same time for 80 ms timers and 90 ms timers. More precisely, the timer is polled every 15.625 ms. So at the end, the player can't use arbitrary repeat delays (the same problem exists in 60 fps frame-based Tetris, where players can only use whole integers to specify DAS).

So here comes my question: Are there more accurate timers around? This question is open for all programming languages (c++, javascript), but I am most interested in Java (since I can only program in Java).
User is offlinePM
Go to the top of the page
+Quote Post
XaeL
post Jun 10 2015, 07:39 AM
Post #4


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



QUOTE(simonlc @ Jun 10 2015, 06:17 AM) *

What is the engine time printing? Time in milliseconds?

Engine time is basically sys.getTime. But its not "right" because time flows while code is executing. The troubling thing was getting two keyboard events on the same glfwWaitEvents() which shouldn't be possible assuming "infinite" speed.



QUOTE

With the keyboard test, the fastest loop I can make in JS is 250hz, which seemed like my keyboard had an update rate that was closer to 1000hz (maybe truely even driven because I could get multiple keypresses closer than 1ms apart) using the built in event handler, which meant it was faster than any loop I could make.

Unfortunately we don't know what javascript is doing under the hood. e.g. say it polls at 20hz and then the "time" that it gives for each event is just sys.time when it pulls it from it's internal polling queue. This could give times that are <1ms apart but in reality actually polled every 20hz.

The same thing is definitely true from my lwjgl test - the "engine time" was basically a time i assigned when i pulled it out of the queue, however the "framecount" was when the poll "found" the keypress.


QUOTE

While the mouse test doesn't mean much for tetris, it seems that js can handle a higher input rate than 60hz for keyboards, which is good news. We just need a good way to be able to test this to confirm.

My mouse test showed it could support 1000hz+ but my keyboard test wasn't very promising. Not sure if it's because LWJGL has different ways of polling input from the OS based on keyboard/mouse.

We need a way to test keyboard polling rate accuracy. Also need a way to get a 1000hz keyboard. Mine is advertised as 1000hz but who knows...


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
XaeL
post Jun 10 2015, 09:07 AM
Post #5


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



QUOTE(Okey_Dokey @ Jun 10 2015, 06:47 AM) *

javax.swing.Timer.

Java's timerTask is shit. I got around this by separating the Draw() and UpdateLogic(). That way your logic can run at 2000hz (hence you can use system.nanoTime()) and in ur updateLogic you can just decrement time remaining. This allows you to consistently get non-multiples of 16ms for das. Of course what's drawn on screen won't match nicely if you have a 60hz monitor, but I have a CRT running at 100hz and could get das in 10ms intervals. The problem i'm dealing with now is that keyboard polling isn't consistent enough - so the das timer is fixed at say 80ms but the time that the game registers your key could be out by some unknown value as of yet.


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
XaeL
post Jun 10 2015, 09:10 AM
Post #6


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



I just tried with a PS/2 keyboard.

Works as it should - i press 8 keys simultaneously and they all show up at different times. However this might be another problem - i'm fairly certain i'm pressing all 8 keys in a <20ms window however the time that it receives the events is over 50ms~.


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
XaeL
post Jun 11 2015, 05:40 AM
Post #7


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



More research:

Windows default timer is 16ms intervals. That means if you call sleep, it will sleep for 16ms. To change this, you can use this tool:
http://vvvv.org/contribution/windows-system-timer-tool

This means sleep(1ms) will actually be 1ms instead of rounding up to 16ms.

This is also important for events - since they will fire on multiples of 16ms instead of as fast as possible.


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
Okey_Dokey
post Jun 11 2015, 06:06 AM
Post #8


Tetris Professional
Group Icon
Posts: 630
Joined: 13-May 15



I started writing this post before I saw Xael's post above.

Regarding my issue with timers: I did some further research, but no progress so far. I learned that on Windows systems, threads wake up every 15.625 ms, maybe every 10 ms on old 1 processor machines. I also learned that there's a function called timeBeginPeriod() in Winmm.dll, that can reduce that time. I did that, but still the same issue. I was definitely able to access that function in Java, because when I used System.out.println each time the counter increased in my repetition loop, the 1000 times 1 ms timer was executed faster than 15 seconds. But if I stopped logging, I got the same times as before. I also checked the timer classes java.util.timer and java.util.concurrent.ScheduledExecutorService, same issue here. I also checked the default keypress classes. Keys were only pressed and released every 15.625 seconds (when I tried to press down 3 keys simultaneously, they were within 0 ms or with a gap of 15 ms). So at the end, my game has the same autorepeat problem as 60 fps frame-based games (autorepeat is executed with a 15 ms range of inaccuracy, no arbitrary delay values can be used), with the difference that it is practically a 64 fps game (in the update logic). Note that I majorly use Windows XP, perhaps ScheduledExecutorService shows better performance at newer Windows systems.

QUOTE(XaeL @ Jun 10 2015, 09:07 AM) *

Java's timerTask is shit. I got around this by separating the Draw() and UpdateLogic(). That way your logic can run at 2000hz (hence you can use system.nanoTime()) and in ur updateLogic you can just decrement time remaining. This allows you to consistently get non-multiples of 16ms for das.

Did you use Java? Which thread function did you use? How do you tell your thread to sleep that it doesn't sleep for a too long time? Could you post more of your code (including LWJGL embedding)?
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Jun 11 2015, 11:03 PM
Post #9


Tetris Grand Master
Group Icon
Posts: 1,932
Joined: 26-June 09



I'm going to move my post from the other thread here. Some context may be confusing.

QUOTE(XaeL @ Jun 9 2015, 01:53 AM) *

QUOTE(myndzi @ Jun 8 2015, 08:25 PM) *

Javascript

Does javascript have an efficient/fast graphics/input library? Just wondering since we want maximal performance.

I'm thinking of writing a simple one in Unity3D. Wouldn't be too hard.

Also, seems like a lot of libraries die at > 1000fps lol. (just had quick look at unity)


The kind of "performance" gains you'd be making by a "fast/efficient graphics library" aren't really relevant to the discussion of event-based input. It's Tetris. Pretty much anything is fast enough. What matters is how you deal with inputs and so on.

I have a lot of code written for performing lots of efficient Tetris operations, for example minimal shift testing and minimal screen updating, along with a 1d array matrix representation for these things to operate within (which eliminates those double x-y loops and makes pretty much *everything* much simpler). I tried this once before and basically made gains of a factor of 10 between my original hack-up of a js tetris engine, to my first write, to my latest code, in terms of how fast the code can calculate piece movement and such.

It doesn't really matter if you can DAS a piece back and forth 1000 times a second or 100,000 times a second, though, since you're only gonna do it like 5ish times a second (if you're MicroBlizz, anyway).

Same kind of thing applies to the graphics work. You can hammer it down, but it's largely pointless, as long as you're not being extremely wasteful. (Rendering the full frame 60 times a second when it only changes a few times a second can be seen as extremely wasteful...) I plan to hammer it down anyway, because I want to... but then, that sort of code is more complex, and therefore both fewer people are capable of writing it and the people who can have more work before them. The constraints I've placed on writing my Tetris engine have put me in the position I'm in now, where I'm just procrastinating to the extreme.

Canvas is plenty fast (especially in IE), Javascript is plenty good, and all you have to do is keep your calculation and garbage generation down so that everything can run in frame rendering intervals.

Good points are raised in this thread and other threads about what these things mean effectively for the amount of responsiveness you can get out of the game, but my goal isn't picosecond accuracy, it's a browser Tetris engine that is fast and responsive. I daresay that with all the optimizations that can be brought to bear, such a Javascript Tetris engine would be the most responsive thing you guys have ever played even with the caveats that exist; just see the reactions to the JS clones that have already been shared on these forums, and none of those have taken things to the extreme.

To summarize, you wouldn't use any special libraries for JS Tetris, you would probably be limited by browser rendering rates, which may differ between browsers, but it probably won't matter to any but the fastest players -- and that last 16ms is embedded DEEP into operating systems, browsers, and the like, making it hard to do anything about. You'd probably need a native binary running its own event loop, and that would peg your CPU because you wouldn't be able to give up cycles to the OS for fear of losing that 1-15ms.

Edit: For what it's worth, I get about 7-8ms differences for simultaneous keypresses in the latest Chrome. I've got plenty of sub-1ms responses in Firefox and Internet Explorer.

This leads me to believe that, even if you can only render frames at 60fps-ish, you can *calculate inputs* at pretty much any precision necessary, which should be more than enough to gain the benefits of event-based inputs as far as reliability in DAS timing and so on.

Double edit: I was deceiving myself; by using XaeL's "press lots of keys at once" approach, I'm only measuring the time between events firing; events fired in the same tick will differ slightly but that's meaningless in terms of resolution of events. If you, instead, measure the difference between a keydown and a keyup, you'll find it extremely hard to get a time below 32ish milliseconds, and if you do it'll be immediately down near 15, confirming the fact that these browsers do in fact behave like all other Windows programs and, as expected, will effectively lock you to the ~60fps input range.

I can't find my usb<->ps2 adapter at the moment to test that, but you can experiment with the code; just paste this into a browser console (hit f12):

CODE
var last = { }; window.addEventListener('keydown', function (ev) { last[ev.keyCode] = performance.now(); }); window.addEventListener('keyup', function (ev) { console.log(performance.now() - last[ev.keyCode]); });


Then click in the main window and press whatever you like. It will log differences between keydown and keyup by the key. If you can get an unusual number like 23 to show up frequently, that result would be heartening.

Don't be deceived, though: you can still get numbers in that range for other reasons; I got a few but at the rate of like one per 30-50 measurements.

Edit3: Fuck this got long. Timer accuracy is a problem in Firefox; I measured the delay between timer functions firing on FF, Chrome, and IE. Firefox got spikes of around 50ms for a 7ms timer in every run of 5. Chrome is rock fucking solid, and IE isn't too bad but still varies up to 16ms. It's possible that optimization would smooth some of this out. Since the accuracy of a timer firing is directly related to the accuracy of DAS, though, things don't look good for our friend the Fox. Some compensation is possible, however: as long as ordering of event sequences is preserved, a temporary delay like this doesn't really affect the whole. From the player's perspective, if he truly did hold the key for the correct amount of time, then the timestamps will show it up, DAS will happen, piece will get dropped after, etc.

Timer code:

CODE
var n = 5, m = performance.now(); (function next() { console.log(performance.now()-m); if (n-- <= 0) { return; } setTimeout(next, 7); m = performance.now(); })();


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Jun 11 2015, 11:39 PM
Post #10


Tetris Grand Master
Group Icon
Posts: 1,932
Joined: 26-June 09



I think it's worth taking a step back and identifying the desired behaviors.

1) When a key is pressed, the piece is observed to move on the screen in as short a time as possible
2) When a key is held, DAS should be seen to take effect as close to the DAS delay after the keypress as possible
3) When a key is held and released, DAS should have taken effect if the difference in time between the hold and release is >= the DAS interval; this is to say, DAS should happen when expected and not happen when not expected
4) If not using instant DAS, the distance the piece has moved should be calculable from the difference in press + release timestamps. Here is another place where using a timer to "stop DAS movement" can cause a piece to be moved too far.

No player fast enough for this stuff to matter is reacting to what they see on the screen, though they might be taken aback/interrupted if what they see does not agree with what they expected. For this reason, #3 is the most important of these items, in my opinion. Depending on implementation, #3 can be somewhat widely variable, and timestamps are the most accurate means of determining duration of keydown. If this is accounted for, I'd say that's about all that can be done for the browser/JS case, and probably many other cases besides.


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
XaeL
post Jun 12 2015, 01:31 AM
Post #11


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



myndzi how do you run javascript code? i tried copy pasting and shoving it in a .html file and opening it but that doesnt work.

In terms of Timer accuracy, if you are using windows it is because windows has a fucked up timer - ti's accuracy can be set by programs and it uses the highest requested accuracy. Chrome sets it to 1ms, firefox is lazy and sets it to 15.6:
run this test to see:
http://www.belshe.com/test/sort/sort.html

To change windows requested accuracy, use this:
http://vvvv.org/contribution/windows-system-timer-tool

Yes, i have been testing keydown+keyup: i can't get anything below 40 consistently, but I am able to get numbers that are multiples of 1ms e.g. (53, 54, 55, 56, 42, 48) . I'll post my results later today (10~ hours from now). The other problem is that keydown+keyup is frequently on the order of 50-60ms, making DAS < 3/60 impossible to use.

EDIT: Here's my output from my test program. I just pressed a key and released it as fast as possible, with a timer displaying the time between keydown and keyup.

https://docs.google.com/spreadsheets/d/1TQi...dit?usp=sharing

The green columns are the key-up times. Seems like it can be fairly accurate. I am using glfwWait which waits until an input is pressed/released. I used glfwPoll (busy-waiting) and i got similar results. My windows timer was 0.5ms but 10ms had similar results.


QUOTE(myndzi @ Jun 11 2015, 11:39 PM) *

Depending on implementation, #3 can be somewhat widely variable, and timestamps are the most accurate means of determining duration of keydown.

Duration is simple for DAS. Assuming we collect the input on the correct time, we just setup a busy-wait or event-based-wait for however many milliseconds. This will be accurate to 0.1ms or even better.

The problem is DETECTION of the keydown and keyup being accurate.

if you detect keydown late, your das timer is fucked. if you detect keyup late, your DAS cancel will be fucked.


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
Simon
post Jun 12 2015, 10:26 PM
Post #12


Tetris Novice
Group Icon
Posts: 11
Joined: 20-March 10



  • LWJGL timestamps all input events for you.
  • Input latency depends on the API, but is generally extremely low.
  • Timer resolution can be set to 1ms under Windows, but there's no reason to use timers in an event-based engine anyway.
  • Timer resolution should not be set to 1ms for energy consumption reasons. Less important for games.
  • Measuring time can be done cycle accurate (ns).
  • Low-speed USB devices communicate events with polling, usually at <100 Hz. That's why you won't get low latency out of an USB keyboard.
  • Redraws happen at most at screen refresh rate. There's no reason to render at above screen refresh rate. You wouldn't see the results quicker.
  • This means you should do DAS at refresh rate (often 60Hz/~15ms), timestamp events (extremely accurately) and do the appropriate calculations at infinite resolution.

That's (almost) what I do in Cultris II. Problem is though, that in practice there are shitty drivers, shitty hardware and shitty configurations that will severely limit what you can achieve.

Cheers,
Simon
User is offlinePM
Go to the top of the page
+Quote Post
XaeL
post Jun 12 2015, 11:25 PM
Post #13


Tetris God
Group Icon
Posts: 2,918
Joined: 30-June 09



QUOTE(Okey_Dokey @ Jun 11 2015, 06:06 AM) *

Did you use Java? Which thread function did you use? How do you tell your thread to sleep that it doesn't sleep for a too long time? Could you post more of your code (including LWJGL embedding)?

Yes, i used java
I did NOT use threads - if you tell it to sleep for even 1ms it might sleep too long, so i just ran it as fast as it will go. This does mean that you are wasting fuckloads of power.


--------------------
IPB Image


QUOTE(Paradox @ Dec 16 2010 @ 05:52 PM)
Like many setups here, it is useful if your opponent doesn't move and you get 4 Ts in a row.
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Jun 13 2015, 12:11 AM
Post #14


Tetris Grand Master
Group Icon
Posts: 1,932
Joined: 26-June 09



QUOTE(XaeL @ Jun 12 2015, 01:31 AM) *

myndzi how do you run javascript code? i tried copy pasting and shoving it in a .html file and opening it but that doesnt work.


I mentioned, but it probably got lost in all that. Hit f12 and click console in whatever browser you're in. There should be an edit line you can type in. You can type code there. It only lasts the duration of the page load.


--------------------
User is offlinePM
Go to the top of the page
+Quote Post
myndzi
post Jun 13 2015, 12:14 AM
Post #15


Tetris Grand Master
Group Icon
Posts: 1,932
Joined: 26-June 09



QUOTE(XaeL @ Jun 12 2015, 01:31 AM) *

Yes, i have been testing keydown+keyup: i can't get anything below 40 consistently, but I am able to get numbers that are multiples of 1ms e.g. (53, 54, 55, 56, 42, 48) . I'll post my results later today (10~ hours from now). The other problem is that keydown+keyup is frequently on the order of 50-60ms, making DAS < 3/60 impossible to use.


Getting those times is not impossible even with a 16ms sync rate; the browser does occasionally do other things, and/or events can get fired while the browser's got the CPU or something. I could get oddball times too, but not nearly as often as the near-multiples of ~16ish. A histogram would probably help. I didn't realize you were talking about Java again

Firefox demonstrates the same behavior as Chrome for me on your link; the top graph is significantly faster.

Yes, the 'detecting the timestamp of the input' is one variable factor; unfortunately it's somewhat out of your hands (lols); fortunately any latency will tend to be about the same, and 16ms of variability is far from the worst thing that could happen.

It's probably fair to say that your game's behavior won't change whether you're using a USB or a PS/2 keyboard; the same steps apply. The only real error within your power to compensate for is lagged timer execution in comparison to keyboard events -- though I suspect if a keyboard event causes the OS to give processing over to the application in question, any relevant timers may fire in that same slice of cpu time(?)



--------------------
User is offlinePM
Go to the top of the page
+Quote Post

2 Pages V  1 2 >
Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 

©2009-2014 Hard Drop Community & Forum
harddrop.com is not sponsored or endorsed by The Tetris Company or its subsidiaries.