Problem Set #2: K

Ciele

• Pracovať so štruktúrovanými typmi.
• Pracovať s dvojrozmerným poľom.
• Pracovať so vstupno-výstupnými parametrami funkcií.

Hra K

Poznáte hru 2048? Aj napriek tomu, že túto hru naprogramoval v marci 2014 v priebehu jedného víkendu 19 ročný taliansky web developer Gabriele Cirulli, stala sa veľmi rýchlo populárnou a obľúbenou. Ak vás teda ošiaľ s menom 2048 obišiel, neváhajte a túto hru si zahrajte. Toto zadanie má totiž k hre 2048 bližšie, ako sa na prvý pohľad môže zdať.

Hra K vychádza z hry 2048 a podobne, ako aj hra 2048 sa hrá na poli o rozmeroch 4x4. Jediným rozdielom medzi týmito hrami je skutočnosť, že v hre K budete miesto čísel na hracích kameňoch používať písmená. Hráč vie tieto kamene posúvať do štyroch strán (v pôvodnej hre pomocou kurzorových kláves, v našom prevedení pomocou načítavania znakov, resp. reťazcov zo štandardného vstupu).

Každý nový ťah hry sa začína vygenerovaním náhodnej dlaždice s písmenom 'A' alebo 'B'. Pri pohybe do strán sa dlaždice presunú tak ďaleko do danej strany, ako je to možné. Zastaviť ich môže buď iná dlaždica alebo okraj hracieho poľa. Ak sa pri presúvaní stretnú (dotknú) dve dlaždice s rovnakým písmenom, spoja sa do nasledujúceho písmena v poradí abecedy. Napr. ak sa pri presúvaní spoja dve písmená 'C', vznikne ich spojením jedno písmeno 'D'. Výsledná dlaždica, ktorá vznikla spojením dvoch iných dlaždíc, už však nemôže byť v danom ťahu spojená so žiadnou inou dlaždicou s rovnakým písmenom.

Hráč dostáva za svoju hru body. Jeho skóre sa aktualizuje zakaždým, ak pri ťahu dôjde k spojeniu dvoch alebo viacerých dlaždíc. Spôsob výpočtu skóre je opísaný v samostatnej časti tohto textu.

Hra sa končí vtedy, keď sa na hracej ploche objaví dlaždica s písmenom 'K' (odtiaľ pramení aj názov tejto hry).

Vašou úlohou bude naprogramovať hru K v jazyku C implementovaním týchto troch modulov:

1. Modul samotnej hry K.
2. Modul reprezentujúci Hall of Fame (sieň slávy najlepších hráčov).
3. Modul UI.

Tieto moduly obsahujú všetky potrebné funkcie na implementáciu hry K. V rámci modulu si samozrejme môžete vytvoriť aj ďalšie pomocné funkcie. Nesmiete však nijako meniť a upravovať hlavičkové súbory oboch modulov!

Modul K

Tento modul predstavuje hlavný modul hry, v ktorom sa budú nachádzať všetky funkcie a údajové typy potrebné pre implementáciu samotnej hry K. Konkrétne bude obsahovať zadefinovaný štruktúrovaný údajový typ struct game a funkcie update(), is_move_possible(), is_game_won() a preddefinovanú funkciu add_random_tile() na pridanie náhodnej dlaždice s písmenom 'A' alebo 'B' do hracieho poľa.

Makro SIZE

Makro SIZE obsahuje veľkosť herného poľa, čo je pre hru K hodnota 4.

Štruktúrovaný údajový typ struct game

Tento údajový typ reprezentuje samotnú hru. Význam jednotlivých položiek je nasledovný:

• board - dvojrozmerné pole reprezentujúce hraciu plochu a aktuálny stav hry, a
• score - aktuálny počet bodov (skóre), ktoré hráč nahral počas hry.

Úloha #1: Je hra vyhratá?

Ako bolo uvedené v pravidlách hry, hra je považovaná za vyhratú vtedy, keď sa na hracej ploche objaví písmeno 'K'. Vašou úlohou je vytvoriť funkciu bool is_game_won(const struct game game), ktorá tento stav overí.

Funkcia má tento parameter:

• const struct game game - štruktúrovaný typ reprezentujúci stav aktuálnej hry

Funkcia vráti hodnotu true, ak sa na hracej ploche už písmeno 'K' nachádza. V opačnom prípade vráti funkcia hodnotu false.

Príklady hracieho poľa, kedy je hra vyhratá a kedy nie, sú ilustrované na nasledujúcich fragmentoch kódu.

// game is won
struct game game = {
    .board = {
        {'A', 'B', 'C', 'D'},
        {'E', 'F', 'G', 'H'},
        {'I', 'J', 'K', 'A'},
        {'B', 'C', 'D', 'E'}
    },
    .score = 0
};

printf("is won: %d\n", is_game_won(game));
// stdout: 1

// game is not won
struct game game = {
    .board = {
        {'A', ' ', ' ', ' '},
        {' ', ' ', ' ', ' '},
        {' ', ' ', ' ', 'A'},
        {'B', ' ', ' ', ' '}
    },
    .score = 0
};

printf("is won: %d\n", is_game_won(game));
// stdout: 0

Úloha #2: Je možné vykonať ďalší ťah?

Hra sa bude hrať dovtedy, pokiaľ bude možné vykonať ďalší ťah. To znamená, že sa na hracom poli bude nachádzať prázdne miesto alebo sa budú vedľa seba nachádzať dve dlaždice s rovnakým písmenom. Vašou úlohou je overiť, či je alebo nie je možné vykonať ďalší ťah. Preto vytvorte funkciu bool is_move_possible(const struct game game), ktorá túto úlohu vyrieši.

Funkcia má tento parameter:

• const struct game game - štruktúrovaný typ reprezentujúci stav aktuálnej hry

Funkcia vráti hodnotu true, ak je možné v hre vykonať ďalší ťah. V opačnom prípade vráti funkcia hodnotu false.

Túto funkciu je možné použiť na overenie, či je možné vykonať v hre ďalší ťah. Ak ďalší ťah už vykonať nie je možné, hra sa pre hráča skončila.

Príklady hracieho poľa, kedy je v hre možné vykonať ďalší ťah alebo už nie je možné vykonať žiadny ťah, sú ilustrované na nasledujúcich fragmentoch kódu.

// another move is possible
struct game game = {
    .board = {
        {'A', 'A', 'C', 'D'},
        {'A', 'F', 'G', 'H'},
        {'I', 'J', 'J', 'A'},
        {'B', 'C', 'D', 'E'}
    },
    .score = 0
};

printf("is move possible: %d\n", is_move_possible(game));
// stdout: 1

// another move is not possible
struct game game = {
    .board = {
        {'A', 'B', 'C', 'D'},
        {'E', 'F', 'G', 'H'},
        {'I', 'J', 'K', 'A'},
        {'B', 'C', 'D', 'E'}
    },
    .score = 0
};

printf("is move possible: %d\n", is_move_possible(game));
// stdout: 0

Úloha #3: Zmena stavu hry

Stav hry sa zmení zakaždým, keď hráč vykoná pohyb do jednej zo štyroch strán - hore, dole, vľavo a vpravo. Ak je možné pohnúť sa, všetky dlaždice sa presunú v danom smere tak ďaleko, ako je to možné. Zastaviť ich môže buď iná dlaždica alebo okraj hracieho poľa. Ak sa pri presúvaní stretnú (dotknú) dve dlaždice s rovnakým písmenom, spoja sa do nasledujúceho písmena v poradí abecedy (Napr. zo spojenia dvoch písmen 'H' vznikne jedno písmeno 'I').

Možnosti spojenia dvoch a viacerých dlaždíc v jednom riadku sú ilustrované na nasledujúcich príkladoch. Rovnaké správanie je však možné aplikovať pre všetky smery.

+---+---+---+---+                   +---+---+---+---+
| A |   | A |   |   (smer vpravo)   |   |   |   | B |
+---+---+---+---+                   +---+---+---+---+

+---+---+---+---+                   +---+---+---+---+
| A |   | A | A |   (smer vpravo)   |   |   | A | B |
+---+---+---+---+                   +---+---+---+---+

+---+---+---+---+                   +---+---+---+---+
| A | A | A | A |   (smer vpravo)   |   |   | B | B |
+---+---+---+---+                   +---+---+---+---+

+---+---+---+---+                   +---+---+---+---+
| B | A | A |   |   (smer vpravo)   |   |   | B | B |
+---+---+---+---+                   +---+---+---+---+

V prípade, že pri presune došlo k spojeniu dvoch dlaždíc, dôjde aj k aktualizácii hráčovho skóre. Hodnota, ktorá sa pripočíta ku celkovému skóre bude daná súčtom hodnoty týchto dvoch písmen (resp. dvojnásobok hodnoty písmena). Hodnoty jednotlivých písmen sú zobrazené v nasledujúcej tabuľke:

Príklad výpočtu skóre ilustruje nasledovná situácia:

    score: 0                                score: 8
    +---+---+---+---+                       +---+---+---+---+
    | A |   |   |   |                       | B |   |   |   |
    +---+---+---+---+                       +---+---+---+---+
    | A |   |   |   |                       | B |   |   | B |
    +---+---+---+---+      (smer hore)      +---+---+---+---+
    | A |   |   |   |                       |   |   |   |   |
    +---+---+---+---+                       +---+---+---+---+
    | A |   |   |   |                       |   |   |   |   |
    +---+---+---+---+                       +---+---+---+---+

    score: 8                                score: 16
    +---+---+---+---+                       +---+---+---+---+
    | B |   |   |   |                       |   |   |   | B |
    +---+---+---+---+                       +---+---+---+---+
    | B |   |   | B |                       |   |   |   | C |
    +---+---+---+---+      (smer vpravo)    +---+---+---+---+
    |   |   |   |   |                       |   | A |   |   |
    +---+---+---+---+                       +---+---+---+---+
    |   |   |   |   |                       |   |   |   |   |
    +---+---+---+---+                       +---+---+---+---+

Vašou úlohou je vytvoriť funkciu bool update(struct game *game, int dy, int dx), ktorá pohyb daným smerom zabezpečí.

Funkcia má tieto parametre:

• struct game *game - referencia na štruktúrovaný typ reprezentujúci stav aktuálnej hry
• int dy - smer v osi Y, ktorý môže mať len jednu z troch hodnôt: -1, ak sa jedná o smer hore, 0, ak sa nejedná o zmenu smeru v y-ovej osi a 1, ak sa jedná o smer dolu.
• int dx - smer v osi X, ktorý môže mať len jednu z troch hodnôt: -1, ak sa jedná o smer vľavo, 0, ak sa nejedná o zmenu smeru v x-ovej osi a 1, ak sa jedná o smer vpravo.

Funkcia vráti hodnotu true, ak sa stav hry zmenil. V opačnom prípade vráti funkcia hodnotu false.

Funkcia však vráti hodnotu false aj v prípade, ak bola funkcia nesprávne použitá. To je v prípade, ak je funkcia zavolaná spôsobom, kedy sa má vykonať pohyb do viac ako jednej strany súčasne alebo naopak do žiadnej strany.

Príklady použitia funkcie update() sú uvedené v nasledujúcich fragmentoch kódu.

// wrong call
bool result = update(&game, 1, 1);
// result = false

// move right
struct game game = {
    .board = {
        {'A', ' ', ' ', ' '},
        {'B', ' ', ' ', 'B'},
        {'C', 'C', 'C', ' '},
        {'D', 'D', 'D', 'D'}
    },
    .score = 0
};

bool result = update(&game, 0, 1);
/*
game = {
    .board = {
        {' ', ' ', ' ', 'A'},
        {' ', ' ', ' ', 'C'},
        {' ', ' ', 'C', 'D'},
        {' ', ' ', 'E', 'E'}
    },
    .score = 88
};
result = true;
*/

