State based design and fixed timestepping

Started by
6 comments, last by Telastyn 18 years, 8 months ago
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]
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


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.
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.
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.
Sorry, didn't read all your question, but you mentioned word "timestamp". So, I suggest to look at those tutorials (especially the second): Glenn Fiedler's physics tutorials.

HTH :-)
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])
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.

This topic is closed to new replies.

Advertisement