15 replies to this topic

[Aerodactyl55]

I recently decided to switch from a variable step to a fixed step game loop. So i created a small application to test the new loop. I dont know why but the new loop does not produce smooth movement. I hope maybe someone here will spot a mistake because i cant find it myself.

Here is the code:

#include "core.h"

struct STAR
{
IDirect3DTexture9* Tex;
D3DXVECTOR2   Pos;
D3DXVECTOR2   prevPos;
D3DXVECTOR2   Vel;
};

LRESULT CALLBACK WndProc( HWND, UINT, WPARAM, LPARAM );
BOOL Init();
void Update( float dt );
void Render();
void Cleanup();

Core::CGraphics gfx;
Core::CSprite sprite;
STAR star;

ULONGLONG tNow = 0;
ULONGLONG tPrev = 0;
ULONGLONG tFreq = 0;
DWORD accumulator = 0;
const int UPDATE_TICKS = 10;
const float DELTA_TIME = UPDATE_TICKS * 0.001f;
float lerp = 0.0f;
wchar_t str[64] = L"";

int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )
{
if( !gfx.InitWindow( hInstance, WndProc, L"Game Loop Test", nCmdShow ) ) return 0;
if( !Init() )
{
  gfx.MsgBoxError( L"Init() Failed!" );
  return 0;
}
MSG msg = { 0 };
QueryPerformanceFrequency( ( LARGE_INTEGER* )&tFreq );
QueryPerformanceCounter( ( LARGE_INTEGER* )&tPrev );
float c = 1.0f / tFreq;
while( WM_QUIT != msg.message )
{
  if( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) )
  {
   TranslateMessage( &msg );
   DispatchMessage( &msg );
  }
  else
  {
   QueryPerformanceCounter( ( LARGE_INTEGER* )&tNow );
   accumulator += ( DWORD )( ( ( tNow - tPrev ) * 1000 ) / tFreq );
   tPrev = tNow;
   while( accumulator >= UPDATE_TICKS )
   {
	Update( DELTA_TIME );
	accumulator -= UPDATE_TICKS;
   }
   lerp = accumulator / ( float )UPDATE_TICKS;
   Render();
  }
}
return static_cast< int >( msg.wParam );
}

BOOL Init()
{
if( !gfx.CreateDirect3D9() ) return FALSE;
if( FAILED( gfx.CreateDevice9() ) ) return FALSE;
if( FAILED( sprite.Init( &gfx ) ) ) return FALSE;
ZeroMemory( &star, sizeof( STAR ) );
if( FAILED( gfx.LoadTextureFromFile( L"star.png", &star.Tex ) ) ) return FALSE;
star.Pos.y = 284.0f;
star.Vel.x = 500.0f;
star.prevPos = star.Pos;
return TRUE;
}

void Update( float dt )
{
star.prevPos = star.Pos;
star.Pos = star.Pos + star.Vel * dt;
if( star.Pos.x + 32.0f > 800.0f )
{
  star.Pos.x = 768.0f;
  star.Vel.x = -star.Vel.x;
  star.prevPos = star.Pos;
}
else if( star.Pos.x < 0.0f )
{
  star.Pos.x = 0.0f;
  star.Vel.x = -star.Vel.x;
  star.prevPos = star.Pos;
}
}

void Render()
{
gfx.Clear();
gfx.BeginScene();
sprite.Begin();
D3DXVECTOR2 p;
p = star.prevPos * lerp + star.Pos * ( 1.0f - lerp );

sprite.Translate( &p );
sprite.Draw( star.Tex, NULL, DODGERBLUE_COLOR );
sprite.End();
gfx.EndScene();
gfx.Present();
}
void Cleanup()
{
Core::ReleaseCOM( star.Tex );
}

LRESULT CALLBACK WndProc( HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam )
{
switch( msg )
{
case WM_DESTROY: Cleanup(); PostQuitMessage( 0 ); break;
default: return DefWindowProc( hwnd, msg, wParam, lParam );
}
return 0;
}

[Khatharr]

It took quite a while to sort out what you're doing there.

I think if you just bite the bullet and refactor this your bug will go away. Also, it may help to use a naming convention that marks m_members, and g_globals or somesuch to help with clarity, but in this case what helped me the most in sorting it out was adding some vertical spacing to separate sections of code that were doing different jobs. That's always a slight suggestion that another function could make things more clear, even if it's only called in one place. Some of the variable and function names are unclear. I find it helps to name things as if I were describing them to another person.

I'll keep looking at this and see if I can spot a problem.

