Pán hadov

Vytvorte implementáciu klasickej hry Snakes, ktorú poznáte zo starých mobilných telefónov.

V hre sa má had pohybovať po hracej ploche a jesť náhodne rozmiestnené odmeny.

Had je tvorený viacerými článkami nasledujúcimi za sebou. Pohyb prebieha tak, že vo zvolenom smere pribudne nový článok a odbudne posledný článok. V prípade, že had práve zjedol odmenu, tak vymazanie posledného článku vynecháme a had je o jedno políčko dlhší.

Ak sa nová pozícia hada nachádza na hadovi alebo mimo hracej plohy tak sa hra končí.

Príprava

Stiahnite si kostru zadania a oboznámte sa so zdrojovými kódmi. Rozbaľte archív do priečinka cv9 do Vašom pracovnom adresári:

curl -O --insecure  https://git.kemt.fei.tuke.sk/dano/snake/archive/master.zip
unzip master.zip
mv snake ~/pvjc24/cv9
cd ~/pvjc24/cv9
ls -l

Projekt sa skladá z viacerých súborov, ich stručný opis nájdete v súbore README.md.

Vašou úlohou bude modifikovať súbor snake.c tak aby boli splnené automatické testy . Nájdete tam niekoľko funkcií, ktoré máte doprogramovať podľa pokynov v súbore snake.h.

Najprv vytvorte spojkový zoznam (funkcie add_snake, remove_snake, free_snake a is_snake).

Spojkový zoznam

Pre reprezentáciu hada je najprirodzenejšie použiť spojkový zoznam.

Had je tvorený viacerými za sebou idúcimi článkami typu struct snake, kde každý článok má svoju pozíciu x,y. Pohyb hada sa dá implementovať pridaním nového prvého článku a zmazaním posledného článku.

Budeme potrebovať tieto operácie:

• Pridanie nového prvku na začiatok (funkcia add_snake).
• Odobratie prvku z konca spojkového zoznamu(funkcia remove_snake).
• Zistenie, či prvok patrí spojkovému zoznamu (funkcia is_snake).
• Uvoľnenie spojkového zoznamu (funkcia free_snake).

Definíciu štruktúry hada a predpisy pre funkcie pre prácu so spojkovým zoznamom nájdete v súbore snake.h.

Pridanie nového prvku na začiatok

Funkcia by mala dynamicky alokovať pamäť pre novú štruktúru typu struct snake. Funkcia calloc automaticky nastaví všetky členy štruktúry na nulu. Pomocu operátora šípka nastavte premenné x a y.

struct snake* head = calloc(1,sizeof(struct snake));
head->x = x;
head->y = y;

Pridanie nového prvku na začiatok znamená pripojiť na koniec nového prvku starý spojkový zoznam.

head->next = snake;

Prechádzanie prvkov hada

Pre zistenie, či je zadaná súradnica súčasťou hada alebo nie musíme prejsť všetky prvky hada.

Na prechádzanie prvkov použijeme pomocný smerník this ktorý bude ukazovať na aktuálny prvok hada.

Je jasné, že prechádzanie má zmysel iba v prípade, že spojkový zoznam má aspoň jeden člen.

struct snake* this = head;

Pomocný smerník môžeme posúvať podľa potreby na ďalší prvok:

this = this->next;

V prípade, že je smerník this nulový tak program spadne. tomu by sme mali zabrániť vhodnou ukončovacou podmienkou.

Napr. ak chceme vyhľadať posledný prvok:

while (this->next != NULL){
    this = this->next;
}

Keď cyklus zbehne, tak smerník this bude ukazovať na posledný prvok.

Alebo keď chceme prejsť všetky prvky:

this = head;
while (this != NULL){
    // Niečo môžme s prvkom this spraviť
    this= this->next;
}

To isté sa dá dokázať aj pomocou cyklu typu for:

for (struct snake* this = head; this != NULL; this=this->next){
    // Niečo môžme s prvkom this spraviť
}

Zrušenie spojkového zoznamu

Každá dynamická alokácia pomocu malloc alebo calloc musí byť vo vhodnej chvíli zrušená pomocou volania funkcie free.

Ak už spojkový zoznam nebudeme potrebovať, tak je potrebné ho zrušiť.

Môžeme to urobiť iteratívne pomocou cyklu, ktorý prejde a zruší všetky prvku. Musíme ale dávať pozor aby sme si "nepodpíli konár" a nezrušili aj smerníkovú premennú next.

struct snake* next = this->next;
free(this);
// this->next je teraz neplatné
this = next;

Dá sa to spraviť aj rekurzívne:

1. Ak je zoznam prázdny, neurob nič.
2. Uvoľni koniec hada. (rekurzívne volanie so smenrníkom next).
3. Uvoľni aktuálny prvok hada.

Odobranie posledného prvku

Funkcia pre odobranie posledného prvku musí spĺňať tieto podmienky:

• Uvoľniť pamäť posledného prvku
• Ak má had predposledný prvok, je potrebné jeho smerník next nastaviť na NULL.
• Musí vrátiť smerník na prvý prvok.
• Ak už žiadny prvok nezostal, musí vrátiť NULL.

Pozor - posledný prvok spojkového zoznamu musí mať vždy smerník next nastaveny na NULL.

Funkcia na odstránenie posledného prvku sa dá implementovať rekurzívne podľa týchto pravidiel.

head je smerník na prvý prvok hada.

1. Ak je head NULL, vráť NULL.
2. Ak je head posledný prvok, uvoľni head a vráť NULL.
3. Inak odstráň posledný prvok z ďalšieho prvku a vráť head.

Alebo odstránenie posledného prvku sa dá implementovať iteratívne:

1. Ak je head NULL, vráť NULL.
2. Ak je head posledný prvok, uvoľni head a vráť NULL.
3. Nájdi posledný prvok hada, ale pamätaj si predposledný prvok.
4. Uvoľni posledný prvok a označ predposledný prvok hada ako posledný
5. Vráť head.

Odovzdanie

Do súboru du7/snake.c.

Previous Post Next Post