Flood Fill 演算法：遊戲背後的科學

你有沒有想過，當你在小畫家使用「油漆桶」工具，或者在玩這款遊戲時，電腦是如何知道哪些格子應該變色，哪些不該變色？這一切都源自於一個經典的電腦科學概念：Flood Fill (溢洪演算法)。

什麼是 Flood Fill？

Flood Fill 是一種用於確定多維陣列中連接區域的演算法。簡單來說，它就像是把水倒在地上，水會流向所有相連的低窪處，直到遇到牆壁或高地為止。

在我們的遊戲中：

• 水源： 你點擊的起始格子（通常是左上角）。
• 流動規則： 如果相鄰的格子顏色與目前顏色相同，水就能流過去。
• 染色： 所有水流到的地方，都會變成你選擇的新顏色。

它是如何運作的？

實作 Flood Fill 主要有兩種方法：

1. 深度優先搜尋 (DFS)

就像走迷宮一樣，選定一條路一直走到黑，撞牆了再回頭找另一條路。這通常用「遞迴 (Recursion)」來實作。

function floodFill(x, y, targetColor, replacementColor) {
  if (color[x][y] != targetColor) return;
  
  color[x][y] = replacementColor; // 染色！
  
  floodFill(x+1, y, targetColor, replacementColor); // 右
  floodFill(x-1, y, targetColor, replacementColor); // 左
  floodFill(x, y+1, targetColor, replacementColor); // 下
  floodFill(x, y-1, targetColor, replacementColor); // 上
}

這種寫法簡單優雅，但如果區域太大，可能會導致「堆疊溢位 (Stack Overflow)」錯誤。

2. 廣度優先搜尋 (BFS)

這是本遊戲採用的方法。就像水波擴散一樣，先處理周圍一圈，再處理更外圍的一圈。我們使用一個「佇列 (Queue)」來記錄待處理的格子。

1. 將起始格子放入佇列。
2. 從佇列取出一個格子，將其染色。
3. 檢查它上下左右的鄰居，如果是同色且未處理過，就加入佇列。
4. 重複直到佇列清空。

遊戲中的應用

除了基本的染色，這個演算法也用於：

• 計算連通區域： 判斷當前擁有的領地大小。
• 提示系統： 電腦會在後台模擬每種顏色的 Flood Fill 結果，幫你找出能獲得最大收益的那一步。

下次當你點擊色盤時，別忘了背後有個勤奮的小演算法，正在以毫秒等級的速度為你計算路徑呢！