掃雷之平鋪演算法

來自專欄前端深夜告解室

前言

作為一名前端攻城獅，寫個假前端的 Topic ，什麼鬼？你說一個好好的前端不做，搞什麼假前端？

FBI WARNING：正宗的前端知識移步專欄里隔壁大神系列

言歸正傳，這個 Topic 系列的文章我會盡量多說一些可能與前端知識關係不太大但非常有意思的東西，是希望將自己實踐中遇到的一些邏輯問題和演算法問題以及一些其他知識與大家分享。

掃雷

在工作之餘，有課外開發的習慣。目的是將自己從重複的業務代碼中擺脫出來，做一些有意思的東西。小時候非常愛玩的一個遊戲就是掃雷，於是就有了這個系列的第一個文章集 -- 假前端之掃雷系列。

規則小結

在我寫出這個東西以後，找了一些同學去玩：

「掃雷啊~~不會啊~」

「不知道怎麼玩~~以前都是瞎點。」

... ...

鑒於此，科普一些規則，熟悉的同學跳過：

掃雷就是點格子！！！

當然，還是有點技巧的：格子數字代表周圍一圈 8 個格子裡面藏著多少個雷~

不小心暴露了單身 20 年的手速~

初始化遊戲實現

現在，就要考慮我們要用一個怎樣的數據結構來表示整個遊戲雷區。

沒錯，一個二維數組。但是我們能不能就用一個一維數組實現呢？完全可以。這裡，就用二維數組來實現，直觀。

我設置了 `const SAFE_CELL = 0` 作為默認填充，這個 0 表示周圍都沒有地雷，這樣一個空白的地雷區域就出現了。

平鋪演算法布雷

遊戲中，地雷的分布是完全了隨機的。需要你通過一定的邏輯判斷找出來。這裡，我選擇了 `const MINE_CELL = 9` 作為地雷標識，原因是 1~8 作為標識周圍雷數需要用到，這個 1~8 的數字就是標識周圍有多少個地雷。

那麼，我們如何將固定數量比例的地雷隨機分布到整個二維數組中呢？

這裡的隨機分布的要求很簡單：

1. 雷的數量是固定的
2. 每個格子是否是雷的概率是一樣的

【替換法】

也許首先想到的方法：在這個二維數組裡隨機找出不是地雷的格子，將其替換成地雷就可以了。

看起來似乎是不錯的方案。實際上， 是有問題的 。問題在哪？

如果雷數密度到達一定高度，挑出一個不是地雷的格子是相當困難的，例如：一個 10 * 10 的雷區，極端情況下有 99 個地雷，那麼第 99 個地雷想找出剩下的兩個 `SAFE_CELL` 非常困難，如果進行判斷：是地雷，再重新隨機挑選一個格子。不僅消耗時間，還很容易進入一個死循環，放棄。

那麼我不進行替換，有沒有別的方法？

【插入法】

生成一個 `SAFE_CELL` 數量的一維數組，將雷隨機插入到數組中，再裂成一個二維數組。例如 10 * 10 的雷區有 10 個雷，生成長度 90 的以為數組，再將 10 個地雷隨機插入到數組中，最後裂成一個 10 * 10 的二維數組。

看似完美解決了無限循環的問題，但是我們知道，對數組元素進行添刪操作是非常消耗性能的，我們在數組中增減一個元素，其後的每一個元素的下表隨之需要移位。

這裡，我介紹下我的平鋪思路：

【洗牌】

生成一個包含所有地雷和空白區域的一維有序數組，利用 洗牌演算法 將數組的順序打亂，最後裂成二維數組。

這裡面涉及到一個洗牌演算法，我簡單的介紹一下。前輩們實現的洗牌演算法多種多樣，性能和效果各異。這裡我選用的是我認為性能和效果兼優，實現也非常簡單的 Fisher–Yates shuffle 演算法。如果你注意過 lodash 源碼的話，lodash 裡面的 shuffle 也是用這個演算法實現的。

思路就是從尾部開始將未打亂的元素與一個隨機的未打亂的剩餘元素進行調換，直到數組的所有元素都被打亂。

下面給出我的實現：

代碼中，元素調換是利用 es6 的解構賦值，由於是就地調換元素的值，所以不存在性能問題。

圖中對比明顯可以看出：

百萬長度的數組，在瀏覽器環境下 `Fisher-Yates` 洗牌演算法穩定在 70 ms 左右；而同樣是 O(n) 時間複雜度的插入演算法，在處理同樣長度的數組時，性能落後非常多！

完成洗牌後，我們將數組裂為二維數組交給 vue 渲染。此時，我們的視圖呈現：

計算環境數字

雷區有了地雷，我們就該計算地雷周圍的環境數字了，這個數字的意義是標識這個數字周圍隱藏著多少個地雷，這個在前文規則一節中有講。

計算環境數字很簡單，循環一遍二維數組，如果遇到這個格子是個地雷，周圍所有個字的數字 +1 就行了。注意格子在邊緣的情況。

此時:

小總結

到此為止，我們終於生成個一個掃雷的初始雷區，包含了隨機分布的地雷以及地雷周圍正確的數字。

在實現的過程中，我們做一下總結：

1. 先思考再動手。
2. 時常保持對代碼邏輯邊際情況的考慮，多想想這麼寫會怎麼崩潰。
3. 把握好細節

下一步，我們需要的是給雷區里的格子加上各種狀態，來隱藏地雷。同時給格子們綁上事件。

在綁定事件的過程中，又有好玩的思考。期待一下吧。