Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (113)
games submitted by our members
Games in WIP (562)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  An efficient discrete step timing loop.  (Read 7506 times)
0 Members and 1 Guest are viewing this topic.
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Posted 2003-07-15 17:19:08 »

I'm going to try to explain a timing loop I've used in pretty much all my recent games.
It lets you have discrete time steps for game logics, and still works with high FPS.

There are two kinds of "ticks", or pulses that are sent through the system: gameticks and clientticks.
Gameticks are sent at a regular interval, and clientticks are sent as often as possible.

First we define how often we want the gameticks, and a very useful derived value
1  
2  
private static final int GAMETICKS_PER_SECOND = 25;
private static final int MILLISECONDS_PER_GAMETICK = 1000 / GAMETICKS_PER_SECOND;

(This can also be done in the constructor if you dislike hardcoded stuff)

Then we build the run method that calls gameTick() and clientTick()

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
long previousTime = timer.getTimeInMillis();
long passedTime = 0;
while (keepGoing)
{
  clientTick();

  long time = timer.getTimeInMillis;
  passedTime += (time-previousTime);
  previousTime = time;
   
  while (passedTime>MILLISECONDS_PER_GAMETICK)
  {
    gameTick();
    passedTime-=MILLISECONDS_PER_GAMETICK;
  }
}


The basic idea is to call clientTick() while there is less "unprocessed time" in passedTime than MILLISECONDS_PER_GAMETICK, then call gameTick() until passedTime is lower than MILLISECONDS_PER_GAMETICK again.

This ensures that gameTick() will be called exactly GAMETICKS_PER_SECOND times per seconds on average, and that clientTick() will be called as often as possible.


(more to come)

Play Minecraft!
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #1 - Posted 2003-07-15 17:32:52 »

gameTick() should manage all physics and other things that should happen at a fixed speed.
clientTick() should handle all the other things that should happen as often as possible, like rendering and sound updating.
I tend to put all networking in gameTick() as well.


If we just let the system be as it is now, we'd get lots of fps, but the camera position would only update 25 times per second, so it wouldn't really work.
To fix this, we interpolate the values in clientTick().
That means that clientTick() will need to know how far along the we are between two gameTicks(), and all previous values for the values that should be interpolated.

To interpolate values, I use a small class called IFloat:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
public class IFloat
{
      private float last;
      private float value;
     
      public IFloat()
      {
            this(0);
      }
     
      public IFloat(float newValue)
      {
            last = newValue;
            value = newValue;
      }
     
      public void setValue(float newValue)
      {
            last = value;
            value = newValue;
      }
     
      public float getValue(float interpolation)
      {
            return (value-last)*interpolation+last;
      }
}


We also need to change the definition of clientTick() to clientTick(float interpolation).
To calculate the interpolation in the main loop, we just have to divide the "unprocessed time" by MILLISECONDS_PER_GAMETICK.

So the new main loop looks like this:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
long previousTime = timer.getTimeInMillis(); 
long passedTime = 0;
while (keepGoing)
{
  float interpolation = passedTime/(float)MILLISECONDS_PER_GAMETICK;
  clientTick(interpolation);
 
  long time = timer.getTimeInMillis;
  passedTime += (time-previousTime);
  previousTime = time;
   
  while (passedTime>MILLISECONDS_PER_GAMETICK)
  {
    gameTick();
    passedTime-=MILLISECONDS_PER_GAMETICK;
  }
}


Play Minecraft!
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #2 - Posted 2003-07-15 17:40:56 »

J3d and LWJGL comes with good timers, but for other things you're going to have find a third party timer if you want it to work on Windows.

I like AdvancedTimer from GAGE.


Advantages:
Very solid code. The game will behave exactly the same regardless of what FPS you're getting.

Disadvantages:
Because of the interpolation, you'll always have a "latency" of at least MILLISECONDS_PER_GAMETICK ms, plus whatever mouse/network/videocard latency you have.

Play Minecraft!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline nickdotjava

Junior Member




I have fallen to the dark side.  I'm using DX9


« Reply #3 - Posted 2003-07-23 14:04:40 »

my question is when is IFloat used.

Another question is why gameTick (happens every so many milliseconds) is called in an inner while loop, and clientTick(interpolation) is called on the outside.  And what is the interpolation used for in clientTick?

Thanks.

-Nick

Edit:  I think I may understand it.  It only goes into the nested while if so many milliseconds has passed, right?  And if this is correct, couldn't it be replaced by an if statement?

-Nick

"Oh ya, that's trivial.  I should have it done in an hour."
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #4 - Posted 2003-07-23 16:34:10 »

