Zadanie č. 2: Sokoban Game

Znenie zadania

Implementujte hru Sokoban v jazyku C pomocou knižnice ncurses. Herný svet nech podporuje Sokoban Level Format s voliteľnou podporou pre Run Level Encoding. Hra bude obsahovať postupnosť levelov, ktoré sa načítajú pri spustení hry zo súboru a počas behu hry budú v pamäti reprezentované pomocou spojkového zoznamu.

Pravidlá hry sú nasledovné:

• Naraz je možné posúvať (tlačiť) len jednu krabicu.
• Krabicu nie je možné ťahať.
• Hráč nemôže prechádzať cez krabice alebo steny.
• Hra je vyriešená, keď sú všetky krabice umiestnené na svojich cieľových pozíciách.

Termín odovzdania

Zadanie sa bude riešiť na cvičeniach v týždňoch 9. až 11. Termín, do ktorého je potrebné zadanie odovzdať, je nedeľa, 6. mája 2012, 23:55.

Všeobecné informácie

Odovzdané zadanie prejde kontrolou originality, ktorá sa uskutoční voči aktuálne vypracovaným zadaniam ako aj zadaniam z minulých rokov. Pokiaľ sa zistí, že študent odovzdal kópiu iného riešenia, nesplní základnú podmienku získania zápočtu a ten mu nebude udelený (bez možnosti opätovného pokusu odovzdať zadanie). Pokiaľ odovzdané zadanie bude vlastné iba čiastočne, zadanie nebude akceptované. Študent bude mať ešte jeden pokus dopracovať zadanie, ale jeho hodnotenie bude penalizované do -5 bodov. O výške penalizácie rozhodne príslušný cvičiaci.

Toto zadanie je zamerané na overenie znalostí z nasledujúcich oblastí:

• práca s jednorozmerným a dvojrozmerným poľom,
• údajové štruktúry,
• enumeračné typy,
• práca so súbormi,
• dynamické údajové typy, a
• modulárne programovanie.

Spracovanie hry a vlastná implementácia

Grafické prevedenie hry

Grafické prevedenie hry môže vyzerať nasledovne:

DELIVER STEPS
5/6     41

    #####             
    #   #             
    #$ $#             
  ###   ###           
  #   $   #           
### #$### #     ######
#   # ### #######  .*#
# $             @  ..#
##### #### ######  ..#
    #      ###  ######
    ########

Legenda:

• '#' - stena, cez ktorú hráč nemôže prejsť
• '$' - krabica, ktorú je možné posúvať
• '@' - hráč
• '.' - cieľová pozícia, na ktorú je potrebné dotlačiť krabicu
• '*' - krabica nachádzajúca sa na cieľovej pozícii
• ' ' - podlaha, po ktorej sa môže hráč pohybovať
• informácia DELIVER v stavovom riadku hovorí, koľko z koľkých krabíc je ešte potrebné dostať na cieľovú pozíciu
• informácia STEPS v stavovom riadku hovorí, koľko krokov už hráč prešiel pri riešení aktuálneho levelu

Reprezentácia levelov hry

Každá úroveň hry bude reprezentovaná pomocou formátu Sokoban Level Format. Voliteľne môžete implementovať podporu pre Run Level Encoding.

Na začiatku hry sa táto postupnosť načíta z na to určeného súboru. Následne sa z týchto levelov a ďalších metaúdajov vytvorí spojkový zoznam, ktorý bude existovať počas celého spustenia hry. Po jej ukončení sa tento zoznam uvoľní z pamäte.

O každom leveli bude potrebné uchovávať tieto informácie:

• name - názov levelu
• description - krátky opis levelu (na navodenie atmosféry alebo len na ftipnú poznámku autora ;)
• map - level uložený vo forme reťazca vo formáte Sokoban Level Format
• password - heslo pre rýchly vstup do konkrétneho levelu

Ukážka takejto postupnosti levelov:

+----------------------------------------------------------------------------------------------------------------------------------------------------+
| name:        "Level Zero"                                                                                                                          |
| description: "Every saga has a beginning..."                                                                                                       |
| map:         "4-5#9--|4-#3-#9--|4-#$2-#9--|2-3#2-$3#9-|2-#2-$--$-#9-|3#-#-3#-#5-6#|#3-#-3#-7#2-2.#|#-$--$9-4-2.#|5#-4#-#@4#2-2.#|4-#6-3#2-6#|4-8#" |
| password:    "zero"                                                                                                                                |
+----------------------------------------------------------------------------------------------------------------------------------------------------+
                                                                            |
                                                                            |
                                                                            v
                                            +-------------------------------------------------------------+
                                            | name:        "The Big Issue"                                |
                                            | description: "There is no description"                      |
                                            | map:         "7#|#.v-#-#|#$*-$-#|#3-$-#|#-2.2-#|#2-*2-#|7#" |
                                            | password:    "issue"                                        |
                                            +-------------------------------------------------------------+

Ukážka formátu vstupného súboru, ktorý bude obsahovať uvedené levely

Level Zero;Every saga has a beginning...;zero;4-5#9--|4-#3-#9--|4-#$2-#9--|2-3#2-$3#9-|2-#2-$--$-#9-|3#-#-3#-#5-6#|#3-#-3#-7#2-2.#|#-$--$9-4-2.#|5#-4#-#@4#2-2.#|4-#6-3#2-6#|4-8#
The Big Issue;There is no description;issue;7#|#.v-#-#|#$*-$-#|#3-$-#|#-2.2-#|#2-*2-#|7#
    

