Игра ЖИЗНЬ на LifeGE.NET

Shaos · Post by **Shaos** » 05 Apr 2008 19:11

Предлагаю пообсуждать игру ЖИЗНЬ (см. топик Conway's Game of Life) с точки зрения возможности применения переборных и генетических алгоритмов для формирования тех или иных паттернов по начальным требованиям (см. http://LifeGE.NET зарегистрированный мной в 2007 году). Когда я много лет назад познакомился с этой игрой (по книжке Гарднера про головоломки) я задумался о возможности создания вычислителей поверх правил игры Жизнь - например путём использования потоков глайдеров как сигналов для передачи информации. Однако сейчас я вижу, что такие решния (а они уже есть) являются чрезвычайно громоздкими. Год назад я обратил внимание на другие конструкции - ZIP и WIRE (и те и другие передают информацию с максимально возможной скоростью - одна клетка за такт и причём по вертикали или горизонтали, а не как диагональные глайдеры). Кроме того для передачи таких "скоростных" сигналов необходима среда распостранения - канал передачи данных (см. тут). Проблема в том что для таких каналов известны паттерны сигналов, но только у некоторых есть паттерны генераторов и совсем у небольшого количества есть паттерны терминаторов (пожирателей сигналов без разваливания конструкции) и совсем нету функций. Нашу задачу я вижу в поиске паттернов "вычислителей" для некоторых наиболее подходящих сигналов. То что задача решаемая - я почти уверен - ведь у нас поверх универсального автомата всегда можно построить более сложный автомат, включая полноценный компьютер.

Shaos · Post by **Shaos** » 06 Apr 2008 09:19

Shaos wrote:Год назад я обратил внимание на другие конструкции - ZIP и WIRE (и те и другие передают информацию с максимально возможной скоростью - одна клетка за такт и причём по вертикали или горизонтали, а не как диагональные глайдеры). Кроме того для передачи таких "скоростных" сигналов необходима среда распостранения - канал передачи данных (см. тут). Проблема в том что для таких каналов известны паттерны сигналов, но только у некоторых есть паттерны генераторов и совсем у небольшого количества есть паттерны терминаторов (пожирателей сигналов без разваливания конструкции)...

Вот пара примеров с вышеуказанного сайта (https://web.archive.org/web/20080516135727/http://www.yucs.org/~gnivasch/life/lightspeed/index.html):

p6osc.gif

p5oscs.gif

Я для начала решил выбрать сигнал с нижней картинки (автор: Noam Elkies, July 1997) - он хорош тем, что он может идти в фазе, противофазе и без сигнала (просто прямая горизонтальная линия) - самый натуральный троичный сигнал

На самой картинке можно видеть генератор (слева) и терминатор (справа) - причём генерируют они некие трёхклеточные конструкции, ползующие слева-направа. Перебором подобрать подобные паттерны генератора и терминатора - дело не простое, поэтому мне нужна распределённый вычислитель где есть много-много CPU

Вышеуказанный сайт какое-то время назад переехал на новый адрес: http://www.gabrielnivasch.org/fun/life/lightspeed-signals

Shaos · Post by **Shaos** » 06 Apr 2008 17:46

Другой пример оттуда же:

glossarysignals.gif

Автор данных сигналов Alan Hensel, 1995. Два сигнала справа легко поглащяются правой кромкой "канала", а вот крайний слева разбивает конструкцию, дойдя до конца. Так вот правые сигналы также можно использовать для передачи троичной информации - их плюс в том что они симметричны, а минус - большая ширина "канала" по сравнению с предыдущим варантом.

Mac Buster · Post by **Mac Buster** » 06 Apr 2008 21:46

Хм, таких конструкций я раньше не встречал. Очень интересна идея насчет передачи данных в троичном коде

По поводу способов реализации распределенной сети для перебора вариантов ты уже думал ?

Shaos · Post by **Shaos** » 07 Apr 2008 05:16

Mac Buster wrote:Хм, таких конструкций я раньше не встречал. Очень интересна идея насчет передачи данных в троичном коде

По поводу способов реализации распределенной сети для перебора вариантов ты уже думал ?

Способы всё те же - головной сервер, раздающий задачи и собирающий решения, и два клиента на выбор - апплет написанный на Java и пускающийся прямо из браузера и программа написанная на C и распостраняемая в исходниках (Java для тех кто не хочет активно участвовать в разбазаривании своего CPU или боится запускать чужие нативные программы).

Shaos · Post by **Shaos** » 15 Apr 2008 20:13

Пожалуй солью вместе блоги LifeGE.net и shaos.net, который возможно смогу притянуть к своему платному хостингу...

Shaos · Post by **Shaos** » 23 Jan 2009 19:46

Вот откопал свою досовскую программку для Turbo-C++ (помните такой?) почти 15-летней давности, реализующую мой собственный "ускоренный" (на самом деле можно ещё ускорять) алгоритм игры ЖИЗНЬ - с подсчитанными заранее соседями:

life.c

Code: Select all

// Шабаршин А.А.  Р-510a   23.10.1994
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <math.h>
class life
 {
 long gener;
 char *l0,*l1,*l2,*l3,*l4,*l5,*l6,*l7;
 void putl(int,int,char);
 char getl(int,int);
 public:
 life();
 ~life();
 int putsos(int,int,int);
 int getsos(int,int);
 int putpix(int,int,int);
 int getpix(int,int);
 int putrod(int,int,int);
 int getrod(int,int);
 int putded(int,int,int);
 int getded(int,int);
 int act(int);
 int save(void);
 int load(void);
 };
 life::life()
 {
  long lll=80*340;
  l0=new char[lll];
  l1=new char[lll];
  l2=new char[lll];
  l3=new char[lll];
  l4=new char[lll];
  l5=new char[lll];
  l6=new char[lll];
  l7=new char[lll];
 }
 life::~life()
 {
 delete l0;
 delete l1;
 delete l2;
 delete l3;
 delete l4;
 delete l5;
 delete l6;
 delete l7;
 }
 int life::save(void)
 {FILE *f0;
 textcolor(15);
 setfillstyle(SOLID_FILL,BLACK);
 bar(0,341,639,349);
 int kb=0,uk=0;
 char fff[14];
 outtextxy(0,342,"W?");
 kb=getch();
 while(kb!=13){
     if(kb==27){uk=0;
                bar(20,341,400,349);
                kb=getch();
                continue;}
     fff[uk++]=kb;
     fff[uk]=0;
     if(uk==8) uk--;
     outtextxy(20,342,fff);
     kb=getch();
 }
 strcat(fff,".lif");
 bar(0,341,400,349);
 char c0;
   f0=fopen(fff,"wb");
   char i0,i1,i2,i3,i4;
   i4=floor(gener/10000);
   i3=floor((gener-i4*10000)/1000);
   i2=floor((gener-i4*10000-i3*1000)/100);
   i1=floor((gener-i4*10000-i3*1000-i2*100)/10);
   i0=gener-i4*10000-i3*1000-i2*100-i1*10;
   fputc(i4+48,f0);
   fputc(i3+48,f0);
   fputc(i2+48,f0);
   fputc(i1+48,f0);
   fputc(i0+48,f0);
   for(int y=0;y<340;y++){
   int x=0;
   for(int i=0;i<80;i++){
       c0=getpix(x++,y)+getpix(x++,y)*2+getpix(x++,y)*4+getpix(x++,y)*8;
       c0=c0+getpix(x++,y)*16+getpix(x++,y)*32+getpix(x++,y)*64+getpix(x++,y)*128;
       fputc(c0,f0);
   }}
   fclose(f0);
 return 1;
 }
 int life::load(void)
 {FILE *f0;
 textcolor(15);
 setfillstyle(SOLID_FILL,BLACK);
 bar(0,341,639,349);
 int kb=0,uk=0;
 char fff[14];
 outtextxy(0,342,"R?");
 kb=getch();
 while(kb!=13){
     if(kb==27){uk=0;
                bar(20,341,400,349);
                kb=getch();
                continue;}
     fff[uk++]=kb;
     fff[uk]=0;
     if(uk==8) uk--;
     outtextxy(20,342,fff);
     kb=getch();
 }
 strcat(fff,".lif");
 bar(0,341,400,349);
 char c0;
   f0=fopen(fff,"rb");
//   fseek(f0,SEEK_SET,0);
   char i0,i1,i2,i3,i4;
   i4=fgetc(f0);
   i3=fgetc(f0);
   i2=fgetc(f0);
   i1=fgetc(f0);
   i0=fgetc(f0);
   gener=(i4-48)*10000+(i3-48)*1000+(i2-48)*100+(i1-48)*10+i0-48;
   for(int y=0;y<340;y++){
   int x=0;
   for(int i=0;i<80;i++){
       c0=fgetc(f0);
       putpix(x++,y,c0&0x01);
       putpix(x++,y,c0&0x02);
       putpix(x++,y,c0&0x04);
       putpix(x++,y,c0&0x08);
       putpix(x++,y,c0&0x10);
       putpix(x++,y,c0&0x20);
       putpix(x++,y,c0&0x40);
       putpix(x++,y,c0&0x80);
   }}
   fclose(f0);
 return gener;
 }
 void life::putl(int x,int y,char b)
 {
 if(x>=0&&x<80)    l0[x+80*y]=b;
 if(x>=80&&x<160)  l1[x-80+80*y]=b;
 if(x>=160&&x<240) l2[x-160+80*y]=b;
 if(x>=240&&x<320) l3[x-240+80*y]=b;
 if(x>=320&&x<400) l4[x-320+80*y]=b;
 if(x>=400&&x<480) l5[x-400+80*y]=b;
 if(x>=480&&x<560) l6[x-480+80*y]=b;
 if(x>=560&&x<640) l7[x-560+80*y]=b;
 }
 char life::getl(int x,int y)
 {
 char o=0;
 if(x>=0&&x<80)    o=l0[x+80*y];
 if(x>=80&&x<160)  o=l1[x-80+80*y];
 if(x>=160&&x<240) o=l2[x-160+80*y];
 if(x>=240&&x<320) o=l3[x-240+80*y];
 if(x>=320&&x<400) o=l4[x-320+80*y];
 if(x>=400&&x<480) o=l5[x-400+80*y];
 if(x>=480&&x<560) o=l6[x-480+80*y];
 if(x>=560&&x<640) o=l7[x-560+80*y];
 return o;
 }
 int life::putsos(int x,int y,int s)
 {
 char b=getl(x,y)&0xF0;
 char ss=s;
 putl(x,y,b+ss);
 return 1;
 }
 int life::getsos(int x,int y)
 {
 int o;
 char b=getl(x,y)&0x0F;
 o=b;
 return o;
 }
 int life::putpix(int x,int y,int p)
 {
 char b=getl(x,y)&0xEF;
 if(p) putl(x,y,b|0x10);
 else  putl(x,y,b);
 return 1;
 }
 int life::getpix(int x,int y)
 {
 int o=getl(x,y)&0x10;
 if(o) o=1;
 else  o=0;
 return o;
 }
 int life::putrod(int x,int y,int p)
 {
 char b=getl(x,y)&0xBF;
 if(p) putl(x,y,b|0x40);
 else  putl(x,y,b);
 return 1;
 }
 int life::getrod(int x,int y)
 {
 int o=getl(x,y)&0x40;
 if(o) o=1;
 else  o=0;
 return o;
 }
 int life::putded(int x,int y,int p)
 {
 char b=getl(x,y)&0xDF;
 if(p) putl(x,y,b|0x20);
 else  putl(x,y,b);
 return 1;
 }
 int life::getded(int x,int y)
 {
 int o=getl(x,y)&0x20;
 if(o) o=1;
 else  o=0;
 return o;
 }
 int life::act(int g)
 {
 char s0[6];
 setfillstyle(SOLID_FILL,0);
 textcolor(14);
 rectangle(0,0,639,340);
 gener=g;
 int sss;
 char pok[24];
 char poo[16];
 strcpy(poo," ПОКОЛЕНИЕ :");
 int x0,y0,x1,y1;
 for(int x=1;x<639;x++){
 for(int y=1;y<339;y++){
         putrod(x,y,0);
         putded(x,y,0);
         sss=0;
         if(getpix(x,y)) putpixel(x,y,4);
         x++;sss+=getpix(x,y);
         y--;sss+=getpix(x,y);
         x--;sss+=getpix(x,y);
         x--;sss+=getpix(x,y);
         y++;sss+=getpix(x,y);
         y++;sss+=getpix(x,y);
         x++;sss+=getpix(x,y);
         x++;sss+=getpix(x,y);
         y--;x--;putsos(x,y,sss);
 }}
 char s1;
 while(!kbhit()){
         for(x0=1;x0<639;x0++){
         for(y0=1;y0<339;y0++){
                 sss=getsos(x0,y0);
                 if(getpix(x0,y0)) if(sss<=1||sss>=4) putded(x0,y0,1);
                 if(!getpix(x0,y0)&&sss==3) putrod(x0,y0,1);
                 }}
         for(x1=1;x1<639;x1++){
         for(y1=1;y1<339;y1++){
                 if(getrod(x1,y1)){
                 x1++;putsos(x1,y1,getsos(x1,y1)+1);
                 y1--;putsos(x1,y1,getsos(x1,y1)+1);
                 x1--;putsos(x1,y1,getsos(x1,y1)+1);
                 x1--;putsos(x1,y1,getsos(x1,y1)+1);
                 y1++;putsos(x1,y1,getsos(x1,y1)+1);
                 y1++;putsos(x1,y1,getsos(x1,y1)+1);
                 x1++;putsos(x1,y1,getsos(x1,y1)+1);
                 x1++;putsos(x1,y1,getsos(x1,y1)+1);
                 y1--;x1--;putrod(x1,y1,0);putpix(x1,y1,1);putpixel(x1,y1,14);}
                 if(getded(x1,y1)){
                 x1++;putsos(x1,y1,getsos(x1,y1)-1);
                 y1--;putsos(x1,y1,getsos(x1,y1)-1);
                 x1--;putsos(x1,y1,getsos(x1,y1)-1);
                 x1--;putsos(x1,y1,getsos(x1,y1)-1);
                 y1++;putsos(x1,y1,getsos(x1,y1)-1);
                 y1++;putsos(x1,y1,getsos(x1,y1)-1);
                 x1++;putsos(x1,y1,getsos(x1,y1)-1);
                 x1++;putsos(x1,y1,getsos(x1,y1)-1);
                 y1--;x1--;putded(x1,y1,0);putpix(x1,y1,0);putpixel(x1,y1,0);}
         }}
         s0[0]=0;
         itoa(gener++,s0,10);
         pok[0]=0;
         strcpy(pok,poo);
         strcat(pok,s0);
         textcolor(14);
         setfillstyle(SOLID_FILL,0);
         bar(0,341,300,349);
         outtextxy(0,342,pok);
 }

 g=gener;
 return g;
}



int main(void)
 {printf("\n-= L I F E =-   Шабаршин А.А.   21.10.1994");
 printf("\n1.ЧИТАТЬ ФАЙЛ\n2.СЛУЧАЙНОЕ ЗАПОЛНЕНИЕ\n");
 int otv=getch();
  int gdriver = EGA, gmode=EGAHI, errorcode;
   initgraph(&gdriver, &gmode, "c:\\system\\tcpp\\bgi\\");
   errorcode = graphresult();
   if (errorcode != grOk)
   {
      printf("Ошибка графики: %s", grapherrormsg(errorcode));
      printf("\nНажмите клавишу для возврата:\n");
      getch();
      exit(1);
   }
 life lll;
 int gg=1;
if(otv==49) gg=lll.load();
else{ randomize();
 int rr;
 for(int x=0;x<640;x++){
 for(int y=0;y<340;y++){
        rr=random(6);
        if (rr) lll.putpix(x,y,0);
        else {lll.putpix(x,y,1);
              putpixel(x,y,1);}
}}}
lll.act(gg);
char s1=getch();if(s1==32) lll.save();
closegraph();
return 0;
}

Shaos · Post by **Shaos** » 24 Jan 2009 13:01

Вот тот же алгоритм на JavaScript:

life.htm

Code: Select all

<html>
<head><title>LIFE TEST</title></head>
<script language="JavaScript">
<!--

var width = 8;
var height = 8;

function neigbour(row,col,val) {
 if(row>=0 && row<height && col>=0 && col<width)
 {
  var name = row + "_" + col;
  var el = document.getElementById(name);
  var nei = parseInt(el.innerHTML);
  nei = nei + val;
  el.innerHTML = nei;
 }
}

function neigbours(row,col,val) {
 var i,j;
 for(j=-1;j<=1;j++){
 for(i=-1;i<=1;i++){
   if(i!=0 || j!=0){
     neigbour(row+j,col+i,val);
   }
 }}
}

function setcolor(row,col,flag) {
 if(row>=0 && row<height && col>=0 && col<width)
 {
  var name = row + "_" + col;
  var el = document.getElementById(name);
  if(el.bgColor=="blue" || el.bgColor=="red")
  {
    el.bgColor="white";
    if(flag==true) neigbours(row,col,-1);
  }
  else
  {
    el.bgColor="blue";
    if(flag==true) neigbours(row,col,1);
  }  
 }
}

function step() {
 var i,j;
 for(j=0;j<height;j++){
 for(i=0;i<width;i++){
  var name = j + "_" + i;
  var el = document.getElementById(name);
  var nei = parseInt(el.innerHTML);
  if(el.bgColor=="blue" && (nei<2 || nei>3))
  {
    el.bgColor="red";
  }
  if(el.bgColor!="blue" && nei==3)
  {
    el.bgColor="purple";
  }  
 }}
 for(j=0;j<height;j++){
 for(i=0;i<width;i++){
  var name = j + "_" + i;
  var el = document.getElementById(name);
  if(el.bgColor=="red" || el.bgColor=="purple")
  { // remove (if red) or add (if purple)
    setcolor(j,i,true);
  }  
 }}
}

// -->
</script>
<body>

<center>
<table border=1>
<tr>
 <td id=0_0 align=center onClick=setcolor(0,0,true)>0</td>
 <td id=0_1 align=center onClick=setcolor(0,1,true)>0</td>
 <td id=0_2 align=center onClick=setcolor(0,2,true)>0</td>
 <td id=0_3 align=center onClick=setcolor(0,3,true)>0</td>
 <td id=0_4 align=center onClick=setcolor(0,4,true)>0</td>
 <td id=0_5 align=center onClick=setcolor(0,5,true)>0</td>
 <td id=0_6 align=center onClick=setcolor(0,6,true)>0</td>
 <td id=0_7 align=center onClick=setcolor(0,7,true)>0</td>
</tr>
<tr>
 <td id=1_0 align=center onClick=setcolor(1,0,true)>0</td>
 <td id=1_1 align=center onClick=setcolor(1,1,true)>0</td>
 <td id=1_2 align=center onClick=setcolor(1,2,true)>0</td>
 <td id=1_3 align=center onClick=setcolor(1,3,true)>0</td>
 <td id=1_4 align=center onClick=setcolor(1,4,true)>0</td>
 <td id=1_5 align=center onClick=setcolor(1,5,true)>0</td>
 <td id=1_6 align=center onClick=setcolor(1,6,true)>0</td>
 <td id=1_7 align=center onClick=setcolor(1,7,true)>0</td>
</tr>
<tr>
 <td id=2_0 align=center onClick=setcolor(2,0,true)>0</td>
 <td id=2_1 align=center onClick=setcolor(2,1,true)>0</td>
 <td id=2_2 align=center onClick=setcolor(2,2,true)>0</td>
 <td id=2_3 align=center onClick=setcolor(2,3,true)>0</td>
 <td id=2_4 align=center onClick=setcolor(2,4,true)>0</td>
 <td id=2_5 align=center onClick=setcolor(2,5,true)>0</td>
 <td id=2_6 align=center onClick=setcolor(2,6,true)>0</td>
 <td id=2_7 align=center onClick=setcolor(2,7,true)>0</td>
</tr>
<tr>
 <td id=3_0 align=center onClick=setcolor(3,0,true)>0</td>
 <td id=3_1 align=center onClick=setcolor(3,1,true)>0</td>
 <td id=3_2 align=center onClick=setcolor(3,2,true)>0</td>
 <td id=3_3 align=center onClick=setcolor(3,3,true)>0</td>
 <td id=3_4 align=center onClick=setcolor(3,4,true)>0</td>
 <td id=3_5 align=center onClick=setcolor(3,5,true)>0</td>
 <td id=3_6 align=center onClick=setcolor(3,6,true)>0</td>
 <td id=3_7 align=center onClick=setcolor(3,7,true)>0</td>
</tr>
<tr>
 <td id=4_0 align=center onClick=setcolor(4,0,true)>0</td>
 <td id=4_1 align=center onClick=setcolor(4,1,true)>0</td>
 <td id=4_2 align=center onClick=setcolor(4,2,true)>0</td>
 <td id=4_3 align=center onClick=setcolor(4,3,true)>0</td>
 <td id=4_4 align=center onClick=setcolor(4,4,true)>0</td>
 <td id=4_5 align=center onClick=setcolor(4,5,true)>0</td>
 <td id=4_6 align=center onClick=setcolor(4,6,true)>0</td>
 <td id=4_7 align=center onClick=setcolor(4,7,true)>0</td>
</tr>
<tr>
 <td id=5_0 align=center onClick=setcolor(5,0,true)>0</td>
 <td id=5_1 align=center onClick=setcolor(5,1,true)>0</td>
 <td id=5_2 align=center onClick=setcolor(5,2,true)>0</td>
 <td id=5_3 align=center onClick=setcolor(5,3,true)>0</td>
 <td id=5_4 align=center onClick=setcolor(5,4,true)>0</td>
 <td id=5_5 align=center onClick=setcolor(5,5,true)>0</td>
 <td id=5_6 align=center onClick=setcolor(5,6,true)>0</td>
 <td id=5_7 align=center onClick=setcolor(5,7,true)>0</td>
</tr>
<tr>
 <td id=6_0 align=center onClick=setcolor(6,0,true)>0</td>
 <td id=6_1 align=center onClick=setcolor(6,1,true)>0</td>
 <td id=6_2 align=center onClick=setcolor(6,2,true)>0</td>
 <td id=6_3 align=center onClick=setcolor(6,3,true)>0</td>
 <td id=6_4 align=center onClick=setcolor(6,4,true)>0</td>
 <td id=6_5 align=center onClick=setcolor(6,5,true)>0</td>
 <td id=6_6 align=center onClick=setcolor(6,6,true)>0</td>
 <td id=6_7 align=center onClick=setcolor(6,7,true)>0</td>
</tr>
<tr>
 <td id=7_0 align=center onClick=setcolor(7,0,true)>0</td>
 <td id=7_1 align=center onClick=setcolor(7,1,true)>0</td>
 <td id=7_2 align=center onClick=setcolor(7,2,true)>0</td>
 <td id=7_3 align=center onClick=setcolor(7,3,true)>0</td>
 <td id=7_4 align=center onClick=setcolor(7,4,true)>0</td>
 <td id=7_5 align=center onClick=setcolor(7,5,true)>0</td>
 <td id=7_6 align=center onClick=setcolor(7,6,true)>0</td>
 <td id=7_7 align=center onClick=setcolor(7,7,true)>0</td>
</tr>
</table>
<p>
<INPUT TYPE="button" NAME="step" VALUE="Step" onClick="step()"> 
</center>

</body>
</html>

Особенности реализации - клетки являются ячейками таблицы, в которых хранится количество соседей (и это количество визуально видно). По ходу пересчёта временное состояние ячеек сохраняется путём установки других (не white или blue) цветов - red для умирающих клеток и purple для рождающихся - но глазом это не заметно т.к. они потом быстро заменяются на нормальные цвета во втором проходе, когда корректируются числа соседей для клеток около которых произошло рождение или смерть.

Живой пример смотреть тут: [urlo]http://shabarshin.com/life/life.html[/urol]

Shaos · Post by **Shaos** » 25 Jan 2009 13:09

Shaos wrote: Особенности реализации - клетки являются ячейками таблицы, в которых хранится количество соседей (и это количество визуально видно). По ходу пересчёта временное состояние ячеек сохраняется путём установки других (не white или blue) цветов - red для умирающих клеток и purple для рождающихся - но глазом это не заметно т.к. они потом быстро заменяются на нормальные цвета во втором проходе, когда корректируются числа соседей для клеток около которых произошло рождение или смерть.

Живой пример смотреть тут: http://shabarshin.com/life/life.html

Написал про это в своём блоге http://shaos.net а также вывесил на http://lifege.net

Ещё раз объясню суть своего алгоритма 15 летней давности (смотреть по сишному коду) - вместо двухмерного массива булеанов имеем двумерный массив байтов, где храним (в младших 4 битах) заранее подсчитанное количество живых соседей для каждой клетки. В старших битах имеем один бит на текущее состояние и два бита на будущее - бит на рождение и бит на смерть. Пробегая по массиву нам уже не надо обегать каждую клетку считая соседей - они уже посчитаны - просто сверяемся по текущему состоянию и числу соседей - если клетка занята и не 2 и не 3 соседа - взводим флаг смерти, если клетка свободна и имеется ровно 3 соседа - взводим флаг рождения. После того как все флаги взведены - пробегаем по таблице ещё раз, обращая внимание только на те клетки где есть флаг смерти или флаг рождения, в соответствии с которыми декрементируем или инкрементируем суммы живых соседей в клетках вокруг. По моим понятиям вычислений будет сильно меньше, нежели в случае "честного" алгоритма, который считает соседей у каждой клетки каждый раз.

Shaos · Post by **Shaos** » 25 Jan 2009 14:30

Shaos wrote:
Shaos wrote: Особенности реализации - клетки являются ячейками таблицы, в которых хранится количество соседей (и это количество визуально видно). По ходу пересчёта временное состояние ячеек сохраняется путём установки других (не white или blue) цветов - red для умирающих клеток и purple для рождающихся - но глазом это не заметно т.к. они потом быстро заменяются на нормальные цвета во втором проходе, когда корректируются числа соседей для клеток около которых произошло рождение или смерть.

Живой пример смотреть тут: http://shabarshin.com/life/life.html
Написал про это в своём блоге http://shaos.net а также вывесил на http://lifege.net

Ещё раз объясню суть своего алгоритма 15 летней давности (смотреть по сишному коду) - вместо двухмерного массива булеанов имеем двумерный массив байтов, где храним (в младших 4 битах) заранее подсчитанное количество живых соседей для каждой клетки. В старших битах имеем один бит на текущее состояние и два бита на будущее - бит на рождение и бит на смерть. Пробегая по массиву нам уже не надо обегать каждую клетку считая соседей - они уже посчитаны - просто сверяемся по текущему состоянию и числу соседей - если клетка занята и не 2 и не 3 соседа - взводим флаг смерти, если клетка свободна и имеется ровно 3 соседа - взводим флаг рождения. После того как все флаги взведены - пробегаем по таблице ещё раз, обращая внимание только на те клетки где есть флаг смерти или флаг рождения, в соответствии с которыми декрементируем или инкрементируем суммы живых соседей в клетках вокруг. По моим понятиям вычислений будет сильно меньше, нежели в случае "честного" алгоритма, который считает соседей у каждой клетки каждый раз.

Нашёл тут один алгоритм от 1992 года, где тоже заранее подсчитанные соседи участвуют, но там клетки ещё и по 3 объединены для быстрых вычислений

http://mytears.org/resources/doc/Assembly/ASNIP11/ASNIP11X/LIFE/QLIFE/

P.S. Интересно что если идти по тому же пути что и тут - складывать вместе 2 или более соседних клеток, то на то чтобы хранить количество соседей для каждой клетки уже ненадо иметь 4 бита - достаточно только 3-х, так как мы имеем как минимум на одного соседа меньше (сосед в том же пакете сидит ; ) и 0...7 (8 минус один) замечательно влезает в 3 бита!

Shaos · Post by **Shaos** » 12 May 2009 19:04

Shaos wrote:Пожалуй солью вместе блоги LifeGE.net и shaos.net, который возможно смогу притянуть к своему платному хостингу...

Продлил http://www.lifege.net ещё на один год...

Shaos · Post by **Shaos** » 10 May 2010 16:37

Shaos wrote:
Shaos wrote:Пожалуй солью вместе блоги LifeGE.net и shaos.net, который возможно смогу притянуть к своему платному хостингу...
Продлил http://www.lifege.net ещё на один год...

И ещё на один...

Shaos · Post by **Shaos** » 13 Apr 2012 14:42

Shaos wrote:
Shaos wrote:Год назад я обратил внимание на другие конструкции - ZIP и WIRE (и те и другие передают информацию с максимально возможной скоростью - одна клетка за такт и причём по вертикали или горизонтали, а не как диагональные глайдеры). Кроме того для передачи таких "скоростных" сигналов необходима среда распостранения - канал передачи данных (см. тут). Проблема в том что для таких каналов известны паттерны сигналов, но только у некоторых есть паттерны генераторов и совсем у небольшого количества есть паттерны терминаторов (пожирателей сигналов без разваливания конструкции)...
Вот пара примеров с вышеуказанного сайта (http://www.yucs.org/~gnivasch/life/ligh ... index.html):

http://www.yucs.org/~gnivasch/life/ligh ... p5oscs.gif

Я для начала решил выбрать сигнал с нижней картинки (автор: Noam Elkies, July 1997) - он хорош тем, что он может идти в фазе, противофазе и без сигнала (просто прямая горизонтальная линия) - самый натуральный троичный сигнал

На самой картинке можно видеть генератор (слева) и терминатор (справа) - причём генерируют они некие трёхклеточные конструкции, ползующие слева-направа. Перебором подобрать подобные паттерны генератора и терминатора - дело не простое, поэтому мне нужна распределённый вычислитель где есть много-много CPU

А сайт с сигналами таки помер - теперь смотреть только через вебархив http://web.archive.org/web/20100325170908/http://www.yucs.org/~gnivasch/life/lightspeed/index.html

P.S. Или по новому адресу: http://www.gabrielnivasch.org/fun/life/lightspeed-signals

Shaos · Post by **Shaos** » 14 Apr 2012 17:28

Shaos wrote:
Shaos wrote:
Shaos wrote:Пожалуй солью вместе блоги LifeGE.net и shaos.net, который возможно смогу притянуть к своему платному хостингу...
Продлил http://www.lifege.net ещё на один год...
И ещё на один...

забыл отметиться в прошлом 2011 году - тогда я тоже продлил LifeGE.net ещё на год и вот теперь приходит время задуматься о продлении в 2012 году

P.S. присмотрелся я тут повнимательнее к фреймворку для распределённых вычислений BOINC и возникла у меня мысль сделать LifeGE-клиента именно под него - глядишь так можно было бы найти кучу волонтёров со своими компьютерами под мои задачи

Shaos · Post by **Shaos** » 23 Apr 2012 18:26

Shaos wrote:
Shaos wrote: Особенности реализации - клетки являются ячейками таблицы, в которых хранится количество соседей (и это количество визуально видно). По ходу пересчёта временное состояние ячеек сохраняется путём установки других (не white или blue) цветов - red для умирающих клеток и purple для рождающихся - но глазом это не заметно т.к. они потом быстро заменяются на нормальные цвета во втором проходе, когда корректируются числа соседей для клеток около которых произошло рождение или смерть.

Живой пример смотреть тут: http://shabarshin.com/life/life.html
Написал про это в своём блоге http://shaos.net а также вывесил на http://lifege.net

Ещё раз объясню суть своего алгоритма 15 летней давности (смотреть по сишному коду) - вместо двухмерного массива булеанов имеем двумерный массив байтов, где храним (в младших 4 битах) заранее подсчитанное количество живых соседей для каждой клетки. В старших битах имеем один бит на текущее состояние и два бита на будущее - бит на рождение и бит на смерть. Пробегая по массиву нам уже не надо обегать каждую клетку считая соседей - они уже посчитаны - просто сверяемся по текущему состоянию и числу соседей - если клетка занята и не 2 и не 3 соседа - взводим флаг смерти, если клетка свободна и имеется ровно 3 соседа - взводим флаг рождения. После того как все флаги взведены - пробегаем по таблице ещё раз, обращая внимание только на те клетки где есть флаг смерти или флаг рождения, в соответствии с которыми декрементируем или инкрементируем суммы живых соседей в клетках вокруг. По моим понятиям вычислений будет сильно меньше, нежели в случае "честного" алгоритма, который считает соседей у каждой клетки каждый раз.

Попробовал этот JS-код в разных браузерах - оказалось что он работает нормально только в Firefox...

Игра ЖИЗНЬ на LifeGE.NET

Игра ЖИЗНЬ на LifeGE.NET

Re: Игра ЖИЗНЬ

Re: Игра ЖИЗНЬ