Stos - gra Linie

Zapoznaj się z materiałami przedstawionymi na poprzednich zajęciach koła:

 

Utwórz nowy katalog projektowy. Skopiuj do niego pliki biblioteki:

newconio.cpp  -  plik źródłowy biblioteki
newconio.h  - plik nagłówkowy dla biblioteki

Utwórz nowy projekt konsoli w Dev-C++. Do projektu dodaj plik źródłowy newconio.cpp z twojego katalogu projektowego.

 

Stos

Stos (ang. stack) jest strukturą danych, w której mamy dostęp do elementów w odwrotnej kolejności niż zostały umieszczone na stosie. Możemy go sobie wyobrazić jako stos kartek, gdzie kartki reprezentują składowane na stosie dane. Dodanie elementu umieszcza go zawsze na szczycie stosu - stos rośnie w górę. Elementy możemy pobierać kolejno tylko ze szczytu. Zatem jako pierwszy dostaniemy element ostatnio umieszczony na stosie - stąd pochodzi nazwa LIFO tej struktury danych (Last In First Out - ostatni wszedł, pierwszy wyszedł).

Stos można realizować w tablicy. Oprócz samej tablicy musimy dodatkowo posiadać zmienną, która pamięta indeks komórki będącej szczytem stosu . Jest to tzw. wskaźnik stosu (ang. stack pointer).

Umówmy się, iż wskaźnik stosu ws wskazuje komórkę tablicy, która leży tuż ponad szczytem stosu. Stos posiada dwie typowe operacje:

push - umieszczenie danych na stosie
pop  - pobranie danych ze stosu

Algorytm operacji push

Dane wejściowe:

e  -  wprowadzany element
stos[ ]  - tablica, w której jest stos
ws  - wskaźnik stosu

Dane wyjściowe:

stos[ ]  - tablica z wstawionym na stos elementem e
ws  -  zmodyfikowany wskaźnik stosu

Lista kroków

K01: stos[ws] ← e
K02: ws ← ws + 1
K03: Zakończ

 

Algorytm operacji pop

Dane wejściowe:

stos[ ]  - tablica, w której jest stos
ws  -  wskaźnik stosu

Dane wyjściowe:

e  -  element pobrany ze szczytu stosu
ws  - zmodyfikowany wskaźnik stosu

Lista kroków

K01: ws ← ws - 1
K02: e ← stos[ws]
K03: Zakończ

 

Jeśli stos zawiera dane, to wskaźnik stosu jest różny od 0. Rozmiar tablicy powinien być tak dobrany, aby stos nie wyszedł poza jej ostatni element.

 

Gra Linie

W grze uczestniczy człowiek i komputer. Każdy z graczy steruje swoją linią rysowaną po planszy. Człowiek ma linię białą, a komputer czarną. Przegrywa ten z graczy, którego linia zderzy się z dowolnym obiektem na ekranie - bandą, linią drugiego gracza lub swoją własną. Po uderzeniu linia gracza jest wymazywana począwszy od jej głowy. Strukturę stosu wykorzystuje się w tej grze do zapamiętywania pozycji, po których poruszał się gracz. Dzięki temu można całą linię wymazać z planszy z bardzo ciekawym efektem.

 

Program

// Linie
// (C)2009 Koło informatyczne w I LO w Tarnowie
// Kurs programowania w C++ dla początkujących
//--------------------------------------------

#include <iostream>
#include "newconio.h"

using namespace std;

// Zmienne globalne
//-----------------
int  stos_bk[2000], stos_bw[2000];    // stosy kolumn i wierszy białego gracza
int  stos_ck[2000], stos_cw[2000];    // stosy kolumn i wierszy czarnego gracza
int  wsb, wsc;                        // wskaźniki stosów białego i czarnego
int  pbk, pbw, pck, pcw;              // pozycje graczy - kolumna, wiersz
int  kierunek_b, kierunek_c, droga_c; // kierunki ruchu
int  punkty_b, punkty_c;
bool przegral_b, przegral_c, gra_w_toku;

