How unpredictable can Doom get?

[printz]

Suppose I make a custom attack in a PrBoom mod using the DEHACKED lump. I want the attack to go like this:

- do melee damage (0 tics, go forward)
- RandomJump (where=previous frame; probability=n/256) (0 tics, go forward)
- exit to the chase states.

What type of random number generator do WinMBF, PrBoom, PrBoom+ and Eternity use? Do the generated sequences prevent the game from overflowing? Can I go safe by choosing a probability below a danger threshold?

[RestlessRodent]

The same as Doom. Probability in this case is just being compared to the number returned from P_Random(), either less than or greater than for jumping. So if it's P_Random() < Probability, then if P_Random() returns 127 and probability is 92 then it will never happen.

probability is either limited to an int or the range of 0-255. In reality anything not within the range of P_Random() is undefined.

[Graf Zahl]

Most Boom descendants use a real RNG, not Doom's 256 entry table. Even though it's unlikely you can never rule out a bad sequence that causes overflows. It's inherently dangerous to rely on the distribution of the values of random number generators unless you know exactly what they will produce.

[Quasar]

Compiled on Visual C++ 6.0, Eternity has 12 KB of stack space. The stack seems to grow by an average of 4 words for each function call, though this of course varies per function. The sequence you are describing involves the following stack trace:

P_MobjThinker
P_SetMobjState
  A_SomeAttack (returns)
  A_RandomJump
    P_SetMobjState
       A_SomeAttack (returns)
       A_RandomJump
         P_SetMobjState
         ....

The stack grows by two function calls everytime A_RandomJump returns to the previous state. If we assume that P_SetMobjState uses a large amount of stack space (let's say 32 bytes, which I don't believe it does), that gives us 384 recursions.

Let's say that the chance of jumping is something in the mid range such as 96/256. Then the chance of jumping every time 384 calls in a row is 2.6792103203592542266441230547023e-164. I'd not bet on those odds.

[Grazza]

printz said:

What type of random number generator do WinMBF, PrBoom, PrBoom+ and Eternity use?

Remember that if you use prboom+ in one of its vanilla complevels (or an equivalent in another port, if applicable), it will use the same RNG as Doom2.exe.

[printz]

Anyway, if Boom-based ports prefer to use a real RNG, this idea wouldn't be feasible any more. I was hoping for the pseudorandom table, because with that I would have been able to calculate the maximum possible iterations easily, and rely on that.

[Quasar]

printz said:

Anyway, if Boom-based ports prefer to use a real RNG, this idea wouldn't be feasible any more. I was hoping for the pseudorandom table, because with that I would have been able to calculate the maximum possible iterations easily, and rely on that.

But you can rely on it anyway. One chance in 2 * 10^164 is such a vanishingly small probability that you'd have a better chance of stirring all the matter in the universe together into a pot and then expecting a specific proton to end up on the end of your spoon when you're done.

There could technically be something wrong with Lee's linear congruential random number generator that causes it to have a specific sequence of numbers more than 384 in length that are all greater than any given number you choose, but empirical testing thus far hasn't uncovered any such sort of glaring flaw.

In my math I used conservative estimates just to show how ludicrous it is. If you use more realistic estimates, considering the number of barrels it took me to stack fault EE by causing simultaneous explosions, and that had a *much* faster growing stack, you get something that is closer to 1000 iterations.

The probability of no return without a jump in 1000 iterations may as well be zero. I think you're perfectly safe to do this. If you're not comfortable with it still, the next best thing is to make a chain of RandomJumps which go to attack sequences of various fixed lengths. This avoids both the more-or-less impossible infinite loop, as well as the potential problem of feeling a lag in the game play if it pauses to calculate too many sequential attacks all at once (this would start to kick in well below the theoretical limit on stack space).

[Graf Zahl]

Being safe and being predictable is not the same. With Doom's table driven RNG you can easily determine all possible iterations and base your settings on it.

With a standard RNG there's far too many possibilities to do anything that depends on max/min number of iterations.