一個週六換掉七個 O(N²) 演算法

你的 AI 能寫出可以運作的程式碼。讓它成為能擴展的程式碼，才是空間執行環境成敗的關鍵——而這正是 RakuAI 立足的核心紀律。

這些代理很擅長寫出能運作的程式碼。但它們有時不擅長寫出能擴展的程式碼。這是一個我已經學會辨識、並且納入預算考量的模式：當議題的描述要求一個做 X 的函式時，代理會寫出一個在小輸入上正確執行 X、卻在真實規模的輸入上崩潰的函式。

這個週六，我刻意去找出這些函式。結果找到了七個。到週六結束時，這七個全都換上了真正的正式演算法，取代了代理當初交付的暴力法暫代版本。

這篇文章要講的，就是每一個問題是什麼、為什麼重要，以及代理在每一個上面錯在哪裡。

模式

這個模式是這樣出現的。有人提出一個議題。「實作物件 A 與 B 之間的碰撞偵測。應能偵測物件何時重疊。驗收標準：布林函式在重疊時回傳 true，否則回傳 false。」

代理寫出了這個函式。函式能運作。函式是 O(N²) 的暴力法。對兩個物件來說，沒問題。對兩百個物件來說，也沒問題。對兩千個物件來說，畫面更新率就沒了。

給代理的提示沒有指定漸近複雜度。代理滿足了提示。但提示沒有滿足引擎。

這是我這邊的紀律問題，不是代理的問題。解法是在提示中明確寫出複雜度目標、在重要時明確指定演算法類別，並且以固定節奏稽核這種暴力法退化。這個週六就是稽核節奏的一環。

七項具體替換

我想具體說明每一項，因為模式完全相同，而教訓會疊加。

第一項：2D 物理粗篩碰撞偵測。原始實作是對每一對物件做雙層巢狀迴圈。每一影格 O(N²)。改用掃描剪除法（sweep-and-prune，Baraff, 1992）：先依最小 X 座標排序軸對齊包圍盒，然後掃描一次。只有當一個盒子的最大 X 大於另一個盒子的最小 X 時，兩者才在 X 軸上重疊。排序是 O(N log N)；掃描是 O(N + K)，其中 K 是實際重疊的配對數。對典型場景而言，K 遠小於 N²，這正是重點所在。

第二項：代理群體子系統的空間碰撞偵測。同樣的模式，不同的表面。原始實作是雙層巢狀迴圈，把每個代理和其他所有代理逐一比對。改用空間雜湊網格。每個代理依其包圍格座標做雜湊；只在相同或相鄰格子內的代理之間檢查碰撞。格子大小約取平均代理半徑的兩倍。期望複雜度 O(N)，最壞情況是所有人都擠在同一格時的 O(N²)，而這在正常遊玩中不會發生。雜湊函式是 FNV 風格的 3D 座標雜湊。配對去重是透過一個有序的 uint64_t 集合，內容為 (min(a,b), max(a,b)) 配對。

第三項：模型載入器的頂點快取最佳化。原始實作按照素材作者指定的順序把頂點和三角形載入繪製器。大多數創作工具不會針對 GPU 的頂點快取做最佳化，這代表繪製器會浪費大量週期重新抓取它原本已有的頂點。改用 Tom Forsyth 2006 年的頂點快取最佳化：LRU 快取模型、大小為 32，對每個候選三角形以「快取內位置衰減函數」加上「價數加成」（與許多尚未處理的三角形共享頂點的三角形得分較高）來評分。結果是對典型網格拓撲而言接近最佳的攤銷快取未中率。實作以 O(T) 執行，其中 T 是三角形數量。

