Реализация игры жизнь

Содержание

ВВЕДЕНИЕ

1 ОПИСАНИЕ

2 БЛОК-СХЕМА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

3 ТЕКСТ ПРОГРАММЫ

4 КОНТРОЛЬНЫЙ ПРИМЕР

5 ВЫВОД

6 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

ВВЕДЕНИЕ

Одной из легенд раннего программирования по праву  является игра, придуманная американским математиком Джоном Хортоном Конуэем. Вот уже несколько десятков лет она привлекает к себе пристальное внимание. В свое время она была настолько популярной среди программистов, что съела немало их рабочего времени и машинного времени первых суперкомпьютеров.

Вообще-то большая часть работ Конуэя относится к области чистой математики, но, помимо серьезных исследований, он увлекается также занимательной математикой. Настоящая же статья посвящена самому знаменитому детищу Конуэя — игре, которую сам Конуэй назвал “Жизнь”.

В эту игру играю  поодиночке. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колоний живых  организмов. По этой причине “Жизнь”  можно отнести к категории  так называемых “моделирующих игр” — игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни. Уже довольно давно никто не играет в эту игру без использования компьютера, хотя это вполне возможно.

Основная идея игры состоит в том, чтобы, начав  с какого-нибудь простого расположения фишек (организмов), расставленных по различным клеткам доски, проследить за эволюцией исходной позиции под действием “генетических законов” Конуэя, которые управляют рождением, гибелью и выживанием фишек. Конуэй тщательно подбирал свои правила и долго проверял их “на практике”, добиваясь, чтобы поведение популяции было достаточно интересным, а главное, непредсказуемым.

Каждая клетка на бесконечном во все стороны  поле имеет ровно восемь соседей. Рождаются и погибают клетки по следующим правилам:

1. Если фишка имеет четырех или более соседей, то она умирает от перенаселенности (с этой клетки снимается фишка).

2. Если фишка не имеет соседей или имеет ровно одного соседа, то она умирает от нехватки общения.

3. Если клетка без фишки имеет ровно трех соседей, то в ней происходит рождение (на клетку кладется фишка).

4. Если не выполнено ни одно из перечисленных выше условий, состояние клетки не изменяется.

Иногда первоначальная колония организмов постепенно вымирает, т.е. все фишки исчезают, однако произойти это может не сразу, а лишь после того, как сменится очень много поколений. В большинстве своем исходные конфигурации либо переходят в устойчивые и перестают изменяться, либо навсегда переходят в колебательный режим. При этом конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы. Обретенные свойства симметрии в процессе дальнейшей эволюции не утрачиваются, а симметрия конфигурации может лишь обогащаться.

Можно, скажем, проследить эволюцию всех возможных “триплетов” — комбинаций из трех клеток. Выживает триплет лишь в том случае, если, по крайней мере, одна фишка граничит с двумя занятыми клетками. Пять триплетов, не исчезающих на первом же ходу, изображены на рис. 1. (При этом ориентация триплетов, т.е. как они расположены на плоскости — прямо, “вверх ногами” или косо, не играет никакой роли.) Первые три конфигурации (а, б, в) на втором ходу погибают. Относительно конфигурации в заметим, что любой диагональный ряд фишек, каким бы длинным он ни оказался, с каждым ходом теряет стоящие на его концах фишки и в конце концов совсем исчезает. Скорость, с которой шахматный король перемещается по доске в любом направлении, Конуэй называет “скоростью света”. Пользуясь этой терминологией, можно сказать, что любой диагональный ряд фишек распадается с концов со скоростью света.

Рис. 1. Эволюция пяти триплетов

Конфигурация г на втором ходу превращается в устойчивую конфигурацию — “блок” (квадрат размером 2x2). Конфигурация д служит простейшим примером так называемых “флип-флопов” (кувыркающихся конфигураций, возвращающихся в исходное состояние через каждые два хода). При этом она попеременно превращается то в вертикальный, то в горизонтальный ряд из трех фишек. Конуэй называет этот триплет “мигалкой”.