It has to be a while loop in case clientTick() ever takes longer than MILLISECONDS_PER_GAMETICK.
Like if your game suddenly pauses for 10 seconds, and you've got 10 ticks per second.. The while loop would "catch up" by running the gamelogic tick 100 times, but the if statement would lag behind for a long time.


IFloat is a class that interpolates between two floats.
Most of the time, clientTick() will get called far more often than gameTick() gets called, so we have to interpolate between the values the last call to gameTick() produced, and the ones before that.

An example:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
IFloat xPlayerPos = new IFloat(0);

public void clientTick(float interpolation)
{
  renderPlayerAt(xPlayerPos.getValue(interpolation));
}

public void gameTick()
{
  float xPos = xPlayerPos.getValue(1);
  xPos+=1;
  xPlayerPos.setValue(xPos);
}


Now if gameTick() gets called once every second, the player would move exactly one "unit" per second, but clientTick() would still make the motion smooth.

Play Minecraft!
Offline nickdotjava

Junior Member




I have fallen to the dark side.  I'm using DX9


« Reply #5 - Posted 2003-07-29 19:21:30 »

I've been testing it out, and it works beautifully in my experiments.

-Nick

"Oh ya, that's trivial.  I should have it done in an hour."
Offline GergisKhan

Junior Member




"C8 H10 N4 O2"


« Reply #6 - Posted 2003-07-29 21:13:02 »

An interesting thought I had, to see if I understand this correctly:

Am I right in saying that you are doing all of this in one thread?  That is to say, there is a clock running in its own thread (GAGE?) and giving you ticks, and you're just reacting at the appropriate times to do rendering and ALSO to do your game management?

