brent's hut

About Conway's Game of Life Applet of Alan Hensel

[A Life pattern called the puffer train]

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

 当前版本0.41d,更新时间2001-1-31,比0.41c版(199-1-22)上提高了些性能。新版本在计划中,只要我的空余时间允许。
 作者:Alan Hensel,

简介:
认识我的人都知道我为什么写这个程序。不是为了学习Java,不是为了提高我的网站的访问量,原因很简单:
我收集Life patterns,而且我喜欢展示它们

当然,这些patterns中的大部分是别人发现的。没人想要从这些Life patterns中获利,所以据我所知这些patterns将留给后代并被赏识,就象国际象棋一样。

请不要给我写信说:我喜欢你的程序,却忘记提起这些patterns。这听起来会象是恭维集邮爱好者他的邮册如何漂亮,对邮票却只字不提。我的程序只是做了它们该做的事情而已。

计算机软件和硬件只是使用者和他的数据之间的工具

这些patterns让人赞叹。如果不信,你可以自己去做一个试试。(我希望这个挑战能促成一些发现。)


给那些写Life程序的学生:
我没有可以给你的源代码。这里没有你找的东西。我提供了这个程序的源代码,但它们超出了计算机课程的范围。它们之所以这么复杂是因为速度优化(这样我才能运行"Breeder"或者其它更大的patterns)。当然,你可以试着读读源代码,但不要强迫自己。你写的作业应该比这个程序简单一百倍。

给来这里学习Java applets的读者:
这是我第一个真正意义上的applet。最好别打算把我的代码拷贝到你的程序中。源代码就在这一页的底部,你可以免费下载,当然,你必须为它付出些东西。若非如此,这将会是一个让人相当有学习动力的applet程序。

你怎么做到这么快的?

好的。没有留心的话也许你不会发现我的程序闪电一样的快。你也许没看到"Warp Speed"按钮,或者你还没用过它,或者你觉得这无所谓。这样的话你可以跳过这个部分。
有人问,你究竟是怎么让它跑得这么快的?!对于这些好奇者,或者那些打算写自己的超级细胞自动机程序的人,我会解释的。

我倾向于把细胞自动机的优化和数据压缩联系起来。这也是一个简单的概念却需要复杂的方法。究竟什么才是最好的方案取决于数据本身。对于康威的Life,倾向于出现点状的图案。

对于点状分布的世界,我们应该考虑把它分割成近似大小的块。对于Life来说,4x4和8x8都是可取的。我选择了8x8,因为:刚好8比特1字节,我曾经考虑过4x4,但运行起来效果不大好。

并且请注意:如果pattern长大并超过了块的范围,需要引入新的块。你可以简单的线性搜索,也可折半查找,或者维护某种映射。我的方法是哈希表。这个表只是用来查找一个新块的邻居。每个已存在的块已经有它的邻居的指针,并且会被多次使用。

必须有高效的算法来处理这些块内部的数据,我选择一次处理块中的所有数据。在处理完整个块之前不需要跳转语句。换句话来说:所有内部循环都被unroll了,并使用了高速的查询表。

注意:CA(细胞自动机)程序一般性的包含了两个主要循环(加上一个显示循环),因为CA规则要求对细胞进行并行处理,但微处理器是线性的。这意味着必须有世界的两分拷贝,这样创建下一代的时候本身的信息才不会被破坏掉。通常这两个拷贝是不对称的。这对我来说相当麻烦,因为每次我从这边取出些东西进行优化,不得不在另一边加点别的什么!几乎每次,例外的情况导致了最好的优化。特别的,需要在位操作:位移,屏蔽和重组之间折中来找一个最好的查找表。

有时块中的细胞会出现稳定的情况,不需要进一步处理。你可以把块从队列中移出,把它设置成“冬眠”状态,只有当邻近的块影响到它。这些块不需要占用处理器的时间,象空白的区域一样。

检测周期为2的振荡器并把它移出处理队列并不难。这对于Life程序是值得的,因为blinker是最常见的随机的残余物。更复杂的振荡器相对比较少见。检测并模拟滑翔机也是可能的。这些方面的优化会得到递减的效果,除非你做到极致。(如HasLife)。

同样,死亡状态:空的块不必马上释放并从哈希表中移走。那样会占用更多的处理器时间,尤其是当振荡器在一定空间内移进移出的时候。仅当可用内存已经很少的时候,才从死亡队列中移除最老的死亡的块。

当程序快到一定程度,必须考虑刷新显示的速度不需要超过人眼可以感知的速度,或者最少不需要超过显示器的刷新频率。特别是在视窗环境,显示时间会是效率的瓶颈。


源代码
以下是我的超级快速的Game of Life applet源代码。
很抱歉这些不是百分百面向对象的。Game of Life并不适合面向对象技术。面向对象适用于你碰到的大多数问题,除了那些效率第一而且相当复杂的项目,康威的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 阅读(473) 评论(0)  编辑 收藏 引用 所属分类: Java


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理