2D圓形隨機分布

本文轉載自凹凸實驗室

文/EC

鏈接：2D圓形隨機分布

1 命題

如何畫出又快又多的圈圈。

一個遊戲：在一個平面、一定時間內消滅一定的目標。

要實現這個遊戲，我們首先要確定，這些元素使用什麼形狀判定有效點擊範圍。因為按照圖示形狀又複雜又沒必要，選擇一個近似的規則幾何圖形即可。

在這裡，我們使用圓形作為目標的形狀。

假設世界觀是圓形互不重疊。那麼會有一下兩種可能性：

• 目標大小是否相同；
• 目標是否靜止。

複雜度依次遞增。

本文主要針對目標大小相同、目標靜止的情況進行探討，並會附上目標大小相同且目標靜止、目標大小不同且目標靜止兩種情況的代碼。

本文的探討不考慮重力因素。有關目標移動的情況，感興趣的可以參考《HTML5 Canvas 基礎教程》。

2 直線思維

隨機生成一個點，圈好佔地範圍，繼續隨機生成一個點，判斷是否與之前生成的圓形重疊，如果是，則拋棄，如果不是，則繼續。

2.1 演算法

生成一個點

/**n * @desc 隨機生成一個點n * @param {w, h} {object} w: 畫布寬，h：畫布高n * @return {x, y} {object} 點坐標n */nfunction randomPoint ({w, h}) {n const x = parseInt(Math.random() * w)n const y = parseInt(Math.random() * h)n return {x, y}n}n

隨機生成的點要排除兩種情況：

• 距離邊界過近。距離邊界過近的目標可能出現隱藏部分過多而難以點擊甚至無法點擊的情況。

• 與已有點重疊。

情況A，需要通過合理地設置單位值與無效範圍來避免。

事實上，在0至畫布寬度之間隨機生成的點保證了目標至少有一半留在畫布中。因此第一種情況可以暫時忽略。

情況B，則涉及到了碰撞檢測。

2.2 少壯幾何殘，老大徒傷悲

節操哥在《「等一下，我碰！」——常見的2D碰撞檢測》總結了多種碰撞檢測的方式。在這裡，我們就簡單的過一遍圓形碰撞檢測的原理。

這個原理一句話就能概括：兩個圓形圓心距離是否大於兩個圓形的半徑之和。

翻譯成坐標語言就是：

/**n * @desc 碰撞檢測n * @param pointA {object} A目標坐標、半徑n * @param pointB {object} B目標坐標、半徑n * @return {boolean} 是否重疊n */nfunction testOverlay (pointA, pointB) {ntconst xGap = Math.abs(pointA.x - pointB.x)ntconst yGap = Math.abs(pointA.y - pointB.y)ntconst distance = Math.sqrt(xGap * xGap + yGap * yGap)ntconst rGap = pointA.r + pointB.rntreturn distance >= rGapn}n

將之應用到整個畫布上，則需要遍歷現有所有的圓形，以檢測新生成的點是否是有效點。

我們將所有有效點都放入一個數組中，一到碰撞檢測時就遍歷一次，一旦遇到檢測失敗的點，則意味著這是個無效點；而一旦整個數組都檢測結束，且所有點都與新生成的這個點距離大於半徑之和，則這個點才是有效點。

流程圖如下：

對應遍歷檢測代碼：

/**n * @desc 有效點檢測n * @param pointArr {array} 已有點坐標、半徑集合數組n * @param newPoint {object} 新點坐標、半徑n * @return {boolean} 新點是否有效n */nfunction testAvailable (pointArr, newPoint) {n let arr = Array.from(pointArr)n let aval = truen while(arr.length > 0) {n let lastPoint = arr.pop()n if (testOverlay(lastPoint, newPoint)) {n aval = falsen break;n }n }n return avaln}n

2.3 放大招

在剛才的流程中，沒有做次數限制，結局就是當畫布差不多填滿的時候，它會一直運行下去，但卻再也找不到能填補的空白了。因此我們需要對它的嘗試次數做一個限制，增加一個計數器，每嘗試一次加一。

完善了最初的流程圖，我們可以得到：

將碰撞檢測的流程加進去，就是這樣子的——

按照這個流程圖擼代碼，思路清晰到飛起哦～

完整代碼：

• 固定半徑 See the Pen 隨機平鋪圓形 by EC (@lyxuncle) on CodePen.
• 隨機半徑 See the Pen 隨機平鋪圓形（隨機半徑） by EC (@lyxuncle) on CodePen.

3 另一種解法

