About Conway's Game of Life Applet of Alan Hensel

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有時塊中的細胞會出現(xiàn)穩(wěn)定的情況，不需要進一步處理。你可以把塊從隊列中移出，把它設(shè)置成“冬眠”狀態(tài)，只有當(dāng)鄰近的塊影響到它。這些塊不需要占用處理器的時間，象空白的區(qū)域一樣。

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

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

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

源代碼
以下是我的超級快速的Game of Life applet源代碼。
很抱歉這些不是百分百面向?qū)ο蟮摹ame of Life并不適合面向?qū)ο蠹夹g(shù)。面向?qū)ο筮m用于你碰到的大多數(shù)問題，除了那些效率第一而且相當(dāng)復(fù)雜的項目，康威的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 閱讀(723) 評論(0)  編輯 收藏 引用 所屬分類: Java