Jump to content
  • Advertisement
Sign in to follow this  
cozman

State based design and fixed timestepping

This topic is 4844 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Disclaimer: I know this is a long question and somewhat complex, I'd really appreciate any ideas any of you guys have on this though. I am currently using a State-based design in my project, and I'm looking to implement an easy way to set a fixed physics step. I'd like to use something similar to the fixed timestep described in the Canonical Game Loop but I am facing a few design problems. At the moment the timeDelta is obtained when it is needed by querying the Application class (Application::getTimeDelta). I have recently implemented code (based on a discussion in a previous post) that allows one to smooth the timestep by averaging the last X timeDeltas. This can help to reduce jittering and minimize error. At the moment this is done in the following manner:
Application::setTimeDeltaMode(TDM_ACTUAL);       // makes timeDelta = actual elapsed time
Application::setTimeDeltaMode(TDM_AVERAGE, 100); // makes timeDelta = average of last 100 frames
I was thinking of adding another mode that would allow for a fixed timestep:
Application::setTimeDeltaMode(TDM_FIXED, 0.01);       // makes timeDelta = 0.01
which of course is a little more complicated than just always returning 0.01. At the moment my project uses a State-based system that has a base state class:
class State
{
...
    virtual void update();   // update logic for current state
    virtual void render();   // update rendering for current state
...
    virtual void onKeyPress(KeyCode key);  // a variety of input handlers are also available
...
};
If I were to fix the timestep, I'd need to use an accumulator to determine when update should be called. In this case however getting the timeDelta from Application probably isn't the best option since update and render need different timeDeltas if interpolation/extrapolation is going to be a feature. (Yes there's the possiblity of having two different ways to query for timeDelta, one for update, one for render, but this seems overly complex) I think my best option is to have update/render take timeDelta arguments: this means they don't need to query Application for the elapsed time, the State management system could pass in the correct values. Before I go and make these adjustments to my State system I wanted to run the idea past some other people: -what do some of you who use a state system/fixed time step do? -do you forsee any problems with my approach that I may be overlooking? -do you use fixed time steps (and interpolation/extrapolation) in your projects? [Edited by - cozman on August 14, 2005 4:14:09 PM]

Share this post


Link to post
Share on other sites
Advertisement
Why would rendering need a fixed timestep?

Anyways, here is the code I use for timestepping:

rms_timer.h

Used to try and generically define a timer setup. The original idea was meant to allow this code to be interchangable with higher performance timers, or ported more easily to non windows OSes. This is the interface, with one global interface defined for app-wide use.

It's missing a [decent] 'pause' feature.

Otherwise, the class takes a parameter to define how many milliseconds is a 'tick' of the time step. By modifying this parameter, the entire app can be tuned to be faster or slower.


#ifndef RMS_TIMER
#define RMS_TIMER

#include <limits>

struct rmstimer{
protected:
long ticks;
long remainder;
long mspertick;
void addms(long ms);
void countbyms(long ms);
void countbyticks(long tks);

public:
long count(){return(ticks);}
virtual void update()=0;

rmstimer(long mpt=33):mspertick(mpt),ticks(0),remainder(0){}
};

void rmstimer::addms(long ms){
//
// Add ms milliseconds to the counter.
//
ticks=ms/mspertick;
remainder=remainder+ms%mspertick;
if(remainder > mspertick){
++ticks;
remainder=remainder-mspertick;
}
}


void rmstimer::countbyms(long ms){
//
// Add ms milliseconds to the timer.
//
addms(ms);
}


void rmstimer::countbyticks(long tks){
//
// Add tks ticks to the timer.
//
addms(tks * mspertick);
}


rmstimer *timer=0;

#endif



rms_win32_timer.h

The concrete implimentation for win32.

#ifndef RMS_WIN32_TIMER
#define RMS_WIN32_TIMER

// include kernel32.dll

#include <windows.h>
#include "rms_timer.h"
#include <limits>

/*
struct hp_win32_timer:
protected rmstimer{

private:
DWORD hpc_per_ms;
void sethpc();
protected:
DWORD last_count;
public:
hp_win32_timer(long mpt):rmstimer(mpt){sethpc();}
void update();
long
*/



struct win32_tickcount_timer:
public rmstimer{
private:
protected:
DWORD last_count;
public:
win32_tickcount_timer(long mpt):rmstimer(mpt),last_count(GetTickCount()){}
void update();
void reset();

};



void win32_tickcount_timer::update(){
//
// Update ticks from GetTickCount()
//
DWORD new_count=GetTickCount();

// handle rollover isolated case.

if (last_count > new_count){
addms((numeric_limits<DWORD>::max)() - last_count + new_count);
}else{
addms(new_count - last_count);
}
last_count=new_count;
}


void win32_tickcount_timer::reset(){
//
// Reset the last_count due to the app losing focus.
//
DWORD new_count=GetTickCount();

last_count=new_count;
ticks=0;
remainder=0;
}

#endif




Now, in actual use, functions are generally defined to process one increment of time. The increment might be one or more ticks. If more than one increment passes, the function will be called multiple times to accumulate the effect. This allows the function to be ignorant of how much time a tick actually is, and focus on the task at hand.

Here's some simple renderers that use the timer. I render as fast as possible. By placing things in the rendering path, they're called each game loop.

rms_timer_renderers.h

Included is the base class, timed_trigger. A timed_trigger stores a functor, and executed that functor a specified number of times, every specified number of 'ticks'. After executing the last time, it auto-matically removes itself from the rendering tree.

Also included is a renderable to cause other renderables to blink. Every so often [determined by the timed_trigger] it toggles a visibility flag for all its children.

fps_counter is a simple fps renderer, which is explicitly set to 1 second checks. It'd be easily fixable to do wider checks by modifying the parameter to timed_trigger to be non-constant.

alpha_fade is a simple renderer to fade in/out its children, at a rate specified.

By having the classes inherit from the base timed_trigger, all of the common functionality of triggering is handled. The only thing the classes need to worry about is implimenting what happens every timestep [or X timesteps].


#ifndef RMS_TIMER_RENDERERS
#define RMS_TIMER_RENDERERS

#include "rms_basic_gui.h"
#include "rms_timer.h"
#include "rmsrect.h"
#include "rmsd3dfont.h"
#include "voidvoid_guiaction.h"
#include "vine.h"

template <typename F>
struct timed_trigger:
virtual public basero{
private:
protected:
F f;
long repeat;
long trigger;
long ticks;
bool onlyf;
public:
virtual void render(){
ticks=ticks + timer->count();
while (ticks>=trigger){
if (repeat>0){
repeat--;
}
ticks=ticks-trigger;
if (onlyf){
// to allow f() to delete 'this'
f();
//
// RMS: jul-24-05:
//
// commenting return, as the current incarnation of rendertree [for_each]
// does not gracefully continue in the tree should the current iterator's
// object be yanked out from underneigth it.
//
// oops... Changed to use an out-of-band sort of callback mechanism.
//
//return;
}else{
f();
}
if (repeat==0){
//out_of_order_executables.push_back(storega(voidvoidfunctor(this, &basero::no_tree_delete)));
no_tree_close();
//repeat--;
//return;
rendertree();
return;
}

}
rendertree();
}
void manual_trigger(){
ticks=trigger;
}

timed_trigger(F inf=F(), long trig=30, long rep=1, bool oof=0):basero(new standard_rect(rect())), f(inf), trigger(trig), repeat(rep), ticks(0), onlyf(oof){}

virtual ~timed_trigger(){}
};

struct blinky_funct{
protected:
basero *target;
public:
void operator()(){
br_child_iterator it;

for (it=target->children.begin(); it != target->children.end(); ++it){
(*it)->toggle_visible();
}
}

blinky_funct(basero *t):target(t){}
};



struct blinky:
virtual public basero, virtual public timed_trigger<blinky_funct>{
private:
protected:
bool enabled;
public:
virtual void enable(){enabled=1;}
virtual void disable(){enabled=0;}
virtual void render(){
if (enabled){
timed_trigger::render();
}else{
basero::render();
}
}

blinky(long rate=33, bool e=1): basero(new standard_rect(rect())), timed_trigger<blinky_funct>( blinky_funct(this), rate, -1, 0), enabled(e){}
};


struct fps_counter:
virtual public basero, virtual public timed_trigger<storega>{
private:
protected:
long frames;
int fps;
public:
// TODO: rerect.
void tick(){
fps=frames;
frames=0;
}
virtual void render(){
++frames;
timed_trigger::render();
}

const int *fpsref(){return(&fps);}
fps_counter(depended_rect_generator *rg, d3dfont *f=fonts.fetch(), DWORD c=0xff000000): basero(rg), timed_trigger<storega>(storega(voidvoidfunctor(this,&fps_counter::tick)),30,-1,0), frames(0), fps(0){
ro_text *rot;
ref_int_renderer *rint;
calculated_font_rect_generator<standard_rect> *cfrg=new calculated_font_rect_generator<standard_rect>(0,0,new standard_rect(rg->fetch()));

rot=new ro_text(cfrg,"FPS: ", f, c);
cfrg->set(&rot->font,rot->txtref());
rot->parent=this;
children.push_back(rot);

rint=new ref_int_renderer(new relative_rect(cfrg->dependable(),new rect_area(cfrg->dependable()),4,0,0,1),fpsref(),f,c);
rint->parent=this;
children.push_back(rint);

}
virtual ~fps_counter(){}
};



struct alpha_fade:
virtual public basero, virtual public timed_trigger<storega>{
private:
protected:
bool direction;
unsigned char limit;
unsigned char rate;
public:
void fade(){
br_child_iterator it;
DWORD c;
unsigned char a;

for(it=children.begin();it!=children.end();++it){
c=(*it)->color();
a=(c & 0xff000000) / 0x01000000;
if (direction){
if (a + rate >= limit){
a=limit;
}else{
a=a+rate;
}
}else{
if (a - rate <= limit){
a=limit;
}else{
a=a-rate;
}
}
c=c % 0x01000000;
c=c + (a * 0x01000000);
(*it)->color(c);
}
}
virtual void render(){
timed_trigger::render();
}
void short_circut(){
br_child_iterator it;
DWORD c;
unsigned char a;

for(it=children.begin();it!=children.end();++it){
c=(*it)->color();
a=limit;
c=c % 0x01000000;
c=c + (a * 0x01000000);
(*it)->color(c);
}
}

alpha_fade(unsigned char r=4, bool d=1, unsigned char l=255):direction(d), limit(l), rate(r), basero(new standard_rect(rect())), timed_trigger<storega>(storega(voidvoidfunctor(this,&alpha_fade::fade)),1,255,0){}
virtual ~alpha_fade(){}
};

#endif



Share this post


Link to post
Share on other sites
I didn't mean that render had a fixed timestep, the reason it would need a timeDelta parameter passed to it would be for interpolation/extrapolation. That is precisely why it can't use the same timeDelta as the update step, update needs to be fixed, while render shouldn't be.

Thanks for sharing all of that timing code, your trigger system in particular is fairly interesting and I'll have to look further into implmenting something similar in the near future as I can definately see times in which it would be very handy.

Share this post


Link to post
Share on other sites
Quote:

the reason it would need a timeDelta parameter passed to it would be for interpolation/extrapolation


In what way? Or perhaps a more concrete example? I am curious.

Share this post


Link to post
Share on other sites
If you check out the link (now fixed) in my first post you'll see the final example adds interpolation/extrapolation.


#if EXTRAPOLATE
render extrapolated state from oldstate to newstate extrapolate by STEPSIZE + (cur - newstatetime);
#else
render interpolated state from oldstate to newstate interpolate by (cur - oldstatetime);
#endif


I've never really done any interpolation/extrapolation (those of you who do use fixed time steps, perhaps you could enlighten me to if you interpolate/extrapolate in your render step)
but I wanted to design the state system so it was possible. And therefore it'd need a method to get the elapsed time.

Share this post


Link to post
Share on other sites
thanks for the links but I'm actually basing my timestep idea on part of his Fix Your Timestep! article (the 2nd just like you suggested)

(for anyone who hasn't read them though I would recommend it [smile])

Share this post


Link to post
Share on other sites
Ah.

Note that my fixed timestep does the same thing as the integral physics, without the integration.

For example, assume we have an object like a ball. The ball has a speed of 5 pixels per timestep. Now, assume that 4 timesteps progress.

The integral physics would call a function that takes the velocity [5] and the time [4] and does integration 0->4 [integral] dx dt. Because the velocity is constant, that's simply 0->4 5x, or 5(4) - 5(0), or simply 20. The math of course gets more complex as velocity is no longer constant... The function would then move the ball 20 pixels.

In the fixed timestep method, a function 'move by velocity' is simply called 4 times [because 4 timesteps have passed]. This essentially does the same thing as the integral, only with brute force, rather than mathematical cleverness. The ball is moved 5 pixels, then another 5 pixels, again and again, a total of 20 pixels.

To extrapolate a position [like player prediction in Quake, or where that ball would be in 400 time steps] the direct physics method is likely far more elegant. That's also the case if you need to do more accurate physics calculations.

[imo] if you're just updating the game every 30ms or so, and you're 99% of the time only ever going to increment one timestep, the brute method is far simpiler to design, impliment, debug, and use. I'm still only doing 2D, mostly turn-based and puzzle affairs, and the method above works well enough for that.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!