其實上面的演算法，已經夠小遊戲用了。但我們換個思路，是不是會得到更加優秀的代碼君呢？

隨機生成一個點，圈好佔地範圍。然後再這個點的周圍，尋找N個有效目標，直到沒有地方為止。然後再在這個點周圍生成的有效點的周圍尋找有效點，直到再也找不到其他有效點為止。

這個時候，再到畫布範圍隨機生成一個點，然後重複上一步。直到畫布沒有位置了為止。

這種演算法我們暫且將之稱為廣搜演算法（廣度優先搜索，Breadth First Search，BFS）與隨機演算法的結合。

2.1 生成相對隨機點

生成相對隨機點的思路其實是碰撞檢測的逆推，首先在有效範圍內生成一個 x（或 y）點，同時在有效範圍內隨機生成一個半徑值，根據這兩個值，計算出對應的 y（或 x）點。

x （或 y）軸的有效範圍

我們以 x 軸坐標為例。

大家看到，上面的方法描述中，對於坐標的要求是在「有效範圍」生成。對於這個有效範圍，第一反應就是以相對點為中心，在兩個目標半徑之和間的範圍。

但是，在第一種演算法中，由於 x 與 y 的取值永遠在畫布範圍內，因此能保證至少4/1個圓形出現在畫布中，不影響用戶的定位與操作。但在這種演算法中，由於是相對取點，如果相對位置已經處於畫布邊緣，那就有極大的可能出現隨機產生的相對點過於超出畫布的情況。

我們可以通過兩種方法來解決這個問題：

• 在有效範圍可以確定的情況下，提前排除這種情況，可以減少無效點生成的次數。這種方法的劣勢在於增加了演算法複雜度。我們姑且將它稱為坐標預判斷的演算法。

/**n * @desc 生成相對隨機點n * @param prev {object} 參照點坐標、半徑n * @param size {object} 畫布長寬、半徑範圍n * @return {object} 新點坐標、半徑n */nfunction randomRelativePoint (prev, size) {n const { maxR, minR} = sizen const nextR = parseInt(Math.random() * (maxR - minR) + minR)n const dia = prev.r + nextRn const xGap = prev.x - dia < 0 ? Math.random() * (prev.x + dia) : prev.x + dia > size.w ? Math.random() * (size.w - prev.x + dia) : Math.random() * (dia * 2)n const x = prev.x - dia < 0 ? parseInt(xGap) : parseInt(xGap + prev.x - dia)n // ...n}n

其中對於 x 的隨機生成做了限制。如圖所示，如果相對目標超出了邊界，則將隨機範圍劃定為邊界至 x 加上兩目標半徑之和這個絕對距離之間。

• 在判斷有效點的邏輯中增加坐標是否超出畫布（或者更為苛刻）的判斷。這種方法也增加了演算法複雜度，但比上一個方法少了一些計算量，不過會有更多的無效點生成，消耗計數器的計數，可能會導致更多的空白區域。這個演算法我們起名坐標後判斷。

/**n * @desc 生成相對隨機點n * @param prev {object} 參照點坐標、半徑n * @param radius {number} 固定半徑n * @return {object} 新點坐標、半徑n */nfunction randomRelativePoint (prev, radius) {n const dia = radius * 2n const xGap = Math.random() * (dia * 2)n const x = parseInt(xGap + prev.x - dia)n // ...n}n

依賴已生成 x（或 y）軸坐標推導出 y（或 x）軸坐標

在這個步驟里，需要考慮的是，根據已知坐標與已知半徑值，可以得出兩個 y （或 x）軸坐標。對於這兩個可能坐標，需要再做一次隨機處理。

以 y 軸坐標的求值為例。

首先，求得三角形三邊中的 b 邊長度。

接著，隨機出一個正負值，然後求得最終的 y 軸坐標。

同樣的，坐標預判斷方法：

/**n * @desc 生成相對隨機點（隨機半徑）n * @param prev {object} 參照點坐標、半徑n * @param size {object} 畫布長寬、半徑範圍n * @return {object} 新點坐標、半徑n */nfunction randomRelativePoint (prev, size) {n const { maxR, minR} = sizen const nextR = parseInt(Math.random() * (maxR - minR) + minR)n const dia = prev.r + nextRn // ...n const sign = Math.random() - 0.5 > 0 ? 1 : -1n const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)))n const y = prev.y - yGap < 0 ? prev.y + yGap : prev.y + yGap > size.h ? prev.y - yGap : yGap * sign + prev.yn return {x, y, r: nextR}n}n

坐標後判斷方法：

/**n * @desc 生成相對隨機點n * @param prev {object} 參照點坐標、半徑n * @param radius {number} 固定半徑n * @return {object} 新點坐標、半徑n */nfunction randomRelativePoint (prev, radius) {n const dia = radius * 2n // ...n const sign = Math.random() - 0.5 > 0 ? 1 : -1n const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)))n const y = yGap * sign + prev.yn return {x, y}n}n

合到一起，就得到一個生成相對隨機點的方法。

坐標預判斷方法：

/**n * @desc 生成相對隨機點（隨機半徑）n * @param prev {object} 參照點坐標、半徑n * @param size {object} 畫布長寬、半徑範圍n * @return {object} 新點坐標、半徑n */nfunction randomRelativePoint (prev, size) {n const { maxR, minR} = sizen const nextR = parseInt(Math.random() * (maxR - minR) + minR)n const dia = prev.r + nextRn const xGap = prev.x - dia < 0 ? Math.random() * (prev.x + dia) : prev.x + dia > size.w ? Math.random() * (size.w - prev.x + dia) : Math.random() * (dia * 2)n const x = prev.x - dia < 0 ? parseInt(xGap) : parseInt(xGap + prev.x - dia)n const sign = Math.random() - 0.5 > 0 ? 1 : -1n const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)))n const y = prev.y - yGap < 0 ? prev.y + yGap : prev.y + yGap > size.h ? prev.y - yGap : yGap * sign + prev.yn return {x, y, r: nextR}n}n

坐標後判斷方法：

/**n * @desc 生成相對隨機點n * @param prev {object} 參照點坐標、半徑n * @param {minR, maxR} {object} 半徑範圍n * @return {object} 新點坐標、半徑n */nfunction randomRelativePoint (prev, radius) {n const dia = radius * 2n const xGap = Math.random() * (dia * 2)n const x = parseInt(xGap + prev.x - dia)n const sign = Math.random() - 0.5 > 0 ? 1 : -1n const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)))n const y = yGap * sign + prev.yn return {x, y}n}n

