Курсовая работа: Аркадна гра "гольф" з елементами трьохвимірної поверхні

Пошук i-го елемента в зв'язаному стиснутому збереженні здійснюється методом повного перегляду, при послідовному збереженні - методом бінарного пошуку.

Переваги і недоліки послідовного стиснутого і зв'язаного стиснутого аналогічні перевагам і недолікам послідовного і зв'язаного збереження.

Розглянемо наступну задачу. На вход задані дві послідовності цілих чисел M=, N=, причому 92% елементів послідовності М дорівнюють нулеві. Скласти програму для обчислення суми добутків Mi * Ni, і=1,2,...,10000.

Припустимо, що список М зберігається послідовно стисло в масиві структур m з оголошенням:

 

struct

{ int nm;

float val; } m[10000];

Для визначення кінця списку додамо ще один елемент із порядковим номером m[j].nm=10001, що називається стопером (stopper) і розташовується за останнім елементом стиснутого збереження списку в масиві m.

 Програма для перебування шуканої суми має вигляд:

 # include

 main()

{ int і,j=0;

float inp,sum=0;

struct /* оголошення масиву */

{ int nm; /* структур */

float val; } m[10000];

 

for(i=0;i<10000;i++) /* читання списку M */ { scanf("%f",&inp); if (inp!="0)" { m[j].nm="i;" m[j++].val="inp;" } } m[j].nm="10001;" /* stopper */ for(i="0,j=0;" i<10000; i++) { scanf("%f",&inp); /* читання списку N */ if(i="=m[j].nm)" /* обчислення суми */ sum+="m[j++].val*inp;" } printf( "сума добутків Mi*Ni дорівнює %f",sum); }

Індексне збереження використовується для зменшення часу пошуку потрібного елемента в списку і полягає в наступному. Вихідний список B = розбивається на трохи підсписків У1,У2, ...,Вм таким чином, що кожен елемент списку В попадає тільки в один з підсписків, і додатково використовується індексний список з М елементами, що вказують на початок списків У1,У2, ...,Ум.

Вважається, що список зберігається ндексно за допомогою підсписків B1,B2, ...,Bm і індексного списку X = , де ADGj - адреса початку підсписка Bj, j=1,M.

При індексному збереженні елемент До підсписка Bj має індекс j. Для одержання індексного збереження вихідний список У часто перетвориться в список В' шляхом включення в кожен вузол ще і його порядкового номера у вихідному списку В, а в j-ий елемент індексного списку Х, крім ADGj, може включатися деяка додаткова інформація про підсписок Bj. Розбивка списку В на підсписки здійснюється так, щоб всі елементи В, що володіють визначеною властивістю Рj, попадали в один підсписок Bj.

Достоїнством індексного збереження є те, що для перебування елемента К с заданою властивістю Pj досить переглянути тільки елементи підсписка Bj; його початок знаходиться по індексному списку Х, тому що для кожного ДО, що належить Bi, при і не рівному j властивість Pj не виконується.

У розбивці В часто використовується ндексна функція G(K), що обчислює по елементі До його індекс j, тобто G(K)=j. Функція G звичайно залежить від позиції ДО, що позначається поз.K, у підсписку В або від значення визначеної частини компоненти ДО - її ключа.

Розглянемо список B= з елементами

ДО1=(17,Y), K2=(23,H), K3=(60,I), K4=(90,S), K5=(66,T),

K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).

Якщо для розбивки цього списку на підсписки як індексну функцію взяти Ga(K)=1+(поз.K-1)/3, то список розділиться на три підсписка:

B1a=<(17,Y),(23,H),(60,I)>,

B2a=<(90,S),(66,T),(77,T)>,

B3a=<(50,U),(88,W),(30,S)>.

Додаючи усюди ще і початкову позицію елемента в списку, одержуємо:

B1a'=<(1,17,Y),(2,23,H),(3,60,I)>,

B2a'=<(4,90,S),(5,66,T),(6,77,T)>,

B3а'=<(7,50,U),(8,88,W),(9,30,S)>.

Якщо як індексну функцію вибрати іншу функцію Gb(K)=1+(поз.K-1)%3, то одержимо списки:

B1b"=<(1,17,Y),(4,90,S),(7,50,U)>,

B2b"=<(2,23,H),(5,66,T),(8,88,U)>,

B3b"=<(3,60,I),(6,77,T),(9,30,S)>.

Тепер для перебування вузла K6 досить переглянути тільки одну з трьох послідовностей (списків). При використанн функції Ga(K) це список B2а', а при функції Gb(K) список B3b".

Для індексної функції Gc(K)=1+K1/100, де K1 - перший компонент елемента ДО, знаходимо:

B1=<(17,Y),(23,H),(60,I),(90,S)>,

B2=<(66,T),(77,T)>,

B3=<(50,U),(88,W)>,

B4=<(30,S)>.

Щоб знайти тут вузол К с першим компонентом-ключем ДО1=77, досить переглянути список B2.

При реалізації індексного збереження застосовується методика А для збереження індексного списку Х (функція Ga(X) ) методика C для збереження підсписків B1,B2,...,Bm (функція Gc(Bi)), тобто використовується, так називане, A-C індексне збереження.

У практиці часто використовується послідовно-зв'язане індексне збереження. Тому що звичайно довжина списку ндексів відома, те його зручно зберігати послідовно, забезпечуючи прямій доступ до будь-якого елемента списку індексів. Підсписки B1,B2,...,Bm зберігаються пов'язано, що спрощує вставку і видалення вузлів(елементів). Зокрема, подібний метод збереження використовується в ЄС ЕОМ для організації, так званих, індексно-послідовних наборів даних, у яких доступ до окремих записів можливий як послідовно, так і за допомогою ключа.

Послідовно-зв‘язане індексне збереження для приведеного приклада зображене на мал.24, де X=.

 Розглянемо ще одну задачу. На вход задана послідовність цілих позитивних чисел, що закінчується нулем. Скласти процедуру для введення цієї послідовності й організації її індексного збереження таким чином, щоб числа, що збігаються в двох останніх цифрах, містилися в один підсписок.

Виберемо як індексну функцію G(K)=K%100+1, а як індексний список Х - масив з 100 елементів. Наступна функція вирішує поставлену задачу:

 #include

 #include

 typedef struct nd

{ float val;

struct nd *n; } ND;

int index (ND *x[100])

{ ND *p;

int i,j=0;

float inp;

for (i=0; i<100; i++) x[i]="NULL;" scanf("%d",&inp); while (inp!="0)" { j++; p="malloc(sizeof(ND));" i="inp%100+1;" p->val=inp;

p->n=x[i];

x[i]=p;

scanf("%d",&inp);

}

return j;

}

Значенням функції, що повертається, index буде число оброблених елементів списку.

Для індексного списку також може використовуватися індексне збереження. Нехай, наприклад, мається список B= з елементами

K1=(338,Z), K2=(145,A), K3=(136,H), K4=(214,I), K5 =(146,C),

K6=(334,Y), K7=(333,P), K8=(127,G), K9=(310,O), K10=(322,X).

Потрібно розділити його на сімох підсписків, тобто X= таким чином, щоб у кожен список B1,B2,...,B7 попадали елементи, що збігаються в першому компоненті першими двома цифрами. Список Х, у свою чергу, будемо індексувати списком індексів Y=, щоб у кожен список Y1,Y2,Y3 попадали елементи з X, у яких у першому компоненті збігаються перші цифри. Якщо списки B1,B2,...,B7 зберігати пов'язано, а списки індексів X,Y індексно, те такий спосіб збереження списку B називається зв'язаним індексним збереженням. Графічне зображення цього збереження приведене на мал.25.

Практична частина

Лістінг програми

Основний модуль golf.c

#include <time.h>

#include <stdlib.h>

#include <dos.h>

#include <conio.h>

#include <math.h>

#include <malloc.h>

#define GRIDSIZE 80 /* Must be bigger than VIEWSIZE */

#define VIEWSIZE 61 /* MUST be odd */

#define DIFF (GRIDSIZE-VIEWSIZE)

#define DEF_DIST -1100

#define DEF_PITCH 122

#define DEF_HEIGHT 120

#define DEF_ROLL 315

#define sine(X) ((long)(sn_tbl[X]))

#define cosine(X) ((long)(sn_tbl[((X)+90) % 360]))

#define C_Plot(X,Y,C) pokeb(0xa000, (X) + 320U*(Y), C)

#define SHIFT 14

#define MASK (GRIDSIZE*GRIDSIZE)

/*

#define GetGrid(X,Y) ((unsigned)grid[((X) + GRIDSIZE*(Y) +idx) % MASK])

#define PutGrid(X,Y,C) grid[((X) + GRIDSIZE*(Y) +idx) % MASK] = (unsigned char)(C)

*/

#define CalcAddress(X,Y) (&grid[((X) + GRIDSIZE*(Y) + idx) % MASK])

extern void far *view_screen;

extern void far *screen;

extern int sn_tbl[360];

extern unsigned char grid[GRIDSIZE*GRIDSIZE];

extern unsigned rand_seed;

unsigned idx = 0;

extern long pitch_sine;

extern long pitch_cosine;

extern long roll_sine;

extern long roll_cosine;

int num_points = GRIDSIZE*GRIDSIZE;

#define START (DIFF/2)

int gx = START,gy = START;

unsigned char *gp;

int cz = DEF_DIST;

int cy = DEF_HEIGHT;

int roll = DEF_ROLL;

int cpitch = DEF_PITCH;

extern void SetMyMode(void);

extern void ClearMyScreen(void);

extern void Project(void);

extern void SwapScreens(void);

extern void DoPlasma(int,int,int,int);

extern int GetRand(void);

extern unsigned GetGrid(void);

extern void PutGrid(void);

#define _GetGrid(X,Y) (_AX = (X), _BX = (Y), GetGrid())

#define _PutGrid(X,Y,C) { _CX = (C); _AX = (X); _BX = (Y); PutGrid(); }

void SetMode(void)

{

         struct REGPACK regs;

         regs.r_ax = 0x13;

         intr(0x10, &regs);

}

void SetTextMode(void)

{

         struct REGPACK regs;

         regs.r_ax = 0x3;

         intr(0x10, &regs);

}

void SetPalette(void)

{

         register int i;

         register int j;

#define DEPTH(X) max((((X)*(3-j))/3), 3)

         for (j = 0; j<4; j++)

                   for (i = 0; i<64; i+=4)

                   {

                            if (i+j > 0)

                            {

                                      disable();

                                      outportb(0x3c8, (i >> 2)+64*j);

                                      outportb(0x3c9, 0);

                                      outportb(0x3c9, 0);

                                      outportb(0x3c9, DEPTH(2*i/3));

                                      enable();

                            }

                            disable();

                            outportb(0x3c8, (i >> 2)+64*j+16);

                            outportb(0x3c9, DEPTH(i/2+10));

                            outportb(0x3c9, DEPTH(i/4+10));

                            outportb(0x3c9, DEPTH(i/6+10));

                            enable();

                            disable();

                            outportb(0x3c8, (i >> 2)+64*j+32);

                            outportb(0x3c9, DEPTH(max(63/2+10-i,0)));

                            outportb(0x3c9, DEPTH(min(64/4+10+3*i/4,63)));

                            outportb(0x3c9, DEPTH(max(63/6+10-i,0)));

                            enable();

                            disable();

                            outportb(0x3c8, (i >> 2)+64*j+48);

                            outportb(0x3c9, DEPTH(i));

                            outportb(0x3c9, DEPTH(63));

                            outportb(0x3c9, DEPTH(i));

                            enable();

                   }

}

/*

int RandPixel(int x,int y,int x1,int y1,int x2,int y2)

{

         int col;

         col = (GetRand()%200 - 100) * (abs(x-x1)+abs(y-y1)) / (GRIDSIZE/6)

                            +((_GetGrid(x1,y1)+_GetGrid(x2,y2)) >> 1);

         if (col < 1) col = 1;

         if (col > 255) col = 255;

         _PutGrid(x,y,col);

         return col;

}

*/

/*

void DoPlasma(int x1, int y1, int x2, int y2)

{

         int x,y,s,p;

         if (x2-x1 <= 1 && y2-y1 <= 1)

                   return;

         x = (x1+x2) >> 1;

         y = (y1+y2) >> 1;

         if ((p = _GetGrid(x, y1)) == 0)

                   p = RandPixel(x,y1,x1,y1,x2,y1);

         s = p;

         if ((p = _GetGrid(x2,y)) == 0)

                   p = RandPixel(x2,y,x2,y1,x2,y2);

         s += p;

         if ((p = _GetGrid(x,y2)) == 0)

                   p = RandPixel(x,y2,x1,y2,x2,y2);

         s += p;

         if ((p = _GetGrid(x1,y)) == 0)

                   p = RandPixel(x1,y,x1,y1,x1,y2);

         s += p;

         if (_GetGrid(x,y) == 0)

                   _PutGrid(x,y,s >> 2);

         DoPlasma(x1,y1,x,y);

         DoPlasma(x,y1,x2,y);

         DoPlasma(x1,y,x,y2);

         DoPlasma(x,y,x2,y2);

}

*/

void BlankGrid(int x1,int y1,int x2,int y2)

{

         register int x,y;

         for (y = y1; y <= y2; y++)

                   for (x = x1; x <= x2; x++)

                            _PutGrid(x,y,0);

}

void NewLand(int x1,int y1,int x2,int y2)

{

         unsigned av = 0;

         int val;

         int num = 0;

         if ((val = _GetGrid(x1,y1)) > 0)

         {

                   av += val;

                   num++;

         }

         if ((val = _GetGrid(x2,y1)) > 0)

         {

                   av += val;

                   num++;

         }

         if ((val = _GetGrid(x2,y2)) > 0)

         {

                   av += val;

                   num++;

         }

         if ((val = _GetGrid(x1,y2)) > 0)

         {

                   av += val;

                   num++;

         }

         if (!av || GetRand() % 32 == 0)

                   av = GetRand() % 256;

         else

                   av /= num;

         if (_GetGrid(x1,y1) == 0)

                   _PutGrid(x1,y1, av + (GetRand() % 80 -40));

         if (_GetGrid(x2,y1) == 0)

                   _PutGrid(x2,y1, av + (GetRand() % 80 -40));

         if (_GetGrid(x2,y2) == 0)

                   _PutGrid(x2,y2, av + (GetRand() % 80 -40));

         if (_GetGrid(x1,y2) == 0)

                   _PutGrid(x1,y2, av + (GetRand() % 80 -40));

         DoPlasma(x1,y1,x2,y2);

}

void Test(void)

{

         register int p;

         register int x;

         int y;

         for (y = 0,p = idx; y < GRIDSIZE; y++)

                   for (x = 0; x < GRIDSIZE; x++, p = (p+1) % MASK)

                            C_Plot(x,y,max(grid[p],63) >> 2);

         for (x = 0; x < VIEWSIZE; x++)

         {

                   C_Plot(gx+x, gy, 0);

                   C_Plot(gx+x, gy+VIEWSIZE, 0);

                   C_Plot(gx, gy+x, 0);

                   C_Plot(gx+VIEWSIZE, gy+x, 0);

         }

/*

         for (y = 0, p = gp; y < VIEWSIZE; y++, p += DIFF)

                   for (x = 0; x < VIEWSIZE; x++,p++)

                            C_Plot(gx+x,gy+y,*p >> 3);

*/

}

void ClearScr(void)

{

         register unsigned i;

         for (i = 0; i < (320U*150); i++)

                   pokeb(0xa000,i,0);

}

void check_gx(void)

{

         if (gx < 0)

         {

                   idx = (idx-DIFF/2 + MASK) % MASK;

                   gx = START-1;

                   BlankGrid(0,0, DIFF/2-1, GRIDSIZE-1);

                   NewLand(0,0,DIFF/2,GRIDSIZE/4);

                   NewLand(0,GRIDSIZE/4,DIFF/2,2*GRIDSIZE/4);

                   NewLand(0,2*GRIDSIZE/4,DIFF/2,3*GRIDSIZE/4);

                   NewLand(0,3*GRIDSIZE/4,DIFF/2,GRIDSIZE-1);

         }

         else if (gx >= DIFF)

         {

                   idx = (idx+DIFF/2) % MASK;

                   gx = START+1;

                   BlankGrid(GRIDSIZE-DIFF/2,0, GRIDSIZE-1, GRIDSIZE-1);

                   NewLand(GRIDSIZE-DIFF/2-1,0,GRIDSIZE-1,GRIDSIZE/4);

                   NewLand(GRIDSIZE-DIFF/2-1,GRIDSIZE/4,GRIDSIZE-1,

                                                                                                                 2*GRIDSIZE/4);

                   NewLand(GRIDSIZE-DIFF/2-1,2*GRIDSIZE/4,GRIDSIZE-1,

                                                                                                                 3*GRIDSIZE/4);

                   NewLand(GRIDSIZE-DIFF/2-1,3*GRIDSIZE/4,GRIDSIZE-1,

                                                                                                                 GRIDSIZE-1);

         }

}

void check_gy(void)

{

         if (gy < 0)

         {

                   idx = (idx-DIFF/2*GRIDSIZE + MASK) % MASK;

                   gy = START-1;

                   BlankGrid(0,0, GRIDSIZE-1, DIFF/2-1);

                   NewLand(0,0,GRIDSIZE/4,DIFF/2);

                   NewLand(GRIDSIZE/4,0,2*GRIDSIZE/4,DIFF/2);

                   NewLand(2*GRIDSIZE/4,0,3*GRIDSIZE/4,DIFF/2);

                   NewLand(3*GRIDSIZE/4,0,GRIDSIZE-1,DIFF/2);

         }

         else if (gy >= DIFF)

         {

                   idx = (idx+DIFF/2*GRIDSIZE) % MASK;

                   gy = START+1;

                   BlankGrid(0,GRIDSIZE-DIFF/2,GRIDSIZE-1, GRIDSIZE-1);

                   NewLand(0,GRIDSIZE-DIFF/2-1,GRIDSIZE/4,GRIDSIZE-1);

                   NewLand(GRIDSIZE/4,GRIDSIZE-DIFF/2-1,

                                                                           2*GRIDSIZE/4,GRIDSIZE-1);

                   NewLand(2*GRIDSIZE/4,GRIDSIZE-DIFF/2-1,

                                                                           3*GRIDSIZE/4, GRIDSIZE-1);

                   NewLand(3*GRIDSIZE/4,GRIDSIZE-DIFF/2-1,

                                                                           GRIDSIZE-1,GRIDSIZE-1);

         }

}

void main(void)

{

         int rollspeed = 0;

         int xspeed = 0, yspeed = 0;

         int i;

         rand_seed = (unsigned) time(NULL);

/*       rand_seed = 2; */

         for (i = 0; i<(360+90); i++)

                   sn_tbl[i]=(int)(sin((double)i / 180.0*3.14159265) * (double)(1<<SHIFT));

         NewLand(0,0,GRIDSIZE-1,GRIDSIZE-1);

         SetMode();

         SetPalette();

//       goto skip;

         for (;;)

         {

                   Test();

                   switch(getch())

                   {

                            case 27:

                                      SetTextMode();

                                      exit(0);

                            case 'e':

                                      gx--;

                                      check_gx();

                                      break;

                            case 'r':

                                      gx++;

                                      check_gx();

                                      break;

                            case 'w':

                                      gy--;

                                      check_gy();

                                      break;

                            case 's':

                                      gy++;

                                      check_gy();

                                      break;

                            case ' ':

                                      goto skip;

                   }

                   gp = CalcAddress(gx,gy);

                   while (kbhit())

                            getch();

         }

skip:

         ;

         SetMyMode();

         SetPalette();

         gp = CalcAddress(gx,gy);

//       yspeed = -1;

//       rollspeed = (rollspeed+358) % 360;

         for (;;)

         {

                   if (kbhit())

                   {

                            switch(getch())

                            {

                            case 27:

                                      SetTextMode();

                                      exit(0);

                            case 'q':

                                      cz += 50;

                                      break;

                            case 'a':

                                      cz -= 50;

                                      break;

                            case 'u':

                                      cy -= 50;

                                      break;

                            case 'j':

                                      cy += 50;

                                      break;

                            case 'Q':

                                      cpitch = (cpitch+1) % 360;

                                      break;

                            case 'A':

                                      cpitch = (cpitch+359) % 360;

                                      break;

                            case 'E':

                                      if (xspeed > -1) xspeed--;

                                      break;

                            case 'R':

                                      if (xspeed < 1) xspeed++;

                                      break;

                            case 'e':

                                      gx--;

                                      break;

                            case 'r':

                                      gx++;

                                      break;

                            case 'W':

                                      if (yspeed > -1) yspeed--;

                                      break;

                            case 'S':

                                      if (yspeed < 1) yspeed++;

                                      break;

                            case 'w':

                                      gy--;

                                      break;

                            case 's':

                                      gy++;

                                      break;

                            case 'i':

                                      roll = (roll+1) % 360;

                                      break;

                            case 'o':

                                      roll = (roll+359) % 360;

                                     break;

                            case 'I':

                                      rollspeed = (rollspeed+1) % 360;

                                      break;

                            case 'O':

                                      rollspeed = (rollspeed+359) % 360;

                                      break;

                            case ' ':

                                      rollspeed = 0;

                                      xspeed = yspeed = 0;

                                      cz = DEF_DIST;

                                      cy = DEF_HEIGHT;

                                      roll = DEF_ROLL;

                                      cpitch = DEF_PITCH;

                                      break;

                            }

                            while (kbhit())

                                      getch();

                   }

                   gy += yspeed;

                   gx += xspeed;

                   check_gx();

                   check_gy();

                   gp = CalcAddress(gx,gy);

                   roll = (roll+rollspeed) % 360;

                   roll_sine = sine(roll);

                   roll_cosine = cosine(roll);

                   pitch_sine = sine(cpitch);

                   pitch_cosine = cosine(cpitch);

                   ClearMyScreen();

                   Project();

                   SwapScreens();

         }

}

Робота з програмою

Далі наведено три скріншоти, які описують процес удару по м”ячику.

Висновки

Була розроблена комп’ютерна гра “Гольф 3D” з елементами трьохвимірної графіки на основі функцій прямого доступу до відеопам’яті в системі MS DOS. При розробці програми використовувався пакет BORLAND C++ 3.0 та бібліотека BGI.

Література.

[1] Касаткин А.И., Вальвачев А.Н. Профессиональное прогрпммирование на языке Си. Мн., 1992. 240 С.

[2] Нейбауэр А. Моя первая программа на С/С++. П., 1995. 368 С.

[3] Бруно Бабэ. Просто и ясно о Borland C++. М., 1996. 400 С.

[4] Шамас Н.К. Основы С++ и обьектно-ориентированного программирования. К., 1996. 448 С.

[5] Справочник по классам Borland C++ 4.0. К., 1994. 256 С.

[6] ObjectWindows для C++. К., 1993., 208 С.

[7] Том Сван. Программирование для Windows в Borland C++. М., 480 С.

[8] Н. Барканати. Программирование игр для Windows на Borland C++. М., 1994. 512 С.