About Conway's Game of Life Applet of Alan Hensel

原文:http://www.ibiblio.org/lifepatterns/lifeapplet.html

?當前版本0.41d，更新時間2001-1-31，比0.41c版(199-1-22)上提高了些性能。新版本在計劃中，只要我的空余時間允許。
?作者:Alan Hensel,

簡介：
認識我的人都知道我為什么寫這個程序。不是為了學習Java，不是為了提高我的網站的訪問量，原因很簡單：
我收集Life patterns，而且我喜歡展示它們

當然，這些patterns中的大部分是別人發現的。沒人想要從這些Life patterns中獲利，所以據我所知這些patterns將留給后代并被賞識，就象國際象棋一樣。

請不要給我寫信說：我喜歡你的程序，卻忘記提起這些patterns。這聽起來會象是恭維集郵愛好者他的郵冊如何漂亮，對郵票卻只字不提。我的程序只是做了它們該做的事情而已。

計算機軟件和硬件只是使用者和他的數據之間的工具。

這些patterns讓人贊嘆。如果不信，你可以自己去做一個試試。(我希望這個挑戰能促成一些發現。)

給那些寫Life程序的學生：
我沒有可以給你的源代碼。這里沒有你找的東西。我提供了這個程序的源代碼，但它們超出了計算機課程的范圍。它們之所以這么復雜是因為速度優化(這樣我才能運行"Breeder"或者其它更大的patterns)。當然，你可以試著讀讀源代碼，但不要強迫自己。你寫的作業應該比這個程序簡單一百倍。

給來這里學習Java applets的讀者:
這是我第一個真正意義上的applet。最好別打算把我的代碼拷貝到你的程序中。源代碼就在這一頁的底部，你可以免費下載，當然，你必須為它付出些東西。若非如此，這將會是一個讓人相當有學習動力的applet程序。

你怎么做到這么快的？
好的。沒有留心的話也許你不會發現我的程序閃電一樣的快。你也許沒看到"Warp Speed"按鈕，或者你還沒用過它，或者你覺得這無所謂。這樣的話你可以跳過這個部分。
有人問，你究竟是怎么讓它跑得這么快的？！對于這些好奇者，或者那些打算寫自己的超級細胞自動機程序的人，我會解釋的。

我傾向于把細胞自動機的優化和數據壓縮聯系起來。這也是一個簡單的概念卻需要復雜的方法。究竟什么才是最好的方案取決于數據本身。對于康威的Life，傾向于出現點狀的圖案。

對于點狀分布的世界，我們應該考慮把它分割成近似大小的塊。對于Life來說，4x4和8x8都是可取的。我選擇了8x8，因為:剛好8比特1字節，我曾經考慮過4x4，但運行起來效果不大好。

并且請注意：如果pattern長大并超過了塊的范圍，需要引入新的塊。你可以簡單的線性搜索，也可折半查找，或者維護某種映射。我的方法是哈希表。這個表只是用來查找一個新塊的鄰居。每個已存在的塊已經有它的鄰居的指針，并且會被多次使用。

必須有高效的算法來處理這些塊內部的數據，我選擇一次處理塊中的所有數據。在處理完整個塊之前不需要跳轉語句。換句話來說：所有內部循環都被unroll了，并使用了高速的查詢表。

注意：CA(細胞自動機)程序一般性的包含了兩個主要循環(加上一個顯示循環)，因為CA規則要求對細胞進行并行處理，但微處理器是線性的。這意味著必須有世界的兩分拷貝，這樣創建下一代的時候本身的信息才不會被破壞掉。通常這兩個拷貝是不對稱的。這對我來說相當麻煩，因為每次我從這邊取出些東西進行優化，不得不在另一邊加點別的什么！幾乎每次，例外的情況導致了最好的優化。特別的,需要在位操作：位移，屏蔽和重組之間折中來找一個最好的查找表。

有時塊中的細胞會出現穩定的情況，不需要進一步處理。你可以把塊從隊列中移出，把它設置成“冬眠”狀態，只有當鄰近的塊影響到它。這些塊不需要占用處理器的時間，象空白的區域一樣。

檢測周期為2的振蕩器并把它移出處理隊列并不難。這對于Life程序是值得的，因為blinker是最常見的隨機的殘余物。更復雜的振蕩器相對比較少見。檢測并模擬滑翔機也是可能的。這些方面的優化會得到遞減的效果，除非你做到極致。(如HasLife)。

同樣，死亡狀態：空的塊不必馬上釋放并從哈希表中移走。那樣會占用更多的處理器時間，尤其是當振蕩器在一定空間內移進移出的時候。僅當可用內存已經很少的時候，才從死亡隊列中移除最老的死亡的塊。

當程序快到一定程度，必須考慮刷新顯示的速度不需要超過人眼可以感知的速度，或者最少不需要超過顯示器的刷新頻率。特別是在視窗環境，顯示時間會是效率的瓶頸。

源代碼
以下是我的超級快速的Game of Life applet源代碼。
很抱歉這些不是百分百面向對象的。Game of Life并不適合面向對象技術。面向對象適用于你碰到的大多數問題，除了那些效率第一而且相當復雜的項目，康威的Game of Life正好屬于這種情況。

以下是16個源文件:

LifeButton.java
LifeFrame.java
Life.java
LifeGUI.java
LifeGen.java
LifeCell.java
LifeHash.java
LifeCoordinate.java
LifeRules.java
LoadBox.java
RuleBox.java
SpeedBox.java
OptionsBox.java
LifeQueue.java
LifeCallback.java
DescribeBox.java

posted on 2005-07-22 18:15 brent 閱讀(713) 評論(0)  編輯 收藏 引用 所屬分類: Java