For your reference, here is how I do random number generation. If you use a lot of random numbers in your game logic (and of course, you do!) then maybe you can get some useful ideas here and add yours to the end of this post.
Ah yes, this algorithm is the one that everyone uses nowadays. It's fast, and produces excellent very long-period sequences of random numbers. It also has a really cool name, involves mersenne primes (primes of the form 2^n - 1) which I think is psychologically comforting.
@p
One interesting thing about MT is that the period is actually longer than the number of 32-bit integers (4 billion). This is because internally it uses 64 bits of state (well, I'd assume the algorithm could be adapted a few different ways for different bit widths, but the one I use takes 32-bit seeds and seems to have 64 bits of internal state.)
This is actually a fairly important concept when you do a lot of procedural generation. I don't do as much of this in Texas as I did in Venture the Void but the principal still holds in places.
@p
Suppose that you are generating 15 planets filled with plant and animal life. Your star system has a 32-bit seed value and so you set up the random number generator and then run your fabulously detailed planet generation algorithm to produce all the wonderful things you want the player to explore.
@p
Let's say in the process of game development you notice that your automatically generated planet Delta Yarg has a few too many Ewokian Mantii on it. You have some code such as:
// generate the ewokian mantii
@p num_ewokian_mantii = RN () * MAX_EWOKIAN_MANTII;
@p for (i = 0; i < num_ewokian_mantii; ++i)
@p add_ewokian_mantis ();
@p // initialize the planet's atmospheric nitrogen patterns
@p add_atmospheric_nitrogen ();
So you change the constant, MAX_EWOKIAN_MANTII and indeed, your planet now has fewer Ewokian Mantii. Now it's time to see if the game is more balanced. You fire it up, and...
@p
The atmospheric nitrogen has now changed drastically! This resulted in later-on code producing no human settlements on this planet, and instead the planet is completely infested by Volrakkians. It's now hard to tell whether the number of Ewokian Mantii was appropriate, or not.
@p
Worse, the next-further-from-the-sun planet in the system, the Lava Giant Excelsior 7, where you were experimenting with your lava flow simulation is now called Glutionous Balrakka and is a Mushroom Spore planet. You'll have to find another Lava Giant to continue work on your lava flow simulation.
@p
What happened? Well, add_ewokian_mantis () adds one Ewokian Mantis, which involves between 40 calls to RN () in order to properly calculate the wingspawn characteristics. But this threw off your random numbers for everything downstream, so the entire planetary system has now changed.
@p
In practice, this makes it really hard to do game design. Not impossible, but it's a major problem.
For instance, nethack (at least at some point in it's history) had a similar problem. As you descended, further dungeon levels were generated as needed from the RN. Single player, you'd never know this was how it worked. But what if you wanted to run a simultaneous-play nethack tournament?
@p
As each player reached subsequent levels, they would all be different. Only the first dungeon level was the same. It sort of makes such a tournament unfair, because player 1 might find a Wand of Wishing and a Magic Marker on Dungeon Level 3 whereas Player 2 had a banded mail and a Container of Lard instead.
@p
Nethack was patched, I think, to fix this.
What you need to do in order to fix this, is have a branching random number generator. Suppose you are generating a star system with planets. Instead of this code:
int num_planets = RN () * MAX_PLANETS;
@p for (int i = 0; i < num_planets; ++i)
@p add_planet (RN);
Use code like this:
rngen planets_RN (RN.get_seed ());
@p int num_planets = planets_RN () * MAX_PLANETS;
@p for (int i = 0; i < num_planets; ++i) {
@p rngen planet_RN (planets_RN.get_seed ());
@p add_planet (planet_RN);
@p }
Thus, you are branching your RN stream. Each planet gets it's own RN stream, so that whatever happens on each planet, stays on that planet (because of planet_RN). Likewise, your code to generate the planets themselves is isolated (planets_RN).
@p
In fact, you could take this further, and at the start of each generation function you do all of your RN branching. This way, you can even re-order your code (e.g., when you realize you need to generate asteroids BEFORE planets) and not affect the content of things quite so much (in practice, you'll be looking at the state of the asteroids when it comes time to generate the planets, so in this case you probably will change the content of your planets, regardless of how well you do your RN branching).
I like to give my random number generator a few useful functions:
Another useful thing is a weighted chooser. It doesn't really work as well in C++, but in LUA it's fairly simple to do something like:
local AlignChoices = { evil = 2, neutral = 5, good = 4 }
@p local Align = RN_choose_weighted (AlignChoices)
The RN_choose_weighted () function computes ratios from the input AlignChoices so that it will return evil 2/11 of the time, neutral 5/11 of the time, and good 4/11 of the time (notice evil + neutral + good = 11).
@p
This is useful when you've got more than two things to choose between. Based on this, you can quite naturally see that good will show up about twice as much as evil, but neutral is a bit more common (5/4) than good. Very handy!
There is a lot of subtlety to how you use your random number generator. Give it some thought.
@p
For instance, in Texas I have a replay system in place. Some of the events that happen in gameplay are based off a "game_RN ()" random number generator. At the start of gameplay, we seed it with the unix time, which is the standard way to initialize your gameplay random number generator.
@p
In this case, what we need to do is actually record the random number seed into the replay file, so that when you playback a replay you seed it with the same value. Otherwise, you won't see the proper enemies spawn, etc.
@p
Another possibility is to implement push/pop semantics for random number streams. This works similar to stream branching, but you have a stack of RN objects and use always the topmost one. When you push, you take a seed value from the topmost one and push a new RN, seeded with that seed value, to the stack. From then on, until the next RN_pop (), you are isolated from RN stream causation.
2009-08-03