Doom's random number generator

I'm using a random number table (0 to 255) for a random number generator for speed and so that every playthrough is identical, and I was thinking a fun homage would to plug in the exact table from Doom.

Does anyone know where I could find it?

 

Nevermind, found it.

Sorry, please delete post.

 

There isn't any point, as random generator is invisible and nobody will ever notice it being the same.

Light flickering, on other hands....
https://www.pcgamer.com/half-life-a...like-they-did-in-quake-almost-25-years-later/
https://www.reddit.com/r/HalfLife/comments/nwrtol/valve_still_uses_the_same_light_flicker_pattern/

 

Of course no one will notice it.

But they will talk about it if they know about it. And I’m all for anyone talking about my game.

And thanks! Definitely got to copy their flicker!

 

Oh, and another big reason I want to use this method is for speed runners and because it’s WAY cheaper than using the built in RNG.

As an example I have a shotgun that will make 19 pellets.

Each pellet will have two random numbers for the pitch and two random numbers for the yaw, then another for the rotation of the entire thing.

Thats 77 random numbers I need to generate in a frame (assuming I don’t want to do it in chunks).

If I want thousands of enemies on screen I can’t be doing expensive RNG.

 

If my memory serves me right, mersenne twister is fast, and unless you're doing cryptography ciphers, most of the PRNGs aren't slow either.

https://en.wikipedia.org/wiki/Mersenne_Twister

Regarding shotgun pellet, it takes 1-2 random numbers to calculate a random direction in 2d, and 2-3 random numbers in 3d. You shouldn't need five random number per pellet.

 

For a shotgun, it probably ought not be random at all, especially if you want multiplayer, and this stuff is never a performance issue, never seen a situation where it was in all my years coding.

Because you'd be doing the random numbers in one frame, not every frame. Even if 16 people all fired shotguns somehow on the exact same frame, it wouldn't be more than 32 random number calculations for the particle systems, which would all be running at different times anyway if purely visual.

This is premature optimisation at it's absolute finest.

Speed runners mostly do games which don't have deterministic maths, so it's pointless if that's your goal.

If you want to ensure each and every run is identical it will be pretty much impossible without a deterministic math library, but behaviour can be pretty close each run (but not the same) if you use an array of numbers.

The one reason I would be using a look up table for random numbers is because I can check if it feels and plays nicely, and works in mp well (assuming it would be required).

 

Is that just an array of preloaded random numbers that you endlessly cycle through every time you need a random value? That sounds like some super 90s coding right there.

 

Yeah, it's not actually a bad idea if you want to have a good spread of numbers that play nicely. It's common with random numbers, like shaking effects and so on to get a duff streak that looks bad, so in this case a deterministic or stored array of numbers can be guaranteed to look nice. It won't be guaranteed to play the same each time without everything else also having that though.

If it's the goal though, setting a seed is enough.

 

All I’m doing is cycling through an array of pre-shuffled numbers, and alternating between A method that moves one space at a time, and another method that moves three spaces at a time.

As for the pellets, I’m adjusting two separate rotations, but I need 2 numbers so it has a bell curve towards the middle.

Like rolling 2 six sided dice will result in a bell curve towards 6 and 7.

 

My memory of original Doom is the basic shotgun fired 4 pellets with a random shot pattern on a flat plane (randomly placed left to right). It sounds like @Not_Sure is more interested in duplicating the original Doom behavior in as performant way as possible than what is really optimal for game play or realistic.

 

Ah, good point. Better not leave anything to chance when it comes to UX.

 

Correct.

It’s not just about shotguns.

It’s about repeatable patterns and extremely cheap RNG.

Also with two numbers inputted into the RNG for one outcome that means there’s 65,536 possible outcomes.

I want it “random”, but not RANDOM random, if that makes since.

I want two players on two different systems having the exact same setup, performing the exact same moves, will have the exact same outcome.

And as for the shotgun, the pellet will be just “random” enough to not have a big ugly repeating pattern, but also dependable where luck means that every once in a while an enemy might need an extra shot.

And I definitely don’t want an outcome like Doom 3’s trash shotgun that is a complete crap shoot.

 

BTW, I already coded it last night.

I’ll post it when I get home so you can see what I’m talking about.

 

I understand that it's a for-fun project and all that, but I wonder if you're getting a bit too into the 1990's mood in that regard?

The minimum spec to run original Doom was a 386 with 4mb of RAM. According to the Steam Hardware Survey a single core on today's most common CPUs is >70 times faster than that in clock speed alone and single core machines are now rare. Plus, CPU performance improvements for the last couple of decades have largely been independent of clock speed.

Today's performance and power constraints on computing are radically different to those of 1993. There are other parts of our computers which haven't seen such consistent and dramatic increases in performance, and memory access speed is one of those.

Back in 1993 a look-up-table probably was a truly efficient way to get random numbers. But is that true today?* I don't know, but I wouldn't assume either way without testing.

Please note that I'm not suggesting that you shouldn't do this. I completely understand that writing efficient code can be fun in and of itself, and hippo has already given some great other reasons to use tables rather than generators. But if "extremely cheap" is your goal then you really can't rely on approaches developed for hardware from 1993.