V prípade, že máte problém s vytváraním vlastných levelov, ako inšpiráciu môžete použiť levely na týchto stránkach:

• http://www.sourcecode.se/sokoban/levels.php
• http://sneezingtiger.com/sokoban/levels.html
• http://sapiens.ya.com/sokobanhomz/

Požiadavky pre úspešné odovzdanie zadania

• projekt musí byť odovzdaný včas pomocou LMS Moodle v správnom formáte (viď nižšie)
• levely musia byť načítateľné vo formáte Sokoban Level Format z externého súboru
• počas prekladu nemôže dôjsť ku žiadnemu varovaniu (warning) a ani ku žiadnej chybe (error)
• vytvorený kód musí byť okomentovaný a to najmä všetky deklarácie funkcií, všetky vytvorené vlastné typy (enumeračné, štruktúrované) spolu s ich položkami, všetky makrá a všetky globálne premenné
• projekt sa bude prekladať prekladačom gcc pomocou nasledovných prepínačov:

                  $ gcc -std=gnu99 -Werror -pedantic -lcurses
              

• výsledný projekt musí byť preložiteľný a spustiteľný na serveri omega.tuke.sk pomocou pripraveného Makefile-u, ktorý sa bude nachádzať v odovzdávanom balíčku
• súbory obsahujúce zdrojové kódy, ako aj súbor Makefile a readme.txt musia používať kódovanie ASCII
• pri ukladaní súborov nepoužívajte názvy, ktoré obsajú medzery alebo diakritiku

Štruktúra balíčka na odovzdanie

Zadanie sa odovzdáva formou zip balíčku, pričom jeho názov bude reprezentovaný jedinečným identifikátorom študenta s rokom odovzdavania v tvare: ROK_AB123CD.zip. Zip balíček bude obsahovať nasledujúcu štruktúru priečinkov, pričom počiatočné lomítko '/' reprezentuje koreňový priečinok v balíčku:

• /bin/ - v tomto priečinku sa bude nachádzať spustiteľná verzia programu (súbor sokoban) spolu so súborom obsahujúcim zoznam všetkých levelov (súbor levels)
• /src/ - priečinok, v ktorom sa budú nachádzať práve tieto súbory:
  • main.c - hlavný súbor, v ktorom sa nachádza funkcia main()
  • library.c a library.h - zdrojové súbory obsahujúce jadro hry
  • levels.c, levels.h a levels.dat - zdrojové súbory potrebné pre implementáciu podpory práce s levelmi v sokobanovi
  • colors.h, ak ste si definovali vlastné farby
  • Makefile - súbor pre make obsahujúci minimálne ciele all na vygenerovanie spustiteľnej binárky; a clean na zmazanie vykompilovaných bináriek a modulov
• /doc/ - priečinok, v ktorom sa bude nachádzať dokumentácia ku zadaniu (viď nižšie) v súbore documentation.pdf; okrem nej sa tu môže nachádzať priečinok html/ s vygenerovanou dokumentáciou z programu Doxygen.
• /readme.txt - súbor, v ktorom budú uvedené informácie o autorovi, a ktorý bude mať nasledujúcu štruktúru:

  NAME        : NAME SURNAME
  STUDENT ID  : ab123cd
  E-MAIL      : name@student.tuke.sk
  YEAR        : 9999
              

Poznámka: Je dôležité, aby vaše súbory zachovali uvedenú štruktúru. Ak sa niektorý zo súborov nachádza v balíčku, ale mimo uvedenej štruktúry, bude to považované za chybu a takto odovzdaný balíček nebude považovaný za správny.

Dokumentácia

Dokumentácia ku zadaniu predstavuje jeden dokument vo formáte .pdf alebo priečinok html/ vygenerovaný ako výstup z vhodného nástroja, napr. Doxygen. Dokumentácia sa skladá z týchto častí:

• Titulná strana
• Znenie zadania
• Dodefinovanie zadania - uviesť obmedzujúce podmienky riešenia, ako napr. maximálna výška a šírka sveta a pod.
• Návrh riešenia úlohy - návrh vlastných údajových štruktúr, enumeračných typov a nových typov - spôsob reprezentácie objektov problémovej oblasti
• Použitie programu - krátky opis použitia vášho programu pri preklade a spúšťaní
  • vytvoriť návod pre použitie programu (t.j. ako možno program preložiť, s akými parametrami je možné program spustiť),
  • zoznam chybových správ (napr. ak sa Karel pokúsi vziať značku z miesta, na ktorom žiadna značka nie je)
• Záver
  • zhodnotenie riešenia
  • možnosti využitia a rozšírenia v súvislosti s existujúcimi obmedzeniami riešenia
• Príloha: Referenčná dokumentácia - pozostáva z dokumentácie všetkých vytvorených funkcií, údajových štruktúr, vlastných typov, enumeračných typov a globálnych premenných. Pre vytvorenie je vhodné použiť automatizovaný nástroj (napr. Doxygen), ktorý dokumentáciu automaticky generuje z komentárov. Využiť môžete predpripravený konfiguračný súbor Doxyfile. Doxygen je možné spustiť aj na serveri omega.tuke.sk z príkazového riadku príkazom doxygen. Vygenerovaná dokumentácia nemusí byť súčasťou .pdf súboru s dokumentáciou, ale stačí výstup vo formáte HTML uložiť do priečinku doc/html/.