Моделирование Виртуальной Вычислительной Системы.
 
Выпуск №6
home URL
автор рассылки: noonv (noonv@narod.ru)

Приветствую вас, уважаемые читатели!

Сегодня мы снова продолжим разговор о клеточных автоматах.

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

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

Ниже приводится исходник игры на ассемблере(исходник взят из примеров к книге Зубкова "Assembler для DOS, Windows и UNIX" )
Если вы не знаете ассемблера и не желаете знать :) ,то можете пропустить этот абзац.

; lifecom.asm
; игра "жизнь" на поле 320x200, версия, компилирующаяся в COM-файл
;
; Компиляция:
; TASM:
; tasm /m lifecom.asm
; tlink /t /x lifecom.obj
; MASM:
; ml /c lifecom.asm
; link lifecom.obj,,NUL,,,
; exe2bin lifecom.exe lifecom.com
; WASM:
; wasm lifecom.asm
; wlink file lifecom.obj form DOS COM
;

.model tiny
.code
.186 ; для команд shl al,4 и shr al,4
org 100h
start:
std ; строки будут обрабатываться от конца к началу
int 1Ah ; функция AH=0 INT 1Ah - получить текущее время.
mov di,320*200+1 ; число точек экрана
fill_buffer:
imul dx,4E35h ; простой генератор случайных чисел
inc dx
mov ax,dx ; текущее число копируется в AX
shr ax,15 ; от него оставляется только один бит
mov byte ptr [di+buffer],al ; который копируется в массив
dec di ; следующая ячейка
jnz fill_buffer ; если di не стал равен нулю - продолжить цикл

mov ax,0013h ; графический режим 320x200 (256 цветов)
int 10h

;
; основной цикл
;

new_cycle:
;
; шаг 1: для каждой ячейки вычисляется число соседей и записывается в
; старшие четыре бита этой ячейки
;
mov di,320*200+1 ; цикл от 320*200+1 до 1
step_1:
mov al,byte ptr [di+1+buffer] ; сумма значений восьми соседних
add al,byte ptr [di-1+buffer] ; ячеек вычисляется в AL:
add al,byte ptr [di+319+buffer] ; младшие четыре бита ячейки равны
add al,byte ptr [di-319+buffer] ; 00 если ячейка пуста и 01 если
add al,byte ptr [di+320+buffer] ; она не пуста. Старшие четыре бита
add al,byte ptr [di-320+buffer] ; предыдущих ячеек содержат числа
add al,byte ptr [di+321+buffer] ; соседей, полученные в предыдущих
add al,byte ptr [di-321+buffer] ; проходах этого цикла, но они не влияют
; на сумму соседей, накапливающуюся в
; младших четырёх битах AL

shl al,4 ; теперь старшие четыре бита AL -
; число соседей текущей ячейки

or byte ptr [di+buffer],al ; поместить их в старшие четыре бита
; ячейки в массиве

dec di ; следующая ячейка
jnz step_1 ; если di не стал равен нулю - продолжить цикл

;
; шаг 2: изменение состояния ячеек в соответствии с полученными в шаге 1
; числами соседей
;


mov di,320*200+1 ; цикл от 320x200+1 до 1
flip_cycle:
mov al,byte ptr [di+buffer] ; считать ячейку из массива
shr al,4 ; AL = число соседей
cmp al,3 ; если число соседей = 3
je birth ; появляется новая точка
cmp al,2 ; если число соседей = 2
je f_c_continue ; ячейка не изменяется
mov byte ptr [di+buffer],0 ; иначе ячейка погибает
jmp short f_c_continue
birth: mov byte ptr [di+buffer],1
f_c_continue:
and byte ptr [di+buffer],0Fh ; обнулить сумму соседей в старших
; битах ячейки
dec di ; следующая ячейка
jnz flip_cycle

;
; Вывод массива на экран прямым копированием в видеопамять

