首页 > Note > 生命游戏&兰顿蚂蚁

生命游戏&兰顿蚂蚁

2013年11月2日 发表评论 阅读评论

最近在这里看到看到了一个开源的软件——Golly,这个主要就是研究生命游戏的,正所谓:科研软件!!【这个还有IOS上的应用】

这个说起来我想起来本科曾经用C++和opencv画过兰顿蚂蚁。。。

生命游戏,其实就是一个元胞自动机,或者叫细胞自动机(元胞自动机的第一次接触还是在本科看一位师兄写的前一届的数模论文上面看到的,用元胞自动机来分析病毒的感染问题!当时觉得很有意思,专门去接触过一下下。。),回到正题,生命游戏,名为游戏,其实就是一个零玩家的“游戏”,维基百科曰:

The "game" is a zero-player game

什么意思呢?就是说,这个游戏的结局只取决于“游戏”初始化的状况而已;起始,决定结局!那为什么叫做游戏呢?这能说这个起名字的人对这个游戏,爱得深沉!!嘛~其实这个东西还真的挺好玩的,变化太多,乐趣无穷~

简单介绍一下这个所谓的生命游戏吧,这个游戏其实就是模拟一个二维世界中的点的变化,在一个二维世界中,初始化所有点的状况,每个点只有两种状态:死,或者活!然后下一时刻,每个点的状况只取决于上一时刻这个点周围八个点的状态而已,具体如下:

  1. 周围(指周围八个点)如果只有少于等于一个点的状态是活,那么这个点下一时刻变成!可以认为是人口太少导致的。
  2. 周围如果有两个点是活的,那么下一时刻状态不变
  3. 如果有超过三个是活着的,那么下一时刻这个点会变成的状态,可以认为是竞争!
  4. 如果一个点是的,但是周围恰好有且仅有三个是活的,那么下一时刻这个点会变成的,原因可以理解为再生。

嗯,就是这样一个简单的规则,但是却可以变化出无穷的好玩的东西来。Mathematica实现的话,这个迭代的过程的代码就是:


mathematica code


然后我们随机初始化一个二维点阵,不断迭代,看看变化:好吧,其实看不出什么来的是吧,毕竟嘛,这个初始状态是随机生成的,所以连最后会不会稳定在几个固定的状态中轮回都是个不确定的。像上面这个最后就没有稳定下来,一直“无序”地乱变。

也有一些最后会稳定下来的例子,比如说起始状态像一个类似π的形状,最后会变成一张卖萌的脸的样子。。。。

其实嘛,研究这个的人都会对这个生命游戏里面的几个最基本的模式很熟悉的,这些模式的特性就是相对稳定,从上面那个最后稳定下来的样子我们就可以有所理解。

维基娘所言,比如说下面这些,所谓的静止模式,不断迭代的话始终保持不变!

Still lifes
Block Game of life block with border.svg
Beehive Game of life beehive.svg
Loaf Game of life loaf.svg
Boat Game of life boat.svg

也有一些短周期的振荡模式:

Oscillators
Blinker (period 2) Game of life blinker.gif
Toad (period 2) Game of life toad.gif
Beacon (period 2) Game of life beacon.gif
Pulsar (period 3) Game of life pulsar.gif

更有甚者,还有“太空漫步式”的:

Spaceships
Glider Game of life animated glider.gif
Lightweight spaceship (LWSS) Game of life animated LWSS.gif

需要说一句的是,虽然这些模式独立的时候很稳定,但是一旦遇到“外敌”,哪怕是一个点,就会完全“混沌化”,你根本把握不了它最后会变成什么样子!!

还是维基娘,它里面介绍了一种叫做Gosper glider gun的模式,通过QQ截图直接粘贴导入mathematica,然后简单图像处理我们就可以赋好二维点阵初值:

很有意思不是么?

