Assigning New SYstem.Randoms in a Loop?

I am restructuring some of my roguelike game so that it is generated using seeds so you can repeat or share runs. The way my generation is set up I am creating multiple RNG using System.Random to handle different systems so that there is no "cross-contamination" between the generators.

The most efficient way to declare these generators seems to be a For loop but for some reason, I cannot get the declaration to work in it. If I declare each generator separately like this outside of a loop it works fine.

Code (CSharp):

1.         seed += 1;
2.         rndDungeon = new System.Random(seed);
3.         seed += 1;
4.         rndCombat = new System.Random(seed);
5.         seed += 1;
6.         rndTrap = new System.Random(seed);

There will end up being a few more generators in the game so I would prefer to use a loop, although I know it is not necessary. Any ideas? Here is the code I have set up to declare within the loop.

Code (CSharp):

1.         seed = Environment.TickCount;
2.  
3.         _rndGenerators.Add(rndDungeon);
4.         _rndGenerators.Add(rndTrap);
5.  
6.         for (int i = 0; i < _rndGenerators.Count; i++)
7.         {
8.             seed += 1;
9.             _rndGenerators[i] = new System.Random(seed);
10.         }

 

Your second bit of code looks good to me, what is it about it that you can't get to work?

 

Looking at your code I see you add 'rndDungeon' and 'rndTrap' to the list '_rndGenerators'. Thing is I don't see these variables instantiated... but instead you overwrite indices 0 and 1 of _rndGenerators to a new Random.

Are you expecting 'rndDungeon' and 'rndTrap' to be equal to the 'Random' that is at 0 and 1 respectively in the list?

Because, if so, that's not how variable referencing works. Maybe something like this instead?

Code (csharp):

1.  
2. seed = Environment.TickCount;
3.  
4. for(int i = 0; i < 2; i++)
5. {
6.     seed++;
7.     _rndGenerators.Add(new System.Random(seed));
8. }
9.  
10. rndDungeon = _rndGenerators[0];
11. rndTrap = _rndGenerators[1];
12.  

 

The Dungeon Generates correctly but the seed doesn't ensure that the generation is the same for some reason. Using the individual declarations (rndDungeon = new System.Random(Seed)) always creates the dungeon the same with the same seed.

However, using the loop you get different results each time even with the same seed.

 

Ah, I think @lordofduct got it. I didn't even catch that.

 

@lordofduct Great catch. Your improved code seems to work great! More testing is still needed but I think you solved it, thanks a bunch!

 

Note that 'System.Random' is not guaranteed to create the same sequence from platform to platform. Not even from version to version of .net/mono.

This is what I use for a platform independent rng that is guaranteed to work across all platforms:

Code (csharp):