Edit - I think this may be it:
[source lang="cpp"] if( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) { TranslateMessage( &msg ); DispatchMessage( &msg ); } else { //no processing is done if there's a message![/source]

I'll keep looking.

Edit - nvm, I think it's your 'lerp' handling. One sec while I bust out the maths.

No, I don't think that's it.

Say, why don't you rehash this real quick and make the star a class instead of using C-style OOP. Try to clean it up a little. It's really hard to walk through right now.

Edited by Khatharr, 04 December 2012 - 04:36 PM.

[ApEk]

First off I would suggest you refine your whitespace and indentation syntax as well as your naming convention.
You are passing a constant delta time to update. Why? I don't know. Instead you should probably be calculating the delta time between previous and current frame and passing that to update. Update then uses the delta time by multiplying it by a constant.

Edit: should work harder on my critical reading.

Edited by ApEk, 04 December 2012 - 06:22 PM.

[FLeBlanc]

The thing with fixed-time loops is that you get best results if you interpolate the transformations of your objects.

Say you have an object that moves at the rate of 100 pixels/sec. In a variable-time update, each time through the loop you calculate elapsed time, dt, (which is probably going to be a very small number) and move the object by 100*dt pixels. Since dt tends to be quite small, it appears as if the object took a very, very small fraction of a step, and only moved a very tiny amount. The accumulation of these tiny increments over one second of time adds up to 100 pixels total movement. Maybe this movement was done in 60 steps, though (if V-sync was enabled) or maybe it was done in more.

In the case of a fixed-time loop, say you have it updating at a rate of 10 times per second. This means that over the same 1 second of time as before, the update portion will now be called exactly 10 times, and each time the object will move 10 pixels. This is locked in place. That means that the object now isn't moving in tiny increments; it's moving in big 10-pixel leaps.

Interpolating the positions will give you back the ability to move the object smoothly. The gist of it is that for each object you store a LastTransform and a CurrentTransform. Each time you update the object you cycle the CurrentTransform into the LastTransform storage, then calculate a new CurrentTransform based on speed of movement etc... Then during the render portion, you calculate how much time has elapsed since the last update was performed, and use this elapsed time value to interpolate between LastTransform and CurrentTransform to obtain the actual transformation you use to draw the object. This transformation is visual only; for logical purposes, the object will still be considered to be located at CurrentTransform; the interpolation merely smooths the jump from Last to Next.

[L. Spiro]

You are passing a constant delta time to update. Why? I don't know. Instead you should probably be calculating the delta time between previous and current frame and passing that to update. Update then uses the delta time by multiplying it by a constant.

Because he is using a fixed time-stamp. The time since last logical update is already known—there is nothing to calculate.

You should describe in what way your game is not smooth. Stuttering? Random jerkiness?


L. Spiro

[Aerodactyl55]

First i am really sorry about bad coding, this isnt my real coding style. This application was rushed just to test how the fixed time-step loop behaved.
This test application only moves a 32x32 sprite left-right. There is visible stuttering in the motion which i was unable to fix even with interpolation. I am not sure if it is the loop itself or something else.

Edited by Aerodactyl55, 05 December 2012 - 12:19 AM.

[Aerodactyl55]

i decided to refine the code a little to make it easier to understand, but i didnt add "g_" to variables because 99% of them are globals.

#include "core.h"


struct OBJECT
{
	  IDirect3DTexture9*	  Tex;  //Object texture
	  D3DXVECTOR2			 Pos;  //Current position
	  D3DXVECTOR2			 prevPos;//Previous position, this will be used for interpolation
	  D3DXVECTOR2			 Vel;  //Velocity
};


LRESULT CALLBACK WndProc( HWND, UINT, WPARAM, LPARAM );
BOOL Init();
void Update( float dt );
void Render();
void Cleanup();


Core::CGraphics gfx;
Core::CSprite sprite;
OBJECT star;


ULONGLONG tNow = 0;
ULONGLONG tPrev = 0;
ULONGLONG tFreq = 0;
DWORD accumulator = 0;

const int UPDATE_TICKS = 10;						  //10ms
const float DELTA_TIME = UPDATE_TICKS * 0.001f; //The dt passed to the update function
float lerp = 0.0f;												//The interpolation value to be used during rendering


int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )
{
	  if( !gfx.InitWindow( hInstance, WndProc, L"Game Loop Test", nCmdShow ) ) return 0;

	  if( !Init() )
	  {
			gfx.MsgBoxError( L"Init() Failed!" );
			return 0;
	  }

	  MSG msg = { 0 };
	
	  QueryPerformanceFrequency( ( LARGE_INTEGER* )&tFreq );
	  QueryPerformanceCounter( ( LARGE_INTEGER* )&tPrev );

	  while( WM_QUIT != msg.message )
	  {
			if( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) )
			{
				  TranslateMessage( &msg );
				  DispatchMessage( &msg );
			}
			else
			{
				  QueryPerformanceCounter( ( LARGE_INTEGER* )&tNow );

				  accumulator += ( DWORD )( ( ( tNow - tPrev ) * 1000 ) / tFreq );
				  tPrev = tNow;

				  while( accumulator >= UPDATE_TICKS )
				  {
						Update( DELTA_TIME );
						accumulator -= UPDATE_TICKS;
				  }

				  //Compute the interpolation value for this frame
				  lerp = accumulator / ( float )UPDATE_TICKS;

				  Render();
			}
	  }

	  return static_cast< int >( msg.wParam );
}


