JS Random Numbers

I. Problem Background

There's a group of NPCs on a 2D plane, each round they can randomly move 1 step in any direction: up/down/left/right, with unit collision volume (NPC positions cannot overlap)

The rules are this simple, initially these NPCs are artificially evenly distributed on the 2D plane, after running N rounds found all NPCs gathered in the bottom-left corner.. How did this happen, what happened to the promised randomness?

II. Analysis

The existing implementation is like this:

1. Judge obtainable positions based on NPC's current position, store results in 1D array arr

P.S. Up/down/left/right at most 4 points (surroundings empty), at least 0 points (surrounded)

2. Generate a random number within [0, arr.length - 1], as target position index value index

    // Generate random number [min, max]
    w.Util.rand = function(min, max) {
   
        return Math.round(Math.random() * (max - min) + min);
    }
   

3. Control NPC to move to arr[index] position

Logic should be no problem, but why does running result show NPCs all went to bottom-left corner for meeting? Wait, why bottom-left instead of other corners?

Because when implementing first step, judgment order is up -> down -> left -> right, finally all went to bottom-left, shows probability of up and right is too small (rand function generating random numbers is no problem, indeed can get [min, max] numbers)

The root cause is Math.random() is not powerful enough, generates decimal between [0, 1), probability of getting 0 and values near 1 is very small, so rand() function generated random numbers getting min and max probability is also very small, possibility of up/right is also smaller

III. Solution

Since probability of getting min and max is very small, middle probability is relatively uniform, that's easy, just cut off these two values. Specific implementation as follows:

function randEx(min, max) {

    var num;
    var maxEx = max + 2; // Expand range to [min, max + 2], introduce two extra values to replace min/max
    
    do{
    
        num = Math.round(Math.random() * (maxEx - min) + min);
        num--;
    } while (num < min || num > max);   // Range incorrect, continue loop
    
    return num;
}

Worth mentioning is the add 2 subtract 1 above is quite clever, can exactly exclude min and max

IV. Running Results

Probability difference of Math.random() return value in JS may be larger than you imagine, unacceptable in practical applications

Test code as follows:

// Generate random number [min, max]
w.Util.rand = function(min, max) {

    return Math.round(Math.random() * (max - min) + min);
}

// Generate more random random number [min, max]
function randEx(min, max) {

    var num;
    var maxEx = max + 2; // Expand range to [min, max + 2], introduce two extra values to replace min/max
    
    do{
    
        num = Math.round(Math.random() * (maxEx - min) + min);
        num--;
    } while (num < min || num > max);   // Range incorrect, continue loop
    
    return num;
}

function testRand(times, fun) {

    var arr = [1, 2, 3, 4];
    var count = [];
    var randVal;
    for (var i = 0; i < times; i++) {

        // Get random number [0, 3]
        randVal = fun(0, arr.length - 1);
        // Record count
        if (typeof count[randVal] !== "number") {
        
            count[randVal] = 0;
        }
        count[randVal]++;
    }
    
    console.log(count);
}

console.log("100 times");
testRand(100, w.Util.rand); // Previous implementation
testRand(100, randEx);      // Improved implementation

console.log("1000 times");
testRand(1000, w.Util.rand); // Previous implementation
testRand(1000, randEx);      // Improved implementation

console.log("10000 times");
testRand(10000, w.Util.rand); // Previous implementation
testRand(10000, randEx);      // Improved implementation

console.log("100000 times");
testRand(100000, w.Util.rand); // Previous implementation
testRand(100000, randEx);      // Improved implementation

Running results as follows:

See, effect is still quite good

Afterword

Theoretically Java's Math.random(), C#'s next may also have this problem, no need to verify here, because randEx function's thought (add 2 subtract 1, if effect not good can also add 4 subtract 2, add 6 subtract 3... until satisfied) is universal