What happens on the lower end if your painting is taking too long and not leaving enough time for your management tasks (gameTick() if I'm not mistaken is where you have all that code)?

gK

"Go.  Teach them not to mess with us."
          -- Cao Cao, Dynasty Warriors 3
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #7 - Posted 2003-07-30 06:08:33 »

Yes, it's all in one thread. if clientTick() (the rendering method) takes too long, gameTick() would execute several times in a row to catch up.

I really don't believe in multithreading applications that don't use a lot of blocking methods, as you just end up with a bunch of synchronisation and duplication of data, with no performance gain whatsoever.

Play Minecraft!
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #8 - Posted 2003-07-30 13:33:50 »

Quote
I really don't believe in multithreading applications that don't use a lot of blocking methods, as you just end up with a bunch of synchronisation and duplication of data, with no performance gain whatsoever.


Unless you are running on a multi-processor system, in which case that's exactly when you want to have multiple threads, since it implies that each thread has useful work to do.

Not the norm for games, but I thought I would point it out.

Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #9 - Posted 2003-07-30 13:37:03 »

You still have to synchronize and duplicate all data. You can't have an item move in the middle of the rendering loop. I don't think the gain in cpu power will outweigh the messier code.

Stuff like AI and IO could probably be split off into separate threads with very good results on multiprocessor systems, however.

Play Minecraft!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #10 - Posted 2003-07-31 13:46:56 »

Yes, AI is something I think can benefit from multi-threading and multiple processors.  Chess being one example, but taken further it might become practical at some point to train a neural net with a background thread so your game AI adapts to the users playing style.   I don't think we are at that point yet though.

Offline Jeff

JGO Coder




Got any cats?


« Reply #11 - Posted 2003-08-09 04:48:35 »

Hmm.  Outside of the fact that I called it "animate" and "render"  this looks a whoe lot like my loop for Scroller Smiley

or am I missing something?


Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #12 - Posted 2003-08-09 06:11:17 »

I wouldn't know, I haven't looked at your Scroller.


And the main point isn't that it uses two methods.. It's how the data produced from the math method is used in the render method (that generally gets called a lot more often).

Play Minecraft!
Offline Kommi

Junior Member




All opinions will be lined up and shot!


« Reply #13 - Posted 2003-09-18 16:31:50 »

Markus I have tried your loop and it works well but I do get image stutter every now and then. Anyway to fine tune it? I am guessing that I ma drawing a lot of frams but most of them go to the garbage bin. Is there a way to limit the fps in your loop?

Kommi
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #14 - Posted 2003-09-18 18:33:28 »

[bogus answer, new one coming below]

Play Minecraft!
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #15 - Posted 2003-09-18 18:36:55 »

You can limit the framerate by just adding a Thread.sleep() in the main loop, or if you want to be more scientific you can time the clientTick() call and sleep n-t milliseconds, where t is 1000/<desired fps>, and n is the number of milliseconds the clientTick() call took.

You might want to use your timer's sleep methods if it has one instead of the Thread sleep method, though.

Play Minecraft!
Offline Kommi

Junior Member




All opinions will be lined up and shot!


« Reply #16 - Posted 2003-09-18 20:09:19 »

Do you yourself find this necessary to do in order to prevent image stutter?

Kommi
Offline shawnkendall

Senior Member





« Reply #17 - Posted 2003-09-18 20:55:19 »

Simply interpolating floats will NOT work correctly for Matrices and most 3D rotation representations. If it did, animation systems would be a WHOLE lot easy and cheaper to implement

Which also means it won't work for physics that use those rotation representations. :-(

This technique can still be applied to those systems, but the interpolation must be computed on a type by type basis, it can't be done generally.

Shawn Kendall
Cosmic Interactive, LLC
http://www.facebook.com/BermudaDash
Offline Kommi

Junior Member




All opinions will be lined up and shot!


« Reply #18 - Posted 2003-09-18 22:00:52 »

What would be a better technique for a game loop then? I understand that the best method is probably using real time.

Kommi
Offline shawnkendall

Senior Member





« Reply #19 - Posted 2003-09-19 01:25:43 »

I think the gameTick pattern is fine and good.
I was just pointing out that the 'tween code will need a higher order of "awareness" of the data it needs to interpolate, so as to use the correct process.
Or from another point of view, each data class can implement the 'tween functionality and main loop and game control can simple call interp on everything.

However, in both cases, I think allot of context specific optimizations will be ugly/difficult.  For example, in character animation, the animation data is compressed and decompressed on the fly.  The decompression code typically will accept a time value in an animation as the target for a matrix generate.  Just like other types of media compression, this may be a directional decompress, i.e only forward, and may take as addition feed, previous generate d values.

Anyway the point is, global, timeless (ticked) based control is bound  to have it's pro and cons just as the all-on-one syncronized update does.  Perhaps your particular app would be the deciding factor.

Shawn Kendall
Cosmic Interactive, LLC
http://www.facebook.com/BermudaDash
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #20 - Posted 2003-09-19 05:04:42 »

Quote
Do you yourself find this necessary to do in order to prevent image stutter?


Nope. I think your stuttering is caused by something else.

Play Minecraft!
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #21 - Posted 2003-09-19 05:08:58 »

Quote
Perhaps your particular app would be the deciding factor.


Yes, definitly.
One thing this system handles poorly is something simple as a ball bouncing against a surface. If the actual "bounce" is between two game ticks, the linear interpolation will cause the ball to magically hover above the ground for a full gametick instead of bouncing on the surface.
This could be solved by adding interpolation keyframes, but then we're deep in gc hell.

Play Minecraft!
Offline fooberry

Junior Newbie




Still working on something clever.


« Reply #22 - Posted 2003-10-07 22:15:30 »

Hi,

First post.  Learned a heck of a lot from you guys- thanks.

Question- while testing this game loop, I notice that my fps seem to be limited to the refresh rate of the screen mode I switch into.  Is this a Window's "feature"?

Edit: Hmm- I just found an answer: http://www.xp-refresh.net/

Also- I understand what vertical synch is all about, but I don't yet see how to "do it" with pure Java.  (I do see how to do it via LWJGL- very nice btw).  I currently get big time flashing- which is what I'd expect if my buffer.show() isn't synched with monitor's vsynch and their respective rates aren't perfectly in synch.  But I'm a big time newb- maybe I'm missing something.

Could someone give me some pointers, advice, links?
Thanks a lot!

Regards,
Fooberry
Offline fooberry

Junior Newbie




Still working on something clever.


« Reply #23 - Posted 2003-10-07 22:56:55 »

Well, I got rid of the flicker by adding a timer.sleep(22000).
I'm using the GAGE AdvancedTimer.
I now get 66 fps while @ 1024x768, 85Hz.

I'm assuming that I don't see the flicker anymore because the 85Hz sufficiently covers the 66fps and the beat frequency becomes unnoticeable.  (yes/no/sorta?)

Still feel like I'm at the mercy of some mysterious forces.
BTW: WinXP home edition, 1.8GHz, NVidia TNT2 Model 64- 32Mb.

Regards,
Fooberry
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #24 - Posted 2003-10-08 07:37:34 »

Welcome.
Your question seems a bit off topic to this thread and  you might want to post some code to make yourself a bit more clear.

Anyway, it seems like the flickering has something to do with buffering (you are double or triple buffering are you?) rather than vertical sync (not syncing to the monitor will not result in flicker, but in 'tearing').
I think using BufferStrategy will sync to the monitor's refresh rate, unless this has been disabled in your video driver.

Hope this helps,
Erik

Offline MGodehardt

Junior Member




why does the chicken cross the road?


« Reply #25 - Posted 2003-10-08 09:02:21 »

Its easy to check your render code.

Remove all rendering, do only buffer flips ( and maybe background clearing )

If the FPS u get is NOT the Refresh Rate of the current mode, your code is buggy.

This is only true for fullscreen mode, in windowed mode you need some special tweaks.

Your app performance is only 77% thats a really bad performance, maybe later it drops below 60fps and below 60Hz its unusable for RT games
Offline fooberry

Junior Newbie




Still working on something clever.


« Reply #26 - Posted 2003-10-08 20:48:48 »

In Markus_Persson's original code, there was a timer.getTimeInMillis().  I accidentally used the AdvancedTimer's getClockTicks(), which is NOT in milliseconds.  Things behave as expected, no more sleeping either, when I slipped in System.currentTimeMillis() temporarily.
I need to do some math in order to correctly use the AdvancedTimer.  Thanks.

Regards,
Fooberry
Offline Conflux

Senior Newbie




Java games rock!


« Reply #27 - Posted 2003-11-19 13:30:04 »

Quote


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
IFloat xPlayerPos = new IFloat(0);

public void clientTick(float interpolation)
{
  renderPlayerAt(xPlayerPos.getValue(interpolation));
}

public void gameTick()
{
  float xPos = xPlayerPos.getValue(1);
  xPos+=1;
  xPlayerPos.setValue(xPos);
}


Now if gameTick() gets called once every second, the player would move exactly one "unit" per second, but clientTick() would still make the motion smooth.


What do you mean with "Unit"? Where is the unit defined? is it the "xPos+=1" or the "xPlayerPos.getValue(1) ??

I'like to speed up the movement of my object. If I try e.g. "xPos+=10" the object moves faster, but is hopping between several pixels (according to the interpolation-value) when there is no further key event.
Offline immudium

Junior Member




Gorram it!


« Reply #28 - Posted 2003-11-20 04:54:00 »

Well "unit" isn't an actual variable or anything.  It's just the distance you want to move in a given amount of time.  That could be 200 pixels per second or 1 inch per minute, etc.  So, in the example, clientTick is the actual framerate you get that may or may not fluctuate wildly from one second to the next, while gameTick is sort of the theoretical, constant framerate that you want to achieve a.k.a the "unit" value.  The interpolation mechanism, then, sort of works as an intermediary between the actual and theoretical framerate to keep the sprite moving at constant "unit" increments.  Thus, if you want ALL of your movement to appear to move faster, you would increase your "unit" value, which, in the case of the example given would be the value of GAMETICKS_PER_SECOND.  Anyway, that's my current understanding of it...
Offline MGodehardt

Junior Member




why does the chicken cross the road?


« Reply #29 - Posted 2003-11-20 07:55:24 »

Quote


Question- while testing this game loop, I notice that my fps seem to be limited to the refresh rate of the screen mode I switch into.  Is this a Window's "feature"?


Hmmm its the sun is shining outside and its brightly, is this a real life feature ?

the fps is directly connected to your monitor refresh rate, a 60Hz refresh means f = 60[s**-1] so a T cycle is T = 1/f = 16.66667 ms

At the beginning of every T cycle your monitor will show a new picture from VRAM, if your FPS exceeds the monitor refresh rate, guess what happens, if u update VRAM in the middle of the T cycle you will not see any new picture on the monitor, simple isnt it !

Quote


Also- I understand what vertical synch is all about, but I don't yet see how to "do it" with pure Java.  (I do see how to do it via LWJGL- very nice btw).  I currently get big time flashing- which is what I'd expect if my buffer.show() isn't synched with monitor's vsynch and their respective rates aren't perfectly in synch.  But I'm a big time newb- maybe I'm missing something.



The VSync marks the beginning of a new T cycle, the buffer show() method waits until a new T cycle is started

Go to your local bookstore and buy some books about game physics, or go to a company where u can learn this profession, professional game developer, its not easy but after 5 or 6 years you can program your own game
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Dwinin (15 views)
2014-09-12 09:08:26

Norakomi (45 views)
2014-09-10 13:57:51

TehJavaDev (57 views)
2014-09-10 06:39:09

Tekkerue (26 views)
2014-09-09 02:24:56

mitcheeb (49 views)
2014-09-08 06:06:29

BurntPizza (33 views)
2014-09-07 01:13:42

Longarmx (19 views)
2014-09-07 01:12:14

Longarmx (21 views)
2014-09-07 01:11:22

Longarmx (20 views)
2014-09-07 01:10:19

mitcheeb (30 views)
2014-09-04 23:08:59
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!