完整代碼：

• 固定半徑 See the Pen 隨機平鋪圓形（廣搜+隨機） by EC (@lyxuncle) on CodePen.
• 隨機半徑
• 演算法一：坐標預判斷 See the Pen 隨機平鋪圓形（廣搜+隨機，隨機半徑。相對隨機點演算法2） by EC (@lyxuncle) on CodePen.
• 演算法二：坐標後判斷 See the Pen 隨機平鋪圓形（廣搜+隨機，隨機半徑。坐標後判斷） by EC (@lyxuncle) on CodePen.

4 兩種演算法的對比

由於廣搜演算法與隨機演算法結合中隨機半徑的兩種演算法效率差距較為明顯，因此只取坐標後判斷演算法與隨機演算法對比。

在320x550的畫布上，兩種演算法的效率差距不大，覆蓋率（也就是密度）的差距在10%以內，相當於多畫了4-5個左右圈。

但在2000x2000的畫布上，隨機演算法的效率就遠高於兩種演算法結合的效率。在隨機半徑的情況下，兩種演算法結合的方法有時甚至需要1s的時間。而覆蓋率的差距依然在10%以內，由於畫布的增大，意味著圈的數量差距也隨之增加。

遊戲中的演算法

Human Resource Machine 是一個彙編編程的小遊戲，通過羅列代碼段來完成遊戲中的命題。從最簡單的 in/out，到簡單的數值計算，再到最後的排序演算法的實現，而僅有11個編程語句可以使用。

每一關都會對你編寫的代碼進行數量與效率的評估，你所要做到的就是對數量與效率兼顧到最好。

通過這個遊戲，會讓你對底層數據的存儲與處理有比較深的了解，同時對代碼的優化進行追根溯源。

有人說這遊戲真是反人類，現在的代碼都講究的是可讀性，以這個遊戲的評判標準，有時候是要以犧牲可讀性為代價的。但在這種極端的情況下比較容易激發大家對於演算法的探索與思考，跳出思維定式，以便找到更佳甚至最佳演算法。畢竟，人家只是個遊戲（雖然過幾天你再打開代碼也許就看不懂了）。

5 完整範例

食在會玩

範例中的代碼使用的是第二種演算法。從畫布面積來看效率上是沒啥問題的，但其實當時是從第一種演算法改為第二種演算法的，因為當時使用的第一種演算法並沒有這次 demo 整理出來的那樣順利。阿婆主也不明白髮生了什麼，也許是因為沒畫流程圖吧[摳鼻]。

推薦閱讀：