生命游戏的设计与实现

生命游戏

生命游戏是元胞自动机(Cellular Automaton)中最著名的一组规则。它由一个二维细胞阵列组成,每个细胞有‘生’或‘死’两种状态。同时对于任意一个细胞,它有8个邻居细胞。

游戏规则

生命游戏在初始化之后,按照以下规则不断演化繁殖:

每个细胞的‘生’或‘死’由它8个邻居细胞的状态决定。

  • “人口过少”:任何活细胞如果活邻居少于2个,则死亡。
  • “正常”:任何活细胞如果活邻居为2个或3个,则继续活着。
  • “人口过多”:任何活细胞如果活邻居大于3个,则死亡。
  • “繁殖”:任何死细胞如果活邻居正好是3个,则活过来。

需求设计

游戏开始,需要动态设定细胞阵列的大小(长宽),随机或设定初始化细胞,可选设置细胞繁殖代数的上限,然后不断演化繁殖直至状态稳定或达到上限。

逻辑文字描述

给定当前细胞阵列,遍历每个细胞,根据该细胞的邻居细胞情况判断该细胞在下一代的生死并保存。遍历结束后判断当前代与下一代是否有区别或者迭代次数是否达到上限。如果需要继续演化,将下一代命名为当前代,并执行上述逻辑。

需求实现

项目框架

1
mvn archetype:generate -DgroupId=com.zju -DartifactId=TheGameOfLife -DarchetypeArtifactId=maven-archetype-webapp -DinteractiveMode=false -DarchetypeCatalog=internal

核心代码

实体类

细胞阵列类,表示阵列的大小和一代细胞的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* 细胞阵列
*/
public class CellularArray {
private int[][] cells;
private int row;
private int col;
public CellularArray() {
}
public CellularArray(int row, int col) {
this.row = row;
this.col = col;
this.cells = new int[row][col];
}
......
public int getCell(int x, int y) {
if (x < 0 || this.row <= x || y < 0 || this.col <= y) {
return -1;
}
return this.cells[x][y];
}
public boolean setCell(int x, int y, int cell) {
if (x < 0 || this.row <= x || y < 0 || this.col <= y) {
return false;
}
this.cells[x][y] = cell;
return true;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) return false;
CellularArray other = (CellularArray) obj;
if (this.row != other.getRow() || this.col != other.getCol()) return false;
for (int i = 0; i < this.row; ++i) {
for (int j = 0; j < this.col; ++j) {
if (this.cells[i][j] != other.getCell(i, j)) {
return false;
}
}
}
return true;
}
}

