關于“生命”游戲由此進。
關于LifeApplet由此進，源文件下載。
本來想自己用wtl寫個CA(細胞自動機)程序，閱讀了LifeApplet后打消了念頭。寫這篇筆記像初中時一個月語文作業沒寫最后濫竽充數幾篇交上去，算是給自己一個交待。
怎么寫一個CA程序和想寫怎樣的一個CA程序有關。剛看完《上帝與新物理學》，我按照書上的規則和圖案寫了一個世界只有20*20大小的CA，細胞的運算是一個個計算的，計算一代就刷新顯示一次，一個細胞用一個字節來保存，可以原諒的是我當時連規則都不清楚，目的只是驗證一下規則。
看了Alan Hensel的代碼后，可能大部分寫過CA程序的人都會覺得汗顏。-_-|||。體驗過Alan Hensel 的LifeApplet的人就會看到:他的世界真大，實際上有2^20 * 2^20個像素；速度真快，可以設置fps(每秒刷新次數)，Generations/Frame(每次刷新間隔生產多少代)，如果設置為warp，CPU就會撒開腿跑起來...還可以設置規則，CA的規則不止Conway的那個，其它的也很有趣。
數據結構：
LifeCell:
Alan Hensel將世界分成一個個16*16的單元，用LifeCell類表示。每個LifeCell包含兩個數組表示 p[]，q[] = new short[16]，總共16*16 bits，表示16*16個細胞。并且在這個數組中按照一種奇怪的方式來排列，比如LifeCell中坐標為(1,1)的點在數組中的位置是65(見LifeCell文件)，代表這個點的bit就在p[6](和q[6])的左起第5位。為什么要這么表示？我想是作者為了以后unroll算法的方便。他究竟怎么得出這個方法的，我不知道。。
每個LifeCell需要兩個數組是因為CA的算法要求的運算必須是并行的。所以只能p生成q,q生成p，沒什么好說的。
每個LifeCell保存了相鄰的東、西、南、北、東南、東北、西南、西北的LifeCell的指針。
保存了上一個，下一個LifeCell的指針。所有LifeCell保存在一個鏈表中。
保存了上一個，下一個需要顯示的LifeCell的指針，用于顯示。
保存了一個Down的LifeCell的指針，用于hash查找。
保存了坐標x,y。
保存了一些狀態，qstate,pstate,flags為運算和優化用的。
LifeHash:
因為所有LifeCell都放置于一個鏈表。而經常要用LifeCell的坐標來查找LifeCell，比如修改某個點的狀態：為了在某個點放置一個細胞，需要通過點的坐標運算出LifeCell的坐標，再通過LifeCell的坐標找到LifeCell對象。
在鏈表中查找一個對象的運算復雜度是o(n)。n在此處最大可達2^16 * 2^16(把整個世界都占滿，這也相當不容易)，所以對于一些超大的CA來說，查找起來會很浪費時間。。。所以有了LifeHash類。
LifeHash中保存了一個2^HASHSIZE * 2^HASHSIZE的LifeCell對象指針數組，數組中每個對象維護一個鏈表，坐標x,y中低HASHSIZE位的值一樣的LifeCell放在這個鏈表中。通過x,y可以快速找到這個鏈表，然后用上面說到的Down指針，比較(x,y)來找到具體的LifeCell。這樣理論上來講減少了查找時間...(我算不出來，哈)。究竟用多大的HASHSIZE才好？作者的值是6，就是占用了2^12 * sizeof(int) = 16k bytes內存。
LifeRules：
LifeRules的目的在于把用字符串表示的規則轉化成一個bool[512]。
比如"23/3"表示有2個或3個相鄰細胞的細胞繼續存活，如果一個位置旁邊剛好有3個細胞，這個位置在下一步就要長出一個細胞。
由于一個位置有8個相鄰的位置，加上自身為9位。把9個位置排序得到一個數，總共512個。比如對于0xC8，表示西北、西有細胞，自身有細胞，根據"23/3" bool[0xC8]的值應該為true。
算法：
為了提高效率，Alan Hensel把LifeCell中每個4*4的運算都unroll了。所以在LifeGen文件中可以看到進一步的setRules(boolean[] Rule)函數，這個函數設置了了crunch(和munch)= new short[65536]。原理和LifeRules中類似，就是不知道這個運算過程怎么得出的，作者數學肯定非常好。。
因為細胞的運算是以LifeCell為單元來運算的，一個單元的細胞會影響到相鄰的單元。如果每次運算的時候都考慮相鄰8個LifeCell的話，會造成CPU的浪費。所以在LifeGen中可以看到運算p狀態和q狀態時，LifeCell的位置是不一樣的。從p狀態生成q狀態時，檢查了東、南、東南方向相鄰的LifeCell，生成的q狀態的位置為p狀態往東南各偏移一個細胞。所以如果p狀態起始坐標為16x,16y，那么q狀態時，起始坐標是16x+1, 16y+1(注意坐標系映射為MM，x在往東方向為正，y在往南方向為正)。在從q狀態到p狀態時，檢查西、北、西北方向相鄰的LifeCell，回到p狀態的位置。
其中具體的運算就算了吧，反正我沒看明白。看明白的地方也不知道為什么。。作者太強悍了。
線程：
這種程序當然至少要兩個線程了，一個UI線程，一個Work線程。UI線程在LifeFrame中，沒做什么事，就是把事件發送給Life對象(見Life.Java)，Life收到事件后并沒有馬上處理，而是放到一個隊列中LifeQueue。
UI線程一啟動，就啟動了work線程。
在Life的run()中，處理細胞的繁衍LifeGen.generate()，顯示，然后處理LifeQueue中的事件。
在LifeGen.generate()中控制生成繁衍的次數和顯示的速度。
為什么兩個線程同時對LifeQueue操作卻沒有聲明synchronous呢？對java不熟，不敢妄言。
有空還可以繼續研究。先到此為止。反正作業就這么稀里糊涂交上去了。