General Purpose Simple Moving Average

Letteroids will continue after some adjustments, not the least of which is catering for the majority of wimpy players out there. I deliberately made it very hard, to see what would happen. 10 players completed the game, which is an amazing feat on their behalf. But I was surprised at how wimpy most players are (50% failure rate on Level 2?)

Anyway, right now I am also developing another quicky game. This one is in 3D, with a custom vehicle physics model and networking. I’m using Unity (of course) and the Photon Network Engine, and even though it makes a lot of things easy, networking is never easy. It’s going well none-the-less.

One issue of course is interpolation and extrapolation of object transform (i.e. position and orientation) data. I’ve come up with a nice solution which is good enough and very simple, but I won’t go through that here. Instead I want to talk about a very useful general technique for creating a moving average, which has many uses.

The idea of a moving average is to average a certain number of previous data points, so that you smooth out that data and get an average which changed over time, but is less noisy. I use this technique in many contexts. Some examples are:

  • Getting a smoothed rendering frame rate for profiling purposes
  • Allowing AI to decide whether a target is actually moving anywhere, or just moving backwards and forwards at random
  • Getting an average update rate for network packets

The most obvious way to do this is to remember the last, say, 10 data points and average them each frame. Wikipedia covers this and goes into more detail , but misses the technique I am about to describe.

First of all, any video game programmer should be familiar with the basic concept of an average. To average a set of data, you simply add the data together and divide the total by the number of data values. The very useful special case is the average of two values: in this case you divide the sum by two (which is very convenient in assembler programming where the divide is a simple bit-wise shift).

Anyway, if we want to average the last 10 data values, we can do that like this:

(\sum_{t=-9}^{0} V_t) \frac{1}{10}

For the math-o-phobes out there, that just means the sum of the last 10 values divided by 10. When coding, you can use a for loop to generate the sum \sum.

Of course what we want is a moving average, which means that we have to calculate the above each time we get a new data value. Well, here comes an optimisation: we could simply add a new value and remove an old each time to a running total:

avg_{new} = avg_{prev} - \frac{V_9}{10}+\frac{V_0}{10}

The problem here is that we have to remember the last 10 values in order to be able to remove the appropriate one from the total. That can be seriously annoying. Maybe you don’t feel like organising storage for this and the additional code complexity. I certainly don’t.

So, instead I do this in a different way. Since I do not want to remember values of the past, I simply subtract the average each time. It does almost the same thing, and in fact is probably better because the moving average will not be affected by past jumps in value:

avg_{new} = avg_{prev} - \frac{avg_{prev}}{10}+\frac{V_0}{10}

This can be simplified to:

avg_{new} = avg_{prev}\frac{9}{10}+\frac{V_0}{10}

Or more generally:

avg_{new} = \frac{avg_{prev}(N-1)+V_0}{N}

Where N is the number of samples you wish to create you moving average over. An extremely useful little expression to keep in your programming toolbox.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: