Динамические структуры данных. Линейный однонаправленный список с головным элементом

Для выявления отношения имеющегося и строящегося классов необхо­димо выполнить анализ структуры объектов предметной области, получен­ных в результате объектной декомпозиции.

Если объекты предметной области слишком сложны, чтобы ставить им в соответствие некий простой класс, то процесс декомпозиции можно про­должить, выделяя внутри сложных объектов более простые.

При этом возможны следующие варианты.

1. Внутри объекта можно выделить объект близкого назначения, но с бо­лее простой структурой и/или поведением - класс для реализации данного объекта следует строить на базе более простого, используя наследование. Ес­ли при этом объекты строящего класса отличаются от объектов базового класса некоторыми аспектами поведения, то следует изменить поведение объектов строящего класса при наследовании, используя полиморфное на­следование с переопределением методов.

2. Внутри объекта можно выделить определенное количество объектов более простой структуры со своим поведением - класс строится объединени­ем объектов других классов с добавлением полей и методов строящегося класса - композиция классов.

3. Внутри объекта можно выделить заранее не предсказуемое количест­во объектов более простой структуры со своим поведением - класс строится с возможностью динамического подключения объектов других классов (на­полнение) и добавлением полей и методов строящегося класса

2.Задача

С помощью языка высокого уровня – «Object Pascal» , спроектировать и создать программный продукт -  игру «Pacman». В программе обязательно должны быть задействованы такие динамические структуры данных: линейный однонаправленный список с головным элементом, объекты.

В игре был определен класс Tghost, впоследствии были созданы три экземпляра данного класса. У объекта есть методы hide (стирает приведение с формы), show (рисует приведение на форме), move (отвечает за смещение приведения) и chdir (отвечает за смену направления движения).

За движение и анимацию объектов отвечают таймеры, которые в заранее определенном интервале запускают методы соответствующих объектов. Экземпляры класса Tghost «охотятся» за pacman-ом, прорисованным на канве, игра заканчивается, когда количество жизней pacman-a равно нулю. Свободное от стен, pacman-a и приведений пространство заполняется «едой» при поедании которой игроку начисляются определенные очки. Новую жизнь pacman получает, когда «съедает» 8 желтых бонусов. На визуальном компоненте StatusBar есть три панелт, в первой отражается количество очков полученных pacman-ом (синий шарик-3 очка, зеленый-2 очка). Количество желтых шариков собранных pacman-ом отражается во второй панели. Когда pacman собирает 8 желтых шариков у него появояется еще одна жизнь. Количество жизней отражается в третьей панели, это число списывается из головного элемента списка.

              Однонаправленным списком с головным элементом в игре является цепь «жизней» pacman-a. Если  pacman собирает 8 желтых шариков, у него появляется жизнь и создается новый элемент списка, который добавляется в конец, если pacman теряет жизнь (попадает на приведение) то элемент удаляется из конца списка. Количество элементов списка, а следовательно и количество жизней, хранится в головном элементе списка.

3.Ход работы

              При запуске игры появляется полностью прорисовывается все элементы игры, которые сразу начинают движение (рис. 1):

Рис. 1.

В любой момент времени игру можно остановить с помощью клавиши «пробел», а продолжить с помощью клавиши «enter».Движение осуществляется с помощью стрелок. Если количество жизней становится равно нулю, игра заканчивается (рис. 2):

Рис. 2.

Если же удалось собрать все шарики, то уровень заканчивается, появлением сообщения «you are win!»   (рис. 3):

Рис. 3.

4.Тестирование

В этом пункте проводится три теста программы и по ним определяется надежность программы.

Тест №1.

Если пакман при движении сталкивается с привидением, должны выполниться действия:

1)                  Количество жизней пакмана должно уменьшится на единицу.

2)                  Если количество жизней равно нулю, игра должна закончится с надписью “Game over” (рис.2).

Тест №2.

              При съедании пакманом еды, очки игрока должны увеличиться. При съедании зеленого шарика- на 1 (рис. 4):

Рис. 4.

Тест №3

При съедании синего шарика количество очков должно увеличиться на три (рис.5):

Рис. 5.

Тест №4.

              При съедании пакманом желтого шарика-бонуса, количество бонусов должно отразиться во второй панели StatusBar (рис. 6):

Рис. 6.

Тест №5.

При съедании 8 желтых шариков в третьем поле StatusBar должно увеличиться на 1 количество жизней (рис. 7):

Рис. 7.

              Все проведенные тесты были выполнены корректно, следовательно, делается вывод – надежность программы равна 100 %.

5.Заключение

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

6.Литература

Основная:

1.       Delphi 7 Наиболее полное руководство. А. Хомоненко, В. Гофман, Е. Мещеряков, В. Никифоров. — СПб.: БХВ-Петербург 2003.

