Limegarden.net Personal site of Wouter Lindenhof

Random distribution

One of the special effects I recently worked one was cellular noise (original made by Steve Worley) and the book that I read used Poisson distribution. The Poisson distribution is a table which holds random values that guarantees certain conditions (like an average mean). However I’m not going to talk about Poisson distribution, it just remembered me of some old error I made and how I finally solved it. Besides there are better sources than me who can explain the math behind it.

But first a talk of a prehistoric me talking about some game that I worked on.

One of the games that I worked on as a student was a shooter like Tyrian but then in 3D. You would race around in hovering car through a fixed path in a 3D city and you would shoot down enemy cars. Since the path was a circle, you would go around and around until you were death, you could jump from one car to another and that was pretty cool to see (and made the game quite easy if you knew the timing). However some cars would be rare to encounter because they had better armor or better weapons and we needed fact in the spawning code. I made up some kind of obscure code for it that based on random number and a “common” value would spawn one of the cars. Before I started on it I thought it wouldn’t be too hard. But this is one of the times I was actually wrong. It worked to some degree but I noticed that some cars were rarely spanned, even though they had a high “common” value. The problem was obvious in the code I had written but at that time I couldn’t think of an algorithm that would solve this issue.

Ok, enough history, let’s go back to the future.

By now I have worked on a lot more of code and when I read how Poisson distribution is used, which is properly how more distribution work, I noticed it was similar to what I once invented.

So to illustrate the problem I will try and remember and describe what I used for that game.

We could use [cci_cpp]rand() % MAX_CAR_ID[/cci_cpp] to generate a lot of random numbers so that we have a list of cars that we use for the game. Using [cci_cpp]std::vector CarSpawnList[rand()%ListSize][/cci_cpp] we could decide the next car. Problem is that this method is slow and does not guarantee the distribution we are looking for and some of the cars might not even be in the list to begin with.

A better method is using two lists. The first list contains all the values we want to have like for every Saab there are five Fords, then we would add the ID of a Saab once and then we add the ID of a Ford five times. Problem with this list is that the numbers are ordered or are in a way ordered. We could still use [cci_cpp]CarSpawnList[rand()%ListSize][/cci_cpp] but if we have a bad seed we could still have three Saabs before we encounter a ford.

So let’s introduce the second list. The second list will start empty and we move every item in the initial list to the second least. So we remove it in the first list and add it to the second list. The item chosen in the first list is random and because it is removed we will make certain that the Saabs and Fords balance each other. In code it would look something like:

[cc_cpp]
#define CAR_SAAB_ID 1
#define CAR_SAAB_MAX 1
#define CAR_FORD_ID 2
#define CAR_FORD_MAX 5
#define CAR_MAX_ORDER 1

void FullListRandom()
{
std::vector lInitialList;
std::vector lFinalList;

for(int i = 0; i < CAR_SAAB_MAX * CAR_MAX_ORDER; i++)
lInitialList.push_back(CAR_SAAB_ID);
for(int i = 0; i < CAR_FORD_MAX * CAR_MAX_ORDER; i++)
lInitialList.push_back(CAR_FORD_ID);

// now create the final list
while(lInitialList.size())
{
int CurId = rand() % lInitialList.size();
lFinalList.push_back( lInitialList[CurId] );
lInitialList.erase( lInitialList.begin() + CurId );
}
};
[/cc_cpp]

Of course you have to put [cci_cpp]lFinalList[/cci_cpp] somewhere more global, I just wrote this code for this post, but if you increase [cci_cpp]CAR_MAX_ORDER[/cci_cpp] then you can prevent a repeating pattern. If you would think of [cci_cpp]lFinalList[/cci_cpp] as circular list (meaning, once you reach the end you start over) this will provide a quite good and consistent distrubution.

By now the above method is common knowledge for me and it is rather simply once you know how to do it.

References

• TEXTURING & MODELING A Procedural Approach, third edition
• The game Tyrian