1/10/2008

01-10-08 - 1

When coding, I often want to have some random event happen roughly once per mean interval T. There are a few ways to do this.

1. Store the next time the event should happen. When that time passes, fire the event and generate a new time. The new time should be a function of the event time, not the frame time, which could differ by the duration of the frame. This method gives you the most flexibility since you can generate the new time from whatever spectrum you want. For example it could just be a constant probability across some interval, or it could be a Gaussian centered on the mean time.

2. Store a probability accumulator. When the accumulator goes over 1.0, fire the event. When the event fires, subtract off 1.0 The way you step the accumulator has some flexibility, but roughly it should be proportional to the frame duration and randomized as you see fit. The advantage of this over #1 comes if your events aren't always random, and for example if two or three events suddenly fire off, you want them to delay longer until they happen again. For single events this isn't very interesting, but for multi-choice events it provides a way of flipping a coin and reducing the chance of repeats.

3. Use a memoryless random event. This is the only way to do it without any side storage. You have some spot in code where you just want to generate a random event with a certain mean interval and you don't want to have to add another state variable. The only random generator that does this is a Poisson Process with rate lambda = 1/T.

Basically the probability rate lambda is the probability of an event per unit time. But you can only use that linearly over an infinitesimal time slice. For a finite frame length, to be properly framerate independent, you should look at the chance of an event happening over the course of the frame. For a frame of length "dt" the probability of any event happening is :

P = 1 - e^(-dt/T)

Of course technically you need to allow 2 or more events to happen per frame, but if we assume dt << T that chance is tiny and we don't care about it anyway.

So, to check whether you should generate a random event you just do :

if ( frandunit() < 1 - e^(-dt/T) )

You may be familiar with doing

if ( frandunit() < (dt/T) )

which is the non-framerate-independent version that sort of works okay for fast frames and long intervals.

Generally this Poisson random is not generally a good looking random event for graphical events, but is a really nice way to do periodic things without a state variable.

No comments:

old rants