BOOL Init()
{
	  if( !gfx.CreateDirect3D9() ) return FALSE;

	  if( FAILED( gfx.CreateDevice9() ) ) return FALSE;

	  if( FAILED( sprite.Init( &gfx ) ) ) return FALSE;

	  ZeroMemory( &star, sizeof( OBJECT ) );

	  //Load the texture
	  if( FAILED( gfx.LoadTextureFromFile( L"star.png", &star.Tex ) ) ) return FALSE;
	
	  star.Pos.y = 284.0f;
	  star.Vel.x = 500.0f;	//The sprite only moves on the x-axis

	  star.prevPos = star.Pos;

	  return TRUE;
}


void Update( float dt )
{
	  //Store the position before updating
	  star.prevPos = star.Pos;

	  //Move the sprite
	  star.Pos = star.Pos + star.Vel * dt;

	  //Prevent the sprite from leaving the screen boundaries [0 - 800]
	  if( star.Pos.x + 32.0f > 800.0f )
	  {
			star.Pos.x = 768.0f;
			star.Vel.x = -star.Vel.x;
			star.prevPos = star.Pos;
	  }
	  else if( star.Pos.x < 0.0f )
	  {
			star.Pos.x = 0.0f;
			star.Vel.x = -star.Vel.x;
			star.prevPos = star.Pos;
	  }
}


void Render()
{
	  gfx.Clear();

	  gfx.BeginScene();

	  sprite.Begin();

	  D3DXVECTOR2 p;	//interpolated position

	  //Interpolate between the previous and the current position
	  p = star.prevPos * lerp + star.Pos * ( 1.0f - lerp );
	
	  //Draw the sprite
	  sprite.Translate( &p );
	  sprite.Draw( star.Tex, NULL, BLUE_COLOR );

	  sprite.End();

	  gfx.EndScene();

	  gfx.Present();
}

void Cleanup()
{
	  //Release the texture
	  Core::ReleaseCOM( star.Tex );
}


LRESULT CALLBACK WndProc( HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam )
{
	  switch( msg )
	  {
	  case WM_DESTROY: Cleanup(); PostQuitMessage( 0 ); break;
	  default: return DefWindowProc( hwnd, msg, wParam, lParam );
	  }

	  return 0;
}

I am still unable to find any mistake but the stuttering is still there.
And thanks for the replies.

[Khatharr]

I'm really tired, but that's a lot easier to read right now. I'm sorting it around and looking at what you're doing.

I think I found what's been bothering me here.

Isn't your loop and lerp there the same as:
[source lang="cpp"] accumulator = ( DWORD )( ( ( tNow - tPrev ) * 1000 ) / tFreq ); star.Pos.x = ((float)accumulator / UPDATE_TICKS) * star.Vel.x; if(star.Pos.x > (800 - 32)) { star.Pos.x = ((800 - 32) * 2) - star.Pos.x; star.Vel.x = -star.Vel.x; } if(star.Pos.x < 0) { star.Pos.x = -star.Pos.x; star.Vel.x = -star.Vel.x; } gfx.Clear(); gfx.BeginScene(); sprite.Begin(); sprite.Translate( &(star.Pos) );[/source]

I'm not lucid enough to be confident in that, but I'll check in again in the morning when I can open my eyes all the way.

Anyway, I think the problem has something to do with applying 'lerp' in the render but not applying it to the position of the sprite. since you don't remove the lerp'ed value from the accumulator I suppose it carries over, but then any discrepancy in the float division may cause different results. DX vectors store their members as floats. Why not just set the position correctly in the star's vector and render it where it really is instead of trying to interpolate between two integrals?

Good luck.

Edited by Khatharr, 05 December 2012 - 06:37 AM.

[Aerodactyl55]

According to this article interpolation is needed to avoid stuttering and this seems to be true because removing the interpolation doesn't help. Maybe I should use the next position instead of the previous. I dont see any error in the way i am calculating the interpolation yet the movement of the sprite is not smooth. I tried putting some sleep calls and it does minimize the stuttering but it doesn't eliminate it completely.

[jHaskell]

I'm having trouble understanding the purpose of the Interpolation in that article. It seems incorrect to me. In fact, the author's very own words are out of sync, at the very end of the article...

Any remainder in the accumulator is effectively a measure of just how much more time is required before another whole physics step can be taken.

I take that to mean that the remainder is the amount of time that has already passed to the next discrete physics step and that makes complete sense, but then he goes on to say...

We can use this remainder value to get a blending factor between the previous and current physics state simply by dividing by dt.

I do not understand how the time between the current and next step can be used as a blending factor between the previous and the current step. That just seems logically incorrect to me.

[Khatharr]

According to this article interpolation is needed to avoid stuttering and this seems to be true because removing the interpolation doesn't help. Maybe I should use the next position instead of the previous. I dont see any error in the way i am calculating the interpolation yet the movement of the sprite is not smooth. I tried putting some sleep calls and it does minimize the stuttering but it doesn't eliminate it completely.

It seems like there's way too much going on to accomplish not very much.

Interpolation is not a magical cure-all. It's just selecting a position between two endpoints.

1+1+1+0.5 = 3.5

So there's no reason to run a loop that adds to your total 1+1+1 times and then manually implements the 0.5 in the rendering because it's the halfpoint lerp value between 0 and 1.

Figure out the position of your sprite and place it in that position then render it where it sits. What you're doing right now is finding a position near where the thing is and then using interpolation to try and make it look like it is where it belongs.

If you want to re-invent floating point division that's up to you I guess, but this code tells lies all over the place. Your delta is not a delta, your position is not a position, your Render() is actually RenderSomethingSimilarButNotQuite().

As for that article, if you need pinpoint precision for positioning then the Runge-Kutta method is appropriate, but if you just let the star's position be its actual position then Euler will give smooth motion without the need to reinvent floating point division. Gaffer is using double precision and RK4 because he's probably thinking about large values in a large space, but for 'pixel per second' you can just use 'normal' Euler math. His use of a fixed 'delta' in that code progression is very misleading. The delta was a delta in the earlier code, but by the time he gets to the end it's just a scalar value for the frame time. The reason he's using interpolation is because he's separating physics simulation steps at specific points. Honestly when he gets to 'accumulator < dt' he should then feed accumulator into the physics instead of carrying it over to the next frame. There's no reason to do that in the code you have here since pixel-width is not high granularity. If you avoid having velocities that are ridiculously high then you should be okay without having to spoon-feed the simulation.

Even if you want to keep the loop for collision test dragging just let the position be the position and do away with 'accumulator' and 'p' and the messy game of 'catch-up'. If you want to interpolate a pixel-per-second motion with interpolation then set your velocity in terms of PPS and then get your delta T and put it in terms of a fraction of a second then multiply it by your motion.

Did you implement single-motion first and then move on to dragging?

Pseudocode:

whatTickIsIt(&nowTime);
ticksPassed = nowTime - prevTime;
prevTime = nowTime;
secondsPassed = ticksPassed / tickHz;
position.x += position.x + (velocity.x * secondsPassed);
if(outOfBounds) {
  //stuff
}

Meanwhile, putting this all in linear order and extracting irrelevant code I think I may see what's causing your stutter.

Try this:

lerp = (float)accumulator / UPDATE_TICKS;

I really wish I had a compiler on this machine. A debugger makes it so much easier to find this kind of thing.

Edited by Khatharr, 05 December 2012 - 04:29 PM.

[Aerodactyl55]

Khatharr, your pseudocode seem to suggest a variable time step which i have used in previous projects, and it works. The problem is if the game slows down a big delta time is passed to Update(), which may result in missed collisions.

Try this:

lerp = (float)accumulator / UPDATE_TICKS;

Doesnt help.

[Khatharr]

Yeah, you can break up the delta if the sim needs it. I'm saying don't carry over the fraction to the next frame. Just pass it in to the sim and start the next frame with a new delta.

Edited by Khatharr, 06 December 2012 - 01:20 AM.

[jHaskell]

Instead of

[source lang="cpp"]while( accumulator >= UPDATE_TICKS )[/source]

try

[source lang="cpp"]while( accumulator >= 0 )[/source]

And change accumulator to a signed int. Then, for any left over accumulator, you're running one update frame into the future, at which point the interpolation makes more sense.

[Aerodactyl55]

After so much frustration this is what worked for me:

int accumulator = ( int )( ( ( tNow - tPrev ) * 1000 ) / tFreq );
tPrev = tNow;

while( accumulator > 0 )
{
	 Update( DELTA_TIME )
	 accumulator -= UPDATE_TICKS;
}

//Compensate for the extra update loop that consumes the remainder
if( accumulator != 0 ) Sleep( abs( accumulator ) );

Render();

And i removed the interpolation.
Thanks everyone.

[NoAdmiral]

I might be wrong, but I think your stuttering came from the fact that you're interpolating in the wrong direction. It looks like you're pushing your star backwards toward where it was at the last update instead of forward by the amount of time left over. The way it's set up looks like your render function should render the star where it would be a given amount of time after the last update call (make a prediction based on its current velocity) rather than where it was between the past two calls.

Like I said, I could be wrong (I just implemented something like this in my own game, and it seems to be working).