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