193

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

Реферат

Информатика, кибернетика и программирование

Установка начальных значений ячеек сетки, анализ поведения различных комбинаций клеток на доске в математический игре Жизнь. Хранение значений клеток методом использования двумерного массива и заполнение его соответственными комбинациями.

Русский

2012-11-14

276 KB

135 чел.

Содержание

ВВЕДЕНИЕ

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> или, если новая комбинация оказывается такой же, как и предыдущая.

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

  1.  

 

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

{$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);

        str(i,t);

        str(j,t1);

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

        outtextxy(550,5,t);

          end;

     end;

  if c=#13 then

     begin

     if (a[i,j]=0) then

        begin

        a[i,j]:=1;

        setcolor(white);

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

        setfillstyle(1,9);

        bar(x1+2,y1+2,x1+14,y1+14);

        end

     else

         begin

         a[i,j]:=0;

         setcolor(white);

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

         setfillstyle(1,0);

         bar(x1+2,y1+2,x1+14,y1+14);

         end;

     end;

  end

  until c=#27;

setcolor(white);

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

for i:=0 to n+1 do

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

for q:=1 to n do

   for w:=1 to m do b[q,w]:=a[q,w];

k:=0;

u:=1;

setfillstyle(1,7);

bar(1,1,400,20);

setfillstyle(1,7);

Repeat

begin

 for i:=1 to n do

for j:=1 to m do

    begin

    h:=vspmas(i,j,a);

   if (h=0) or (h=1) or (h>3) then b[i,j]:=0;

   if (h=3) then b[i,j]:=1;

   h:=0;

    end;

{  rec(n,m); }

 see_a(n,m,b);

 setfillstyle(1,7);

 bar(495,2,650,30);

 str(u,t);

 t:='Џ®Є®«ҐЁҐ: '+t;

 outtextxy(500,10,t);

 outtextxy(10,10,'‚лЇ®«ҐЁҐ...');

delay(250);

k:=0;

for q:=1 to n do

 for w:=1 to m do if (a[q,w]<>b[q,w]) then k:=k+1;

if (k=0) then c:='q';

 for q:=1 to n do

for w:=1 to m do a[q,w]:=b[q,w];

 end;

 inc(u);

Until (keypressed) or (c='q');

bar(1,1,400,30);

Outtextxy(10,10,'ЏаҐ®Ўа §®ў Ёп ®Є®зҐл! Ќ ¦¬ЁвҐ <ENTER>... ');

readln;

end.

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

Начальное окно программы:

Рисунок 1

Основное окно программы:

Рисунок 2

Работа программы:

Рисунок 3

  1.  
    ВЫВОД

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

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

  1.  Фролов В. В. Турбо паскаль 7.0. начальный курс. Учебное пособие. Издательство «ОМД Групп» , 2003, -616с, ил.  
  2.   Интернет университет информационных технологий
  3.  Шериков А. В.  Сравнительный анализ сортировок массивов
  4.  Методические указания к лабораторным работам. ГОУВПО «воронежский государственный технический университет»; сост. Р.В.Батищев. Воронеж, 2006. 53с.
  5.  Л.Д. Михелев. «Язык программирования паскаль» издательство.

 Москва, 2007. – 432с.:ил.

  1.  А.И. Сенокосов Игра жизнь


 

А также другие работы, которые могут Вас заинтересовать

68818. Привод общего назначения 1016 KB
  Расчет зубчатой передачи и передачи винтгайка. Расчет ременной передачи. Литература Введение Редуктором называют механизм состоящий из зубчатых или червячных передач выполненный в виде отдельного агрегата и служащий для передачи вращения от вала двигателя к валу рабочей машины.
68819. ПРИВОД КОНВЕЙЕРА 551.5 KB
  Привод – устройство для приведения в действие двигателем различных рабочих машин. Энергия, необходимая для приведения в действие машины или механизма, может быть передана от вала двигателя непосредственно или с помощью дополнительных устройств (зубчатых, червячных, цепных, ременных и др. передач).
68820. КОРОБКА СКОРОСТЕЙ 1.85 MB
  Коробкой скоростей называется механизм, состоящий из зубчатых передач, выполненный в виде отдельного органа и служащий для передачи вращения от вала двигателя к валу рабочей машины. Назначение коробки скоростей - понижение угловой скорости и повышение вращающего момента ведомого вала по сравнению с ведущим.
68821. Проект привода конвейера 841.5 KB
  Выбираем цилиндрический редуктор с горизонтальным положением колёс. Корпус редуктора выполнен разъемным, литым из чугуна марки СЧ15 ГОСТ 1412-79. Сборка и разборка редуктора производится при снятой крышке. Контроль зацепления колёс производится через смотровой люк.
68823. Привод (Электродвигатель: АИР 100L6) 866 KB
  Наиболее распространены горизонтальные редукторы. Как горизонтальные, так и вертикальные редукторы могут иметь колеса с прямыми, косыми и круговыми зубьями. Корпус чаще всего выполняют литым чугуном, реже сварным стальным. Валы монтируются на подшипниках качения или скольжения.
68824. Перетворення вхідної граматики у LL(1)-граматику 93 KB
  Аналогічне ствердження має місце відносно ліворекурсивного циклу приклад якого дають правила 1. У наведеному прикладі правила 2 3 4 6 утворюють ліворекурсивний цикл який завжди можна вилучити перетворив одне з правил наприклад 6 у ліву рекурсію. Для С існують два правила 4 та 5.
68825. Застосування ДМП-автомату для реалізації висхідного аналізу 179 KB
  Для реалізації висхідного аналізу використовується ДМП-автомат, який працює за таким принципом. Якщо вхідний рядок приймається, то у кожному такті конкатенація символів, що знаходяться у магазині, і символів, що належать до ще непрочитаної частини вхідного рядка, утворює...