* Judging by that article alone I would guess the answer is "absolutely not", but note that the article is a few years old, and the trend graph in there is older again.

 

Code (CSharp):

1. using System.Collections;
2. using System.Collections.Generic;
3. using UnityEngine;
4.  
5. public class GameStatics : MonoBehaviour
6. {
7.     static int p_rngIndex1 = 0;
8.     static int p_rngIndex2 = 0;
9.     static int e_rngIndex1 = 0;
10.     static int e_rngIndex2 = 0;
11.  
12.     static int[] rngTable = new int[256]
13.     {0,   8, 109, 220, 222, 241, 149, 107,  75, 248, 254, 140,  16,  66 ,
14.   74,  21, 211,  47,  80, 242, 154,  27, 205, 128, 161,  89,  77,  36 ,
15.   95, 110,  85,  48, 212, 140, 211, 249,  22,  79, 200,  50,  28, 188 ,
16.   52, 140, 202, 120,  68, 145,  62,  70, 184, 190,  91, 197, 152, 224 ,
17.   149, 104,  25, 178, 252, 182, 202, 182, 141, 197,   4,  81, 181, 242 ,
18.   145,  42,  39, 227, 156, 198, 225, 193, 219,  93, 122, 175, 249,   0 ,
19.   175, 143,  70, 239,  46, 246, 163,  53, 163, 109, 168, 135,   2, 235 ,
20.   25,  92,  20, 145, 138,  77,  69, 166,  78, 176, 173, 212, 166, 113 ,
21.   94, 161,  41,  50, 239,  49, 111, 164,  70,  60,   2,  37, 171,  75 ,
22.   136, 156,  11,  56,  42, 146, 138, 229,  73, 146,  77,  61,  98, 196 ,
23.   135, 106,  63, 197, 195,  86,  96, 203, 113, 101, 170, 247, 181, 113 ,
24.   80, 250, 108,   7, 255, 237, 129, 226,  79, 107, 112, 166, 103, 241 ,
25.   24, 223, 239, 120, 198,  58,  60,  82, 128,   3, 184,  66, 143, 224 ,
26.   145, 224,  81, 206, 163,  45,  63,  90, 168, 114,  59,  33, 159,  95 ,
27.   28, 139, 123,  98, 125, 196,  15,  70, 194, 253,  54,  14, 109, 226 ,
28.   71,  17, 161,  93, 186,  87, 244, 138,  20,  52, 123, 251,  26,  36 ,
29.   17,  46,  52, 231, 232,  76,  31, 221,  84,  37, 216, 165, 212, 106 ,
30.   197, 242,  98,  43,  39, 175, 254, 145, 190,  84, 118, 222, 187, 136 ,
31.   120, 163, 236, 249};
32.  
33.     public static int PlayerRNG1(){
34.         p_rngIndex1 += 1;
35.         if (p_rngIndex1 > 255) p_rngIndex1 = 0;
36.         return rngTable[p_rngIndex1];
37.     }
38.  
39.     public static int PlayerRNG2()
40.     {
41.         p_rngIndex2 += 3;
42.         if (p_rngIndex2 > 255) p_rngIndex2 = 0;
43.         return rngTable[p_rngIndex2];
44.     }
45.  
46.     public static int EnemyRNG1()
47.     {
48.         e_rngIndex1 += 1;
49.         if (e_rngIndex1 > 255) e_rngIndex1 = 0;
50.         return rngTable[e_rngIndex1];
51.     }
52.     public static int EnemyRNG2()
53.     {
54.         e_rngIndex2 += 3;
55.         if (e_rngIndex2 > 255) e_rngIndex2 = 0;
56.         return rngTable[e_rngIndex2];
57.     }
58. }
59.  

Feel free to steal.

 

I've thought about this a lot. Do you think there's a possibility for conflicts when multiply different things pull random numbers from the same table as opposed to each thing or at least each task having its own table? Think of to-hit-rolls in a tactics game. I'd want to use some kind of shuffle bag RNG to make things feel fair, but I would expect if I do that I also need to keep track of different number lists for e.g. shots that my guys take vs. shots that the enemy guys take, to ensure that both teams hit exactly half of 50% hit chance shots and not e.g. 40 vs 60 because both are pulling numbers from the same bag and one team pulled more low numbers accross the course of a fight.

 

If you look at the code at the bottom you’ll note there’s 4 different index tracking int’s.

One for the player that moves by 1 and another that moves by 3. Then one for enemies/environment that moves by 1 and another that moves by 3.

 

Man I thought there was something familiar about that flickering, but I just couldn't put my finger on it!

 

Boom!

Subconscious nostalgia.

 

Just in case - don't forget that OG Doom also used different rng for visuals.
So gamelogic rng is not altered when visuals or sounds are randomized.

 

Yup, thanks.

You’ll note I already have it in my code.

 

Yeah modern (desktop) CPU have memory access bottleneck, which is why cache miss is an issue. A typical RNG will probably take a seed then loop data on the register, which is the fastest memory available, while reading a table even in L1 cache is magnitude slower. For mobile micro joule is another bottleneck.