193

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

Реферат

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

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

Русский

2012-11-14

276 KB

118 чел.

Содержание

ВВЕДЕНИЕ

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


 

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

74102. Қазақстан жеріндегі әскери қозғалыстар мен соғысқа кіруі 21.52 KB
  Қазақстан азамат соғысы жылдарында 19181920 жж. Ленин қол қойған халық комитетінің декреті бойынша қырғыз қазақ революциялық комитеті қүрылды. Оның қарамағына Қазақ Совет автономиясы жарияланып өлке Советтерінщ құрылтай съезі шақырылғанға дейін қазақ тұрғындары мекендеген Орал ТорғайАқмола Семей облысы мен Астрахань губерниясы жерівдегі барлық жоғарғы әскериазаматтық басқармалар берілді.
74103. Көтерілістің шығу себептері 21.34 KB
  Қатардағы қарапайым қазақтар жерді солардан жалға алып пайдаланды. Қазақ ақсүйектері орыс помещиктерінен жалға алған жерлерді өздерінің жеке қалауы бойынша қазақ ауылдарынакөтеріңкі қымбат бағаға тағы да қайыра жалға беріп отырды. Сөйтіп қазақтардан әр түрлі айыппұлдар мен алымсалықты еселеп алып тұрды 1836 жылы халық көтерілісі басталды.
74104. соты және олардың қазақ қоғамы өміріндегі атқарған рөлі 21.14 KB
  XIX ғасырдың 20жылдарынан бастап патша үБилер билер соты және олардың қазақ қоғамы өміріндегі атқарған рөлі[өңдеу] Ресей Қазақстан аумағына азаматтық және әскери сот жүйесін енгізгенге дейін мұнда дәстүрлі билер соты болатын. Қазақ қоғамында билер ешқашан сайланып та тағайындалып та қойылмаған. Ондай билердің атақдаңқы жөніндегі хабар дала тұрғындары арасына тез таралатын.
74105. Түрік қағандығы 20.71 KB
  Түрік немесе қажыр қайраттылар деген атпен белгілі болды. Түрік қағанаты Түрік Қағандығының қоғамдық өмірінде әскери іс маңызды орын алды. Түріктер мал шмен аңшылықпен айналысты.
74107. Қыпшақ хандығы 19.99 KB
  Қыпшақтар туралы алғашқы хабар Қытайдың жазба деректерінде кездеседі. Қыпшақтар ең әуелі Алтай Саян тауларының баурайларын мекендеген. VIIX ғасырларда Қазақстан аумағында қыпшақ этникалық қауымдастығының ұзаққа созылған қалыптасу процесі жүрді.
74108. Жәңгірұлы Тәуке хан 19.7 KB
  Тәуке ел ағасы жасына келіп ақыл тоқтатқан мемлекет ісіне араласып мол тәжірибе жинақтаған білікті жан болатын. Тәукені өзге қазақ хандарынан ерекшелеп оның шын мәнінде көреген басшы ақылды реформатор екенін танытанын қасиеті де осы өзіндік жолмен жүруінде. Тәуке ханның елі үшін сіңірген ерен еңбегі екі қырымен айрықша назар аударады.
74109. Шығыс Түрік қағанаты 19.42 KB
  Түрік қағанатында саясиәлеуметтік қайшылықтардың шиеленісуі оның дербестікке ұмтылған жеке бөліктерінде оқшаулану үрдісінің күшеюі Шығыс және Батыс қағанаттарының құрылуына алып келді. Шығыс түріктері Қытаймен жүргізген қиянкесті соғыстың нәтижесінде 682 жылы Монғолияда өз мемлекетін қалпына келтірді. Шығыс Түрік қағандығы 682744 Қазақстан Орталық Азия Шығыс Түркістан Оңтүстік Сібір жерлерін алып жатты.
74110. Үйсін мемлекеті 18.65 KB
  3 ғасырда Қазақстанды мекендеген тайпаларда мемлекеттіктің алғашқы белгілері болды. Ежелгі үйсіндерде әлеуметтікэкономикалық қатынастар өтпелі кезеңге тән сипатта болды. Жартылай көшпелі және жартылай отырықшы үйсін коғамында өндірістің екі негізгі түрі болды: мал және жер. Рулық құрылыстың ыдырауы барысында туындаған таптық қатынастар құлиеленушілік сипатқа ие болды.