7 ms·

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

serf 11y ago
Quoted 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 ago
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().
- ethbro 11y ago
  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).
pygy_ 11y ago
That's the case with every pseudorandom number generator (ie any deterministic algorithm that spews "random" numbers). The period here is unusually short, but it is enough for the use case. If you want a non-predictable random bit source, you have to sample a quantum phenomenon using dedicated hardware.
veddox 11y ago
It is basically just that :-) What I don't understand is the following line: prndindex = (prndindex+1)&0xff; (I'm not a C programmer.) AFAIK, the &0xff is a pointer - but what precisely does it do?
- kaesve 11y ago
  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.
- pjc50 11y ago
  No, it's a bitwise AND operation. The line adds one to prndindex modulo 256.
- felhr 11y ago
  Incrementing the index and limiting the value to 0-255 (AND 0xff)?
- barsonme 11y ago
  It's not a pointer, it's a bitwise AND. It's essentially the same[0] as `prndindex = (prndinex+1) % 256`, except bitwise AND takes less effort to compute. Modulo is essentially[1]: `mod = a - b * (a / b)` unless the compiler can manage to use bitwise shifting/masks instead. Back when Doom was popular, the bitmask would have been much more efficient. [0] http://stackoverflow.com/q/3072665/2967113 http://stackoverflow.com/q/3072665/2967113 [1] I'm not 100% positive that's how it's implemented with an IDIV instruction.
  - derf_ 11y ago
    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 movl %edi, %edx sarl $31, %edx shrl $24, %edx leal (%rdi, %rdx), %eax andl $255, %eax subl %edx, %eax I.e., six instructions instead of one. This is still faster than using a divide.
ajuc 11y ago
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.

serf 11y ago

Quoted 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 ago

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

ethbro 11y ago
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).

pygy_ 11y ago

That's the case with every pseudorandom number generator (ie any deterministic algorithm that spews "random" numbers). The period here is unusually short, but it is enough for the use case. If you want a non-predictable random bit source, you have to sample a quantum phenomenon using dedicated hardware.

veddox 11y ago

It is basically just that :-) What I don't understand is the following line: prndindex = (prndindex+1)&0xff; (I'm not a C programmer.) AFAIK, the &0xff is a pointer - but what precisely does it do?

kaesve 11y ago
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.
pjc50 11y ago
No, it's a bitwise AND operation. The line adds one to prndindex modulo 256.
felhr 11y ago
Incrementing the index and limiting the value to 0-255 (AND 0xff)?
barsonme 11y ago
It's not a pointer, it's a bitwise AND. It's essentially the same[0] as `prndindex = (prndinex+1) % 256`, except bitwise AND takes less effort to compute. Modulo is essentially[1]: `mod = a - b * (a / b)` unless the compiler can manage to use bitwise shifting/masks instead. Back when Doom was popular, the bitmask would have been much more efficient. [0] http://stackoverflow.com/q/3072665/2967113 http://stackoverflow.com/q/3072665/2967113 [1] I'm not 100% positive that's how it's implemented with an IDIV instruction.
- derf_ 11y ago
  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 movl %edi, %edx sarl $31, %edx shrl $24, %edx leal (%rdi, %rdx), %eax andl $255, %eax subl %edx, %eax I.e., six instructions instead of one. This is still faster than using a divide.

ajuc 11y ago

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.