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