国际完美世界下载,完结小说,欢乐颂第一季免费阅读

沒事兒的時候我喜歡玩玩那些經典的 2D 網頁小游戲，我發現很多游戲都要涉及地圖的隨機生成，比如掃雷游戲中地雷的位置應該是隨機分布的：

再比如經典炸彈人游戲，障礙物的位置也是有一定隨機性的：

這些 2D 游戲相較現在的大型 3D 游戲雖然看起來有些簡陋，但依然用到很多有趣算法技巧，本文就來深入研究一下地圖的隨機生成算法。

2D 游戲的地圖肯定可以抽象成一個二維矩陣，就拿掃雷舉例吧，我們可以用下面這個類表示掃雷的棋盤：

class Game {
    int m, n;
    // 大小為 m * n 的二維棋盤
    // 值為 true 的地方代表有雷，false 代表沒有雷
    boolean[][] board;
}

如果你想在棋盤中隨機生成k個地雷，也就是說你需要在board中生成k個不同的(x, y)坐標，且這里面x, y都是隨機生成的。

對于這個需求， 首先一個優化就是對二維矩陣進行「降維打擊」，把二維數組轉化成一維數組 ：

class Game {
    int m, n;
    // 長度為 m * n 的一維棋盤
    // 值為 true 的地方代表有雷，false 代表沒有雷
    boolean[] board;

    // 將二維數組中的坐標 (x, y) 轉化為一維數組中的索引
    int encode(int x, int y) {
        return x * n + y;
    }

    // 將一維數組中的索引轉化為二維數組中的坐標 (x, y)
    int[] decode(int index) {
        return new int[] {index / n, index % n};
    }
}

這樣，我們只要在[0, m * n)中選取一個隨機數，就相當于在二維數組中隨機選取了一個元素。

但問題是，我們現在需要隨機選出k個不同的位置放地雷。你可能說，那在[0, m * n)中選出來k個隨機數不就行了？

是的，但實際操作起來有些麻煩，因為你很難保證隨機數不重復。如果出現重復的隨機數，你就得再隨機選一次，直到找到k個不同的隨機數。

如果k比較小m * n比較大，那出現重復隨機數的概率還比較低，但如果k和m * n的大小接近，那么出現重復隨機數的概率非常高，算法的效率就會大幅下降。

那么，我們有沒有更好的辦法能夠在線性的時間復雜度解決這個問題？其實是有的，而且有很多種解決方案。

洗牌算法

第一個解決方案，我們可以換個思路，避開「在數組中隨機選擇k個元素」這個問題，把問題轉化成「如何隨機打亂一個數組」 。

現在想隨機初始化k顆地雷的位置，你可以先把這k顆地雷放在board開頭，然后把board數組隨機打亂，這樣地雷不就隨機分布到board數組的各個地方了嗎？

洗牌算法，或者叫隨機亂置算法就是專門解決這個問題的，我們可以看下力扣第 384 題「打亂數組」：

這個shuffle函數是算法的關鍵，直接看解法代碼吧：

class Solution {
    private int[] nums;
    private Random rand = new Random();
    
    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int[] reset() {
        return nums;
    }
    
    // 洗牌算法
    public int[] shuffle() {
        int n = nums.length;
        int[] copy =  Arrays.copyOf(nums, n);
        for (int i = 0 ; i < n; i++) {
            // 生成一個 [i, n-1] 區間內的隨機數
            int r = i + rand.nextInt(n - i);
            // 交換 nums[i] 和 nums[r]
            swap(copy, i, r);
        }
        return copy;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

洗牌算法的時間復雜度是 O(N)，而且邏輯很簡單，關鍵在于讓你證明為什么這樣做是正確的。排序算法的結果是唯一可以很容易檢驗的，但隨機亂置算法不一樣，亂可以有很多種，你怎么能證明你的算法是「真的亂」呢？

分析洗牌算法正確性的準則：產生的結果必須有n!種可能 。這個很好解釋，因為一個長度為n的數組的全排列就有n!種，也就是說打亂結果總共有n!種。算法必須能夠反映這個事實，才是正確的。

有了這個原則再看代碼應該就容易理解了：

對于nums[0]，我們把它隨機換到了索引[0, n)上，共有n種可能性；

對于nums[1]，我們把它隨機換到了索引[1, n)上，共有n - 1種可能性；

對于nums[2]，我們把它隨機換到了索引[2, n)上，共有n - 2種可能性；

以此類推，該算法可以生成n!種可能的結果，所以這個算法是正確的，能夠保證隨機性。

水塘抽樣算法

學會了洗牌算法，掃雷游戲的地雷隨機初始化問題就解決了。不過別忘了，洗牌算法只是一個取巧方案，我們還是得面對「在若干元素中隨機選擇k個元素」這個終極問題。

要知道洗牌算法能夠生效的前提是你使用數組這種數據結構，如果讓你在一條鏈表中隨機選擇k個元素，肯定不能再用洗牌算法來蒙混過關了。

再比如，假設我們的掃雷游戲中棋盤的長和寬非常大，已經不能在內存中裝下一個大小為m * n的board數組了，我們只能維護一個大小為k的數組記錄地雷的位置：

class Game {
    // 棋盤的行數和列數（非常大）
    int m, n;
    // 長度為 k 的數組，記錄 k 個地雷的一維索引
    int[] mines;

    // 將二維數組中的坐標 (x, y) 轉化為一維數組中的索引
    int encode(int x, int y) {
        return x * n + y;
    }

    // 將一維數組中的索引轉化為二維數組中的坐標 (x, y)
    int[] decode(int index) {
        return new int[] {index / n, index % n};
    }
}