3
\$\begingroup\$

I'm writing a 2D web racing game with procedural generated maps using perlin noise(as a university project). The server is written using C# and the client using Javascript. I've developed procedural generating of maps on the server but I've realized that's so time consuming. I've thought that players can generate maps and the server can validate some key points so server doesn't have to do both. The problem is that I don't know how to generate same map on the client (in JS) and the same map on the server (in C#). I've read some about deterministic random number generators which are platform independent. But I'm not sure how to search noise generators with them. Do you know where can I find some, especially in programming languages I'm using? Do I have to write own noise generator?

\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

I was expecting that it was trivial to seed the javascript pseudo-random number generator. Turns out you can't, at least not in any standard portable way.

Alright, we are going to implement one. The following is mulberry32 in JavaScript:

function mulberry32(a) {
    return function() {
      a |= 0; a = a + 0x6D2B79F5 | 0;
      var t = Math.imul(a ^ a >>> 15, 1 | a);
      t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    }
}

Taken from bryc/code.

It is very easy to use, just initialize with the seed. It is also very fast. I have taken the liberty to translate this to (ideomatic) C#:

public sealed class Mulberry32
{
    private uint _seed;

    public Mulberry32(int seed)
    {
        _seed = (uint)seed;
    }

    public double Next()
    {
        _seed += 0x6D2B79F5;
        var t = (_seed ^ (_seed >> 15)) * (1 | _seed);
        t = (t + ((t ^ (t >> 7)) * (61 | t))) ^ t;
        return (t ^ (t >> 14)) / (double)4294967296;
    }
}

In fact, I went back and rewrote Mulberry32 a bit:

function Mulberry32(seed) {
    "use strict";
    return {
        next: function () {
            seed |= 0; seed = seed + 0x6D2B79F5 | 0;
            var t = Math.imul(seed ^ seed >>> 15, 1 | seed);
            t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
            return ((t ^ t >>> 14) >>> 0) / 4294967296;
        }
    };
}

Now, what you need to do is generate a seed on the server and send it to the client. It could be DateTime.Now.GetHashCode() or something like that. If both client and server use the same value, they should generate the same pseudo-random numbers.

I do not know how your noise code looks like... however you should be able to update it to use your new random number generator. It could be that the generator you have has it own seeding mechanism that we got to identify and replace (probably a seed function).

Assuming your noise generator uses generic random...

On C# replace this code:

var random = new Random(/*seed*/);
var x = random.NextDouble();

With this:

var random = new Mulberry32(seed);
var x = random.Next();

Make sure to add the seed you generated. The same that you send to the client.

On JavaScript replace this code:

var x = Math.random();

With this:

var random = new Mulberry32(seed);
var x = random.next();

Make sure to pass the seed you got from the server. Please note that mulberry32(seed) is initialization, and you are meant to do that only once, and continue using the function it returns as if it were Math.random. Similary to how in C# you initialize your random object and reuse it.


I had a look to some nice to use and easy to modify perlin noise solution for javascript... found this one: esimov/perlin.js. We have to replace seed.

Ern... be honest with you, I decided to port it to C#, and then back to JavaScript. I suppose I could just have ported that javascript to C# along with its seed method, forget that I already had ported the pseudo-random number generator... Instead I decided to pass the pseudo-random number generator in the constructor.

This is C#:

public sealed class Perlin
{
    private readonly int[][] _grad3 =
    {
        new[]{1, 1, 0}, new[]{-1, 1, 0}, new[]{1, -1, 0}, new[]{-1, -1, 0},
        new[]{1, 0, 1}, new[]{-1, 0, 1}, new[]{1, 0, -1}, new[]{-1, 0, -1},
        new[]{0, 1, 1}, new[]{0, -1, 1}, new[]{0, 1, -1}, new[]{0, -1, -1}
    };