push 0A000h ; адрес видеопамяти
pop es ; в ES
mov cx,320*200 ; число ячеек
mov di,cx ; стартовый адрес в видеопамяти 320*200
mov si,cx ; стартовый адрес в массиве -
inc si ; 320*200+1
add si,offset buffer ; + начало буфера
rep movsb ; выполнить копирование

mov ah,1 ; если не нажата клавиша
int 16h
jz new_cycle ; следующий шаг жизни

mov ax,0003h ; иначе: восстановить текстовый режим
int 10h
ret ; и завершить программу

buffer: ; начало буфера
end start


Если у вас нет компилятора ассемблера, то ниже приведены ссылки на бинарник (COM-файл).
Из-за особенностей хостинга на агаве(*.h1) двоичные файлы вынужден размещать на зркалах сайта.
http://wave.prohosting.com/noonv/se/r/f/6/lifecom.com
http://www.noonv.narod.ru/se/r/f/6/lifecom.com
(141b 8-))

А теперь продумаем алгоритм и реализуем игру на C/C++.
Итак, для реализации нам понадобится массив хранящий нашу микровселенную, пусть он будет типа char. Размер этого типа 1 байт (можете убедится использовав sizeof(char)), таким образом для поля 320x200 (которое реализует программа на ассемблере) нам понадобится такой же массив, а => потребуется 62.5kb памяти ! Конечно, при современных маштабах оперативки это не так страшно, но согласитесь нельзя не призадуматься :)
Алгоритм следующий:
Считать начальную конфигурацию из файла и занести в массив.
Выполнять в цикле обработку конфигурации пока пользователю не надоест ;-).
ниже приведён исходник с подробными комментариями. Замыкания границ не происходит.Начальная конфигурация считывается из файла life.txt. Программа консольная. Архив с exe-ником и файлом life.txt можно скачать по адресам:
http://wave.prohosting.com/noonv/se/r/f/6/6.zip
http://www.noonv.narod.ru/se/r/f/6/6.zip

//////////////////////////////////////////////////////////////////////
//
// 6.cpp
// for LIFE GAME
// issue N6
// Started: long ago
//
//                                                    XIII
//////////////////////////////////////////////////////////////////////
// d - will die in next step
// a - will born in next step
#ifndef _6_CPP_
#define _6_CPP_

#include<fstream.h>
//#include<windows.h> // for Sleep()
#include<conio.h> // for getch()
char *prog_name="life v0.7";
// size of life-massive
#define L_SIZE 20
typedef unsigned int uint;
// variables
char *file_name="life.txt";
fstream fs; // for manipulations with file
char l_mas[L_SIZE+2][L_SIZE+2]; // life-massive
int l_i,l_j; // counter's
char l_temp; // temporary
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;
//	cout<<"for Exit press Ctrl-C"<<endl; // for while(1)
	// set border
	for(l_i=0;l_i<L_SIZE+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_SIZE+1]='|';
	l_mas[L_SIZE+1][0]=l_mas[0][L_SIZE+1]='+';
	l_mas[0][0]=l_mas[L_SIZE+1][L_SIZE+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_SIZE+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')//while(1)
	{
		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_SIZE+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_SIZE+1;l_j++)
				calculate(l_i,l_j);
		}
//		Sleep(250);//for while(1)
	}
	////////////
	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_SIZE+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, то увидите, что на 2-ом шаге исчезает "мусор" и остаются только три фигуры:
мигалка( которая то опрокидывается, то поднимается)
*
*
*

блок(одна из стабильных фигур)
**
**

и самая интересная - глайдер, он движется с севера на юг
**
***
***

ладно, выпуск и так разросся , в следующий раз продолжим.

Подробнее об игре можно почитать на сайте http://www.famlife.narod.ru, там же можно найти программу, реализующую эту игру.
Заодно приведу прямую ссылку на архив с очень подробной статьёй: http://www.famlife.narod.ru/gardner.zip (237kb). Настоятельно рекомендую ознакомиться ;-)

Счастливо!

[noonv@volodia noonv]$ logout

XIII

Рейтинг@Mail.ru
Хостинг от uCoz