2.       Фундаментальные алгоритмы и структуры данных в Delphi. Джулиан Бакнелл — СПб.: БХВ-Петербург, 2003.

3.       Фленов М. Е. Библия Delphi. — 2-е изд., перераб. и доп. — СПб.: БХВ-Петербург

4.       Лекции  «Объектная модель Delphi». В.П. Грибанов

Дополнительная:

1.       http://delphiworld.narod.ru – создание объектных переменных.

http://delphiworld.narod.ru/base/create_objective_vars.html

2.       http://delphi-master.ucoz.ru – работа со списками.

http://delphi-master.ucoz.ru/forum/4-10-1

Листинг функциональных частей

// Структура класса Tghost

Tghost=class

    public

      coordX:integer;

      coordY:Integer;

      stX:integer;

      stY:integer;

      dir:Char; //direction

      col:Tcolor;

      constructor create;overload;virtual;

      procedure hide;

      procedure show;virtual;

      procedure chdir;

      procedure move;

  end;

//создание списка

first := new (point);

//FIRST := NIL;

first^.INF1:=0;

FIRST.NEXT := NIL;

k:=0;

//добавление элемента в конец списка

PROCEDURE TForm1.INS_END_LIST;

var

  q,p : point;

BEGIN

Q:=FIRST;

WHILE Q.NEXT <> NIL DO

                                                Q:=Q.NEXT;

                                                  Q.NEXT:= new(Point);

                            Q.NEXT.NEXT:=NIL;

               K:=k+1;

               first.inf1:=k;

end;

// удаление элемента из конца списка

PROCEDURE TForm1.DEL_END_LIST;

VAR

Q,P,T:point;

BEGIN

                       IF FIRST <> NIl THEN

           BEGIN

                                                 IF  FIRST.NEXT = NIL THEN

             BEGIN

                                                                           P := FIRST;

                                               DISPOSE (P);

                                                                           FIRST := NIL;

                                                                    END

                                         ELSE    BEGIN

                                                                                   Q := FIRST;

                                                                    T := FIRST;

                                         WHILE Q^.NEXT <> NIL DO

                                                                    BEGIN

                                                                            T := Q;

                                                          Q:=Q^.NEXT;

                                                          END;

                                                                    DISPOSE  (Q);

                                                                    T^.NEXT := NIL;

                                                                 END ;

                                      END;

               k:=k-1;

               first.inf1:=k;

END;

// движение объекта

procedure TForm1.tmrghostTimer(Sender: TObject);

begin

for i:=0 to 2 do

ghost[i].move;

procedure Tghost.move;

function can_dvig_vprav: boolean;

var i,j:integer;

begin

result:=TRUE;

I:=coordY DIV 30;

J:=coordX DIV 30;

if  ((coordX+d+7)>Form1.clientwidth) or (mas[I+1,j+2]=4) then

begin

result:=FALSE;

end;

end;

function can_dvig_vlev: boolean;

var i,j:integer;

begin

result:=TRUE;

I:=coordY DIV 30;

J:=coordX DIV 30;

if  ((coordX-sd)<0) or (mas[I+1,j]=4) then

begin

result:=FALSE;

end;

end;

function can_dvig_vniz: boolean;

var i,j:integer;

begin

result:=TRUE;

I:=coordY DIV 30;

J:=coordX DIV 30;

if  ((coordY+d+d-1)> Form1.clientheight) or (mas[I+2,j+1]=4) then

begin

result:=FALSE;

end;

end;

function can_dvig_vverh: boolean;

var i,j:integer;

begin

result:=TRUE;

I:=coordY DIV 30;

J:=coordX DIV 30;

if  ((coordY-sd)<0) or (mas[I,j+1]=4) then

begin

result:=FALSE;

end;

end;

begin

   if (dir='R') AND  (can_dvig_vprav) then

   begin                             //go right

     hide;

     coordX:=coordX+d;

     show;

   end else

   if (dir='L') AND  (can_dvig_vlev) then

   begin                             //go left

     hide;

     coordX:=coordX-d;

     show;

     // ghost.chdir;

   end else

   if (dir='D') AND  (can_dvig_vniz) then

   begin                             //go down

     hide;

     coordY:=coordY+d;

     show;

    //  ghost.chdir;

   end else

   if (dir='U') and (can_dvig_vverh)then

   begin                             //go up

     hide;

     coordY:=coordY-d;

     show;

   end else

   begin

     chdir;

   end;

end;

procedure Tghost.hide;

begin

with Form1.image1.canvas do

begin

   pen.Color:=clBlack;

   brush.Color:=clBlack;

   Rectangle(coordX,coordY,coordX+d,coordY+d);

   end;