1.  
2.         /// <summary>
3.         /// A simple deterministic rng using a linear congruential algorithm.
4.         /// Not the best for security, but fast and effective for deterministic rng for games.
5.         ///
6.         /// Various known parameter configurations are included as static factory methods for ease of creating known long-period generators.
7.         /// See the wiki article for a list of more known long period parameters: https://en.wikipedia.org/wiki/Linear_congruential_generator
8.         /// </summary>
9.         public class LinearCongruentialRNG : IRandom
10.         {
11.  
12.             #region Fields
13.  
14.             private ulong _mode;
15.             private ulong _mult;
16.             private ulong _incr;
17.             private ulong _seed;
18.  
19.             #endregion
20.  
21.             #region CONSTRUCTOR
22.  
23.             public LinearCongruentialRNG(long seed, ulong increment, ulong mult, ulong mode)
24.             {
25.                 _mode = System.Math.Max(1, mode);
26.                 _mult = System.Math.Max(1, System.Math.Min(mode - 1, mult));
27.                 _incr = System.Math.Max(0, System.Math.Min(mode - 1, increment));
28.                 if (seed < 0)
29.                 {
30.                     seed = System.DateTime.Now.Millisecond;
31.                 }
32.                 _seed = (ulong)seed % _mode;
33.             }
34.  
35.             #endregion
36.  
37.             #region IRandom Interface
38.  
39.             public double NextDouble()
40.             {
41.                 _seed = (_mult * _seed + _incr) % _mode;
42.                 return (double)_seed / (double)_mode;
43.             }
44.  
45.             public float Next()
46.             {
47.                 _seed = (_mult * _seed + _incr) % _mode;
48.                 return (float)_seed / (float)_mode;
49.             }
50.  
51.             public int Next(int size)
52.             {
53.                 _seed = (_mult * _seed + _incr) % _mode;
54.                 return (int)(size * ((double)_seed / (double)_mode));
55.             }
56.  
57.             public int Next(int low, int high)
58.             {
59.                 _seed = (_mult * _seed + _incr) % _mode;
60.                 return (int)((high - low) * ((double)_seed / (double)_mode)) + low;
61.             }
62.  
63.             #endregion
64.  
65.             #region Static Factory
66.  
67.             public static LinearCongruentialRNG CreateMMIXKnuth(long seed = -1)
68.             {
69.                 return new LinearCongruentialRNG(seed, 1442695040888963407, 6364136223846793005, ulong.MaxValue);
70.             }
71.  
72.             public static LinearCongruentialRNG CreateAppleCarbonLib(int seed = -1)
73.             {
74.                 return new LinearCongruentialRNG(seed, 0, 16807, 16807);
75.             }
76.  
77.             public static LinearCongruentialRNG CreateGLibc(int seed = -1)
78.             {
79.                 return new LinearCongruentialRNG(seed, 12345, 1103515245, 2147483648);
80.             }
81.  
82.             #endregion
83.  
84.         }
85.  

It's based on the linear congruential algorithm:
https://en.wikipedia.org/wiki/Linear_congruential_generator

 

@lordofduct I just received the notification for your custom RNG, for some reason it was delayed. I "understand" most of what you have posted but I do not get the Static Factory part. If you don't mind could you explain slightly why you are creating different RNGs? Say if I wanted to create a new rng with a custom seed, which one would I call? The CreateMMIXKnuth, CreateAppleCarbonLib, or the CreateGLibc?

RNG is all pretty foreign to me so I am kind of just looking for a simple way to implement it into my game, but I don't fully understand the method behind it. I am working on studying it a bit so I understand it more but right now I am still a novice at this stuff.

Thanks in advance.

 

Whichever one you like... just be consistent since each one is only deterministic to itself. MMIXKnuth does not create the same sequence as AppleCarbonLib.

As for the difference, if you go to the wiki article I linked about Linear Congruential Generators it'll explain it in much better detail than me.

But to sum it up, the algorithm is value independent. The algorithm basically just being:
next = (mult * next + incr) % mode

You can put any values in for mult, next (seed), incr, and mode and get different sequences. Thing is not all sequences are created equal. Some are better than others. Some have longer periods, better distribution, etc.

Over the years different people have come up with parameters that create more satisfactory sequences (a list of like 30 common ones can be found in the wiki article I linked). I included a couple as static factories.

MMIXKnuth - my personal preferred. It has a huge period with decent distribution. And it's from Knuth... I like Knuth.

AppleCarbonLib - it's a small range sequence, really old school. I don't know... maybe you want an old school small sequence for an old school game.

Glibc - cause it's from glibc, one of the most ubiquitous c libraries out there... this means if you wrote some C code, used the glibc library, used the 'rand' method from that library, and compiled it with GCC. Well you can have a C# side deterministic LCG rng to match sequence to your c code.

...

The usefulness of having them as static factories is you don't have to memorize the parameters for each of them. You just use the one you want.

Also, if you wanted to add a different set of parameters (say you like one of the other libraries in that list in the wiki article)... just add it as a static factory method and call that one instead.

...

Mind you LCG is not the best rng out there, far far far far far from. It's not strong enough for cryptography, it's distribution is not equal across the entire period (rather it has linear phases, hence the name linear congruential, see the wiki article for visual reference), and they can usually be easily predicted after a short sequence.