// can't move left
struct game game = {
    .board = {
        {'A', 'B', 'C', 'D'},
        {'A', 'B', 'C', 'D'},
        {'A', 'B', 'C', 'D'},
        {'A', 'B', 'C', 'D'}
    },
    .score = 1234
};

bool result = update(&game, 0, -1);
/*
game = {
    .board = {
        {'A', 'B', 'C', 'D'},
        {'A', 'B', 'C', 'D'},
        {'A', 'B', 'C', 'D'},
        {'A', 'B', 'C', 'D'}
    },
    .score = 1234
};
result = false;
*/

Modul hof

Súčasťou hry bude v tomto prípade aj tzv. sieň slávy (z angl. Hall of Fame, skrátene hof). Bude reprezentovaná zoznamom desiatich najlepších hráčov hry. Tento zoznam sa bude nachádzať v samostatnom súbore, ktorý v prípade potreby nahráte a po jeho aktualizácii ho zasa uložíte späť na disk.

Tento modul bude obsahovať zadefinovaný štruktúrovaný údajový typ struct player, funkciu add_player() a funkcie save() a load().

Údajový typ struct player

Tento údajový typ reprezentuje záznam v tabuľke Hall of Fame. Význam jednotlivých položiek je nasledovný:

• name - meno hráča, a
• score - počet bodov (skóre), ktoré hráč dosiahol.

Úloha #4: Nahratie HOF z disku

Funkcia load() zabezpečí nahratie zoznamu zo súboru a jeho uloženie do výstupného parametra funkcie list.

Funkcia má tieto parametre:

• struct player list[] - Referencia na aktuálny zoznam desiatky najlepších hráčov. Zoznam je reprezentovaný ako jednorozmerné pole, ktoré je dlhé práve 10 položiek typu struct player.

Funkcia vráti počet načítaných položiek, pričom max. počet, ktorý zo súboru načíta, je práve 10. V prípade, že sa funkcii súbor nepodarí načítať, vráti hodnotu -1.

Sieň slávy je na disku reprezentovaná formou textového súboru, v ktorom každý riadok má nasledovnú štruktúru:

NAME SCORE

kde NAME reprezentuje meno hráča, ktoré pozostáva z postupnosti znakov bez znaku medzera; a SCORE je celé číslo reprezentujúce dosiahnuté skóre hráča. Táto dvojica je od seba oddelená znakom medzera.

Úloha #5: Uloženie HOF na disk

Funkcia save() zabezpečí uloženie zoznamu do súboru. Zoznam funkcia uložení usporiadaný od najlepšieho hráča po najhoršieho. O úspešnosti, resp. neúspešnosti tejto operácie funkcia informuje návratovou hodnotou typu bool.

Funkcia má tieto parametre:

• struct player list[] - Referencia na aktuálny zoznam desiatky najlepších hráčov. Zoznam je reprezentovaný ako jednorozmerné pole, ktoré je dlhé práve 10 položiek typu struct player.
• int size - Skutočná veľkosť zoznamu siene slávy, ktorý je dlhý max. 10 položiek. Zoznam môže byt kratší v prípade, ak vašu hru začínate s prázdnou sieňou slávy.

Po úspešnom uložení aktuálnej siene slávy na disk vráti funkcia hodnotu true. V opačnom prípade vráti hodnotu false.

Úloha #6: Aktualizácia Hall of Fame

Po dohratí hry nasleduje kontrola toho, či dosiahnuté skóre umožní hráčovi zápis do siene slávy. Ak áno, jeho meno bude zaradené na správne miesto v desiatke najlepších hráčov v poradí od najlepšieho hráča (hráč, ktorý získal najviac bodov). Vašou úlohou je teda vytvoriť funkciu bool add_player(struct player list[], int* size, const struct player player), ktorá v prípade, že hráč do siene slávy patrí, ho zaradí na správne miesto.

Funkcia má tieto parametre:

