Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
104 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

Triggers/Interpolators

It's time to look at a couple more 'utility' objects - 'utility' in that they're internal engine objects that you don't really use on their own. However, that doesn't stop me from having found them to be some of the most useful objects in the engine. They're fairly similar in design and operation - they just behave a little differently - which is why I'm presenting them together.

Interpolators

Interpolators are particularly useful objects when it comes to polish and effects.

Quite simply, Interpolators take an input value - most often the clock - and use it to interpolate an output value. The output is set by reference, so the interpolator can directly change it with no problems. Want a fade-out effect? Simply set up an interpolator with your global alpha value as the output. It's also very simple to set up different types of interpolation - plain linear interpolation may do for many things, but smoother methods - quadratic and cubic - will be shown here as well.

class IInterpolator : public IMMObject
{
protected:
  float ⌖
  static std::list< CMMPointer<IInterpolator> > interpolators;
public:
  IInterpolator(float &t);
  virtual ~IInterpolator();

  bool bFreeze;

  virtual void Update(float dt)=0;
  void Kill();

  friend class CInterpolatorUpdater;
  AUTO_SIZE;
};

We're going to assume that all interpolators work with float values (I can't think of many situations where they wouldn't be - though if you *really* needed to, you could set it up with templates). So, we have a float reference to our 'target' value - our output. We also have a list of CMMPointers to IInterpolators.

This next one took me a while to get right. Interpolators are sort of self-referencing objects. When you create one, it will add itself to the 'interpolators' list using a CMMPointer - which means that even if you release all your pointers to the interpolator, it'll still be held in existence by that pointer in the list. Why is that useful? It means you can create an interpolator, and drop it out of scope, without it dying. It's going to need to be alive to function. When it comes down to it, you don't even need to keep a local copy of the interpolator - you can just do 'new CLinearInterpolator(...);' as a standalone statement, and this will handle the rest. Of course, if you do that you lose control of the interpolator - you can't pause it or kill it unless it pauses or kills itself. A possible extension to this system, then, would be a way to give an interpolator an ID - a string or unique number - which you give the interpolator when it is created, and can then be used to retrieve a pointer to the interpolator later on, so you can (for example) kill it.

Now we get to the public functions. There's the constructor and destructor - the constructor taking the initial value for 'target.' bFreeze is a boolean flag which you can set to 'freeze' the interpolator - it will not be updated while it is frozen.

Update() is the function derived classes must implement. It's that function which 'powers' the interpolator - does the calculation and assigns to the output value. It takes dT - 'delta time' - as a parameter, because 95% of our interpolators will be time-based so, unless you're going for micro-optimization and consider the time taken to pass the argument too much, there's no point having them all fetch the time themselves. If an interpolator doesn't need it, it ignores it.

Kill() is a simple function to remove the interpolator from it's own list. If you call Kill() on an interpolator, and then drop all references to it, it really *will* be destroyed. Technically, you can call Kill() on it and still keep references to it, but it won't be updated any more (unless you call IInterpolator::Update() on it yourself each frame).