visual ref, you can see over time the sequence results in linear streaks across the number space. A better rng would be smoother, filling in completely rather than with streaks:


But for games... so what?

It's fast, simple, gets the job done, and is deterministic.

 

Man, you're awesome @lordofduct ! I really appreciate the help you have been. I think I will implement something similar to this once I finish with another system I am currently busy with for my game.

Cheers!

 

For games the choice of a good PRNG is very important because the game mechanics depend on it. Bad PRNGs will negatively affect the game mechanics. Because good non-cryptographic PRNGs are still very simple to implement, it makes no sense to use something weak.

An example of a weak PRNG is your implementation of the LCG PRNG. LCGs suffer from extremely weak least significant bits, and that's exactly what you're using without adding anything to them to strengthen them.

You're also not using a modulus of 2^64, but rather 2^64-1 (ulong.MaxValue). Since you're using 64bit integers you don't need the modulus operator (integer multiplications are modulus 2^nr of bits). This is important, because not using a power of two as the modulus creates extra bias. If, for example, you'd use a modulus of 15, then the generator is likely to output 0 twice as often as the other values (1 to 14);

To strengthen those uselessly weak least significant bits you can use xorshift:

Code (csharp):

1. lcg = lcg * 0x5851f42d4c957f2d + 123456789; // increment can be any odd number
2. result =  lcg ^ (xo_lcg >> 32); // xorshift

This is still not stellar, but vastly better already.

If you want something that's actually really good and passes various really stringent tests, and is still really simple, then PCG is a very good choice:

Code (csharp):

1. class PCG
2. {
3.    public ulong state, inc;
4.  
5.    public PCG(ulong seed = 0, ulong stream = 1)
6.    {
7.        state = seed;
8.  
9.        if (seed == 0)
10.            state = (ulong)DateTime.UtcNow.Ticks;
11.  
12.        inc = stream | 1;
13.    }
14.  
15.    public uint Next()
16.    {
17.        ulong oldstate = state;
18.  
19.        state = oldstate * 6364136223846793005 + inc;
20.  
21.        uint xorshifted = (uint)(((oldstate >> 18) ^ oldstate) >> 27);
22.        int rot = (int)(oldstate >> 59);
23.  
24.        return (xorshifted >> rot) | (xorshifted << (64 - rot));
25.    }
26. }

PCG website: http://www.pcg-random.org/

PCG accepts a 64 bit seed and a 64 bit increment (has to be odd). The increment (called steam in the code above) gives you independent (non-overlapping) sequences of numbers (streams). You can now use the same seed and a different increment for each generator instance.

The downside of this generator is that the output is 32 bit.

Another option is xoshiro. Author's website is here: http://xoshiro.di.unimi.it/

In this day and age the use of weak PRNGs isn't necessary anymore and should be avoided especially seeing how the programming effort required for implementing strong PRNGs is negligible.

 

That's opinion.

As is it my opinion to think LCG is perfectly fine.

Case in point... glibc thinks it's fine. We all have opinions.

Yeah, you're not telling me anything new. I specifically clarified that LCG isn't the best on multiple occassions and included links to how it's implemented and it too covers that fact.

You're correct, I am using 2^64 - 1... oops. Sorry.

Sure... but then it's not LCG.

Then it's PCG.

Which I COULD also use.

But again... that's all subjective.

What if I like it though?

As I pointed out with the applecarbonlib, what if you want it. If you want to mimic glibc?

I make 90's style low-poly videogames mimicking Sega Saturn and Playstation style games. Maybe I like old school.

But yes, at OP, PCG is also an alternative. You're welcome to use that as well.

 

No, this isn't an opinion, it's a fact. Weak PRNGs don't have good statistical properties. This can cause, among other things, the number of one and zero bits not being close to equal.

This can lead to things like, for example in an RPG, hit chance calculations being off, which means that the stat screen will show a different hit chance than you're actually getting. It might say that the hit chance is 80%, while in reality the player is getting 60% hits.