На рис. 8 изображены пять тетрамино (четыре клетки, из которых состоит элемент тетрамино, связаны между собой ходом ладьи, квадрат а относится к категории “любителей спокойной жизни”. Конфигурации б и в после второго хода превращаются в устойчивую конфигурацию, называемую “ульем”. Тетрамино, обозначенное буквой г, также превращается в улей, но на третьем ходу. Особый интерес представляет тетрамино д, которое после девятого хода распадается на четыре отдельные “мигалки”. Вся конфигурация носит название “навигационные огни”, или “светофоры”.

Рис. 2. Пять видов тетрамино

Интересным является r-образное пентамино, изображенное на рис.3.

Рис. 3. r-пентамино

Конуэй проследил развитие r-образного пентамино вплоть до четыреста шестидесятого хода, после  которого данная конфигурация распалась на множество “глайдеров”. Конуэй пишет, что “от фигуры осталось множество мертвых (не изменяющихся) обломков и лишь несколько малых областей, в которых все еще теплилась жизнь, так что отнюдь не очевидно, что процесс эволюции должен происходить бесконечно долго”.

Одним из самых замечательных  открытий Конуэя следует считать  конфигурацию из пяти фишек под названием  “глайдер”, изображенную на рис. 4. После второго хода “глайдер” немного сдвигается и отражается относительно диагонали. В геометрии такой тип симметрии называется “скользящим отражением”, отсюда же и происходит название фигуры.  
В результате двух последующих ходов “глайдер” “выходит из пике”, ложится на прежний курс и сдвигается на одну клетку вправо и на одну клетку вниз относительно начальной позиции. Выше уже отмечалось, что скорость шахматного короля в игре “Жизнь” принято называть скоростью света. Выбор Конуэя пал именно на этот термин из-за того, что в изображенной им игре большие скорости просто не достигаются. Ни одна конфигурация не воспроизводит себя достаточно быстро, чтобы двигаться с подобной скоростью. Конуэй также доказал, что максимальная скорость по диагонали составляет одну четверть скорости света. Поскольку “глайдер” воспроизводит сам себя после четырех ходов и при этом опускается на одну клетку по диагонали, то говорят, что он скользит по полю со скоростью, равной одной четвертой скорости света.

Рис. 10. “Глайдер?”

Конуэй также  показал, что скорость любой конечной фигуры, перемещающейся по вертикали или по горизонтали на свободные клетки, не может превышать половину скорости света. Напомним, что скорость движения определяется дробью, в знаменателе которой стоит число ходов, необходимых для воспроизведения фигуры, а в числителе — число клеток, на которое она при этом смещается. Например, если какая-нибудь фигура за каждые четыре хода передвигается на две клетки по вертикали или по горизонтали, повторяя свою форму и ориентацию, то скорость такой фигуры будет равна половине скорости света. Надо сказать, что поиски перемещающихся по доске фигур — дело чрезвычайно сложное. Конуэю известны всего четыре такие конфигурации, которые он называет “космическими кораблями”. В их число входит уже известный нам “глайдер”. (“Глайдер” считается “космическим кораблем” легчайшего веса, потому что все остальные корабли состоят из большего числа фишек.)

Это не единственные фигуры, которые можно получить на игральной доске, но эти фигуры являются самыми простыми и интересными.

 

1. ОПИСАНИЕ

 

Особенностью  реализации игры «Жизнь» на компьютере является невозможность создания бесконечного поля, поэтому ограничимся лишь полем экрана компьютера.

Для хранения значений клеток будем использовать двумерный массив, заполняя его значениями 0 и 1 для  пустой и заполненной клетки соответственно. Нам понадобиться 3 массива. Первые два для попеременного хранения комбинации. Последний массив, для исследования окружения, каждой отдельной клетки.

Чтобы пользователь мог видеть преобразования, воспользуемся возможностями  модуля GRAPH, входящего в комплект любой версии PASCAL. Задавать графическую среду мы будем в отдельной функции. Экран разобьем на две части. В верхней части будет показываться полезная для пользователя информация, в том числе о поколениях, состоянии работы программы и другие. В нижней будем выводить само поле. Для увеличения скорости работы программы и создании беспрерывной анимации не будем каждый раз перерисовывать сетку поля, а начертим её только в начале работы программы.

Для наглядного представления эволюции клеток, создадим ещё одну процедуру, которая будет выводить, пустую или заполненную клетку в зависимости от значения ячейки массива. В этой процедуре в стандартном выводе значений двумерного массива заменим вывод значений массива на рисование квадрата, соответствующего цвета. Соответственно цветом заполненной клетки будем считать синий, а цветом пустой клетки – цвет фона. Таким образом, нам не нужно будет постоянно очищать экран, и выводить значения заново, цвет эволюционирующей клетки будет заменять предыдущий цвет. С помощью такого приема мы уберём мерцание из работы программы и добьемся эффекта непрерывного воспроизведения.

Заполнение  поля зададим с помощью цикла. На каждом этапе будем анализировать  введённый с клавиатуры символ и в соответствии с его кодом будем исполнять соответствующее действие. Если нажата клавиша навигации, то в зависимости от направления производим следующие действия. Во-первых, зарисовываем указатель с текущими координатами. Во-вторых, изменяем координаты в соответствии с нужным направлением. В-третьих, рисуем указатель с новыми координатами. Если была нажата клавиша <ENTER>, то задаём условие, какое значение массива соответствует этой ячейке? Если значение 1, то рисуем на этом месте закрашенную клетку, иначе рисуем очищенную клетку. Цикл прекращается при нажатии клавиши <Esc>.

Для обработки  массива необходимо ввести новую  функцию. В этой функции считаем, сколько закрашенных клеток в  окружении данной ячейки и возвращаем это значение в переменную. На основе этих данных выполняем преобразования по правилам, оговоренным выше. Все преобразования выполняются в цикле. Цикл завершается при нажатии клавиши <Esc> или, если новая комбинация оказывается такой же, как и предыдущая.

 

2. БЛОК-СХЕМА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. ТЕКСТ ПРОГРАММЫ

 

{$S-}

{$R-}

program kurs;

uses crt, graph;

type mas = array[1..100,1..100] of integer;

var b,a,ol:mas;

    grDriver,grMode,res:integer;

    h,n,m,i,j,x1,y1,q,w,k,m1,n1,y2,x2,u:integer;

    c,o:char;

    t,t1:string;

function vspmas(i,j:integer;ol:mas):integer;

var ii,jj:integer;

begin

for ii:=i-1 to (i+1) do

for jj:=j-1 to (j+1) do

if (a[ii,jj]=1) then inc(h);

if (a[i,j]=1) then h:=h-1;

vspmas:=h;

end;

procedure see_a(n,m:integer; var ol:mas);

var q,w,y2,x2:integer;

begin

 

x2:=50;

y2:=50;

setbkcolor(white);

  {setcolor(blue);}

settextstyle(0,0,0);

setcolor(8);

setfillstyle(1,9);

for q:=1 to n do

       begin

for w:=1 to m do

begin

 

if (a[q,w]=1) then

begin

        setfillstyle(1,9);

bar(x2+2,y2+2,x2+14,y2+14);

        end

      else

          begin

          setfillstyle(1,0);

  bar(x2+2,y2+2,x2+14,y2+14);

          end;

x2:=x2+17;

end;

y2:=y2+17; x2:=50;

end;

   setcolor(1);

setcolor(yellow);

setfillstyle(1,9);

 

end;

procedure rec(n,m:integer);

var q,w,y2,x2:integer;

  begin

  cleardevice;

x2:=50;

y2:=50;

  setcolor(7);

  rectangle(0,0,1000,35);

  setfillstyle(1,7);

  floodfill(1,1,7);

setcolor(8);

setfillstyle(1,9);

for q:=1 to n do

       begin

for w:=1 to m do

begin

      rectangle(x2-1,y2-1,x2+17,y2+17);

x2:=x2+17;

end;

y2:=y2+17; x2:=50;

end;

setcolor(red);

setfillstyle(1,9);

rectangle(48,48,51+m*17,51+n*17);

  setcolor(7);

  outtextxy(500,470,'‘ҐаҐЈЁ ‘ҐаЈҐ©');

  end;

begin

clrscr;

writeln('„«п Є®а४⮩ а Ў®вл Їа®Ја ¬¬л ўў®¤ЁвҐ n<25 Ё m<33 !!!');

writeln('‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® бва®Є Ё бв®«Ўж®ў: ');

readln(n,m);

grDriver:=detect;

initgraph (grDriver,grMode,'');

for i:=0 to n+1 do for j:=0 to m+1 do a[i,j]:=0;

rec(n,m);

setcolor(red);

outtextxy(10,10,'‚ўҐ¤ЁвҐ  з «мго Є®¬ЎЁ жЁо дЁиҐЄ');

see_a(n,m,a);

x1:=50; y1:=50;

i:=1;j:=1;

repeat

   begin

   c:=readkey;

   if c=#077 then

      begin

      if (x1<=18+m*17) and (y1<=35+n*17) then

         begin

         setcolor(white);

         rectangle(x1+1,y1+1,x1+15,y1+15);

         setcolor(12);

         rectangle(x1+18,y1+1,x1+32,y1+15);

         x1:=x1+17;

         gotoxy(x1+8,y1+8);

         j:=j+1;

 

         setfillstyle(1,7);

         setcolor(yellow);

         bar(495,2,650,30);

         str(i,t);

         str(j,t1);

         t:='['+t+','+t1+']';

         outtextxy(550,5,t);

         end;

      end;

   if c=#072 then

      begin

      if (x1<=35+m*17) and (y1-16>=49) then

         begin

         setcolor(white);

         rectangle(x1+1,y1+1,x1+15,y1+15);

         setcolor(12);

         rectangle(x1+1,y1-16,x1+15,y1-2);

         y1:=y1-17;

         gotoxy(x1+8,y1+8);i:=i-1;

 

         setfillstyle(1,7);

         setcolor(yellow);

         bar(495,2,650,30);

         str(i,t);

         str(j,t1);

         t:='['+t+','+t1+']';

         outtextxy(550,5,t);

         end;

      end;

   if c=#080 then

      begin

      if (x1+16<=50+m*17) and (y1+33<=50+n*17) then

         begin

         setcolor(white);

         rectangle(x1+1,y1+1,x1+15,y1+15);

         setcolor(12);

         rectangle(x1+1,y1+18,x1+15,y1+32);

         y1:=y1+17;

         gotoxy(x1+8,y1+8);i:=i+1;

 

         setcolor(yellow);

         setfillstyle(1,7);

         bar(495,2,650,30);

         str(i,t);

         str(j,t1);

         t:='['+t+','+t1+']';

         outtextxy(550,5,t);

         end;

      end;

   if c=#075 then

      begin

         if (x1-17>=49) and (y1+16<=50+n*17) then

         begin

         setcolor(white);

         rectangle(x1+1,y1+1,x1+15,y1+15);

         setcolor(12);

         rectangle(x1-16,y1+1,x1-2,y1+15);

         x1:=x1-17;

         gotoxy(x1+8,y1+8);j:=j-1;

 

         setcolor(yellow);

         setfillstyle(1,7);

         bar(495,2,650,30);