193

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

Реферат

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

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

Русский

2012-11-14

276 KB

140 чел.

Содержание

ВВЕДЕНИЕ

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.  А.И. Сенокосов Игра жизнь


 

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

36065. История России 30 KB
  История России неотъемлемая часть всемирной истории. В России была сделана героическая попытка создать посткапиталистическое общество социализм которая оказала прогрессивное влияние на развитие всего человечества. В XVIII XIX XX веках Россия оказывала влияние на процессы происходившие в Европе и мире: участие в Тридцатилетней войне Семилетняя война война со Швецией походы Суворова разгром армии Наполеона Священный Союз поддержка Северной Америки в войне с Англией за независимость участие России в I мировой войне Великая...
36066. Философия, Конспект лекций. История и теория философии 1.34 MB
  Можно видеть ореол вокруг человека а можно и просто ореол без людей. К середине 19 в в науке и философии сложилось понимание того что все или почти все проблемы человека лежат в отношениях между людьми или в социуме Но в обществе все либо прямо либо опосредованно зависит от деятельности людей а действуют люди имеющие тройственную сущность биологическую психическую и социальную. Данная ситуация привела к новому облику философии: появилось деление: рационализм психологическое направление иррационализм рассматривание социальных...
36067. Схоластика в традиции европейской ментальности 135.1 KB
  Философ Эриугена от которого ведут начало схоластики был приглашен ко двору короля Карла Лысого в Париж из далекой Ирландии где в монастырских школах сохранились традиции латинской и греческой образованности. Неосхоластика или вторая схоластика ряд течений католической философской мысли ориентированных на возрождение схоластики осуществляемое в рамках: контрреформации 15 вв. Теоретическими источниками формирования схоластики выступают: византийская теология и патристика прежде всего сочинения Августина Блаженного....
36068. Целевое конспектирование источников по дисциплине «Философия» 2.14 MB
  Но когда у человека его вожделения резко клонятся к чемунибудь одному мы знаем что от этого они слабеют в отношении всего остального словно поток отведенный в сторону. Если ему свойственны возвышенные помыслы и охват мысленным взором целокупного времени и бытия думаешь ли ты что для такого человека много значит человеческая жизнь Нет это невозможно Значит такой человек и смерть не будет считать чемто ужасным Менее всего. Вот почему рассматривая философская ли душа у какогонибудь человека или нет ты сразу еще в его...
36069. Философия. Основы философии 1.2 MB
  В своих сочинениях Платон не просто ставит и решает те или иные философские проблемы он дает нам чистый образец того что есть философское рассуждение само по себе что за мир открывается философу и каково значение обращения души человека к миру умопостигаемого. Душа видевшая всего больше попадает в плод будущего поклонника мудрости и красоты или человека преданного Музам и любви; вторая за ней в плод царя соблюдающего законы в человека воинственного или способного управлять; третья в плод государственного деятеля хозяина...
36070. Философия жизни 130.5 KB
  Ницше: он подверг критике рационалистические концепции мира человека истории которые господствовали в философии на протяжении XVII XVIII первой половины XIX вв. НИЦШЕ гениальный немецкий философ главным мучением всей жизни которого был вопрос: Можно ли надеяться когданибудь облагородить человечество Наделенный ясновиденьем нервов С. Цвейг Ницше пережил смерть Бога в личном трагическом опыте и вместе с тем провозвещая XX век постиг как судьбу современного человека. Обозначив кризис европейского гуманизма философия Ницше...
36071. Конспект лекцій з курсу Філософія 1.63 MB
  Філософія як форма світогляду її роль в житті суспільства і людини. Буття людини. У цій ситуації проблеми світоглядної орієнтації людини усвідомлення нею свого місця і ролі в суспільстві мети і сенсу соціальної і особистої активності відповідальності за свої вчинки і вибір форм і напрямів своєї діяльності стають головними життєвими цінностями. У становленні і формуванні світоглядної культури людини філософія завжди грала особливу роль повязану з її багатовіковим досвідом критичнорефлексивного осмислення глибинних...
36072. Потенціал підприємства: сутність і механізм функціонування 73.5 KB
  Предмет мета завдання курсу управління потенціалом підприємства УПП . Елементи підприємницького потенціалу підприємства ППП Джерела потенціалу підприємства і шляхи його збільшення. Управління потенціалом підприємства УПП є сферою економічного дослідження і створення методів аналізу і оцінювання можливостей підприємств з урахуванням практики діагностики внутрішнього і зовнішнього середовища підприємств.
36073. Структурний аналіз ресурсного потенціалу в системі управління витратами і інвестиціями 92 KB
  Структурний аналіз ресурсного потенціалу в системі управління витратами і інвестиціями. Обєкти субєкти цілі в системі управління витратами. Аналіз витрат і прийняття управлінського рішення. Резерви підприємства можуть бути повязані з витратами.