// Start gry
//----------
void start()
{
  _cinit();

  srand((unsigned)time(NULL));

  fullscreen(true); cursoroff(); textattr(0x1f); clrscr();
  fillframe(FRAME_SINGLE,0xe9,20,19,59,29);
  
  textattr(0xe2);
  center(21,_pl("(C)2009 I Liceum Ogólnokształcące"));
  center(22,_pl("im. Kazimierza Brodzińskiego"));
  center(23,"w Tarnowie");
  textattr(0xe0);
  center(25,_pl("KOŁO NAUKOWE INFORMATYKI"));
  textattr(0xe4);
  center(27,"G-R-A   L-I-N-I-E");

  fillrectattr(0,0,49,79,49);
  textattr(0x0f);
  center(49,_pl("Naciśnij dowolny klawisz, aby rozpocząć grę..."));

  while(!getch());
}

// Sprawdza, czy gracz chce ponownie zagrać
//-----------------------------------------
bool jeszcze_raz()
{
  textattr(0x80); center(49,"Jeszcze raz? (T = TAK)");
  
  char klawisz;
  
  while(!(klawisz = getch()));
  
  return (klawisz == 'T') || (klawisz == 't');
}

// Tworzy planszę gry
//-------------------
void plansza()
{
  textattr(0x80); clrscr();

  // narożniki bandy

  putxy(218,0x80,1,1);  putxy(192,0x80,1,48);
  putxy(191,0x8f,78,1); putxy(217,0x8f,78,48);
  
  // czarna połowa bandy

  fillrect(196,0x80,2,1,39,1);
  fillrect(196,0x80,2,48,39,48);
  fillrect(179,0x80,1,2,1,47);
  
  // biała połowa bandy

  fillrect(196,0x8f,40,1,77,1);
  fillrect(196,0x8f,40,48,77,48);
  fillrect(179,0x8f,78,2,78,47);
}

// Wyświetla punkty graczy
//------------------------
void punkty()
{
  textattr(0x80); gotoxy(15,0); cout << "CZARNE : " << punkty_c;
  textattr(0x8f); gotoxy(55,0); cout << _pl("BIAŁE : ") << punkty_b;     
}

// Obsługuje klawiaturę w grze
//----------------------------
void klawiatura()
{
  delay(1);

// Jeśli jest wciśnięty jakiś klawisz, odczytujemy go
// i zgodnie z jego kodem ustawiamy kierunek ruchu linii
// białego gracza lub w przypadku klawisza ESC kończymy
// rozgrywkę
  
  if(kbhit())
  {
    int klawisz;
    
    while(!(klawisz = getch()));
    
    switch(klawisz)
    {
      case 72: kierunek_b = 0; break;     // w górę
      case 77: kierunek_b = 1; break;     // w prawo
      case 80: kierunek_b = 2; break;     // w dół
      case 75: kierunek_b = 3; break;     // w lewo
      case 27: gra_w_toku = false; break; // klawisz ESC
    }           
  }     
}

// Obsługuje ruchy białego gracza
//-------------------------------
void ruch_b()
{
  // zapisujemy na stosie pozycję białego gracza - kolumna i wiersz
  
  stos_bk[wsb] = pbk; stos_bw[wsb] = pbw; wsb++;
  
  // na bieżącej pozycji umieszczamy biały kwadrat
  
  putxy(219,0xf,pbk,pbw);
  
  // w zależności od kierunku kreślenia linii przesuwamy pozycję
  
  switch(kierunek_b)
  {
    case 0: pbw--; break;
    case 1: pbk++; break;
    case 2: pbw++; break;
    case 3: pbk--; break;
  }

  // jeśli na nowej pozycji jest jakaś przeszkoda, to gracz
  // biały kończy grę.
  
  if(getchxy(pbk,pbw) != ' ')
  {
    gra_w_toku = false;  przegral_b = true; punkty_c++;  punkty();
  }
}

