JS 隨機數

一。問題背景

一個二維平面上有一群 NPC，每一回合可以隨機向上/下/左/右任一方向走 1 步，有單位碰撞體積（NPC 位置不能重合）

規則就這麼簡單，初始情況下這群 NPC 是被人工均勻分佈在二維平面上的，運行 N 個回合後發現所有 NPC 都集中在了左下角。。怎麼會這樣，說好的隨機呢？

二。分析

現有的實現是這樣的：

1. 根據 NPC 的當前位置判斷得到可以去的位置，把結果存放在一維數組 arr 裏

P.S. 上/下/左/右最多 4 個點（周圍空蕩蕩的），最少 0 個點（被圍起來了）

2. 生成 [0, arr.length - 1] 內的一個隨機數，作為目標位置索引值 index

   // 生成隨機數 [min, max]
   w.Util.rand = function(min, max) {
   
       return Math.round(Math.random() * (max - min) + min);
   }
   

3. 控制 NPC 移動到 arr[index] 的位置

邏輯應該是沒有問題的，可是為什麼運行結果是 NPC 都跑到左下角開會去了呢？等等，為什麼是左下而不是其它角角？

因為實現第一步的時候是按照上 -> 下 -> 左 -> 右的順序判斷的，最後都去了左下角，說明向上和向右的概率太小了（生成隨機數的函數 rand 是沒問題的，確實能得到 [min, max] 的數）

問題的根源是 Math.random() 不給力，生成 [0, 1) 之間的小數，取到 0 和靠近 1 的值概率很小，所以 rand() 函數生成的隨機數取到 min 和 mix 的概率也很小，向上/向右的可能性也就小了

三。解決方案

既然取到 min 和 max 的概率很小，中間概率比較均勻，那好辦，切掉這兩個值就好了。具體實現如下：

function randEx(min, max) {

    var num;
    var maxEx = max + 2; // 擴大範圍到 [min, max + 2]，引入兩個多餘值替換 min/max
    
    do{
    
        num = Math.round(Math.random() * (maxEx - min) + min);
        num--;
    } while (num < min || num > max);   // 範圍不對，繼續循環
    
    return num;
}

值得一提的是上面的加 2 減 1比較巧妙，能夠恰好排除 min 和 max

四。運行結果

JS 中 Math.random() 返回值的概率差異可能比你想象的要大些，在實際應用中是不可接受的

測試代碼如下：

// 生成隨機數 [min, max]
w.Util.rand = function(min, max) {

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

// 生成更隨機的隨機數 [min, max]
function randEx(min, max) {

    var num;
    var maxEx = max + 2; // 擴大範圍到 [min, max + 2]，引入兩個多餘值替換 min/max
    
    do{
    
        num = Math.round(Math.random() * (maxEx - min) + min);
        num--;
    } while (num < min || num > max);   // 範圍不對，繼續循環
    
    return num;
}

function testRand(times, fun) {

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

        // 獲取 [0, 3] 的隨機數
        randVal = fun(0, arr.length - 1);
        // 記錄次數
        if (typeof count[randVal] !== "number") {
        
            count[randVal] = 0;
        }
        count[randVal]++;
    }
    
    console.log(count);
}

console.log("100 times");
testRand(100, w.Util.rand); // 之前的實現
testRand(100, randEx);      // 改進過的實現

console.log("1000 times");
testRand(1000, w.Util.rand); // 之前的實現
testRand(1000, randEx);      // 改進過的實現

console.log("10000 times");
testRand(10000, w.Util.rand); // 之前的實現
testRand(10000, randEx);      // 改進過的實現

console.log("100000 times");
testRand(100000, w.Util.rand); // 之前的實現
testRand(100000, randEx);      // 改進過的實現

運行結果如下：

看到了吧，效果還是很不錯的

後話

理論上 Java 的 Math.random()，C# 的 next 可能也存在這個問題，這裡就沒有必要驗證了，因為 randEx 函數的思想（加 2 減 1，嫌效果不好還可以加 4 減 2、加 6 減 3……直到滿意為止）是通用的