• struct player list[] - Referencia na aktuálny zoznam desiatky najlepších hráčov. Zoznam je reprezentovaný ako jednorozmerné pole, ktoré je dlhé práve 10 položiek typu struct player.
• int* size - Skutočná veľkosť zoznamu siene slávy, ktorý je dlhý max. 10 položiek. Zoznam môže byt kratší v prípade, ak vašu hru začínate s prázdnou sieňou slávy.
• const struct player player - Hráč, ktorý má byť vložený do siene slávy.

Funkcia vráti hodnotu true v prípade, že hráč sa do siene slávy dostal alebo hodnotu false, ak sa do nej nedostal. Okrem toho v prípade úspešného zápisu aktualizuje zoznam, na ktorý ukazuje parameter list a rovnako tak v prípade potreby aktualizuje aj celkovú veľkosť zoznamu, ktorá je uložená v parametri size.

V prípade, ak hráč dosiahol rovnaký počet bodov ako už existujúci záznam v sieni slávy, nový záznam sa dostane v poradí pred už existujúci záznam. Ak by sa takýto už existujúci záznam nachádzal na poslednom 10. mieste v sieni slávy, po aktualizácii skóre od nového hráča bude tento (starý záznam) z tabuľky vyradený.

Príklady použitia funkcie add_player() sú ilustrované na nasledovných príkladoch:

// case 1: the list is empty
struct player list[10];
int size = 0;
struct player player = {
    .name = "John",
    .score = 100
};

bool result = add_player(list, &size, player);

/* result = true, size = 1
list:
John 100
*/

// case 2: the list contains 10 entries
/*
file: score
manager 5000
manager 4000
manager 3000
manager 2000
manager 1000
manager 500
manager 400
manager 300
manager 200
manager 100
*/

struct player list[10];
struct player player = {
    .name = "john",
    .score = 400
};
int size = load(list);
bool result = add_player(list, &size, player);

/* result = true, size = 10
list:
manager 5000
manager 4000
manager 3000
manager 2000
manager 1000
manager 500
john 400
manager 400
manager 300
manager 200
*/

// case 3: player has same score as last player in HOF
/*
file: score
manager 5000
manager 4000
manager 3000
manager 2000
manager 1000
manager 500
manager 400
manager 300
manager 200
manager 100
*/

struct player list[10];
struct player player = {
    .name = "john",
    .score = 100
};
int size = load(list);
bool result = add_player(list, &size, player);

/* result = true, size = 10
list:
manager 5000
manager 4000
manager 3000
manager 2000
manager 1000
manager 500
manager 400
manager 300
manager 200
john 100
*/

Modul UI

Tento modul obsahuje funkciu render(), ktorá slúži na vykreslenie stavu hry na obrazovku. Funkcia sa nachádza v samostatnom module preto, aby ostatné dva moduly neboli nijako závislé na grafickej reprezentácii hry. Tým pádom môžete pre vykresľovanie použiť ľubovoľnú knižnicu, ako napríklad curses, SDL, ale kľudne môžete zostať aj pri štandardnom vstupe a výstupe.

Úloha #1: Vykreslenie stavu hry

Funkcia render() slúži na vykreslenie hracieho poľa hráča. Podoba vykreslenia nie je definovaná a taktiež nebude hodnotená v testoch. S grafickou stránkou hry sa teda môžete pohrať sami.

Funkcia má jeden paremeter:

• struct game *game - referencia na štruktúrovaný typ reprezentujúci stav aktuálnej hry

Upozornenie

V súbore ui.c sa nachádza ukážková implementácia funkcie, ktorá používa knižnicu curses. Výsledok jej použitia vidíte na obrázku nižšie.

Ak použijete knižnicu curses, nezabudnite pri kompilácii modulu UI použiť prepínač -lcurses.

Odovzdávanie projektu

Zadanie sa odovzdáva prostredníctvom systému na správu verzií Git na serveri git.kpi.fei.tuke.sk. Riešenie tejto úlohy odovzdáte ako súčasť vášho projektu.