Then there's also a problem with PRNGs that have a large state space, like Mersenne Twister. If it's state contains mostly zero bits, it can take tens of thousands of calls before you get statistically good output, and is therefore not recommendable for games (that's also not what it was designed for, and Mersenne Twister has been superseded by better, faster and simpler PRNGs anyway). For the RPG example this means the player thinks they're getting 80% hit chance but most of their hits will miss.

You have to look at this from the player's perspective, because game development is ultimately about the player experience.

If you want better output, then you have no choice but add add something like xorshift, because LCGs have extremely weak least significant bits. For example, bit zero will toggle between zero and one!

The problem in this case that we don't have access to the most significant bits of the multiplication, because in C# 64 bit multiplications are modulus 2^64, while multiplying two 64 bit numbers should yield a 128 bit result, and it's exactly the bits that we we don't have access to that are the strongest.

It really isn't. It's about picking the right algorithms for the job. If you want quality then you need good algorithms.

What I don't get is why you'd go for something you know is bad while good PRNGs are so simple to implement.

Sorry, but I have to make a point of this because other people will be reading this as well, and they may not be aware of just how problematic LCGs can be, while there are better, fool proof, options available that are very simple to implement.

 

No... it's a fact that they have less even distribution resulting in less optimal statistical properties. I fact I agreed as being correct.

It being good or bad for a game is opinion. An opinion we both don't necessarily agree on. Which is fine. I'm not trying to convince you otherwise.

Yet video games have done it for years without a single gamer really noticing it unless they're freaks about the game. Which sure, if you're making the next WoW... probably should anticipate for statistical freaks.

Bringing up Mersenne is conjecture. What does it have to do with my opinion about LCG in games? (that's rhetorical)

Yep... and that's subjective.

'better' is subjective

Because I want to.

Note, I will repeat myself... I never said that this was the best algorithm. I specifically stated it's not the best, and specifically included sources that repeated that fact. I included VISUAL REPRESENTATION of the the problem with the statistical distribution of the algorithm.

Now... sure, maybe I should have included others as well. I actually have several PRNG wrappers written in my code base (all using my IRandom interface, hence its existence).

I shared LCG here as a sort of introduction to the concept of RNG since its algorithm is stupid stupid stupid simple (by which I mean the math involved is so basic that a non-math person can figure it out with a short amount of effort). It's the first one I learned over 15 years ago. Sorry my historical education bias took me over.

But I included the "but it's not the best" becuase there are other RNGs out there that people can look into when they want to.

Cool, and I hope they read up on your sources as well.

Sorry I didn't expel more effort on this and it upset you so much that you had to make your 3rd post ever about it.

But mind you I made my first post on a break at work over a week ago in a very short period of time. Then my followup was just an answer to OPs question, within that context. It was a multi-paragraph response and I highlighted the caveats. Sure I could have gone on longer with a tome of information, but I try to cut myself back a bit becuase people get very annoyed around these parts with my "walls-o-text" sometimes. So instead I summed that aspect up by listing the caveats and espousing my opinion that it's not a big deal.

Because I don't think it is.

And yes... that's opinion.

...

On an aside, I do thank you for pointing out that glaring flaw in my MMIX LCG implementation... I did not account for the sig value range of double, as well as transposing the mode of MMIX as 2^64-1 instead of the correct 2^64. I've since corrected my personal source code as a result.

With all that said... I don't need to argue with you on this topic anymore (not argue in the sense of fight, but in the sense of pedantically debating what opinion is).

At other readers... heed the sources thorham brings up. There are OTHER RNG algorithms out there, and they linked them. If you're looking for more even distribution, you can look into using one of them. Or you could use the built in .Net one, or the built in Unity one, or any number of them out there at your disposal.

Hopefully that satisfies your quibble thorham.

 

It was an example that shows a potential problem with choosing the wrong PRNG for the job.

Perhaps, but not when things don't work the way they're supposed to.

Microsoft's Random class is broken (Microsoft has acknowledged this). Not a widely known fact.

Anyway, I only made such a big deal out of this because of my obsession with high quality PRNGs