simulation of langton's ant

Introduction to Langton’s Ant

简单来说 Langton’s ant 就是一个简单的数学游戏.

在一平面上,存在无限的等大小的正方形方格,每一个方格要么是白色,要么是黑色. 我们在某一个上放了一只蚂蚁(Ant). 这只蚂蚁每一步可以朝四个方向行走,并且每步行走遵从以下两条规则:

  • 如果蚂蚁在色格子时,就会向转90°,同时颠倒该格子的颜色(变为黑色),最后再向前走一步。
  • 如果蚂蚁在色格子时,就会向转90°,同时颠倒该格子的颜色(变为白色),最后再向前走一步。

更多参考资料 : wikipedia - Langton’s ant or Youtube - Langton’s Ant - Numberphile

Analazation

从介绍中可以看出,有两样是必备的:

  • Ant。也就是移动的蚂蚁
  • Grids。也就是网格。

所以接下来从这两方面分别入手:

Ant

蚂蚁负责移动,而移动的方向如果用东南西北(NEWS)表示的话,那么要涉及它的朝向问题。即:当它的朝向是向南时,那么它的右转实际是用西转。所以可以设计两个函数turn_left()turn_right()。函数可以改变蚂蚁的位置,作出正确的左转和右转。
接下来是如何让它自动按规矩走。为了不影响程序的运行,我决定使用多线程。使用多线程的好处之一就是如果需要多只蚂蚁移动时,只需要轻松地启动几个线程就好了。所以蚂蚁类应该扩充Runnable接口。每一步行走时获取当前格的颜色,并进行修改。

Grids

首先很明显我可以用一个网格布局来管理每一个小网格,如 GridLayout(100, 100)100 X 100 的网格布局。接下来需要用一个控件来表示小网格。每一个网格需要变换颜色,所以这个用作网格的控件就首先必须要有一个可以改变颜色的方法。要使用 JPanel 么? JPanel确实可以变换颜色,但是实际测试就会发现一个问题,每一个小网格之间没有边界线,整个网格看上去就像一张白纸一样。JButton如何?JButton也有一个改变颜色的方法 setBackground()。而且在网格布局时,每一个JButton和JButton之间有一个明显的分界线,可以很明显地看出是一个100 * 100 的网格布局,显示效果比用JPanel要好。就这样决定了,使用JButton表示每一个小网格。
除此之外,为了方便蚂蚁获取颜色和修改颜色,编写两个方法:getColor(int x, int y) setColor(int x, int y) 供蚂蚁查询和修改 (x, y) 位置的颜色。

Coding

我的项目地址 : Langton-s-Ant-Java
这里不展示所有的代码,只写一些我认为关键的部分。

Ant 部分:

1
2
3
4
5
6
7
public class Ant implements Runnable {

int x, y, forward; // forward 为朝向
private Grids grid = null; // 注意此处的 grid 用作引用
private boolean alive; // 判断此蚂蚁是否存活

}

Run()函数部分:

  • 每次移动时,记录移动前格子的颜色,以便反色。
  • 同时把移动后的格子变为红色,可以在实际运行时表明蚂蚁的位置,加强交互性。
  • stay_idle() 代表延时,可以起到控制蚂蚁速度的作用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void run() {
// record the original color of grid[x][y]
Color ori_color = grid.getColor(x, y);
int old_x, old_y;
while (this.alive) {
old_x = x;
old_y = y;
// black : turn left
if (ori_color == Ant_Util.black ) {
grid.setColor(old_x, old_y, Ant_Util.white);
this.turn_left();
ori_color = grid.getColor(x, y);
grid.setColor(x, y, Ant_Util.red);
} else { // white : turn right
grid.setColor(old_x, old_y, Ant_Util.black);
this.turn_right();
ori_color = grid.getColor(x, y);
grid.setColor(x, y, Ant_Util.red);
}
stay_idle();
}
}

Grids 部分:

主要就是构造函数,以及上面提到的供Ant调用以得到和改变颜色的函数。
简单起见,默认全部为白三色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Grids extends Container {
// every button is a grid
private JButton[][] grid = new JButton[Ant_Util.Grid_Height][Ant_Util.Grid_Width];

public Grids() {
this.setLayout(new GridLayout(Ant_Util.Grid_Height, Ant_Util.Grid_Width));
for (int i = 0; i < Ant_Util.Grid_Height; ++ i) {
for (int j = 0; j < Ant_Util.Grid_Width; ++ j) {
grid[i][j] = new JButton();
grid[i][j].setBackground(Ant_Util.white);
this.add(grid[i][j]);
}
}
}

public Color getColor(int x, int y) {
return grid[x][y].getBackground();
}

public void setColor(int x, int y, Color c) {
grid[x][y].setBackground(c);
}
}

其他部分

  • class App , 用作主窗口。实例化 Ant 类 以及 Girds 类。
  • Class Ant_Util,用作存放常量,比如蚂蚁的速度,网格的数量,窗口的大小等,需要修改时只要在此类里修改更改就好,不用跑到其它类里满地找,而且调用起来也会方便很多。