Problem Set #1: K

Ciele

Deadline

Toto zadanie je potrebné odovzdať do polnoci (23:59:59) nedele 11.mar.2018.

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ť.

Obr. 1: Hra 2048 tak, ako ju všetci poznáme
Obr. 1: Hra 2048 tak, ako ju všetci poznáme

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.

Upozornenie

Toto makro používajte všade tam, kde pracujete s veľkosťou herného poľa. Ak totiž dôjde k zmene tejto hodnoty a vy budete vo svojom kóde priamo používať konštantu 4, váš program nebude pracovať správne!

Štruktúrovaný údajový typ struct game

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

Ú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:

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:

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:

písmeno hodnota
A 2
B 4
C 8
D 16
E 32
F 64
G 128
H 256
I 512
J 1024
K 2048

Poznámka

Keďže hra končí vtedy, keď sa na hracej ploche zobrazí písmeno 'K', je hodnota tohto písmena v uvedenj tabuľke čisto informačná.

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 |   |   |
    +---+---+---+---+                       +---+---+---+---+
    |   |   |   |   |                       |   |   |   |   |
    +---+---+---+---+                       +---+---+---+---+

Poznámka

Po vykonaní pohybu sa vo výslednom hracom poli vygenerovali náhodne aj nové dlaždice s písmenami 'A' a 'B'.

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:

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ý:

Ú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:

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.

Upozornenie

Súbor so zoznamom najlepších hráčov nemusí obsahovať vždy len 10 položiek - nemusí obsahovať žiadnu a dokonca sám nemusí existovať. Rovnako tak môže obsahovať viac položiek ako 10.

Rovnako sa nespoliehajte na to, že tento súbor nemusí obsahovať zotriedený zoznam záznamov. Nezabudnite preto vždy túto skutočnosť overiť.

Ú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:

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:

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:

Poznámka

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.

Obr. 2: Rozhranie hry K pomocou knižnice curses
Obr. 2: Rozhranie hry K pomocou knižnice curses

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 s názvom prog-2018.

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

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

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

Do súboru README, ktorý sa nachádza priamo v priečinku prog-2018/, 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).

Upozornenie

Je dôležité, aby vaše súbory zachovali uvedenú štruktúru. Ak sa niektorý zo súborov síce v repozitári nachádza, ale v inom priečinku, bude to považované za chybu a takýto projekt nebude považovaný za správny! Ak sa naopak vo vašom projekte nachádzajú súbory alebo priečinky navyše, tieto nebudú považované za chybu.

Upozornenie

Pri názvoch priečinkov, súborov a obsahu súboru README záleží na veľkosti písmen!

Kostra projektu

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

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

wget http://it4kt.cnl.sk/c/pvjc/2018/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:

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 a to konkrétne o 0300, 0600, 0900, 1200, 1500, 1800, 2100 a 2400.

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!