    private readonly double _inverseMaximumPersistence;
    private readonly double[] _octaveFrequency;
    private readonly double[] _octavePersistence;
    private readonly int _octaves;
    private readonly byte[] _p = new byte[256];
    private readonly byte[] _perm = new byte[512];

    public Perlin(Func<double> random, int octaves, double persistence)
    {
        if (random == null)
        {
            throw new ArgumentNullException(nameof(random));
        }

        for (var i = 0; i < 256; i++)
        {
            _p[i] = (byte)Math.Abs(Math.Truncate(random() * 256));
        }

        // To remove the need for index wrapping, double the permutation table length
        for (var j = 0; j < 512; j++)
        {
            _perm[j] = _p[j & 255];
        }

        _octaves = octaves;
        _octaveFrequency = new double[_octaves];
        _octavePersistence = new double[_octaves];

        double maximumPersistence = 0;
        for (var octaveIndex = 0; octaveIndex < _octaves; octaveIndex++)
        {
            var addedPersistence = Math.Pow(persistence, octaveIndex);
            maximumPersistence += addedPersistence;
            _octaveFrequency[octaveIndex] = Math.Pow(2, octaveIndex);
            _octavePersistence[octaveIndex] = addedPersistence;
        }

        _inverseMaximumPersistence = 2 / maximumPersistence;
    }

    public double Noise2D(double x, double y)
    {
        var result = 0.0;
        for (var index = 0; index < _octaves; index++)
        {
            var frequency = _octaveFrequency[index];
            result += _octavePersistence[index] * SimplexNoise2D(frequency * x, frequency * y);
        }

        return ((result * _inverseMaximumPersistence) + 0.8) * 0.5;
    }

    public double Noise3D(double x, double y, double z)
    {
        var result = 0.0;
        for (var index = 0; index < _octaves; index++)
        {
            var frequency = _octaveFrequency[index];
            result += _octavePersistence[index] * SimplexNoise3D(frequency * x, frequency * y, frequency * z);
        }

        return ((result * _inverseMaximumPersistence) + 0.8) * 0.5;
    }

    // Return the dot product for 2d perlin noise
    private static double Dot2(int[] g, double x, double y)
    {
        return (g[0] * x) + (g[1] * y);
    }

    // Return the dot product for 3d perlin noise
    private static double Dot3(int[] g, double x, double y, double z)
    {
        return (g[0] * x) + (g[1] * y) + (g[2] * z);
    }

    private static double Fade(double t)
    {
        return t * t * t * ((t * ((t * 6.0) - 15.0)) + 10.0);
    }

    private static double Lerp(double a, double b, double t)
    {
        return ((1.0 - t) * a) + (t * b);
    }

    // 2D Simplex Noise
    private double SimplexNoise2D(double x, double y)
    {
        // Find unit grid cell containing point
        var cellX = (int)Math.Floor(x) & 255;
        var cellY = (int)Math.Floor(y) & 255;

        // Get relative xyz coordinates of point within that cell
        x -= Math.Floor(x);
        y -= Math.Floor(y);

        var u = Fade(x);
        var v = Fade(y);

        // Calculate a set of four hashed gradient indices
        var n00 = _perm[cellX + _perm[cellY]] % 12;
        var n01 = _perm[cellX + _perm[cellY + 1]] % 12;
        var n10 = _perm[cellX + 1 + _perm[cellY + 1]] % 12;
        var n11 = _perm[cellX + 1 + _perm[cellY + 1]] % 12;

        // Calculate noise contributions from each of the four corners
        var gi00 = Dot2(_grad3[n00], x, y);
        var gi01 = Dot2(_grad3[n01], x, y - 1);
        var gi10 = Dot2(_grad3[n10], x - 1, y);
        var gi11 = Dot2(_grad3[n11], x - 1, y - 1);

        // Interpolate the results along axises
        return Lerp
        (
            Lerp(gi00, gi10, u),
            Lerp(gi01, gi11, u),
            v
        );
    }

