Игра Жизнь


Нейман сформулировал идею клеточных автоматов в 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>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


Добавить комментарий

Arduino

Что такое Arduino?
Зачем мне Arduino?
Начало работы с Arduino
Для начинающих ардуинщиков
Радиодетали (точка входа для начинающих ардуинщиков)
Первые шаги с Arduino

Разделы

  1. Преимуществ нет, за исключением читабельности: тип bool обычно имеет размер 1 байт, как и uint8_t. Думаю, компилятор в обоих случаях…

  2. Добрый день! Я недавно начал изучать программирование под STM32 и ваши уроки просто бесценны! Хотел узнать зачем использовать переменную типа…

3D-печать AI Android Arduino Bluetooth CraftDuino DIY IDE iRobot Kinect LEGO OpenCV Open Source Python Raspberry Pi RoboCraft ROS swarm ИК автоматизация андроид балансировать бионика версия видео военный датчик дрон интерфейс камера кибервесна конкурс манипулятор машинное обучение наше нейронная сеть подводный пылесос работа распознавание робот робототехника светодиод сервомашинка собака управление ходить шаг за шагом шаговый двигатель шилд

OpenCV
Робототехника
Будущее за бионическими роботами?
Нейронная сеть - введение