关于“生命”游戏由此进。
关于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不熟，不敢妄言。
有空还可以继续研究。先到此为止。反正作业就这么稀里糊涂交上去了。