Ak vytvárate projekt prvýkrát, urobte tak na tejto stránke. Návod na to, ako si inicializovať prostredie a ako pracovať s GitLab-om, nájdete na stránkach predmetu ZAP.

Štruktúra vášho projektu bude vyzerať nasledovne:

.
├── ps2/
│   ├── k.c
│   ├── k.h
│   ├── hof.c
│   ├── hof.h
│   ├── main.c
│   ├── Makefile
│   ├── ui.c
│   └── ui.h
└── README

kde význam súborov v priečinku ps2/ je nasledovný:

• k.c, k.h - Zdrojový kód a hlavičkový súbor modulu pre hru K.
• hof.c, hof.h - Zdrojový kód a hlavičkový súbor modulu pre operácie nad Hall of Fame.
• ui.c, ui.h - Zdrojový kód a hlavičkový súbor modulu pre vykreslovanie stavu hry na obrazovku.
• main.c - Zdrojový kód obsahujúci funkciu main().
• Makefile - Makefile súbor bude obsahovať minimálne tieto ciele:
  • hof.o pre vygenerovanie modulu hof,
  • k.o pre vygenerovanie modulu k,
  • ui.o - pre vygenerovanie modulu ui,
  • all pre vygenerovanie spustiteľného programu s menom game, a
  • clean pre odstránenie priebežne vytvorených objektových a spustiteľných súborov.

Do súboru README, ktorý sa nachádza priamo v koreňovom priečinku vášho projektu, uveďte označenie vašej skupiny, ktorú navštevujete na cvičeniach (zistíte si ju na rozvrhovom portáli maisu) v tvare:

GROUP : X1

Ak ste opakujúci študent, uveďte v README skupinu v tvare:

GROUP : O<P>

kde <P> nahradíte písmenom paralelky, ktorá podľa rozvrhu zodpovedá vášmu študijnému programu (napr. A pre informatikov).

Kostra projektu

Z nasledujúceho odkazu si stiahnite súbor k.zip, ktorý obsahuje kostru projektu. Tento balíček obsahuje nasledujúce súbory:

• k.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre hru K.
• k.c - súbor obsahuje pripravenú funkciu add_random_tile().
• hof.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre Hall of Fame.
• ui.h - hlavičkový súbor, v ktorom sa nachádzajú deklarácie všetkých požadovaných funkcií pre použivateľské rozhranie hry.
• ui.c - súbor obsahuje ukážkovú implementáciu funkcie render().
• score - ukážkový súbor s hodnotením

V prostredí OS Linux môžete pre stiahnutie použiť príkaz wget v tvare:

wget https://kurzy.kpi.fei.tuke.sk/pvjc/2024/download/k.zip

Hodnotenie a testovanie

V rámci tohto zadania nie je predpísaná grafická podoba výstupu ani dialóg medzi používateľom a počítačom. V tom máte voľnú ruku, aby ste sa mohli realizovať ako herní vývojári. Ak sa chcete pochváliť, vytvorte vo svojom projekte priečinok screenshots/, kde môžete umiestniť obrázky z vašej hry (hracia plocha a hall of fame).

Vaše hodnotenie sa bude odvíjať od výsledku testov, ktorými vaše zadanie úspešne prejde. Overovať sa bude:

• Štruktúra vášho projektu (či sa v ňom nachádzajú všetky potrebné súbory).
• Statická analýza vášho kódu pomocou nástroja cppcheck.
• Kontrola únikov v pamäti pomocou nástroja valgrind
• Prítomnosť globálnych premenných vo vašom kóde.
• Funkčnosť vašej implementácie.

Váš kód sa bude prekladať prekladačom gcc s nasledovnými prepínačmi:

$ gcc -std=c11 -Werror -Wall -Wconversion -lm

Testovanie vašich riešení sa bude vykonávať automaticky každé 3 hodiny.

Vaše riešenia opäť prejdú kontrolou originality. Preto sa pri práci na vašom zadaní správajte podľa pravidiel etického kódexu! V prípade, že odovzdáte zadanie, ktoré nie je vaše, budete vylúčení z predmetu!