加速元胞自動機

Question

用某種算法或類似的算法加速元胞自動機是否可能？我使用的是a Conway's Game of Life implementation made in XNA，它工作完美，但問題是，當我使用大於128x128的網格時，它會變得非常慢。

我不認爲是與代碼或XNA如何處理紋理和繪圖，但事實上，更新這麼多的單元格（即評估每個單元格的鄰居，並基於獲得其新的狀態）它是計算的lot。

當然，理想的細胞自動機應該是無限大的，但實際上這是不可能的。但在我看來，128x128太小而不能真正看到系統的行爲。

任何幫助將不勝感激！

Answer 1

如果你try this幾次，你會看到時間的推移。

一個不應該猜測，但我的猜測基本上是所有的時間進入渲染。 鄰居評估可能看起來像很多代碼，但很可能是非常簡單的。 如果您有辦法避免重新渲染未更改的單元格，這可能會節省很多。

Answer 2

我會推薦使用OpenGL和GLSL。通過這種方式，您可以消除從CPU到GPU的數據傳輸，並獲得10倍或更高的不錯加速。

Answer 3

Hashlife算法使用四叉樹，散列和記憶來壓縮CA的時間和空間，以大幅度提高性能。查看Golly獲取示例實現。

我仍然試圖找出自己，並尋找好的圖書館。

這裏有很好的解釋（例子代碼）：http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478。