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.<p>Perlin Noise is still used to this day for generating clouds, natural-looking terrains, and other textures that are pleasing to the human brain.<p>Python implementation: <a href="https://github.com/caseman/noise/blob/master/perlin.py" rel="nofollow">https://github.com/caseman/noise/blob/master/perlin.py</a><p>Excellent talk by its creator:
<a href="http://www.noisemachine.com/talk1/" rel="nofollow">http://www.noisemachine.com/talk1/</a>
There's enough old Softdisk/id Software code released that you can trace the evolution of this RNG.<p>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:<p><a href="https://github.com/FlatRockSoft/Catacomb/blob/master/CATASM.ASM#L397" rel="nofollow">https://github.com/FlatRockSoft/Catacomb/blob/master/CATASM....</a><p>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.<p>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".<p><a href="https://github.com/FlatRockSoft/Hovertank3D/blob/master/IDASM.ASM#L698" rel="nofollow">https://github.com/FlatRockSoft/Hovertank3D/blob/master/IDAS...</a><p>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.<p>The same year also saw the release of Keen Dreams, in which only the table-based RNG survives:<p><a href="https://github.com/keendreams/keen/blob/master/id_us_a.asm" rel="nofollow">https://github.com/keendreams/keen/blob/master/id_us_a.asm</a><p>(The state variables of the LFG are still defined, but the code is missing.)
There was a post about tampering with randomness in Doom some time ago with some interesting hn comments explaining the reason for this design: <a href="https://news.ycombinator.com/item?id=9429889" rel="nofollow">https://news.ycombinator.com/item?id=9429889</a>
I hope I don't sound too dumb, but how does it work, exactly? It doesn't look random to me, more like an unordered (but repeating) sequence..
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.
Curious. Just eyeballing I see there's no 1, 2 and 222 are repeated as well as 36 and 136. There are probably more.<p>If there's a purpose behind the table being constructed with those omissions/repetitions it's lost on me.
Interestingly, Half-Life (released in 1998) uses a slightly more complex table-based generator:<p><a href="https://github.com/ValveSoftware/halflife/blob/master/dlls/util.cpp" rel="nofollow">https://github.com/ValveSoftware/halflife/blob/master/dlls/u...</a><p>Note that this is only used for certain parts of the game. For others it uses a closed source non-table based generator.
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.