Игра Жизнь

Нейман сформулировал идею клеточных автоматов в 40-х годах XX века. Клеточные автоматы были задуманы, как «универсальная вычислительная среда для построения, анализа и сравнения характеристик алгоритмов» (cellular automata machine).
Представьте себе поле, разделённое равномерной сеткой.

[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]


В идеале это поле должно быть бесконечно.

Каждая ячейка может нахоиться в n -состояниях. Причём в зависимости от состояния соседних клеток она может дискретно менять своё состояние.

[ ][N][ ]
[W][+][E]
[ ][S][ ]


Очевидно, что можно постулировать число клеток, которые оказывают влияние, на «центральную ячейку».
Так на клетку могут влиять только четыре клетки, с которыми она граничит сторонами (т.е. Север, Восток, Юг, Запад) — это «окрестность фон Неймана».
Если на ячейку влияют ещё диагональные клетки (Северо-Восток, Юго-Восток,… etc.) — это полная окрестность клетки носит название «окрестность Мура».

Сфера применения клеточных автоматов необычно широка: от «крестиков-ноликов» (tic-tac-toe) до моделирования фазовах переходов в физических системах и искусственного интеллекта(Artificial Intelligence).

Игра «Жизнь» Дж. Конвея, является самым известным клеточным автоматом. Эта игра имитируют процессы, происходящие в реальной жизни.
Я впервые узнал об этой игре очень давно, прочитав статью в каком-то старом журнале, тогда компьютера у меня ещё не было и я забавлялся играя в неё копейками на шахматной доске. Вот тогда-то передо мной остро встал вопрос: «что делать на границе?», ведь поле должно быть бесконечно. Этот вопрос решается замыканием границ. Верхняя граница замыкается с нижней, а правая с левой ( это можно представить взяв лист бумаги и склеив его верхнюю и нижнюю грани: получится труба, теперь если было бы можно склеить другие грани листа(торцы трубы), то получилась бы замкнутая поверхность — бублик), полученна фигура называется — тор.

Правила игры «Жизнь»
1. Каждая клетка может находиться в одном из двух состояний: «живое» / «мертвое» (1 / 0).
2. Состояние клетки на m -ом шаге определяется следующим образом:
определяется состояние самой клетки и её соседних клеток на m-1 -ом шаге и в зависимости от этого клетке назначается одно из двух сосотояний.
Правила жизни клеток просты:
— если живая клетка на m-1 -ом шаге имеет меньше двух или больше трёх соседей (в окрестности Мура, то шаге m она умирает (можно сказать- «от скуки» или «от перенаселенности»),
— на месте мёртвой клетки на шаге m появляется живая клетка, если у неё на m-1 -ом шаге в окрестности ровно три соседа.

Простота правил не исключает возникновения в этой виртуальной вселенной очень сложных и интерестных фигур ;)
Известный пример – Глайдер – символ хакеров ;)


Исходник программы на C++

//////////////////////////////////////////////////////////////////////
//
// 7.cpp
// for LIFE GAME
// issue N7
// Started: 03.07.03 12:32:26
//
//                                                    XIII
//////////////////////////////////////////////////////////////////////
// d - will die in next step
// a - will born in next step
#ifndef _7_CPP_
#define _7_CPP_ 1