生命游戏的有趣之处在于,本来是一种变化的,但是改变一下周围的模式,很可能就会变成另一种状况了,像上面的那个π的方案,周围放两个蛇状的东西:(图片来自果壳然后就会变成这种演化,原本的卖萌就被吞噬了。。很有意思吧。生命游戏还有很多神奇的变换方式,比如说一开始说的Golly的那个主页,这个元胞自动机简直碉堡:利用Golly的软件,就可以很容易作出自动表白机这种Geek专用的神器。。。还有一些更吓人的,比如说下面这个,用生命游戏的模式来生成生命游戏。。。真是让人叹为观止。。【预计视频应该有广告。。】:


兰顿蚂蚁(Langton Ant):

还有一种元胞自动机叫做兰顿蚂蚁的,度娘百科说是一个叫做克里斯托夫·兰顿提出的,年代未知,也不想了解;

和上面的生命游戏的不同点在于,每一时刻只有一个点的状态需要变换,我们可以认为初始状态下二维平面上有一只蚂蚁,朝着某个方向,然后如果这一时刻蚂蚁所在的格子的状态是1,那么蚂蚁右转90°,把当前格子变成0,然后前进一步,如果所在格子状态是0,那么蚂蚁左转90°,把当前格子变成1,然后前进1步,就是按照这个规律不断的移动。。。

我当年第一次听到这个规则的时候,一开始直觉上觉得,这样应该很快就循环,不断的绕圈子了吧;但实际上完全不是的,我们可以很简单的用几行mathematica代码就仿真出这个情形。【我本科用C++写这个可是花了100多行的。。】


mathematica code

我们可以看看对于一个全空的二维点阵,前500步的变化情形:下面是5000步之后的情况,只见的越来越混沌。。。

下面这个视频是以前本科那个C++程序写的,可以直接拖到最后去看,嗯,很难想象,兰顿蚂蚁的最后会以这样一种规律重复出现。。。。

兰顿蚂蚁其实也可以作为一种表白机器来玩弄,很简单,我们需要先设定我们最后想展示的那个场景,比如黑白像素图表示的“”,然后以此作为初始点阵,把兰顿蚂蚁算法逆推N步,N要取比较大的值,以至于让逆推N步之后的点阵已经完全看不出原本想表达的意思了,然后再用正序跑一边兰顿蚂蚁,这样就。。。嘿嘿。。。【我觉得凡是对这个表白方法觉得可行的童鞋,请千万小心注孤生!!因为我突然想起了本科宿舍附近某位跳舞晚会送女神!!!!!!的某位同学。。】

嘛,我们姑且不论表白成不成功的问题,我们先来研究一下这个方法的可行性问题,算法层面上的,不是表白层面上的。。。
我们想要从这一时刻的位置逆推出上一时刻的位置,那么看下图, 假设红色为当前位置,前一时刻的位置只有可能在其尾部的那个格子那里,然而,前一时刻的方向有两种选择,如图中的蓝黄两种颜色,但是很容易从尾部那个格子当前的颜色是黑还是白推算出原本蚂蚁的方向是哪一个。这个功能的实现我们可以比较容易用mathematica完成,首先我们先构造出我们想要表示的最后结果的点阵,比如说:然后就是逆推出兰顿蚂蚁想要爬出这个图形,N步之前二维点阵应该是什么样子:
然后,“表白”的时候用的就是正宗的兰顿蚂蚁的代码,嗯,正推算法,正面推导(倒):我这里跑了一个600步逆推之后正推的过程,额,初始状态下感觉效果不好,但其实可以算是600步太少的缘故,但是没办法啊,这个博客上传的gif大小有限制,步数太长的话文件过大,就传不上来了。。。另外,网上也有人用双蚂蚁来跑,这样的话步数也就不需要太长了。。。


以上です!!


【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

分类: Note 标签: ,
  • 有没有把生命游戏倒过来玩的方法,由当前状态回溯

    • 应该不可能,因为逆推结果不唯一;

  • 额。 我在Mathematica 10 里面 推导步数 >500 就会报错额。各种 The expression <<1>> cannot be used as a part specification. 但是在200步左右还比较正常,各种推倒都OK。