Отправляет email-рассылки с помощью сервиса Sendsay

Моделирование Виртуальной Вычислительной Системы.

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 452 RSS
←   Июль 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://noonv.h1.ru/se/r/r.htm
Открыта: 12-05-2003

Автор
noonv

Статистика

452 подписчиков
0 за неделю
←   Все выпуски   →

Моделирование Виртуальной Вычислительной Системы.


Информационный Канал Subscribe.Ru
Моделирование Виртуальной Вычислительной Системы.
 
Выпуск №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
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное