KervenGame · February 8, 2023 13:26 · Jul 3, 2022 · Feb 25, 2021 · Feb 25, 2021
diff --git a/Unity-XORShift.md b/Unity-XORShift.md
@@ -1,3 +1,4 @@
+Unity随机数算法，使用的是Xorshift128
 This is a partial C# implementation of `UnityEngine.Random` with (almost) 1-to-1 parity.
 
 Unity uses [Xorshift](https://en.wikipedia.org/wiki/Xorshift) for psuedorandom number generation. In particular Xorshift128, which uses a state consisting of four unsigned 32-bit integer values. The state is initialized in `UnityEngine.Random.InitState` using a signed 32-bit integer seed, which is shuffled around with a technique similar to the way a [Mersenne Twister](https://en.wikipedia.org/wiki/Mersenne_Twister#Initialization) is initialized.

diff --git a/Tests.cs → ~Tests.cs b/Tests.cs → ~Tests.cs
diff --git a/Tests.cs b/Tests.cs
@@ -0,0 +1,111 @@
+using UnityEngine;
+using System.Runtime.InteropServices;
+using Random = UnityEngine.Random;
+
+public class Tests : MonoBehaviour
+{
+    System.Text.StringBuilder sb = new System.Text.StringBuilder();
+
+    // Start is called before the first frame update
+    void Start()
+    {
+        UnityEngine.Random.InitState(1234);
+        XORShift128.InitSeed(1234);
+
+        // Print some ranged integers
+        // 0 to max
+        IntegerTests(0, int.MaxValue);
+        // 0 to min
+        IntegerTests(0, int.MinValue);
+        // Min to max
+        IntegerTests(int.MinValue, int.MaxValue);
+        // Max to min
+        IntegerTests(int.MaxValue, int.MinValue);
+        // Min to min (error)
+        IntegerTests(int.MinValue, int.MinValue);
+
+        // Print some floating points
+        for (int i = 0; i < 5; i++) AppendTestFloat(Random.value, XORShift128.NextFloat());
+
+        // Print some ranged floating points
+        // 0 to 100
+        FloatingPointTests(0f, 100f);
+        // 0 to 100000
+        FloatingPointTests(0f, 100000f);
+        // 0 to max (not accurate)
+        FloatingPointTests(0f, float.MaxValue);
+        // 0 to min (not accurate)
+        FloatingPointTests(0f, float.MinValue);
+        // Min to max
+        FloatingPointTests(float.MinValue, float.MaxValue);
+        // Max to min
+        FloatingPointTests(float.MaxValue, float.MinValue);
+        // Min to min
+        FloatingPointTests(float.MinValue, float.MinValue);
+
+        Debug.Log(sb.ToString());
+    }
+
+    void IntegerTests(int min, int max)
+    {
+        sb.AppendLine("--- " + min + " to " + max + " ---");
+
+        for (int i = 0; i < 5; i++)
+        {
+            int ur = UnityEngine.Random.Range(min, max);
+            int xr = XORShift128.NextIntRange(min, max);
+            AppendTestInt(ur, xr);
+        }
+    }
+
+    void FloatingPointTests(float min, float max)
+    {
+        sb.AppendLine("--- " + min + " to " + max + " ---");
+        for (int i = 0; i < 5; i++)
+        {
+            float ur = UnityEngine.Random.Range(min, max);
+            float xr = XORShift128.NextFloatRange(min, max);
+            AppendTestFloat(ur, xr);
+        }
+    }
+
+    void AppendTest(string a, string b)
+    {
+        var state = (RandomStateWrapper)UnityEngine.Random.state;
+        sb.AppendLine(state.v3.ToString().PadRight(15) + XORShift128.w.ToString().PadRight(15) + a.PadRight(15) + b.PadRight(15));
+    }
+
+    void AppendTestInt(int a, int b)
+    {
+        AppendTest(a.ToString(), b.ToString());
+    }
+
+    void AppendTestFloat(float a, float b)
+    {
+        AppendTest(a.ToString(), b.ToString());
+    }
+}
+
+[StructLayout(LayoutKind.Explicit)]
+public struct RandomStateWrapper
+{
+    [FieldOffset(0)] public Random.State state;
+    [FieldOffset(0)] public uint v0;
+    [FieldOffset(4)] public uint v1;
+    [FieldOffset(8)] public uint v2;
+    [FieldOffset(12)] public uint v3;
+
+    public static implicit operator RandomStateWrapper(Random.State aState)
+    {
+        return new RandomStateWrapper { state = aState };
+    }
+    public static implicit operator Random.State(RandomStateWrapper aState)
+    {
+        return aState.state;
+    }
+
+    public override string ToString()
+    {
+        return v0 + ", " + v1 + ", " + v2 + ", " + v3;
+    }
+}
diff --git a/Unity-XORShift.md b/Unity-XORShift.md
@@ -0,0 +1,151 @@
+This is a partial C# implementation of `UnityEngine.Random` with (almost) 1-to-1 parity.
+
+Unity uses [Xorshift](https://en.wikipedia.org/wiki/Xorshift) for psuedorandom number generation. In particular Xorshift128, which uses a state consisting of four unsigned 32-bit integer values. The state is initialized in `UnityEngine.Random.InitState` using a signed 32-bit integer seed, which is shuffled around with a technique similar to the way a [Mersenne Twister](https://en.wikipedia.org/wiki/Mersenne_Twister#Initialization) is initialized.
+
+This has been tested as far back as Unity 4.7.0f1, and as recent as Unity 2020.1.17f1.
+
+### Notes ###
+- Huge thanks to MoatShrimp for figuring out how Unity initializes the Xorshift state parameters in InitState, and floating point generation.
+- **C#** - As below. Values may differ in .NET 5.0, but thankfully Unity doesn't yet support that.
+- **JavaScript** - Check out MoatShrimp's JS implemention (and neat Undermine loot lookup tool) here:
+  - http://moatshrimp.com/
+- **Lua** - I've translated this into Lua for use on [MediaWiki](https://www.mediawiki.org/wiki/MediaWiki) wikis with the [Scribunto](https://www.mediawiki.org/wiki/Extension:Scribunto) extension installed. Note that this only works if Lua was compiled with `LUA_NUMBER = double`, which should be the case for most wikis. In my case the initial goal was to evaluate random loot lists in Pillars of Eternity, for use on the wiki.
+  - [Module:Lootlist](https://pillarsofeternity.gamepedia.com/Module:Lootlist) (might have to scroll down a bit)
+- If you translate this into other languages, or have any improvements/insights, feel free to comment below!
+- If you do translate this, be mindful of:
+  - How your language handles numbers. Most programming languages that only define one type for numbers will use a double-precision floating point value to represent all numbers.
+  - Integer overflow, and casting behaviours (particularly from uint to int)
+  - Differences in the `%` operator (modulo vs remainder)
+
+### Unknowns ###
+- How Unity initializes `UnityEngine.Random` when a seed is not provided. Probably seeded based on time, perhaps hourly? Need to do further testiong.
+- Floating point RPG is slightly inaccurate. Unity's implementation is likely done differently, though their exact method is unknown.
+
+## Tests ##
+The following tests were performed using the C# implementation in Unity, initialized with: `UnityEngine.Random.InitState(1234)` and `XORShift128.InitSeed(1234)`, generated sequentially (**the state isn't reset between runs**).
+
+`UnityEngine.Random.State.s3` and `XORShift128.w` are the last state parameter in Xorshift, the actual number that was generated in Xorshift. This value is a `uint` and is used as a basis for all other Random functions.
+
+### Integer ####
+Uses `UnityEngine.Random.Range(min, max)` and `XORShift128.NextIntRange(min, max)`
+
+0 to `int.MaxValue`
+
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 3463400838 | 1315917191 | 1315917191
+| 3496203776 | 1348720129 | 1348720129
+| 3452947669 | 1305464022 | 1305464022
+| 1278673611 | 1278673611 | 1278673611
+| 4169168310 | 2021684663 | 2021684663
+
+0 to `int.MinValue` (-2,147,483,648)
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 916287344  | -916287344 | -916287344
+| 2240259090 | -92775442 | -92775442
+| 1901252403 | -1901252403 | -1901252403
+| 2323917162 | -176433514 | -176433514
+| 1472147877 | -1472147877 | -1472147877
+
+`int.MinValue` to `int.MaxValue`
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 4020283508 | 1872799860 | 1872799860
+| 141347300 | -2006136348 | -2006136348
+| 2735243002 | 587759354 | 587759354
+| 227819815 | -1919663833 | -1919663833
+| 3885870057 | 1738386409 | 1738386409
+
+`int.MaxValue` to `int.MinValue`
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 2312142103 | -164658456 | -164658456
+| 1775189369 | 372294278 | 372294278
+| 3338523678 | -1191040031 | -1191040031
+| 3426086347 | -1278602700 | -1278602700
+| 3322349983 | -1174866336 | -1174866336
+
+`int.MinValue` to `int.MinValue` (error is caught and a suitable value is returned before a value is even generated, hence the non-changing state value)
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 3322349983 | -2147483648 | -2147483648    
+| 3322349983 | -2147483648 | -2147483648    
+| 3322349983 | -2147483648 | -2147483648    
+| 3322349983 | -2147483648 | -2147483648    
+| 3322349983 | -2147483648 | -2147483648
+
+### Floating point ####
+Uses `UnityEngine.Random.value` and `XORShift128.NextFloat()`
+
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 3593715923 | 0.4043221 | 0.404322
+| 4266042159 | 0.551855 | 0.551855
+| 2642301593 | 0.9868958 | 0.9868957
+| 1674312536 | 0.593608 | 0.5936079
+| 733387434 | 0.426595 | 0.426595
+
+Uses `UnityEngine.Random.Range(min, max)` and `XORShift128.NextFloatRange(min, max)`
+0.0 to 100.0
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 3760331560 | 73.35463 | 73.35463
+| 2410116911 | 69.16753 | 69.16753
+| 3012185272 | 91.95337 | 91.95337
+| 745993129 | 7.068896 | 7.068908
+| 3699201620 | 2.080286 | 2.080297
+
+0.0 to 100000.0
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 1758944507 | 31747.49 | 31747.5
+| 2312712917 | 30313.62 | 30313.62
+| 313095164 | 67614.8 | 67614.8
+| 609241099 | 37280.14 | 37280.14
+| 4138924286 | 60177.63 | 60177.64
+
+0.0 to `float.MaxValue` (3.402823E+38)
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 3065852775 | 1.775827E+38 | 1.775827E+38
+| 4023550175 | 1.209507E+38 | 1.209507E+38
+| 1231330622 | 7.280383E+37 | 7.280387E+37
+| 678488548 | 4.010639E+37 | 4.010643E+37
+| 1997128070 | 3.143466E+38 | 3.143466E+38
+
+0.0 to `float.MinValue` (-3.402823E+38)
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 212231104 | -2.382252E+38 | -2.382252E+38
+| 1632010759 | -1.528401E+38 | -1.528402E+38
+| 3470161922 | -1.104089E+38 | -1.104089E+38
+| 4159346095 | -5.693158E+37 | -5.693162E+37
+| 3362607345 | -4.967007E+37 | -4.967012E+37
+
+`float.MinValue` to `float.MaxValue`
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 2641274177 | -2.480102E+38 | -2.480101E+38
+| 3758475398 | 3.095331E+38 | 3.095331E+38
+| 1138851524 | -1.78091E+38 | -1.780909E+38
+| 3785966737 | 1.208649E+38 | 1.208649E+38
+| 151368008 | 3.100158E+38 | 3.100158E+38
+
+`float.MaxValue` to `float.MinValue`
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 3347712278 | -2.869245E+38 | -2.869245E+38
+| 2413123709 | 1.13493E+38 | 1.13493E+38
+| 619907290 | 2.713464E+38 | 2.713463E+38
+| 5796605 | 1.299941E+38 | 1.299941E+38
+| 2534213977 | -2.709683E+38 | -2.709683E+38
+
+`float.MinValue` to `float.MinValue`
+| `s3` / `w` | Unity | XORShift
+| --- | --- | ---
+| 2990456181 | -3.402823E+38 | -3.402823E+38
+| 238536240 | -3.402823E+38 | -3.402823E+38
+| 3443233425 | -3.402823E+38 | -3.402823E+38
+| 847449518 | -3.402823E+38 | -3.402823E+38
+| 1964100510 | -3.402823E+38 | -3.402823E+38
diff --git a/XORShift128.cs b/XORShift128.cs
@@ -0,0 +1,108 @@
+public static class XORShift128
+{
+    public static uint x = 0, y = 0, z = 0, w = 0;
+
+    const uint MT19937 = 1812433253;
+
+    // Initialize Xorshift using a signed integer seed, calculating the state values using the initialization method from Mersenne Twister (MT19937)
+    // https://en.wikipedia.org/wiki/Mersenne_Twister#Initialization
+    public static void InitSeed(int seed)
+    {
+        x = (uint)seed;
+        y = (uint)(MT19937 * x + 1);
+        z = (uint)(MT19937 * y + 1);
+        w = (uint)(MT19937 * z + 1);
+    }
+
+    // Explicitly set the state parameters
+    public static void InitState(uint x, uint y, uint z, uint w)
+    {
+        XORShift128.x = x;
+        XORShift128.y = y;
+        XORShift128.z = z;
+        XORShift128.w = w;
+    }
+
+    // XORShift, returns an unsigned 32-bit integer
+    public static uint XORShift()
+    {
+        uint t = x ^ (x << 11);
+        x = y; y = z; z = w;
+        return w = w ^ (w >> 19) ^ t ^ (t >> 8);
+    }
+
+    // UInt32 / uint
+
+    // UnityEngine.Random doesn't have any uint functions so these functions behave exactly like int Random.Range
+
+    // Alias of base Next/XORShift
+    public static uint NextUInt()
+    {
+        return XORShift();
+    }
+
+    // Generate a random unsigned 32-bit integer value in the range 0 (inclusive) to max (exclusive)
+    public static uint NextUIntMax(uint max)
+    {
+        if (max == 0) return 0;
+        return XORShift() % max;
+    }
+
+    // Generate random unsigned 32-bit integer value in the range min (inclusive) to max (exclusive)
+    public static uint NextUIntRange(uint min, uint max)
+    {
+        if (max - min == 0) return min;
+
+        if (max < min)
+            return min - XORShift() % (max + min);
+        else
+            return min + XORShift() % (max - min);
+    }
+
+    // Int32 / int
+
+    // Generate a random signed 32-bit integer value in the range -2,147,483,648 (inclusive) to 2,147,483,647 (inclusive)
+    public static int NextInt()
+    {
+        return (int)(XORShift() % int.MaxValue);
+    }
+
+    public static int NextIntMax(int max)
+    {
+        return NextInt() % max;
+    }
+
+    // Generate a random signed 32-bit integer value in the range min (inclusive) to max (exclusive)
+    // If you only need to generate positive integers, use NextUIntRange instead
+    public static int NextIntRange(int min, int max)
+    {
+        // If max and min are the same, just return min since it will result in a DivideByZeroException
+        if (max - min == 0) return min;
+
+        // Do operations in Int64 to prevent overflow that might be caused by any of the following operations
+        // I'm sure there's a faster/better way to do this and avoid casting, but we prefer equivalence to Unity over performance
+        long minLong = (long)min;
+        long maxLong = (long)max;
+        long r = XORShift();
+
+        // Flip the first operator if the max is lower than the min,
+        if (max < min)
+            return (int)(minLong - r % (maxLong - minLong));
+        else
+            return (int)(minLong + r % (maxLong - minLong));
+    }
+
+    // Single / float
+
+    // Generate a random floating point between 0.0 and 1.0 (inclusive?)
+    public static float NextFloat()
+    {
+        return 1.0f - NextFloatRange(0.0f, 1.0f);
+    }
+
+    // Generate a random floating point between min (inclusive) and max (exclusive) 
+    public static float NextFloatRange(float min, float max)
+    {
+        return (min - max) * ((float)(XORShift() << 9) / 0xFFFFFFFF) + max;
+    }
+}