Hacker News Reader

Comment by GaiusCoffee | Hacker News Reader

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

View on HN

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

edit: here's a much better article contributed by user aciuix in this thread : http://doomwiki.org/wiki/Pseudorandom_number_generator

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.

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.

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?

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.

No, it's a bitwise AND operation. The line adds one to prndindex modulo 256.

Incrementing the index and limiting the value to 0-255 (AND 0xff)?

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 [1] I'm not 100% positive that's how it's implemented with an IDIV instruction.

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.

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"

OK, thanks for the clarification everyone!

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

Reply on news.ycombinator.com