brent's hut

LifeApplet 阅读笔记

关于“生命”游戏由此进
关于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不熟,不敢妄言。

有空还可以继续研究。先到此为止。反正作业就这么稀里糊涂交上去了。

posted on 2005-08-11 17:32 brent 阅读(323) 评论(0)  编辑 收藏 引用 所属分类: Java


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理