#include<fstream.h>
#include<conio.h>
char *prog_name="life v0.71";
// size of life-massive
#define L_SIZE 20
#define L_SIZEY 60
typedef unsigned int uint;
// variables
char *file_name="life.txt";
fstream fs; // for manipulations with file
char l_mas[L_SIZE+2][L_SIZEY+2]; // life-massive
int l_i,l_j; // counter's
uint l_age=0; // age of population
uint l_coef=0; // coefficient for check cell
// functions
int in_file(char*); // get data from file and set life-massive
void calculate(uint,uint); // calculate one cell 
int main()
{
	// print Hello :)
	cout<<"+---------------+\n";
	cout<<"|  Life         |\n";
	cout<<"|               |\n";
	cout<<"|          XIII |\n";
	cout<<"+---------------+"<<endl;
	cout<<"press eny key to play; for Exit press q"<<endl;
	// set border
	for(l_i=0;l_i<L_SIZEY+2;l_i++)
		l_mas[0][l_i]=l_mas[L_SIZE+1][l_i]='-';
	for(l_j=0;l_j<L_SIZE+2;l_j++)
		l_mas[l_j][0]=l_mas[l_j][L_SIZEY+1]='|';
	l_mas[L_SIZE+1][0]=l_mas[0][L_SIZEY+1]='+';
	l_mas[0][0]=l_mas[L_SIZE+1][L_SIZEY+1]='+';
	// set elements of l_mas zero
	for(l_i=1;l_i<L_SIZE+1;l_i++)
	{
		for(l_j=1;l_j<L_SIZEY+1;l_j++)
			l_mas[l_i][l_j]='0';
	}
	// get data
	if(in_file(file_name))
		return 1; // error open file 
	while(getch()!='q')
	{
		cout<<"Age: "<<l_age++<<endl;
		// print life-massive
		for(l_i=0;l_i<L_SIZE+2;l_i++)
		{
			for(l_j=0;l_j<L_SIZEY+2;l_j++)
			{
				if(l_mas[l_i][l_j]=='d')
					l_mas[l_i][l_j]='0'; // amen 8-)
				if(l_mas[l_i][l_j]=='a')
					l_mas[l_i][l_j]='*'; // new cell
				if(l_mas[l_i][l_j]=='0')
					cout<<" ";
				else
					cout<<l_mas[l_i][l_j];
			}
			cout<<endl;
		}
		// calculate next configuration
		for(l_i=1;l_i<L_SIZE+1;l_i++)
		{
			for(l_j=1;l_j<L_SIZEY+1;l_j++)
				calculate(l_i,l_j);
		}
	}
	////////////
	return 0;
}
int in_file(char*file)
{// get data from file and set life-massive
	fs.open(file,ios::in);
	if(!fs)
	{// can't open file
		cout<<"Error open file!\t"<<file_name<<endl;
		return 1;
	}
	// get data
	for(l_i=1;l_i<L_SIZE+1;l_i++)
	{
		for(l_j=1;l_j<L_SIZEY+1;l_j++)
			fs>>l_mas[l_i][l_j];
	}
	fs.close();
	return 0;
}
void calculate(uint x,uint y)
{// calculate one cell with x,y
	switch(l_mas[x][y])
	{
	case 'a':
	case 'd':
	case '+':
	case '|':
	case '-':
	break;
	case '0':
	case '*':
		//-------------------------------------//
		l_coef=0;
		if(l_mas[x][y-1]=='*'|| l_mas[x][y-1]=='d') // west
			l_coef++;
		if(l_mas[x-1][y-1]=='*'|| l_mas[x-1][y-1]=='d')// north-west
			l_coef++;
		if(l_mas[x-1][y]=='*'||l_mas[x-1][y]=='d')// north
			l_coef++;
		if(l_mas[x-1][y+1]=='*'||l_mas[x-1][y+1]=='d')// north-east
			l_coef++;
		if(l_mas[x][y+1]=='*'||l_mas[x][y+1]=='d')// east
			l_coef++;
		if(l_mas[x+1][y+1]=='*'||l_mas[x+1][y+1]=='d')// south-east
			l_coef++;
		if(l_mas[x+1][y]=='*'||l_mas[x+1][y]=='d')// south
			l_coef++;
		if(l_mas[x+1][y-1]=='*'||l_mas[x+1][y-1]=='d')// south-west
			l_coef++;
		switch(l_coef)
		{
		case 0: 
		case 1: // will die
			if(l_mas[x][y]=='*')
			l_mas[x][y]='d';
			break;
	//	case 2:// stable =)
	//		if(l_mas[x][y]=='*')
	//			l_mas[x][y]='*';
	//		break;
		case 3: // will born
			if(l_mas[x][y]=='0')
				l_mas[x][y]='a';
			break;
		case 4: // will die
		case 5:
		case 6:
		case 7:
		case 8:
			if(l_mas[x][y]=='*')
				l_mas[x][y]='d';
			break;
		default:
			break;
		}
		//-------------------------------------//
		break;
	default:
		break;
	}

}
#endif


Программа считывает файл life.txt и запускается на обработку:
Файл может быть таким:


000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
0000000****0000000000000000000000000000000000000000000000000
000000*000*0000000000000000000000000000000000000000000000000
0000000000*0000000000000000000000000000000000000000000000000
00**00*00*00000000000000000000000000000000000000000000000000
00***0000000000000000000000000000000000000000000000000000000
00**00*00*00000000000000000000000000000000000000000000000000
0000000000*0000000000000000000000000000000000000000000000000
000000*000*0000000000000000000000000000000000000000000000000
0000000****0000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000

— эта конфигурация называется – Паровоз — он будет двигаться с запада на восток.
Т.к. замыкания границ не происходит – он благополучно врезается в восточную стенку и взрывается :)

Ссылки:
http://ru.wikipedia.org/wiki/Игра_жизнь

По теме:
Одноклеточные самособирающиеся роботы
Игра Жизнь на Arduino
  • 0
  • 8 октября 2009, 14:49
  • noonv

Комментарии (0)

RSS свернуть / развернуть

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.