生命游戏简介及算法分析(整理)
生命游戏
生命游戏(game of life)为1970年由英国数学家J. H. Conway所提出,某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻之细胞。
规则
生命游戏中,对于任意细胞,规则如下: 每个细胞有两种状态-存活或死亡,每个细胞与以自身为中心的周围八格细胞产生互动。 当前细胞为死亡状态时,当周围有3个存活细胞时,该细胞变成存活状态。 (模拟繁殖) 当前细胞为存活状态时,当周围低于2个(不包含2个)存活细胞时, 该细胞变成死亡状态。(模拟人口稀少) 当前细胞为存活状态时,当周围有2个或3个存活细胞时, 该细胞保持原样。 当前细胞为存活状态时,当周围有3个以上的存活细胞时,该细胞变成死亡状态。(模拟过度拥挤) 可以把最初的细胞结构定义为种子,当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。继续让规处理当前的细胞图,可以得到下一代的细胞图,周而复始。在游戏的进行中,杂乱无序的细胞会逐渐演化出各种精致、有形的结构;这些结构往往有很好的对称性,而且每一代都在变化形状。一些形状已经锁定,不会逐代变化。有时,一些已经成形的结构会因为一些无序细胞的“入侵”而被破坏。但是形状和秩序经常能从杂乱中产生出来。
算法实现(C语言)
生命游戏的规则可简化为以下,并使用CASE比对即可使用程式实作: 邻居个数为0、1、4、5、6、7、8时,则该细胞下次状态为死亡。 邻居个数为2时,则该细胞下次状态为复活。
邻居个数为3时,则该细胞下次状态为稳定。
//主程序 int row, col; initLives(); int i = 0; while(i < TOTAL_GENERATIONS) { printf(" Generation %d ",i+1); outputMap(); for(row = 0; row < MAXROW; row++) { //计算下一代 for(col = 0; col < MAXCOL; col++) { switch (neighbors(row, col)) { case 0: case 1: case 4: case 5: case 6: case 7: case 8: newmap[row][col] = DEAD; break; case 2: newmap[row][col] = newmap[row][col]; break; case 3: newmap[row][col] = ALIVE; break; } } } i++; }
//初始化细胞世界 void initLives() { int row, col; for(row = 0; row < MAXROW; row++)//初始化,细胞都是死的 for(col = 0; col < MAXCOL; col++) newmap[row][col] = DEAD; puts("Game of life Program"); int j = 0; while(j < ORIGINAL_LIVES) {//随机生成50个活细胞 row = arc4random()%MAXROW; col = arc4random()%MAXCOL; if(0 <= row && row < MAXROW && 0 <= col && col < MAXCOL) newmap[row][col] = ALIVE; else if(row == -1 || col == -1) break; else printf("(x, y) exceeds map ranage!"); j++; } }
//统计邻居数目 int neighbors(int row, int col) {//判断邻居数目 int count = 0, c, r; for(r = row-1; r <= row+1; r++) for(c = col-1; c <= col+1; c++) { if(r < 0 || r >= MAXROW || c < 0 || c >= MAXCOL) continue; if(newmap[r][c] == ALIVE) count++; } if(newmap[row][col] == ALIVE)//判断时包含了被判断的坐标,所以如果为ALIVE要减1 count--; return count; }
//输出 void outputMap(){ int row, col; printf("Game of life cell status"); for(row = 0; row < MAXROW; row++) { printf(" %20c", ); for(col = 0; col < MAXCOL; col++) if(newmap[row][col] == ALIVE) putchar(0); else putchar(-); } }
下一篇:
十一届蓝桥杯c组--省一国二