Lastly, it marks CInterpolatorUpdater (we'll meet it in a minute) as a friend class, and then uses the expected AUTO_SIZE macro to fulfill abstract functions on IMMObject, from which it derives.

Here's the (brief) implementation of the non-abstract functions:

IInterpolator::IInterpolator(float &t) : target(t)
{
  interpolators.push_back(this);
  bFreeze=false;
}

IInterpolator::~IInterpolator()
{

}

void IInterpolator::Kill()
{
  std::list< CMMPointer<IInterpolator> >::iterator it=
      (std::find(interpolators.begin(),interpolators.end(),this));
  if(it!=interpolators.end())
    (*it)=0;
}

The constructor sets up the target reference, and adds itself to the list of pointers. It also has the interpolator start in a non-frozen state by default. The destructor does nothing (it's only there to make sure derived destructors works properly). Lastly, Kill() finds the interpolator in the list and (assuming it can find it) sets its pointer to zero, releasing it.

So... we've got all these interpolators knocking about with Update() functions on them, all in a list - sounds fairly easy to do. We'll use a task for it:

class CInterpolatorUpdater : public ITask
{
public:
  bool Start();
  void Update();
  void Stop();
  AUTO_SIZE;
};

That's about as minimial a task as you can get.

bool CInterpolatorUpdater::Start() { return true; }
void CInterpolatorUpdater::Stop() { IInterpolator::interpolators.clear(); }
void CInterpolatorUpdater::Update()
{
  PROFILE("Interpolator task");
  std::list< CMMPointer<IInterpolator> >::iterator it,
            ite=IInterpolator::interpolators.end(), itT;
  for(it=IInterpolator::interpolators.begin(); it!=ite; it++)
  {
    if((*it).isValid())
    {
      (*it)->Update(CGlobalTimer::dT);
    }else{
      //remove invalid entries from the list, just to keep things fast
      itT=it;
      --it;
      IInterpolator::interpolators.erase(itT);
    }
  }
}

Start() does nothing (it doesn't need to do anything). Stop() kills the list of pointers - thus releasing all interpolators when the task is shut down (otherwise they'd still be in scope when CollectRemaningObjects gets called, giving 'unreleased object' reports in the logs). Update() simply loops through the list of interpolators; for each interpolator, it tests that the pointer is actually valid, and if it is, calls Update() on it. If not, it removes that entry from the list - no point iterating over dead entries, and as more and more interpolators are created and destroyed, those dead entries would build up.

So, that's our basic interpolator system. Let's see some objects we'll actually use!

class ITimebasedInterpolator : public IInterpolator
{
protected:
  float elapsedTime, totalTime;
  virtual void Calculate()=0;
public:
  void Reset();
  void Update(float dt);  
  ITimebasedInterpolator(float &targ, float time);
  AUTO_SIZE;
};

This is the base class for interpolators which interpolate from start to finish across a fixed time period. Note that there are plenty of interpolators that *use* time but are not considered time-based - a sine-wave interpolator would be an example, an interpolator which oscillates its target value at a given phase, amplitude and frequency for an indefinite period of time. This base class implements Update() - which updates the elapsed time and checks to see if the total time has been exceeded (in which case the interpolator expires, Kill()ing itself). There's also a Reset() function, which sets elapsedTime back to zero (to 'restart' the interpolator). However, it adds an abstract function of its own - Calculate - which the classes below implement to work out the output value in their own specific ways:

class CLinearTimeInterpolator : public ITimebasedInterpolator
{
protected:
  float startVal, endVal;
  void Calculate();
public:
  CLinearTimeInterpolator(float &targ, float time, float sV, float eV);
  AUTO_SIZE;
};

class CQuadraticTimeInterpolator : public ITimebasedInterpolator
{
protected:
  float startVal, midVal, endVal;
  void Calculate();
public:
  CQuadraticTimeInterpolator(float &targ, float time,
                             float sV, float mV, float eV);
  AUTO_SIZE;
};

class CCubicTimeInterpolator : public ITimebasedInterpolator
{
protected:
  float startVal, midVal1, midVal2, endVal;
  void Calculate();
public:
  CCubicTimeInterpolator(float &targ, float time, float sV,
                         float mV1, float mV2, float eV);
  AUTO_SIZE;
};

How do these interpolators work? To answer that, we're going to need to do a little math.

Firstly, we can treat the time as a value between 0 and 1 - 0 means no time has elapsed, and 1 means all time (totalTime) has elapsed. Call that value 'b.' In a linear interpolator, we want a 'b' value of 0 to produce the start value, and a 'b' value of 1 to produce the end value. A 'b' value of 0.5 should produce a value half-way between the start and end.

We could say that the start value is equal to 'startValue * 1 + endValue * 0' and that the end value is equal to 'startValue * 0 + endValue * 1.' In fact, for any value through the interpolator, it'll be 'startValue * someNumber + endValue * someOtherNumber.' someNumber and someOtherNumber will always add up to 1 - that is, 'one whole value.' They're blending weights.

When 'b' is 0 someOtherNumber is 0, and when 'b' is 1 someOtherNumber is 1 - it doesn't take too much effort to suppose that someOtherNumber=b. Given that someOtherNumber + someNumber = 1, someNumber must = 1 - b. We'll call that 'a.'

So, in a linear interpolator, the output is 'a * startVal + b * endVal.' And if you look at the code:

void CLinearTimeInterpolator::Calculate()
{
  //calculate b, keeping it clamped to the range [0,1]
  float b=clamp(elapsedTime/totalTime,0,1);
  target = startVal*(1-b) + endVal*b;
}

Exactly what we said. How about the next interpolators, though? Are they quite as simple?

Nearly. We've established that '(a+b)=1'. That means that '(a+b)^2=1' (because 1^2=1). If you multiply out (a+b)^2, you get 'a^2 + 2ab + b^2' - three values. If we add to our startValue and endValue a 'middleValue,' we can do 'a^2 * startValue + 2ab * middleValue + b^2 * endValue.' The placement of the middleValue with respect to the start and end values will affect the 'steepness' of things at each end - for a sudden fade-in and then gradual fade-out, you could use a quadratic interpolator with the middleValue near the startValue. Fun fact: quadratics were how Quake 3 did its curvy surfaces ('bezier patches').

void CQuadraticTimeInterpolator::Calculate()
{
  float b=clamp(elapsedTime/totalTime,0,1), a=1-b;
  target = startVal*a*a + midVal*2*a*b + endVal*b*b;
}

The theory extends. If '(a+b)^2=1' produces an expression with 3 terms - 'coefficients' - then it's not a tremendous leap of the imagination to say that '(a+b)^3' would produce 4 terms. That's right - 'a^3 + 3ba^2 + 3ab^2 + b^3' - so we can plug four values into our interpolator. The expression (a+b)^3 is 'a plus b cubed,' thus this is a 'cubic' interpolator.

It's possible to have an interpolator which accepts any number of values. Given 'n' values, you just expand '(a+b)^(n-1)' to get your coefficients. It follows a nice pattern - for term 'r' out of a total of 'n' terms, the coefficient is something like 'nCr * a^r * b^(n-r).' Google for the 'binomal theorem' if you want to know more; more terms mean more calculation time, though, and cubic interpolation is usually good enough for me.

void CCubicTimeInterpolator::Calculate()
{
  float b=clamp(elapsedTime/totalTime,0,1), a=1-b;
  target = startVal*a*a*a + midVal1*3*a*a*b + midVal2*3*a*b*b + endVal*b*b*b;
}

The only thing that remains:

void ITimebasedInterpolator::Update(float dt)
{
  if(bFreeze)return;
  elapsedTime+=dt;
  Calculate();
  if(elapsedTime>totalTime)
  {
    Kill();
  }
}

Triggers

Triggers, like interpolators, are small objects that you can chuck around pretty liberally. They have a task updating them in the same way as the interpolators, but rather than working with changing an output, instead they monitor an input. Again, the input is set by reference; the idea is that you set a trigger up with a variable to 'watch' and a functor to call when a certain condition is met, and then let it get on with things; "don't call us, we'll call you."

class ITrigger : public IMMObject
{
public:
  ITrigger(Functor *h, bool fo);
  virtual ~ITrigger();

  void Kill();
protected:
  CMMPointer<Functor> handler;
  bool bFireOnce;

  virtual bool Test()=0;

  static std::list< CMMPointer<ITrigger> > triggerList;

  friend class CTriggerTask;

private:
  void Tick();
};

You should spot some similarities to the IInterpolator base class; there's the friend declaration, and the list of memory-managed ITrigger pointers. There's also that Kill() function, to remove a trigger before it expires (or if, indeed, it's set not to expire). Notice that the base class doesn't have a reference to an input variable - that's because unlike the Interpolators, we're going to allow Triggers to work with any type (not just float).

ITrigger::ITrigger(Functor *h, bool fo)
{
  handler=h;
  bFireOnce=fo;
  triggerList.push_back(this);
}

ITrigger::~ITrigger()
{

}

void ITrigger::Kill()
{
  std::list<CMMPointer<ITrigger> >::iterator it=
      std::find(triggerList.begin(), triggerList.end(), this);
  if(it!=triggerList.end())
    (*it)=0;
}

void ITrigger::Tick()
{
  if(Test())
  {
    (*handler)();
    if(bFireOnce)
    {
      Kill();
    }
  }
}

Again, all fairly familiar stuff. The constructor handles the self-referencing list stuff again, and the Kill() function has just changed interpolatorList to triggerList. The Tick() function is the equivalent of the Update() function in the interpolators, and as such is called every frame. The Test() function performs the actual test - in most derived classes it'll be a one-line function, as you'll see. If it returns true - that is, the test condition is satisfied - then the handler is called, and the trigger is destroyed (if it's been set to only fire once).

class CTriggerTask : public ITask
{
public:
  bool Start();
  void Update();
  void Stop();
  AUTO_SIZE;
};

bool CTriggerTask::Start() { return true; }
void CTriggerTask::Stop() { ITrigger::triggerList.clear(); }
void CTriggerTask::Update()
{
  PROFILE("Trigger task");
  std::list< CMMPointer<ITrigger> >::iterator it,
        ite=ITrigger::triggerList.end(), itT;
  for(it=ITrigger::triggerList.begin(); it!=ite; it++)
  {
    if((*it).isValid())
    {
      (*it)->Tick();
    }else{
      itT=it;
      --it;
      ITrigger::triggerList.erase(itT);
    }
  }
}

Identically minimalistic. (This one actually *was* a copy-and-paste job).

Now, onto some derived classes. I use the names 'subject' and 'object' for the input and the thing it's tested against ('subject-predicate-object', where predicate is the test itself):

template<class T>
class CEqualsTrigger : public ITrigger
{
protected:
  T &subject;
  T object;
public:
  CEqualsTrigger(T& s, T o, Functor *h, bool fo=true)
    : ITrigger(h,fo), subject(s)
  {
    object=o;
  }

  bool Test(){return (subject==object);}

  AUTO_SIZE;
};

You can now see why most of the Test() functions will be one-line jobs. Any type you want to use with the triggers system is going to need operators for whatever test you want to perform, of course - you won't be able to create a CEqualsTrigger<SomeClass> if SomeClass doesn't provide an == operator (you'll get a compiler error). You'll also need assignment operators - for the 'object' parameter, at the very least.

template<class T>
class CNotEqualsTrigger : public ITrigger
{
protected:
  T &subject;
  T object;
public:
  CNotEqualsTrigger(T& s, T o, Functor *h, bool fo=true)
    : ITrigger(h,fo), subject(s)
  {
    object=o;
  }

  bool Test(){return !(subject==object);}

  AUTO_SIZE;
};

template<class T>
class CLessTrigger : public ITrigger
{
protected:
  T &subject;
  T object;
public:
  CLessTrigger(T& s, T o, Functor *h, bool fo=true)
    : ITrigger(h,fo), subject(s)
  {
    object=o;
  }

  bool Test(){return (subject<object);}

  AUTO_SIZE;
};

template<class T>
class CGreaterTrigger : public ITrigger
{
protected:
  T &subject;
  T object;
public:
  CGreaterTrigger(T& s, T o, Functor *h, bool fo=true)
    : ITrigger(h,fo), subject(s)
  {
    object=o;
  }

  bool Test(){return (subject>object);}

  AUTO_SIZE;
};

You get the idea. It becomes drastically easy to write trigger classes - so easy, in fact, that I provided you a macro for doing it (commented out, in triggers.h). TRIGGER_CLASS(classname, test) will define a trigger class - there are a couple of examples there for you. Of course, for those of you who consider macros to be the devil, I invite you to exorcise it from the file, liberally redecorate with holy water, and write the classes out in full. Your choice. There are also a bunch of 'key' triggers, designed to work with the input system, which call functors when keys are pressed/released (making key binding incredibly simple).



The Buildstamp

Contents
  Serialization
  Triggers & Interpolators
  The Buildstamp

  Source code
  Printable version
  Discuss this article

The Series
  Part I
  Part II
  Part III
  Part IV
  Part V