7 ms·
The random number generator of DOOM
- tbrake 11y agoCurious. 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.
- Zikes 11y agoMaybe they were chosen at random?
- tbrake 11y agoLooks like it by the note in the other comment by serf. I had begun to wonder if certain values caused issues when used in code and it was deemed easier to just not get certain values back. That's crazy talk though.
- detaro 11y agoNaa, that sounds like something game developers totally would do.
- mrnohr 11y agohttp://bit.ly/1NxaZrC http://bit.ly/1NxaZrC A few numbers like 239 and 242 occur 3 times. And a bunch do not occur at all.
- Scarblac 11y agoObviously numbers like 222 and 136 are way more random than 1.
- GaiusCoffee 11y agoI 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..
- serf 11y agoQuoted from the Doom wikia: " 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. " [0]: http://doom.wikia.com/wiki/Pseudorandom_number_generator http://doom.wikia.com/wiki/Pseudorandom_number_generator edit: here's a much better article contributed by user aciuix in this thread : http://doomwiki.org/wiki/Pseudorandom_number_generator http://doomwiki.org/wiki/Pseudorandom_number_generator
- paulannesley 11y agoTL;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().
- kdrakon 11y agoFor a video game, I suppose it was random 'enough'.
- paulannesley 11y agoRelated: http://jmtd.net/log/deterministic_doom/ http://jmtd.net/log/deterministic_doom/ Via: https://news.ycombinator.com/item?id=9429889 https://news.ycombinator.com/item?id=9429889
- naugtur 11y agoHaha, just wanted to link that. To draw people's attention: this article explores results of replacing this array of numbers with predictable values.
- deleted 11y ago[deleted]
- perlin 11y agoIn 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 https://github.com/caseman/noise/blob/master/perlin.py Excellent talk by its creator: http://www.noisemachine.com/talk1/ http://www.noisemachine.com/talk1/
- zzalpha 11y agoAnd 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.
- perlin 11y agoGood point! Here's two OpenGL animations across multiple 1-dimensional vertices: Perlin- https://i.imgur.com/ROww6bw.gif https://i.imgur.com/ROww6bw.gif Random- https://i.imgur.com/EurTdaZ.gif https://i.imgur.com/EurTdaZ.gif
- aerique 11y agoI animated these tentacles using Perlin noise: http://www.youtube.com/watch?v=RMwJXP8EOU4 http://www.youtube.com/watch?v=RMwJXP8EOU4 (By manipulating the available variables in a Bezier curve.)
- DougMerritt 11y agoIs your account name homage?
- 11y ago
- i_have_to_speak 11y agoMandatory xkcd mention: https://xkcd.com/221/ https://xkcd.com/221/
- userbinator 11y agoThat 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.
- Renaud 11y agoI 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.
- paulannesley 11y agoPresumably they were optimizing for CPU cycles rather than RAM, and the 256 bytes that it does consume isn't much in the scheme of a game like Doom. This must be pretty fast (and compact) code: rndindex = (rndindex+1)&0xff; return rndtable[rndindex]; The example C code at https://en.wikipedia.org/wiki/Linear_feedback_shift_register https://en.wikipedia.org/wiki/Linear_feedback_shift_register looks like it would compile to more bytes, and require more CPU cycles to execute. Based on https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator it seems LCGs also micro-optimize for memory rather than CPU performance. 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.
- vortico 11y agoWhat does the P and M stand for in the function names?
- mahouse 11y agoP for "Game logic/behaviour", M for "Miscellaneous". http://doomwiki.org/wiki/Doom_source_code http://doomwiki.org/wiki/Doom_source_code
- megablast 11y agorandom_number = 4// just tested it with a dice
- oneeyedpigeon 11y agoFor anyone missing the reference, here's the obligatory xkcd: https://xkcd.com/221/ https://xkcd.com/221/
- netheril96 11y agoYet another random number generator that depends on global mutable state and therefore unsafe to be used in multithreaded context.
- pjc50 11y agoDOOM was, of course, single-threaded and built to run on the single-core CPUs of the time.
- netheril96 11y agoPeople 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.
- Tepix 11y agoYou do realize this code is around 20 years old?
- netheril96 11y agoI did not. Perhaps I was being too harsh to criticize this particular project.
- pgy 11y agoThere 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 https://news.ycombinator.com/item?id=9429889
- pdw 11y agoThere'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.ASM#L397 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/IDASM.ASM#L698 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 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.)
- tmoertel 11y agoThat's a fascinating history. Thanks for tracing it back. According to a comment in the Catacomb source, the LFG logic was derived from a macro supplied with the Merlin assembler for Apple 2 GS computers: ;this routine was converted from ;the Random macro on Merlin GS
- xiaq 11y agoIf you realize that any RNG on [0,256) always has a cycle of at most 256, this is actually pretty decent.
- eterm 11y agoIs that true? 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.
- deathanatos 11y ago> Is that true? 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.) [1]: https://en.wikipedia.org/wiki/Pseudorandom_number_generator#Periodicity https://en.wikipedia.org/wiki/Pseudorandom_number_generator#...
- xiaq 11y agoThanks for pointing this out. I have confused the size of output with the size of state.
- sytelus 11y agoThis 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.
- TomGullen 11y agoInterested as to why this method was picked over say doing "MSPlayed % 256"
- deathanatos 11y agoAssuming 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…) Also see this post: https://news.ycombinator.com/item?id=9429889 https://news.ycombinator.com/item?id=9429889 [1]: https://news.ycombinator.com/item?id=9810073 https://news.ycombinator.com/item?id=9810073 [2]: http://doomwiki.org/wiki/Pseudorandom_number_generator http://doomwiki.org/wiki/Pseudorandom_number_generator
- TomGullen 11y agoThat makes sense, thanks!
- frontfor 11y agoInterestingly, Half-Life (released in 1998) uses a slightly more complex table-based generator: https://github.com/ValveSoftware/halflife/blob/master/dlls/util.cpp 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.