end;

procedure Tghost.show;

begin

with Form1.image1.canvas do

begin

   pen.Color:=col;

   brush.Color:=col;

   Rectangle(coordX,coordY,coordX+d,coordY+d);

   end;

end;

procedure Tghost.chdir;

var a:integer;

begin

  a:=Random(4);

  case a of

    0:dir:='L';

    1:dir:='R';

    2:dir:='U';

    3:dir:='D';

  end;

end;

//создание формы, изначальная прорисовка карты

procedure TForm1.FormCreate(Sender: TObject);

begin

Form1.DoubleBuffered:=True;

with image1.canvas do

begin

brush.Color:=clblack;

  fillrect(rect(0,0,clientwidth,clientheight));

  end;

  for i:=1 to 15 do

  for j:=1 to 15 do

  mas[i,j]:=5;

mas[2,2]:=3;

mas[3,2]:=4;

mas[3,3]:=4;

mas[3,4]:=4;

mas[3,5]:=4;

mas[3,6]:=4;

mas[3,9]:=4;

mas[3,10]:=4;

mas[3,11]:=4;

mas[3,12]:=4;

mas[3,13]:=4;

mas[4,9]:=4;

mas[5,9]:=4;

mas[6,9]:=4;

mas[7,9]:=4;

mas[8,9]:=4;

mas[9,9]:=4;

mas[10,9]:=4;

mas[5,4]:=4;

mas[6,4]:=4;

mas[7,4]:=4;

mas[8,4]:=4;

mas[11,3]:=4;

mas[12,3]:=4;

mas[13,3]:=4;

mas[14,3]:=4;

mas[14,4]:=4;

mas[14,5]:=4;

mas[14,6]:=4;

mas[14,7]:=4;

mas[14,8]:=4;

mas[14,9]:=4;

mas[14,10]:=4;

mas[14,11]:=4;

mas[14,12]:=4;

mas[14,13]:=4;

mas[13,13]:=4;

mas[12,13]:=4;

mas[11,13]:=4;

for i:=1 to 15 do

for j:=1 to 15 do

  begin

if (mas[i,j]<>4) and (mas[i,j]<>3)

then     mas[i,j]:=random(3);

end;

for i:=1 to 15 do

for j:=1 to 15 do  begin

if mas[i,j]=4 then

begin

sx:=d*(j-1);

sy:=d*(i-1);

with image1.canvas do

begin

pen.Color:=clcream;

   brush.Color:=clcream;

rectangle(sx,sy,sx+d,Sy+d);

end;

end;

if mas[i,j]=3 then

begin

x1:=d*(j-1);

y1:=d*(i-1);

with image1.canvas do

begin

pen.Color:=clred;

   brush.Color:=clred;

   ellipse(x1,y1,x1+d,y1+d);

   end;

end;

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

begin

sx:=d*(j-1);

sy:=d*(i-1);

with image1.canvas do

begin

pen.Color:=clgreen;

   brush.Color:=clgreen;

   ellipse(sx+7,sy+7,sx+16,sy+16);

   end;

end;

if (mas[i,j]=1)  then

begin

sx:=d*(j-1);

sy:=d*(i-1);

with image1.canvas do

begin

pen.Color:=clblue;

   brush.Color:=clblue;

   ellipse(sx+7,sy+7,sx+16,sy+16);

   end;

end;

if (mas[i,j]=2)  then

begin

sx:=d*(j-1);

sy:=d*(i-1);

with image1.canvas do

begin

pen.Color:=clyellow;

   brush.Color:=clyellow;

   ellipse(sx+7,sy+7,sx+16,sy+16);

   end;

end;

end;

   for i:=0 to 2 do

   ghost[i]:=Tghost.create; //create, draw

   ghost[0].col:=$00EECFF5;

   ghost[1].col:=$00400040;

   ghost[2].col:=clMaroon;

   ghost[0].dir:='L';

   ghost[1].dir:='R';

   ghost[2].dir:='U';

   ghost[0].stX:=3;

   ghost[1].stX:=4;

   ghost[2].stX:=4;

   ghost[0].stY:=3;

   ghost[1].stY:=4;

   ghost[2].stY:=6;

   for i:=0 to 2 do

     begin

       ghost[i].coordX:=ghost[i].stX*d;

       ghost[i].coordY:=ghost[i].stY*d;

     end;

    spbonus:=0;

   win:=0;

   bonus:=0;

   timer1.Enabled:=true;

tmrghost.Enabled:=true;

tmrgame.Enabled:=true;

redraw.Enabled:=true;

  tmnaprav.Enabled:=true;

naprav:=#0;

bonus:=0;

sum:=0;

  form1.StatusBar1.panels[1].text:=inttostr(bonus);