In 1982 (several years before DOOM), Ken Perlin invented an algorithm meant to produce random numbers that more closely resembled a human's interpretation of "random" numbers (versus those generated by computers). Humans, it seemed, tended to choose a lot of different numbers, whereas random numbers from a CPU actually produced lots of repeating sequences. His work in the field was vital to developing the first 3D shaded graphics in a Hollywood film (Tron), for which he won an Academy Award for Technical Achievement.
Perlin Noise is still used to this day for generating clouds, natural-looking terrains, and other textures that are pleasing to the human brain.
I remember many years ago the iTunes player had to include an option for "humanizing" the randomness of their shuffle play (or whatever they called it).
Turns out that good randomness didn't seem random to people. They might hear three songs in a row from the same album and think "that's not right, it should be random!" Of course, humans often have a different idea of what "random" is.
What I expect from a music player is to play all my songs in random order, such that once a song has been played, it is not picked again until all songs have been played.
There is a difference between randomly picking an element from a list and reordering a list in a random order. This is not a matter of how random really are the random numbers.
One of the classic radio stations in Chicago does this a couple times a year -- they play their entire catalog A-Z. I agree that it does come out pretty nice.
And not just textures or terrain. Apply Perlin noise to a vector field and you create smoothly random motion, which can be used to simulate things like air currents.
To be fair, the key insight to the DOOM prng is that it was used frequently enough for hundreds of mundane events that a player didn't realize (or care) that it wasn't very random at all. There was never a "guess the number" game. A good write-up is here: http://jmtd.net/log/deterministic_doom/
But that does not make the question why the DOOM solution is so much smaller than the perlin noise code more valid. It is simply not the same thing. One is a table of set of generated data, the other a generator of data that can be tabulated.
There's enough old Softdisk/id Software code released that you can trace the evolution of this RNG.
First, check out Catacomb (1989). I think this is the oldest of Carmack's games for which source code has been released. This game uses a lagged fibonacci generator:
This makes sense, it's a generator that requires little memory and no expensive operations such as multiplications. You'll probably also find it in Softdisk's Apple II releases.
Carmack's first 3D game is Hovertank 3D, released in 1991. The LFG still exists, but now a "table-based RND generator" also appears. This seems to be the first appearance of the "Doom RNG".
The LFG is used when setting up the map, while the table-based is used for enemy AI during gameplay. Obviously every cycle counts when trying to do 3D on a 286.
The same year also saw the release of Keen Dreams, in which only the table-based RNG survives:
There was a post about tampering with randomness in Doom some time ago with some interesting hn comments explaining the reason for this design: https://news.ycombinator.com/item?id=9429889
" The Doom pseudorandom number generator is simplistic yet adequate for gameplay. Its simplicity has the virtue of speed.
The file m_random.c in the Doom source code contains a static table 256 bytes long containing numbers between 0 and 255 in a fixed, scrambled order. There is an index to this table which starts at zero. Each call to the function P_Random advances the index by one (wrapping around to zero after 255) and returns the table entry at that index.
There is another function, M_Random, that is identical except that it uses its own independent index. P_Random is used in play simulation situations, such as calculating hit damage. M_Random is used otherwise.
The reason for the existence of two individual indexes is to maintain multiplayer synchronisation: for example, M_Random is used to apply a random pitch variation to sounds. As two players may not hear the same sound effect (they may be in different parts of the level), using a single index would cause the game to become desynchronised. To use a model-view-controller analogy, P_Random is used for random number generation at the 'model', while M_Random is used for random number generation at the 'view'.
The function M_ClearRandom resets both functions' indexes to zero. It is called during initialization of each new level so that demos will be the same each time they are played, and so that multiplayer games are synchronised.
Although the table is 256 bytes long, it does not contain all of the numbers between 0 and 255 inclusive. For example, 0 appears twice and 1 does not appear at all; 145 appears five times, more than any other number. Thus the values are not uniformly distributed, but in fact they are nearly so. The mean value is 128.852, whereas it would be 127.500 if all values were equally likely. All of this suggests that the table was generated using a conventional pseudorandom number generator of reasonable quality. "
TL;DR: rand() loops through a fixed set of values, but unpredictable user input leads to unpredictable sequence of rand() calls (e.g. an animation calling it before or after a sound-effect selector), providing an unpredictable output from rand().
This is the most interesting part to me, and the irony of the random output.
The "random number generator" isn't actually the table, but rather the table <-> the amount of times the function is actually called (aka player input as a source of randomness).
If the game were coded in such a way that there are more deterministic random calls (enemy seeding at beginning of a level, etc) then it would feel less random. If it were coded in a way that there are more non-deterministic random calls (enemy spawning based on table index when a player enters a room) then it would feel more random.
The table is deterministic, but the exact value returned for any given event X is the product of how many random() calling events happened before event X.
Or, in the ideal engineering way: achieve the minimal randomness required for player belief, and use the saved computational overhead on my interesting things (e.g. graphics).
All PRNGs all just repeating sequences. Usually they are just longer and use clever math to generate the next term of the sequence instead of just storing it in array. But always it repeats itself eventually.
For Doom speed was more important than length of the sequence so they just made it a lookup table.
Sibling posts have correctly pointed out that the & here is a bitwise AND. However, I wanted to note that `&` is also the take-address-of operator in C, which is why you think it has to do with pointers: there are two operators (one taking the address of something, the result of which is a pointer, another taking a bitwise AND); they both use the same symbol "&".
The difference is that the AND is a binary operator — i.e., it takes two arguments:
A & B
whereas the address-of operator "&" is a "unary" operator; it only takes one argument:
&A
There can be something before it in a more complete context, such as:
x = 3 + &y;
(though this is more often conventionally written the other way "&y + 3"; I only use this for demonstration)
But here "+" is the binary operator. (You can't have two binary operators in a row; that would be like "3 + * 2", which is nonsensical.) This is similar to "3 + -2": the negative here is a unary operator, the "+" here is the binary operator "add"
Any reasonable compiler will implement x%256 using bitwise arithmetic, but C semantics require that x == d*(x/d) + (x%d), which means that if x is negative (x%256) must be negative, while (x&0xff) will be positive.
This difference means that the AND is still faster than the MOD when used on signed integers, if the compiler is not smart enough to prove that the input will never be negative.
For example, with gcc 4.7.3 the resulting assembly is
> there are two operators (one taking the address of something, the result of which is a pointer, another taking a bitwise AND); they both use the same symbol "&".
Don't you just love C? ;-) (On a serious note, I've been meaning to learn it for some time, but didn't yet get down to the nitty-gritty.)
in this case the & is not to point to an adress, but a bitwise and. 0xff is hexadecimal for 255, or 00000000000000000000000011111111 (assuming 32-bit integers), so the logical and masks out the lower 8 bits of (prndindex+1), effectively doing modulo 255.
This is great RNG for games although most computer scientists would strongly disagree. We focus so heavily on having huge cycle length for RNG that we forget that human memory is not all that great at remembering exact sequence of even just handful of random numbers, let alone 255 of them. So you don't need RNGs with guarantees of huge cycles for gaming scenarios like adding error in to projectile's path. The advantage of this RNG is that it's blazingly fast (think all the cache hits!). Of course this would be useless for any real work on physics simulation or weather simulation etc.
Assuming by "MSPlayed" you mean "milliseconds played";
Another poster[1] links to a Doom wiki article[2], which explains,
> The reason for the existence of two individual indexes is to maintain multiplayer synchronisation
If you sync the PRNG's state at the beginning of the game, you can simply transmit the other client's input (such as keyboard/mouse): since each PRNG is in the same state on all the players' machines, you don't need to distribute over the network the results of PRNG choices: each client can just compute it locally. So long as all the code uses the PRNG's output stream for the same purposes, in the same order, everything is deterministic (while appearing to be random).
Milliseconds played would also likely require some sort of OS/hardware interaction, to get to a timer. This is an add, an AND, and a memory lookup: likely significantly quicker (bear in mind the hardware Doom was created with/for). (Perhaps there are cycle counts, but I'm not sure that instruction was a thing yet? Though it was more reliable then…)
That seems like a very unusual (and large) way to produce a pseudorandom sequence. Why not a linear congruential generator or LFSR? They have approximately the same state storage requirements, but much less static data.
Doom was probably squeezing every last cycle out of 386 @ 25 MHz machines to render frames, but they did have at least 4MB–8MB RAM; 256 bytes seems a good trade-off.
I presume that speed was the determining factor, not saving bytes.
This may also present the advantage of being tweakable to avoid repeated sequences that better generator may naturally produce but are not perceived as 'random enough' by humans.
Imagine I want to sample [0,2), then I can use the following table: [0,0,0,1,1,0,1,1]. This has cycle length 8. Much longer cycles can be obtained, it just requires the state of the prng to be larger than range being sampled.
It is not, at least not the way you (and me) are interpreting it. A RNG's period is bounded by the number of states it has, internally[1]:
> The period is bounded by the number of the states
> If a PRNG's internal state contains n bits, its period can be no longer than 2 ^ n results, and may be much shorter.
Our state in the Doom generator is the variable rndindex (or prndindex; we have two generators here); rndindex holds an index in [0, 256) (it is 8 bits), hence we have at most that many states (2 ^ 8, or 256). (I'm assuming the table does not repeat itself, as that would be silly, so in this case, the period is exactly 256 outputs long.)
People should not get into the habit of depending on global mutable state. What if the project evolves and now going to work multithreaded? What if parts of the project are extracted to be used in another one? What if a toy project grows to be massive?
I say this because I have investigated many crypto libraries for usage and nearly every one of them (especially openssl) have random generators that depend on global state. The attitude of not caring about correctness and thread safety is just pervasive.
DOOM was one of those games that relied on stretching the hardware to its limits to produce previously-unseen visual effects. The only thing that mattered was getting pixels on the screen as fast as possible.
Edit: no, of course there weren't any mutex primitives in DOS/4GW. It's a single-process single-thread bare metal environment. You have to realise that, in 1993 PC gaming, shared memory multithreading was simply not something that developers would ever encounter. It had no concievable advantages as you had only one CPU, not even a graphics accelerator. Games generally wouldn't multitask either; again, this predates consumer availability of Win32 and certainly is several years before DirectX.
The Doom engine uses a lot of global mutable state. In context, there's nothing wrong with this. Why pass around state explicitly when there's just one instance of the state? Multithreading wasn't on the horizon for game engines in 1993. Single CPU cycles were very much a concern. Developer time was also limited (most of this code was written by a single person in about a year). This wasn't a toy project that could have evolved in a million different ways, and it wasn't a crypto library either. There was a game that had to be shipped, and John Carmack was surely more concerned about getting the game engine to do precisely what it needed to do to run the game than proofing the code for hypothetical future scenarios.
Doom was released in 1993. I'm guessing that netheril96 wasn't made until 3 years later.
Tech is a very ahistorical discipline. We don't look back at the "old masters". We reinvent things every generation (or in Javascript land, every week).
Perlin Noise is still used to this day for generating clouds, natural-looking terrains, and other textures that are pleasing to the human brain.
Python implementation: https://github.com/caseman/noise/blob/master/perlin.py
Excellent talk by its creator: http://www.noisemachine.com/talk1/