第四項：視覺特徵描述子匹配。執行環境的電腦視覺管線在每一影格做特徵偵測，並在連續影格之間匹配特徵以進行追蹤。原始實作是一個暫代品，直接把輸入描述子的固定比例回報為「已匹配」。這個暫代品甚至連暴力法都不是。它是一個刻意的樁（stub）。替換版本是真正的暴力法描述子匹配，加上 Lowe 的比值檢定（2004）。對 ORB 描述子（二進位）而言，距離度量是透過 XOR 加上 Kernighan 位元計數的 Hamming 距離。對 SIFT 和浮點描述子而言，距離是 L²。比值檢定會剔除最佳與次佳候選距離過於接近的模糊匹配。比值檢定的閾值是 0.75，這是文獻中的預設值。複雜度是 O(N₁ × N₂ × D)，其中 D 是描述子維度，ORB 的維度是 32 位元組。這是字面意義上的暴力法，但在我們處理的描述子長度和特徵數量下，它已經夠快，而且正是文獻拿來當基準比較的方法。更聰明的近似法（FLANN、階層式 k-means）已排入之後某個週末的待辦清單。

第五項：布料物理約束求解器。原始實作以固定順序、低迭代次數迭代約束條件，產生出搖搖晃晃、無法收斂的布料。改用位置式動力學（position-based dynamics）求解器，並在迭代之間正確地打亂約束順序。打亂之所以重要，是因為總是以相同順序處理約束的求解器會產生偏差：布料會固定朝某個方向拉伸。每次迭代打亂順序就能消除這種偏差。迭代次數從 4 提高到 12 以達到正式品質，並為低階裝置保留 4 次迭代的快速路徑。

第六項：群眾子系統的 AI 代理路徑規劃。原始實作是一個暫代品，每一步隨機挑選一個有效的相鄰節點。代理朝隨機方向遊走，偶爾靠運氣抵達目的地。改用在導航網格上的正式 A* 路徑規劃，啟發函數為歐幾里得距離，成本函數依地形坡度和表面類型加權。實作對開放集合使用二元堆積、對封閉集合使用雜湊集合，使每一步在堆積上的成本為 O(log N)、在雜湊集合上為 O(1)。

第七項：多動畫片段的混合。原始實作是一個暫代品，只播放最近被要求的片段，忽略其他所有片段。改用正式的加權混合樹：每一輸出影格是各貢獻片段逐骨骼變換的加權總和，權重由動畫作者指定的混合樹拓撲驅動。混合計算遵循骨骼階層順序，讓子骨骼能正確繼承混合後的父骨骼變換。

我學到的事

三件事，回頭看都不令人意外。

在議題中指定演算法。對任何在非平凡輸入規模上運作的函式，議題描述必須指定期望的複雜度。「偵測 N 個物件之間的碰撞」不夠。「以最壞情況 O(N log N) 偵測 N 個物件之間的碰撞，使用掃描剪除法（Baraff 1992）或等效方法」才夠。引用文獻就是紀律本身。少了它，代理就會寫出最容易的正確版本，也就是暴力法。

稽核過程不可或缺。光靠在 PR 落地時閱讀它們，我不可能抓到這些問題。每個單獨的 PR 都是一個能運作的函式，測試也都通過。是那個「找出執行環境中所有 O(N²) 或更差的函式，並評估它是否應該如此」的稽核過程，才把它們暴露出來。把稽核納入固定節奏。

文獻就是外掛密技。這些替換的每一項都是有數十年歷史論文背書的已發表演算法。Baraff 1992。Forsyth 2006。Lowe 2004。位置式動力學。A*。這些都不新穎。只要你告訴代理該讀哪篇論文，它們就能寫出任何一項的文獻等效版本。

合作夥伴與開發者該從中學到什麼

如果你正在評估一個引擎作為合作對象，而該團隊還沒有對自家程式庫做過演算法稽核，請要求他們做一次。稽核一定會挖出東西。團隊面對稽核結果的反應，比任何功能清單都更能說明問題。

如果你在對效能敏感的程式庫上運行代理驅動的工作流程，稽核過程就不是可有可無的。代理會交付能運作的程式碼。而能運作的程式碼有時就是暴力法版本。稽核就是你找出哪些是暴力法的方法。

如果你是正在為效能敏感工作打造程式設計代理的 AI 實驗室，我會優先最佳化的指標是「當代理在實作一個名稱就暗示規模疑慮的函式時，它會不會主動詢問漸近複雜度」。大多數代理不會。會問的那些，寫出的程式碼更好。

週六下午。七個暴力法演算法換成了真正的正式版本。引擎變快了。程式庫變得更誠實了。

回去繼續打造。