细胞状态枚举类,具体定义了细胞的状态,保持代码的可读性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 细胞状态
*/
public enum CellState {
DEAD(0),
LIVE(1);
private int value;
CellState(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
Service类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package com.zju.service;
import com.zju.meta.CellState;
import com.zju.meta.CellularArray;
import org.springframework.stereotype.Service;
import java.util.Random;
@Service
public class TheGameOfLifeService {
//方向数组
private int[] direct = {-1, 0, 1};
/**
* 给定阵列和坐标,计算坐标点的邻居存活数量
* @param now 细胞阵列
* @param x 横坐标
* @param y 纵坐标
* @return
*/
private int countLiveNeighbor(CellularArray now, int x, int y) {
int count = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (CellState.LIVE.getValue() == now.getCell(x + this.direct[i], y + this.direct[j])) {
++count;
}
}
}
if (CellState.LIVE.getValue() == now.getCell(x, y)) {
--count;
}
return count;
}
/**
* 给定细胞阵列,生成下一代的细胞阵列
* @param now 细胞阵列
* @return
*/
public CellularArray generate(CellularArray now) {
if (null == now) {
return null;
}
int liveCount;
CellularArray next = new CellularArray(now.getRow(), now.getCol());
for (int i = 0; i < next.getRow(); ++i) {
for (int j = 0; j < next.getCol(); ++j) {
liveCount = this.countLiveNeighbor(now, i, j);
if (CellState.LIVE.getValue() == now.getCell(i, j) && (liveCount < 2 || liveCount > 3)) { //人口过少,人口过多
next.setCell(i, j, CellState.DEAD.getValue());
} else if (CellState.LIVE.getValue() == now.getCell(i, j) && (2 <= liveCount && liveCount <= 3)) { //正常
next.setCell(i, j, CellState.LIVE.getValue());
} else if (CellState.DEAD.getValue() == now.getCell(i, j) && (3 == liveCount)) { //繁殖
next.setCell(i, j, CellState.LIVE.getValue());
}
}
}
return next;
}
/**
* 给定细胞阵列,产生随机结果
* @param cellularArray 细胞阵列
* @return
*/
public CellularArray randInit(CellularArray cellularArray) {
if (null == cellularArray) return null;
Random r = new Random();
int value;
for (int i = 0; i < cellularArray.getRow(); ++i) {
for (int j = 0; j < cellularArray.getCol(); ++j) {
value = r.nextInt(2);
cellularArray.setCell(i, j, value);
}
}
return cellularArray;
}
/**
* 给定细胞阵列,产生初始化结果
* @param cellularArray
* @return
*/
public CellularArray emptyInit(CellularArray cellularArray) {
if (null == cellularArray) return null;
for (int i = 0; i < cellularArray.getRow(); ++i) {
for (int j = 0; j < cellularArray.getCol(); ++j) {
cellularArray.setCell(i, j, CellState.DEAD.getValue());
}
}
return cellularArray;
}
}
Controller类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package com.zju.controller;
import com.zju.meta.CellularArray;
import com.zju.service.TheGameOfLifeService;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.ResponseBody;
import javax.annotation.Resource;
@Controller
@RequestMapping("/")
public class TheGameOfLifeController {
private static final int defaultRow = 15;
private static final int defaultCol = 15;
@Resource
private TheGameOfLifeService service;
@ResponseBody
@RequestMapping("/randInit")
public Object getRandInit(@RequestParam(required = false) Integer row, @RequestParam(required = false) Integer col) {
if (null == row) row = defaultRow;
if (null == col) col = defaultCol;
CellularArray cellularArray = service.randInit(new CellularArray(row, col));
return cellularArray;
}
@ResponseBody
@RequestMapping("/generate")
public Object generate(@RequestBody CellularArray now) {
CellularArray next = service.generate(now);
return next;
}
@ResponseBody
@RequestMapping("/empty")
public Object empty(@RequestParam(required = false) Integer row, @RequestParam(required = false) Integer col) {
if (null == row) row = defaultRow;
if (null == col) col = defaultCol;
CellularArray next = service.emptyInit(new CellularArray(row,col));
return next;
}
}
Spring配置

Spring-mvc配置fastjson作为json转换器,同时配置支持text/plainapplication/json媒体类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<mvc:annotation-driven/>
<context:component-scan base-package="com.zju"/>
<mvc:annotation-driven>
<mvc:message-converters register-defaults="true">
<bean class="com.alibaba.fastjson.support.spring.FastJsonHttpMessageConverter">
<property name="supportedMediaTypes">
<list>
<value>text/plain</value>
<value>application/json</value>
</list>
</property>
<property name="features">
<array>
<value>WriteMapNullValue</value>
<value>DisableCircularReferenceDetect</value>
<value>WriteDateUseDateFormat</value>
</array>
</property>
</bean>
</mvc:message-converters>
</mvc:annotation-driven>
Web配置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<web-app>
<display-name>The Game Of Life</display-name>
<servlet>
<servlet-name>spring-mvc</servlet-name>
<servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
<init-param>
<param-name>contextConfigLocation</param-name>
<param-value>classpath:Spring/*.xml</param-value>
</init-param>
<load-on-startup>1</load-on-startup>
</servlet>
<servlet-mapping>
<servlet-name>spring-mvc</servlet-name>
<url-pattern>/backend/*</url-pattern>
</servlet-mapping>
<welcome-file-list>
<welcome-file>/index.html</welcome-file>
</welcome-file-list>
</web-app>
展示页面

html文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>The Game Of Life</title>
<!-- 新 Bootstrap 核心 CSS 文件 -->
<link rel="stylesheet" href="http://cdn.bootcss.com/bootstrap/3.3.0/css/bootstrap.min.css">
<!-- 本地CSS 文件 -->
<link rel="stylesheet" href="/index.css">
</head>
<body id="body">
<div>
<form>
<div class="form-group">
<label>长度</label>
<input type="text" class="form-control" id="rowText" placeholder="长度">
</div>
<div class="form-group">
<label>宽度</label>
<input type="text" class="form-control" id="colText" placeholder="宽度">
</div>
<div class="form-group">
<label>当前代数</label>
<input type="text" class="form-control" id="generateCount" placeholder="代数">
</div>
<button id="initButton" type="button" class="btn btn-primary">随机初始化</button>
<button id="countCleanButton" type="button" class="btn btn-primary">代数清零</button>
<button id="cellCleanButton" type="button" class="btn btn-primary">细胞清零</button>
<button id="generateButton" type="button" class="btn btn-primary">繁衍</button>
</form>
</div>
<div id="table">
</div>
<!-- jQuery文件。务必在bootstrap.min.js 之前引入 -->
<script src="http://cdn.bootcss.com/jquery/1.11.1/jquery.min.js"></script>
<!-- 最新的 Bootstrap 核心 JavaScript 文件 -->
<script src="http://cdn.bootcss.com/bootstrap/3.3.0/js/bootstrap.min.js"></script>
<!-- 本地JavaScript 文件 -->
<script src="/index.js"></script>
</body>
</html>

javascript文件

在ajax配置中,设定dataType: "JSON"contentType: "application/json",统一和后端的数据传输格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
var cellularArray;
//根据参数控制页面显示的细胞阵列
function createTable(cellularArray) {
//清空控件内容
$("#table").empty();
var rowCount = cellularArray.row;
var colCount = cellularArray.col;
var table = $("<table border='1' float:center>");
table.appendTo($("#table"));
var cells = cellularArray.cells;
for (var i = 0; i < rowCount; ++i) {
var tr = $("<tr></tr>");
tr.appendTo(table);
for (var j = 0; j < colCount; ++j) {
var td;
if (cells[i][j] == 0) {
td = $("<td class='td-white' data-x='" + i + "' data-y='" + j + "' onclick=\"{checkCell(this)}\">" + "</td>");
} else {
td = $("<td class='td-black' data-x='" + i + "' data-y='" + j + "' onclick=\"{checkCell(this)}\">" + "</td>");
}
td.appendTo(tr);
}
}
$("#table").append("</table>");
}
//点击细胞后反转其生死
function checkCell(cell) {
var x = parseInt($(cell).attr("data-x"));
var y = parseInt($(cell).attr("data-y"));
var cells = cellularArray.cells;
cells[x][y] = (cells[x][y] + 1) % 2;
this.createTable(cellularArray);
}
$("#initButton").click(function () {
var rowCount = $("#rowText").val();
var colCount = $("#colText").val();
$.ajax({
url: "/backend/randInit",
type: "GET",
dataType: "JSON",
contentType: "application/json",
data: {
row: rowCount,
col: colCount
},
success: function (result) {
cellularArray = result;
createTable(cellularArray);
}
});
$("#generateCount").val(0);
});
$("#generateButton").click(function () {
var rowCount = $("#rowText").val();
var colCount = $("#colText").val();
var generateCount = $("#generateCount").val();
$.ajax({
type: "POST",
url: "/backend/generate",
dataType: "JSON",
contentType: "application/json",
data: JSON.stringify(cellularArray),
success: function (result) {
cellularArray = result;
createTable(cellularArray);
}
});
$("#generateCount").val(parseInt(generateCount) + 1);
});
$("#countCleanButton").click(function () {
$("#generateCount").val(0);
});
$("#cellCleanButton").click(function () {
var rowCount = $("#rowText").val();
var colCount = $("#colText").val();
$.ajax({
url: "/backend/empty",
type: "GET",
dataType: "JSON",
contentType: "application/json",
data: {
row: rowCount,
col: colCount
},
success: function (result) {
cellularArray = result;
createTable(cellularArray);
$("#generateCount").val(0);
$("#rowText").val(cellularArray.row);
$("#colText").val(cellularArray.col);
}
});
});

css文件

1
2
3
4
5
6
7
8
9
10
11
12
13
.td-white {
background-color: white;
width: 20px;
height: 20px;
}
.td-black {
background-color: black;
width: 20px;
height: 20px;
}
body {
margin: 10px;
}

测试

页面可配置细胞阵列的大小,模拟细胞繁衍结果,以及手动改变细胞生死。

滑翔者

Gliders

脉冲星

Pulsar

源代码

https://github.com/TedHacker/PracticeArea/tree/master/TheGameOfLife

小结

一些问题

  • 如何把数组传输给后端

    将数组转换成json格式进行传输。

  • 统一前后端数据传输规范

    配置ajax请求为json,同时配置spring-confing可以支持json媒体格式。

  • Javascript异步回调

    依赖回调结果的数值修改需要写在回调函数里面,不然容易出现数据不一致