    // 3D Simplex Noise
    private double SimplexNoise3D(double x, double y, double z)
    {
        // Find unit grid cell containing point
        var cellX = (int)Math.Floor(x) & 255;
        var cellY = (int)Math.Floor(y) & 255;
        var cellZ = (int)Math.Floor(z) & 255;

        // Get relative xyz coordinates of point within that cell
        x -= Math.Floor(x);
        y -= Math.Floor(y);
        z -= Math.Floor(z);

        var u = Fade(x);
        var v = Fade(y);
        var w = Fade(z);

        // Calculate a set of eight hashed gradient indices
        var n000 = _perm[cellX + _perm[cellY + _perm[cellZ]]] % 12;
        var n001 = _perm[cellX + _perm[cellY + _perm[cellZ + 1]]] % 12;
        var n010 = _perm[cellX + _perm[cellY + 1 + _perm[cellZ]]] % 12;
        var n011 = _perm[cellX + _perm[cellY + 1 + _perm[cellZ + 1]]] % 12;
        var n100 = _perm[cellX + 1 + _perm[cellY + _perm[cellZ]]] % 12;
        var n101 = _perm[cellX + 1 + _perm[cellY + _perm[cellZ + 1]]] % 12;
        var n110 = _perm[cellX + 1 + _perm[cellY + 1 + _perm[cellZ]]] % 12;
        var n111 = _perm[cellX + 1 + _perm[cellY + 1 + _perm[cellZ + 1]]] % 12;

        // Calculate noise contributions from each of the eight corners
        var gi000 = Dot3(_grad3[n000], x, y, z);
        var gi001 = Dot3(_grad3[n001], x, y, z - 1);
        var gi010 = Dot3(_grad3[n010], x, y - 1, z);
        var gi011 = Dot3(_grad3[n011], x, y - 1, z - 1);
        var gi100 = Dot3(_grad3[n100], x - 1, y, z);
        var gi101 = Dot3(_grad3[n101], x - 1, y, z - 1);
        var gi110 = Dot3(_grad3[n110], x - 1, y - 1, z);
        var gi111 = Dot3(_grad3[n111], x - 1, y - 1, z - 1);

        // Interpolate the results along axises
        return Lerp
        (
            Lerp
            (
                Lerp(gi000, gi100, u),
                Lerp(gi001, gi101, u),
                w
            ),
            Lerp
            (
                Lerp(gi010, gi110, u),
                Lerp(gi011, gi111, u),
                w
            ),
            v
        );
    }
}

Usage in C#:

// seed: 5646
var random = new Mulberry32(5646);
// 3 octaves
// 0.2 persistence
var perlin = new Perlin(random.Next, 3, 0.2);
// x = 0.5, y = 0.1
Console.WriteLine(perlin.Noise2D(0.5, 0.1)); // output: 0.221234322580645

This is JavaScript:

function Perlin(random, octaves, persistence) {
    "use strict";
    if (typeof(random) !== "function") {
        throw "argument `random` should be a function";
    }

    let _grad3 = [[1, 1, 0], [-1, 1, 0], [1, -1, 0], [-1, -1, 0], [1, 0, 1], [-1, 0, 1], [1, 0, -1], [-1, 0, -1], [0, 1, 1], [0, -1, 1], [0, 1, -1], [0, -1, -1]];
    let _p = new Uint8Array(256);
    let _perm = new Uint8Array(512);

    let i = 0;
    while (i < 256) {
        _p[i] = (Math.abs((random() * 256) | 0)) | 0;
        i = ((i + 1) | 0);
    }

    let j = 0;
    while (j < 512) {
        _perm[j] = (_p[(j & 255)] | 0);
        j = ((j + 1) | 0);
    }

    let _octaves = (octaves | 0);
    let _octaveFrequency = new Float64Array(_octaves);
    let _octavePersistence = new Float64Array(_octaves);

    let maximumPersistence = 0;
    let octaveIndex = 0;
    while (octaveIndex < _octaves) {
        let addedPersistence = (Math.pow(+persistence, octaveIndex));
        maximumPersistence += addedPersistence;
        _octaveFrequency[octaveIndex] = (Math.pow(2, octaveIndex));
        _octavePersistence[octaveIndex] = addedPersistence;
        octaveIndex = ((octaveIndex + 1) | 0);
    }

    let _inverseMaximumPersistence = +(2 / maximumPersistence);

    function dot2(g, x, y) {
        return (((g[0]) * x) + ((g[1]) * y));
    }

    function dot3(g, x, y, z) {
        return ((((g[0]) * x) + ((g[1]) * y)) + ((g[2]) * z));
    }

    function fade(t) {
        return (((t * t) * t) * ((t * ((t * 6) - 15)) + 10));
    }

    function lerp(a, b, t) {
        return (((1 - t) * a) + (t * b));
    }

    function simplexNoise2D(x, y) {
        let cellX = ((Math.floor(x)) | 0) & 255;
        let cellY = ((Math.floor(y)) | 0) & 255;
        x -= (Math.floor(x));
        y -= (Math.floor(y));
        let u = fade(x);
        let v = fade(y);
        let n0 = (((_perm[((cellX + (_perm[cellY] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n = (((_perm[((cellX + (_perm[((cellY + 1) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n2 = (((_perm[((((cellX + 1) | 0) + (_perm[((cellY + 1) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n3 = (((_perm[((((cellX + 1) | 0) + (_perm[((cellY + 1) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let gi0 = dot2(_grad3[n0], x, y);
        let gi = dot2(_grad3[n], x, y - 1);
        let gi2 = dot2(_grad3[n2], x - 1, y);
        let gi3 = dot2(_grad3[n3], x - 1, y - 1);
        return lerp(
            lerp(gi0, gi2, u),
            lerp(gi, gi3, u),
            v
        );
    }

    function simplexNoise3D(x, y, z) {
        let cellX = ((Math.floor(x)) | 0) & 255;
        let cellY = ((Math.floor(y)) | 0) & 255;
        let cellZ = ((Math.floor(z)) | 0) & 255;
        x -= (Math.floor(x));
        y -= (Math.floor(y));
        z -= (Math.floor(z));
        let u = fade(x);
        let v = fade(y);
        let w = fade(z);
        let n0 = (((_perm[((cellX + (_perm[((cellY + (_perm[cellZ] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n = (((_perm[((cellX + (_perm[((cellY + (_perm[((cellZ + 1) | 0)] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n2 = (((_perm[((cellX + (_perm[((((cellY + 1) | 0) + (_perm[cellZ] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n3 = (((_perm[((cellX + (_perm[((((cellY + 1) | 0) + (_perm[((cellZ + 1) | 0)] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n4 = (((_perm[((((cellX + 1) | 0) + (_perm[((cellY + (_perm[cellZ] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n5 = (((_perm[((((cellX + 1) | 0) + (_perm[((cellY + (_perm[((cellZ + 1) | 0)] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n6 = (((_perm[((((cellX + 1) | 0) + (_perm[((((cellY + 1) | 0) + (_perm[cellZ] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let n7 = (((_perm[((((cellX + 1) | 0) + (_perm[((((cellY + 1) | 0) + (_perm[((cellZ + 1) | 0)] | 0)) | 0)] | 0)) | 0)] | 0) % 12) & 0xFF);
        let gi0 = dot3(_grad3[n0], x, y, z);
        let gi = dot3(_grad3[n], x, y, z - 1);
        let gi2 = dot3(_grad3[n2], x, y - 1, z);
        let gi3 = dot3(_grad3[n3], x, y - 1, z - 1);
        let gi4 = dot3(_grad3[n4], x - 1, y, z);
        let gi5 = dot3(_grad3[n5], x - 1, y, z - 1);
        let gi6 = dot3(_grad3[n6], x - 1, y - 1, z);
        let gi7 = dot3(_grad3[n7], x - 1, y - 1, z - 1);
        return lerp(
            lerp(
                lerp(gi0, gi4, u),
                lerp(gi, gi5, u),
                w
            ),
            lerp(
                lerp(gi2, gi6, u),
                lerp(gi3, gi7, u),
                w
            ),
            v
        );
    }

    return {
        noise2D: function (x, y) {
            let _x = +x;
            let _y = +y;
            let result = 0;

            let index = 0;
            while (index < (_octaves | 0)) {
                let frequency = _octaveFrequency[index];
                result += _octavePersistence[index] * simplexNoise2D(frequency * _x, frequency * _y);
                index = ((index + 1) | 0);
            }

            return (((result * _inverseMaximumPersistence) + 0.8) * 0.5);
        },
        noise3D: function (x, y, z) {
            let _x = +x;
            let _y = +y;
            let _z = +z;
            let result = 0;

            let index = 0;
            while (index < (_octaves | 0)) {
                let frequency = _octaveFrequency[index];
                result += _octavePersistence[index] * simplexNoise3D(frequency * _x, frequency * _y, frequency * _z);
                index = ((index + 1) | 0);
            }

            return (((result * _inverseMaximumPersistence) + 0.8) * 0.5);
        }
    };
}

Usage in JavaScript:

// seed: 5646
var random = new Mulberry32(5646);
// 3 octaves
// 0.2 persistence
var perlin = new Perlin(random.next, 3, 0.2);
// x = 0.5, y = 0.1
console.log(perlin.noise2D(0.5, 0.1)); // output: 0.22123432258064518

Hmmm... Let us compare the values:

C#:         0.221234322580645
JavaScript: 0.22123432258064518

Yeah, this is an obstacle if you want to sample the noise to compare it. I tested on a large range of numbers, and apparently they they match up to 13 places after the decimal point (some values one or two digits more).

\$\endgroup\$
1
  • \$\begingroup\$ I've tried the Mulberry32 number generator and it works pretty good. I guess that's what I needed. And as for the noise implementation, I've decided to rewrite that code github.com/Auburns/FastNoise_CSharp in JavaScript using some tricks like "Math.imul" to simulate it correctly. Everything seems to work but I'm afraid of those differences between floating-point numbers in C# and JS. Anyway thank you :) \$\endgroup\$
    – Jelony
    Commented Jan 22, 2020 at 15:20
0
\$\begingroup\$

Your first problem doing this would be with JavaScript. It doesn't really have a deterministic, seedable random number generator. (Deterministic means it produces the same array of values every time you use it given the same starting conditions, seedable means you can set those starting conditions).

C# does have this, when you create a new Random object you can pass in a seed. Try setting it to something, it will produce the same results every time you run it (e.g. var rand = new Random(1337);)

So the first thing you'll have to do is either to reimplement the algorithm in JS (for more info, look here) or to implement a different algorithm in both languages (they're surprisingly simple if you give them some thought).

After this you'll have to implement your noise function using this random number generator in both languages. If everything is correct, they should generate the same values.

Alternatives

Firstly, if I were you, I would ditch C# and go with Node.js if possible. It allows you to use the exact same code (and given Chromiums very alarming growth rate, probably the exact same JavaScript engine), which basically guarantees the exact same output (almost, you'll still need a new random number generator, but there are readily available options).

Secondly, if the noise generator algorithm is your own, I would try looking for ways to speed it up. You could also use one, which has been thoroughly tested to be fast enough for modern games, such as Perlin noise (Ken Perlin still has the original source code on his university site written in Java, which is really just 3 steps from C#. It's also very compact. You'll have to shuffle the permutation array using the random number generator to randomize the output. There's a great shuffling algorithm described here)

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .