The Game Of Life – 数据结构与算法的敲门砖

The Game Of Life（生命游戏，又称为细胞自动机）几乎是所有数据结构与算法导论教程前言的一个很经典的程序了。这是一个零玩家游戏，发生在一个平面网格里。每个格子的细胞都有死亡和存活两种状态，在代与代之间有两种状态，如果每一个细胞周围少于或等于1个细胞或多于4个细胞时，他会在下一代死亡；如果一个格子周围恰好有3个细胞，他将会重新活过来。

例如，当一种特别的状态被初始化后，会形成下列状态。

https://billc.io/wp-content/uploads/2019/02/1.gif
周期为4的轻量级飞船

也会有循环或者稳定的状态：

https://billc.io/wp-content/uploads/2019/02/2.gif
周期为3的脉冲星
https://billc.io/wp-content/uploads/2019/02/3.gif
周期为3的Cross

更有甚者发现的「滑行者枪」，可以源源不断地向外发射滑行者。

https://billc.io/wp-content/uploads/2019/02/4.gif
滑行者枪
 

接下来是一个用C++和控制台实现生命游戏的尝试。本可以很短小的，但上周闲下来的时候东增西补地加了许多东西，也算是当作初学面向对象的一个习题了吧，实现了一个可以自动运行，随机初始化和自定义规则的黑框框生命游戏。

运行效果

Source Code:

  1 #include "pch.h"
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <windows.h>
  6 constexpr int FIRST_INTRODUCTION = 0;
  7 constexpr int MANIPUNATE_INSTRUCTION = 1;
  8 constexpr int WITH_GENERATION_INFO = 1;
  9 constexpr int NO_GENERATION_INFO = 0;
 10 //Define rules;
 11 int BOTTOM_LIMIT = 1;
 12 int UPPER_LIMIT = 4;
 13 int REBIRTH_NUM = 3;
 14 //define characters to print
 15 const char LIVEC = '#';
 16 const char DIEC = '.';
 17 const int MAXL = 101;
 18 using namespace std;
 19 class LifeMap {
 20 public:
 21     int width;
 22     int height;
 23     int matrix[MAXL][MAXL] = { 0 };
 24     int surround[MAXL][MAXL] = { 0 };
 25     int generation = 0;
 26     void instructor(int type) {
 27         switch (type) {
 28         case FIRST_INTRODUCTION:
 29             cout << "Welcome to the Game of Life!" << endl << endl <<
 30                 "生命游戏是一个零玩家游戏，它包括一个二维矩形世界，这个世界中的每个方格居住着一个活着的或死了的细胞。一个细胞在下一个时刻生死取决于相邻八个方格中活着的或死了的细胞的数量。如果相邻方格活着的细胞数量过多，这个细胞会因为资源匮乏而在下一个时刻死去；相反，如果周围活细胞过少，这个细胞会因太孤单而死去。"
 31                 << endl << "实际中，你可以设定周围活细胞的数目怎样时才适宜该细胞的生存。如果这个数目设定过低，世界中的大部分细胞会因为找不到太多的活的邻居而死去，直到整个世界都没有生命；如果这个数目设定过高，世界中又会被生命充满而没有什么变化。所以我们把这个数目选取为2或者3；这样整个生命世界才不至于太过荒凉或拥挤，而是一种动态的平衡。"
 32                 << endl << "这样的话，游戏的规则就是：当一个方格周围有2或3个活细胞时，方格中的活细胞在下一个时刻继续存活；即使这个时刻方格中没有活细胞，在下一个时刻也会“诞生”活细胞。在这个游戏中，还可以设定一些更加复杂的规则，例如当前方格的状况不仅由父一代决定，而且还考虑祖父一代的情况。"
 33                 << endl << "你作为这个世界的上帝，随意设定某个方格细胞的死活，以观察对世界的影响。在游戏的进行中，杂乱无序的细胞会逐渐演化出各种精致、有形的结构；这些结构往往有很好的对称性，而且每一代都在变化形状。一些形状已经锁定，不会逐代变化。有时，一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。"
 34                 << endl << endl << " Please insert the width AND the height of the grid:" << endl << "(Max Length is " << MAXL - 2 << ")" << endl;
 35             break;
 36         case MANIPUNATE_INSTRUCTION:
 37             cout << endl << "Now you can insert "L X Y" (eg. L 2 3 or l 2 3 to set the cell located in the 2nd row, 3rd column) to set a cell to live,"
 38                 << endl << "insert "D X Y" to set a cell to die. insert "P" to print the current status."
 39                 << endl << ""N" for simply jump tp the next generation.
N (optional)GENERATIONS (optional)INTERVAL_TIME for evolve multiple generation at a time."
 40                 << endl << "Insert "R" to reset your gird and "Q" to quit." << endl
 41                 << "Inset X to define rules."
 42                 << "Most interstingly, you can radomlize every cell by insert "!"" << endl << "You can set multiple cells' status in one line." << endl;
 43             break;
 44         }
 45 
 46     }
 47     void initialize(int W, int H) {
 48         int i, j;
 49         for (i = 0; i < MAXL; i++) {
 50             for (j = 0; j < MAXL; j++) {
 51                 matrix[i][j] = 0;
 52                 surround[i][j] = 0;
 53             }
 54         }
 55         width = W;
 56         height = H;
 57         generation = 0;
 58     }
 59     void printer(int gen) {
 60         //gen = 1 for printing with generation info.
 61         if (gen == 1) {
 62             cout << "
   Generation No." << generation << ":" << endl;
 63         }
 64         cout << endl;
 65         int i, j;
 66         cout << "  ";
 67         for (i = 0; i < width; i++) {
 68             printf("%2d ", i + 1);
 69         }
 70         cout << endl;
 71         for (i = 0; i < height; i++) {
 72             printf("%2d ", i + 1);
 73             for (j = 0; j < width; j++) {
 74                 if (matrix[i + 1][j + 1] == 0) printf("%c  ", DIEC);
 75                 else if (matrix[i + 1][j + 1] == 1) printf("%c  ", LIVEC);
 76             }
 77             cout << endl;
 78         }
 79         cout << endl;
 80         //print ratio
 81         if (gen == 1) {
 82             int liveCells = 0;
 83             for (i = 0; i < height; i++) {
 84                 for (j = 0; j < width; j++) {
 85                     if (matrix[i + 1][j + 1] == 1) liveCells++;
 86                 }
 87             }
 88             cout << "   Live cell ratio: " << (double)liveCells / (double)(width*height) * 100.0
 89                 << "% (" << liveCells << "/" << width * height << ")" << endl << endl;
 90         }
 91     }
 92     void SetLiving(int W, int H) {
 93         if (W <= 0 || W > width || H <= 0 || H > height)
 94             cout << "Unvalid input, please try again.
";
 95         else {
 96             matrix[W][H] = 1;
 97             cout << "Cell (" << W << " ," << H << ") came alive." << endl;
 98         }
 99 
100     }
101     void SetDying(int W, int H) {
102         if (W <= 0 || W > width || H <= 0 || H > height)
103             cout << "Unvalid input, please try again.
";
104         else {
105             matrix[W][H] = 0;
106             cout << "Cell (" << W << " ," << H << ") has been dead." << endl;
107         }
108 
109     }
110     void Radomlize() {
111         int i, j;
112         cout << "Randomlizing cell status..." << endl;
113         for (i = 0; i < height; i++) {
114             for (j = 0; j < width; j++) {
115                 //srand(time(NULL));
116                 if ((rand() % 2) == 1) matrix[i + 1][j + 1] = 0;
117                 else {
118                     matrix[i + 1][j + 1] = 1;
119                     cout << "Cell (" << i + 1 << " ," << j + 1 << ") came alive." << endl;
120                 }
121             }
122         }
123     }
124     void Next() {
125         int i, j;
126         //Initialize the surround matrix.
127         for (i = 0; i < MAXL; i++) {
128             for (j = 0; j < MAXL; j++) {
129                 surround[i][j] = 0;
130             }
131         }
132         //Calculate the surrounded live cells
133         for (i = 0; i < height; i++) {
134             for (j = 0; j < width; j++) {
135                 if (matrix[i][j] == 1) surround[i + 1][j + 1]++;
136                 if (matrix[i][j + 1] == 1) surround[i + 1][j + 1]++;
137                 if (matrix[i][j + 2] == 1) surround[i + 1][j + 1]++;
138                 if (matrix[i + 1][j] == 1) surround[i + 1][j + 1]++;
139                 if (matrix[i + 1][j + 2] == 1) surround[i + 1][j + 1]++;
140                 if (matrix[i + 2][j] == 1) surround[i + 1][j + 1]++;
141                 if (matrix[i + 2][j + 1] == 1) surround[i + 1][j + 1]++;
142                 if (matrix[i + 2][j + 2] == 1) surround[i + 1][j + 1]++;
143             }
144         }
145         //Rules
146         for (i = 0; i < height; i++) {
147             for (j = 0; j < width; j++) {
148                 if (surround[i + 1][j + 1] >= UPPER_LIMIT) matrix[i + 1][j + 1] = 0;
149                 if (surround[i + 1][j + 1] <= BOTTOM_LIMIT) matrix[i + 1][j + 1] = 0;
150                 if (surround[i + 1][j + 1] == REBIRTH_NUM) matrix[i + 1][j + 1] = 1;
151             }
152         }
153         generation++;
154     }
155     void Definer() {
156         int i, j, k;
157         cout << "Please insert three value to define the rules: (Defaul Configuration:1 4 3)" << endl
158             << "BOTTOM_LIMIT UPPER_LIMIT REBIRTH_NUM" << endl;
159     inputrule: cout << ">> "; cin >> i >> j >> k;
160         if (cin.fail() || i >= 8 || j >= 8 || k >= 8 || i < 0 || j < 0 || k < 0) {
161             cout << "Invalid input, please input three positive integers smaller than 8." << endl;
162             cin.clear();
163             while (cin.get() != '
');
164             goto inputrule;
165         }
166         else {
167             BOTTOM_LIMIT = i;
168             UPPER_LIMIT = j;
169             REBIRTH_NUM = k;
170             printf("Rules have been defined to %d %d %d.
", i, j, k);
171         }
172     }
173 };
174 int main()
175 {
176     LifeMap Map;
177     //These variables are used for manipunating.
178     int X, Y;
179     //these two labels are used for jumping for input that's too large and the reset command.
180 start: Map.instructor(FIRST_INTRODUCTION);
181 input: cin >> X >> Y;
182     while (cin.fail()) {
183         cout << "Unvalid input, please try again. Pleas type two integers." << endl;
184         cin.clear();
185         while (cin.get() != '
') continue;
186         cin >> X >> Y;
187     }
188     while (X >= 100 || Y >= 100) {
189         cout << "Too long." << endl;
190         cin.clear();
191         goto input;
192     }
193     Map.instructor(MANIPUNATE_INSTRUCTION);
194     cout << "This is all the cells you have." << endl;
195     Map.initialize(X, Y);
196     Map.printer(NO_GENERATION_INFO);
197     cin.clear();
198     while (cin.get() != '
') continue; // Clear datas in the cache.
199     char command;
200     while ((command = toupper(cin.get())) != 'Q') {
201         switch (command) {
202         case 'L':
203             cin >> X >> Y;
204             if (cin.fail()) {
205                 cout << "Unvalid input, please try again." << endl;
206                 cin.clear();
207                 while (cin.get() != '
') continue;
208             }
209             else
210                 Map.SetLiving(X, Y);
211             break;
212         case 'D':
213             cin >> X >> Y;
214             if (cin.fail()) {
215                 cout << "Unvalid input, please try again." << endl;
216                 cin.clear();
217                 while (cin.get() != '
') continue;
218             }
219             else
220                 Map.SetDying(X, Y);
221             break;
222         case 'P':
223             Map.printer(WITH_GENERATION_INFO);
224             break;
225         case 'N':
226             //gens mens the number of generations to evolve
227             //interval means the interval times between two evolutions
228             int i, gens, interval;
229             if (cin.get() != '
') {
230                 cin >> gens;
231                 if (cin.get() == '
') interval = 0;
232                 else cin >> interval;
233                 if (gens <= 0 || interval < 0) {
234                     cout << "Unvalid input, please enter positive integers." << endl;
235                     cin.clear();
236                     while (cin.get() != '
') continue;
237                 }
238                 else {
239                     for (i = 0; i < gens; i++) {
240                         system("cls");
241                         Map.instructor(MANIPUNATE_INSTRUCTION);
242                         Map.Next();
243                         Map.printer(WITH_GENERATION_INFO);
244                         Sleep(interval);
245                     }
246                 }
247             }
248             else {
249                 system("cls");
250                 Map.instructor(MANIPUNATE_INSTRUCTION);
251                 Map.Next();
252                 Map.printer(WITH_GENERATION_INFO);
253             }
254             break;
255         case 'R':
256             system("cls");
257             goto start;
258             break;
259         case '!':
260             Map.Radomlize();
261             cout << "OK, now it's just chaos." << endl;
262             Map.printer(WITH_GENERATION_INFO);
263             break;
264         case 'X':
265             Map.Definer();
266         case '
': break;
267         case ' ': break;
268         default:
269             cout << "Unknown Command:(" << endl;
270             //while (cin.get() != '
') continue;
271         }
272     }
273     cout << "See you:)

";
274     system("pause");
275     return 0;
276 }
277

GitHub：https://github.com/BillChen2000/LearnigRepo/blob/master/Course/数据结构与算法/LifeGame/

图源：https://www.guokr.com/article/439770/

另外这里还有一个LifeWiki有详细的整理和介绍：http://www.conwaylife.com/wiki/

来源：https://billc.io/2019/02/the-game-of-life/

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/AlanChen2k/p/the-game-of-life.html