from Hacker News

The random number generator of DOOM

by danshapiro on 7/1/15, 4:01 AM with 74 comments

  • by perlin on 7/1/15, 4:49 AM

    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.

    Python implementation: https://github.com/caseman/noise/blob/master/perlin.py

    Excellent talk by its creator: http://www.noisemachine.com/talk1/

  • by pdw on 7/1/15, 8:18 AM

    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:

    https://github.com/FlatRockSoft/Catacomb/blob/master/CATASM....

    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".

    https://github.com/FlatRockSoft/Hovertank3D/blob/master/IDAS...

    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:

    https://github.com/keendreams/keen/blob/master/id_us_a.asm

    (The state variables of the LFG are still defined, but the code is missing.)

  • by paulannesley on 7/1/15, 4:23 AM

  • by pgy on 7/1/15, 7:40 AM

    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

  • by GaiusCoffee on 7/1/15, 4:23 AM

    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..

  • by sytelus on 7/1/15, 8:39 AM

    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.

  • by tbrake on 7/1/15, 4:22 AM

    Curious. Just eyeballing I see there's no 1, 2 and 222 are repeated as well as 36 and 136. There are probably more.

    If there's a purpose behind the table being constructed with those omissions/repetitions it's lost on me.

  • by megablast on 7/1/15, 7:25 AM

    random_number = 4// just tested it with a dice

  • by frontfor on 7/1/15, 9:23 AM

    Interestingly, Half-Life (released in 1998) uses a slightly more complex table-based generator:

    https://github.com/ValveSoftware/halflife/blob/master/dlls/u...

    Note that this is only used for certain parts of the game. For others it uses a closed source non-table based generator.

  • by TomGullen on 7/1/15, 8:52 AM

    Interested as to why this method was picked over say doing "MSPlayed % 256"

  • by userbinator on 7/1/15, 5:49 AM

    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.

  • by kdrakon on 7/1/15, 4:23 AM

    For a video game, I suppose it was random 'enough'.

  • by vortico on 7/1/15, 6:40 AM

    What does the P and M stand for in the function names?

  • by i_have_to_speak on 7/1/15, 5:15 AM

    Mandatory xkcd mention: https://xkcd.com/221/

  • by xiaq on 7/1/15, 8:37 AM

    If you realize that any RNG on [0,256) always has a cycle of at most 256, this is actually pretty decent.

  • by netheril96 on 7/1/15, 7:28 AM

    Yet another random number generator that depends on global mutable state and therefore unsafe to be used in multithreaded context.