Conway生命游戏
2019-11-29

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址  http://www.cnblogs.com/Colin-Cai/p/9986679.html   作者:窗户  QQ/微信:6679072  E-mail:6679072@qq.com

  1970年,英国数学家Conway发明了生命游戏。抛开元胞自动机的复杂概念,我们只是去感受一下二维的生命游戏,这其实是元胞自动机的一个特例。

  

  生命游戏

  

  我们先考虑有限的情况,对于mXn的方格,每个方格都会有一个状态,该状态有两个可能值:有生命、无生命。

  

  如上图8X8的方格,红色的格子代表状态为有生命,白色的格子代表状态为无生命。

  生命游戏是一代一代的演化,每一代就是所有格子的一组状态。我们来说演化规则,对于每个格子,我们来数这个格子所有的周围格子状态为由生命的数目。

  这里的周围格子是指:这个格子的上、下、左、右、左上、右上、左下、右下这8个格子。当然,有例外,角上的格子只有3个周围格子,而边上的格子只有5个周围格子。

  于是,我们把上面这个图的每个格子的周围有生命格子数目标注出来。

  

  下一代所有格子状态由以下规则确定:

  1.如果周围有生命格子的数目小于2,则下一代这个格子状态为无生命(解释为太孤单)。

  2.如果周围有生命格子的数目大于3,则下一代这个格子为无生命(解释为周围生命太多,资源消耗厉害)。

  3.如果周围有生命格子的数目等于2,则下一代这个格子的状态继续保持当前的状态。

  4.如果周围有生命格子的数目等于3,则下一代这个格子的状态为有生命。

  

  于是,下一代应为如下:

  

  

  把各代组成动画如下:

  

  只可惜这个到了第6代,所有的格子都变成无生命状态。

 

  震荡子

 

  有一类神奇的图案,可以反复不断的循环,称为震荡子。

 

  

  上面这个震荡子周期为15。

 

  枪型图

  

  下面这个图是Bill Gosper于1970年发现的第一个Gun,你看那一个个向右下方向而去的像不像“子弹"?实际上,Gun描述的是一个无限的方格,因为子弹是在不断变多的,图形的尺寸实际上会越来越大,但在有限的方格情况下其实是震荡子(下图实际上是虚拟的从无限的方格中截取的有限图像)。

  

  

  这是发现的第二个Gun。

  

  以我的能力,我是完全不知道这两个Gun是怎么被拼出来的。

  

  程序实现

 

  生命游戏规则简单,我想在学习程序的过程中实现一个并不是什么难事。

  我上面的这些动画实际上也是用程序生成的,我推荐python用cv2库,它属于opencv,开发效率还是很高的。

  真想从底层动手,那就用C语言造轮子吧,只要体力好,也没什么不可以。

  如果要生成bmp,研究一下bmp文件的格式,wiki上就有,https://en.wikipedia.org/wiki/BMP_file_format

  如果想要jpeg,那么可以使用libjpeg,只是libjpeg只有从bmp文件转成jpeg,默认接口里没有从内存转的,这可能不太方便,需要的话得自己来加个接口,很多年前我加过。

  

  计算周围生命格子数目

  

  我想大部分的人来计算都是对于某个点,依次数周围的格子,然后挨个相加,从而计算整个矩阵的加法数量的线性系数是7(因为大多格子周围都是8个格子,要做7次加法),也就是加法数量除以矩阵规模(节点数)的极限为7。

  如果只从加法数量来说,这个规模不能让人满意。下面这个方法会好很多。

 

  第一步,同行的两两结对相加。

  

  a0,0+a0,1 a0,2+a0,3 a0,4+a0,5 ...

  ...

  an,0+an,1 an,2+an,3 an,4+an,5 ... 

  ...

  这样使用线性系数0.5次加法

  

  第二步,每个格子再多加一次得到这个格子自身和左、右两格的和。

  

  显然,这次使用加法数量系数为1。

  于是我们看到了,使用系数为1.5的加法数量就完成了每个格子自身和左、右两格的和,而本来平凡的手段这个系数为2。

 

  第三步,在此基础上,使用第一步、和第二步,只是第一步和第二步从矩阵的横向考虑,现在统统改成纵向。

  

  这样就得到了每个格子以自身为中心的九宫格的九个格子之和。

  这样累计一下,系数翻个倍,为3。

 

  第四步,上面其实多加了自身这个格子,于是减掉自身。

  系数就变成4,比之前7要好。

 

  以上只是简单的说一说道理,而真正在优化卷积、中值滤波等应用的时候,要比这个复杂的多。

 

  稀疏矩阵

 

  先放个动画。

  

  我们似乎在上述动画中看到了星际战争^_^

  图像中大多数格子的状态都是无生命,这种情况下,如果还是依次去计算矩阵的每一个格子,是个很大的浪费。

  实际上,我们只需要记录其中状态为有生命的格子就行了,这是因为,下一代有生命的格子就在这一代有生命的格子的近旁。

  这就是稀疏矩阵的出发点,当然,稀疏矩阵本身有着非常多的算法,基本都是本着相近的元素会发生相互作用,从而相近的元素要给予更为快速的查找。对于完全无序的集合,稀疏矩阵的元素一旦多起来,效率非常低下。

  有兴趣的就自己去研究吧,比如四叉树就是常用的空间索引。