// Obsługuje ruchy komputera
//--------------------------
void ruch_c()
{
  // zapamiętujemy na stosie pozycję gracza czarnego
  
  stos_ck[wsc] = pck; stos_cw[wsc] = pcw; wsc++;
  
  // na zapamiętanej pozycji umieszczamy czarny kwadrat
  
  putxy(219,0x80,pck,pcw);
  
  // jeśli komputer przeszedł w zadanym kierunku swoją drogę
  // to losujemy nową drogę oraz nowy kierunek
  
  if(!(--droga_c))
  {
    droga_c    = 5 + rand() % 5;
    kierunek_c = rand() % 4;                
  }
  
  // zapamiętujemy bieżące współrzędne gracza czarnego
  // w zmiennych pomocniczych
    
  int ppck = pck;
  int ppcw = pcw;
  
  // wykonujemy próbny ruch w bieżącym kierunku
  // ruch jest wykonywany na zmiennych pomocniczych
  
  switch(kierunek_c)
  {
    case 0: ppcw--; break;
    case 1: ppck++; break;
    case 2: ppcw++; break;
    case 3: ppck--; break;
  }
  
  // jeśli w nowym miejscu nie ma przeszkody, to
  // wyliczone współrzędne gracza czarnego przepisujemy
  // do zmiennych podstawowych i wychodzimy z funkcji
  
  if(getchxy(ppck,ppcw) == ' ')
  {
    pck = ppck; pcw = ppcw;

    return;                      
  }
  
  // w tym miejscu jesteśmy w przypadku, gdy na nowej pozycji
  // gracza czarnego jest jakaś przeszkoda. W takim przypadku
  // odczytamy z ekranu pozycje wokół bieżącej pozycji i jeśli
  // będą wolne, zapamiętamy ich kierunki w tablicy kierunki[]
  // następnie tablicę pomieszamy i przeszukamy, czy zawiera
  // jakiś kierunek. Jeśli tak, ustawimy go za bieżący, zmodyfikujemy
  // współrzędne gracza czarnego i zakończymy funkcję.
  // Jeśli w tablicy nie będzie wolnego kierunku, to gracz
  // czarny przegrywa.
  
  int kierunki[4];
  
  // przeszukujemy pozycje szukając wolnych kierunków
  
  for(int i = 0; i < 4; i++)
  {
    // na początku zaznaczamy brak kierunku
    
    kierunki[i] = -1;
    
    // szukamy dookoła
    
    if(getchxy(pck + (i == 1 ? 1 :(i == 3) ? -1 : 0), pcw + (i == 2 ? 1 : (i == 0 ? -1 : 0))) == ' ')
      kierunki[i] = i;
  }

  // mieszamy tablicę
  
  for(int i = 0; i < 20; i++) swap(kierunki[rand() % 4],kierunki[rand() % 4]);        

  // szukamy wolnego kierunku

  for(int i = 0; i < 4; i++)
    if(kierunki[i] != -1)
    {
      
      // kierunek znaleziony
      
      kierunek_c = kierunki[i];
      
      // wykonujemy ruch w tym kierunku
      
      switch(kierunek_c)
      {
        case 0: pcw--; break;
        case 1: pck++; break;
        case 2: pcw++; break;
        case 3: pck--; break;                
      }

      return;
    }

  // brak wolnego kierunku, gracz czarny przegrał
  
  gra_w_toku = false;  przegral_c = true; punkty_b++;  punkty();
}

// Kasuje z ekranu gracza przegranego
//-----------------------------------
void przegrana()
{  
  while((przegral_b && wsb) || (przegral_c && wsc))
  {
    delay(10);
    if(wsb && przegral_b)
    {
      wsb--; putxy('.',0x8f,stos_bk[wsb],stos_bw[wsb]);       
    }
    if(wsc && przegral_c)
    {
      wsc--; putxy('.',0x80,stos_ck[wsc],stos_cw[wsc]);       
    }
  }

// czyścimy bufor klawiatury

  while(kbhit())
  {
    delay(100); while(!getch());
  }
}
    
// Główna część programu
//----------------------
main()
{
  start();
  
  do
  {
    plansza();
    punkty();

    pbk = 60; pbw = 24;
    pck = 20; pcw = 25;

    wsb = wsc = 0;
 
    kierunek_b = 3;           // biały rozpoczyna zawsze w lewo
    kierunek_c = rand() % 4;
    droga_c    = 5 + rand() % 5;

    przegral_b = przegral_c = false;

    gra_w_toku = true;

    int czas = 1;
    
    do
    {
      putxy('*',0x8f,pbk,pbw);
      putxy('*',0x80,pck,pcw);

      klawiatura();

      if(!(--czas))
      {
        czas = 5 + (20 * 2000) / (2000 - wsb);
 
        ruch_b();
        ruch_c();
      }

    } while(gra_w_toku);

    przegrana();
 
  } while(jeszcze_raz());
  
  fullscreen(false); cursoron(); textattr(7); clrscr(); 
}

 

Gra z komputerem nie jest specjalnie ciekawa - łatwo go pokonać, wystarczy mu nie przeszkadzać, a sam się załatwi. Dlatego ambitnym proponuję rozbudowę algorytmu gry, która zwiększy inteligencję komputera lub taką modyfikację, aby w grę mogło grać dwóch ludzi.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.