ˇ ´IRODOVEDECK ˇ ´ FAKULTA UNIVERZITY PALACKEHO ´ PR A KATEDRA INFORMATIKY
´ RSK ˇ ´ PRACE ´ BAKALA A
Poˇc´ıtaˇcov´a hra Bludiˇstˇe
2014
Mgr. Petr Dohnal
Anotace C´ılem bakal´aˇrsk´e pr´ace bylo vytvoˇren´ı poˇc´ıtaˇcov´e hry Bludiˇstˇe, ve kter´e je u ´kolem hr´aˇce proj´ıt bludiˇstˇe a nal´ezt v´ychod. Hra umoˇzn ˇuje vytv´aˇret nebo generovat bludiˇstˇe, pr˚ uchod bludiˇstˇem a mˇeˇren´ı ˇcasu pro nalezen´ı c´ıle cesty, uloˇzen´ı a zobrazen´ı v´ysledk˚ u.
Dˇekuji Mgr. Tom´aˇsi K¨ uhrovi, Ph.D. za veden´ı m´eho bakal´aˇrsk´eho projektu.
Obsah ´ 1. Uvod
7
2. Zad´ an´ı bakal´ aˇ rsk´ e pr´ ace 2.1. C´ıl bakal´aˇrsk´e pr´ace . . . . . . . . . . . . . . . . . . . . . . . . .
8 8
3. Bludiˇ stˇ e 3.1. V´ yznam a historie bludiˇstˇe . . . . . . . . . . . . . . . . . . . . . . 3.2. Typy bludiˇstˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9 9 10
4. Matematick´ a reprezentace 4.1. Graf . . . . . . . . . . . 4.2. Pr˚ uchod grafem . . . . . 4.3. Generov´an´ı bludiˇstˇe . . . 4.4. Prohled´av´an´ı do hloubky 4.5. Nalezen´ı cesty v bludiˇsti
. . . . .
12 12 12 14 14 17
5. Uˇ zivatelsk´ a dokumentace 5.1. Poˇzadavky na syst´em . . 5.2. Spuˇstˇen´ı aplikace . . . . 5.3. Ovl´ad´an´ı . . . . . . . . . 5.3.1. Volby menu . . . 5.3.2. Hra . . . . . . . . 5.3.3. Editace . . . . . 5.3.4. N´astroje . . . . . 5.3.5. V´ ysledky . . . . . 5.3.6. Stavov´a liˇsta . . . 5.3.7. Poj´ıdaˇci . . . . . 5.4. Generovan´a trasa . . . .
bludiˇ stˇ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
18 18 18 19 19 21 21 23 23 24 24 26
6. Program´ atorsk´ a dokumentace 6.1. Technologie . . . . . . . . . . . . . . . . . 6.1.1. Microsoft Visual Studio 2008 . . . . 6.1.2. C# . . . . . . . . . . . . . . . . . . 6.1.3. .NET Framework . . . . . . . . . . 6.1.4. XML (Extesible Markup Language) 6.1.5. Datov´e zdroje . . . . . . . . . . . . 6.2. Aplikace . . . . . . . . . . . . . . . . . . . 6.2.1. Tˇr´ıdy . . . . . . . . . . . . . . . . 6.3. V´ yvoj aplikace . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
27 27 27 27 27 28 28 29 29 33
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Z´ avˇ er
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
34
4
Conclusions
35
Reference
36
7. Pˇ r´ıloha A - Obsah pˇ riloˇ zen´ eho CD
37
5
Seznam obr´ azk˚ u 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
Kr´etsk´ y labyrint. . . . . . . . . Typy bludiˇstˇe. . . . . . . . . . . Bludiˇstˇe reprezentovan´e grafem. Pr˚ uchod grafu do hloubky. . . . Pr´azdn´e bludiˇstˇe s grafem. . . . Algoritmus generov´an´ı bludiˇstˇe. Z´akladn´ı obrazovka. . . . . . . . Vygenerovan´e bludiˇstˇe a zaˇca´tek ˇ Sablona pro editaci. . . . . . . . Nastaven´ı bludiˇstˇe. . . . . . . . V´ ysledky hry. . . . . . . . . . . Stavov´a liˇsta. . . . . . . . . . . Poj´ıdaˇci v bludiˇsti. . . . . . . . Generovan´a trasa. . . . . . . . . Tˇr´ıdy. . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . hry. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
9 11 12 13 14 15 18 21 22 23 24 24 25 26 29
1.
´ Uvod
Tato pr´ace se zab´ yv´a anal´ yzou, n´avrhem a implementac´ı poˇc´ıtaˇcov´e hry Bludiˇstˇe. Aplikace umoˇzn ˇuje generovat nebo vytv´aˇret bludiˇstˇe a pr˚ uchod vytvoˇren´ ym bludiˇstˇem. C´ılem hry je naj´ıt cestu k v´ ychodu. Hra mˇeˇr´ı ˇcas a vyhodnocuje u ´spˇeˇsnost hr´aˇce. Vygenerovan´e bludiˇstˇe je tak´e moˇzn´e vytisknout a proj´ıt v pap´ırov´e podobˇe. Hra je zamˇeˇrena na dˇeti a je tak´e urˇcena k propagaci katedry informatiky. Tuto hru jsem si zvolil, protoˇze samotn´ y pojem bludiˇstˇe je l´akav´ ya tajupln´ y a skr´ yv´a spustu zaj´ımav´ ych pravidel a algoritm˚ u.
7
2.
Zad´ an´ı bakal´ aˇ rsk´ e pr´ ace
2.1.
C´ıl bakal´ aˇ rsk´ e pr´ ace
C´ılem pr´ace je vytvoˇren´ı poˇc´ıtaˇcov´e hry, ve kter´e bude u ´kolem hr´aˇce nalezen´ı cesty bludiˇstˇem. Vytvoˇren´a aplikace by mˇela splˇ novat n´asleduj´ıc´ı poˇzadavky: • Umoˇznit uˇzivateli vytv´aˇret, editovat, ukl´adat a naˇc´ıtat bludiˇstˇe. • Umoˇznit automatick´e generov´an´ı bludiˇstˇe. • Vyhodnocovat u ´speˇsnost hr´aˇce (rychlost nalezen´ı cesty, d´elku nalezen´e cesty; pˇr´ıpadnˇe obsahovat datab´azi nˇekolika nejlepˇs´ıch hr´aˇc˚ u pro dan´e bludiˇstˇe). • Pr˚ uchod bludiˇstˇem muˇze b´ yt zpestˇren r˚ uzn´ ymi pˇrek´aˇzkami ˇci nestv˚ urami. • Hra by mˇela b´ yt vhodn´a pro propagaci katedry informatiky.
8
3. 3.1.
Bludiˇ stˇ e V´ yznam a historie bludiˇ stˇ e
Bludiˇstˇe je spletit´a s´ıt’ cestiˇcek s jednou nebo v´ıce slep´ ymi vˇetvemi. Je to hlavolam, kter´ y je ˇreˇsiteln´ y a m´a dosaˇziteln´ y c´ıl. Bludiˇstˇe maj´ı svou tis´ıciletou historii. Nejstarˇs´ı bludiˇstˇe nebyla sloˇzit´a, stezky se v nich jednoduˇse st´aˇcely a nejednalo se o r´ebusy. Mˇela pravdˇepodobnˇe pouze kultovn´ı a spoleˇcensk´ y v´ yznam. Slouˇzila jako past na zl´e duchy nebo jako vyznaˇcen´a trasa pro ritu´aln´ı tance. Z pozdˇejˇs´ı doby je nejzn´amˇejˇs´ı kr´etsk´ y labyrint postaven´ y podle b´aje Daidalem pro obludn´eho M´ınotaura. Daidalos postavil labyrint ˇsikovnˇe a chytˇre, mˇel spoustu slep´ ych chodeb a smyˇcek. M´ınotaura zabil udatn´ y at´ensk´ y hrdina Th´eseus. Musel vˇsak proj´ıt labyrint, naj´ıt Minotaura, zab´ıt ho a zase se vr´atit zpˇet. Aby se neztratil, dostal od Ariadny nit, pomoc´ı kter´e si znaˇcil cestu. Kdyˇz postupoval do nezn´am´ ych m´ıst bludiˇstˇe, nit odmot´aval. Kdyˇz se vracel, nit namot´aval zp´atky na klubko. Namot´av´an´ı nitˇe ho vyvedlo pˇred vchod do bludiˇstˇe. [3]
Obr´azek 1. Kr´etsk´ y labyrint. Ve stˇredovˇeku je labyrint symbolem cesty k Bohu s jasnˇe definovan´ ym centrem (B˚ uh) a jedn´ım vstupem (narozen´ı). Labyrinty lze povaˇzovat za symbolickou formu pouti; lid´e j´ı mohou proj´ıt, stoupaj´ıc´ı ke sp´ase nebo osv´ıcen´ı. Pozdˇeji naˇsly bludiˇstˇe ˇsirok´e uplatnˇen´ı v zahrad´ach. Ve 12. stolet´ı se zaˇcaly pouˇz´ıvat v zahrad´ach v Anglii a slouˇzily jako ide´aln´ı m´ısto pro romantick´e chv´ıle. Postupnˇe se rozˇs´ıˇrily po cel´e Evropˇe, zejm´ena ve Francii, Anglii a It´alii. Maj´ı kruhov´e i pravo´ uhl´e uspoˇr´ad´an´ı a pr˚ uchoz´ı pˇeˇsiny jsou vymezeny stˇr´ıhan´ ymi stˇenami, konstrukcemi s pop´ınav´ ymi dˇrevinami ˇci kamenn´ ymi zdmi. D´elka pˇeˇsin dosahovala ˇcasto i nˇekolika kilometr˚ u. V modern´ı dobˇe jsou bludiˇstˇe pouˇz´ıvan´a k biologick´emu testov´an´ı uˇcen´ı a pamˇeti ˇzivoˇcich˚ u od hmyzu aˇz po lidi. K testov´an´ı se pouˇz´ıvaj´ı r˚ uzn´e metody. 9
Pro experiment´aln´ı metody studia prostorov´eho uˇcen´ı se pouˇz´ıvaj´ı bludiˇstˇe speci´aln´ıch tvar˚ u a vlastnost´ı, napˇr´ıklad radi´aln´ı bludiˇstˇe, Y-bludiˇstˇe, T-bludiˇstˇe nebo Morrisovo vodn´ı bludiˇstˇe. [2] Zp˚ usob˚ u, jak bludiˇstˇe vytvoˇrit, je nˇekolik. Lze jej ruˇcnˇe navrhnout ˇci nakreslit, vytvoˇrit na z´akladˇe ˇsablony nebo vyuˇz´ıt algoritmick´eho pˇr´ıstupu. V dneˇsn´ı dobˇe lze bludiˇstˇe postavit a proj´ıt v poˇc´ıtaˇci. T´ım se tak´e zab´ yv´a tato pr´ace. Uk´aˇzeme si, jak´ ym zp˚ usobem lze bludiˇstˇe teoreticky navrhnout a jak´e m˚ uˇzeme pouˇz´ıt postupy pˇri generov´an´ı a pr˚ uchodu bludiˇstˇem. Asi kaˇzd´ y by dok´azal pomoc´ı nitˇe a kˇr´ıdy proj´ıt bludiˇstˇe, ale jak to nauˇcit ´ poˇc´ıtaˇc ? Ukolem je tedy zvolit reprezentaci bludiˇstˇe v poˇc´ıtaˇci, vyuˇz´ıt vhodn´e datov´e struktury a algortitmy pro vytvoˇren´ı bludiˇstˇe tak, aby bludiˇstˇe bylo pr˚ uchodn´e.
3.2.
Typy bludiˇ stˇ e
Bludiˇstˇe lze rozdˇelit podle r˚ uzn´ ych parametr˚ u. Podle dimenze, tvaru, zp˚ usobu pr˚ uchodu a dalˇs´ıch kriteri´ı. Existuj´ı bludiˇstˇe ve dvou nebo tˇrech dimenz´ıch a z hlediska datov´ ych struktur lze vytvoˇrit bludiˇstˇe i v´ıcedimenzion´aln´ı. Jejich vizualizace je vˇsak komplikovan´a a pro ˇclovˇeka pomˇernˇe tˇeˇzko pˇredstaviteln´a. Podle tvaru m˚ uˇzeme bludiˇstˇe dˇelit na ortogon´aln´ı, tedy pravo´ uhl´a bludiˇstˇe, d´ale mozaikov´a, radi´aln´ı nebo speci´aln´ıch tvar˚ u. Zaj´ımav´ ym typem pro zkoum´an´ı by bylo frakt´aln´ı bludiˇstˇe, kde kaˇzd´a buˇ nka je opˇet bludiˇstˇem a rekurzivnˇe se tento postup opakuje. Tato pr´ace se zab´ yv´a dvoudimenzion´aln´ım ortogon´aln´ım bludiˇstˇem. Dalˇs´ı rozdˇelen´ı m˚ uˇze b´ yt podle smˇerov´an´ı cest a na z´akladˇe toho, jak´ ym zp˚ usobem jsou cesty v bludiˇsti propojeny. Z´akladn´ım typem jsou bludiˇstˇe, ve kter´ ych neexistuje rozcest´ı. Od zaˇc´atku do c´ıle vede jedna dlouh´a klikat´a cesta. Kr´etsk´e bludiˇstˇe bylo tak´e tohoto typu (Obr´azek 2, bludiˇstˇe 1). Sloˇzitˇejˇs´ım typem jsou bludiˇstˇe s jednoduch´ ym propojen´ım cest, ve kter´ ych neexistuj´ı cykly a oddˇelen´e ˇca´sti (Obr´azek 2, bludiˇstˇe 2). Dalˇs´ım typem jsou bludiˇstˇe, ve kter´ ych je povolena existence slep´ ych konc˚ u (Obr´azek 2, bludiˇstˇe 3) a posledn´ım type je bludiˇstˇe, ve kter´em se vyskytuj´ı i 10
oddˇelen´e ˇca´sti (Obr´azek 2, bludiˇstˇe 4). Program generuje bludiˇstˇe se slep´ ymi konci bez oddˇelen´ ych ˇca´st´ı.
Obr´azek 2. Typy bludiˇstˇe.
11
4. 4.1.
Matematick´ a reprezentace bludiˇ stˇ e Graf
Pro matematickou reprezentaci bludiˇstˇe je vhodn´ y graf. Graf G = (U, H) je matematick´a struktura tvoˇren´a dvˇema mnoˇzinami U a H. Prvky mnoˇziny U jsou uzly a prvky mnoˇziny H jsou hrany. Kaˇzd´e hranˇe n´aleˇz´ı dva uzly, kter´e se naz´ yvaj´ı koncov´e body hrany. U neorientovan´ ych graf˚ u na poˇrad´ı uzl˚ u nez´aleˇz´ı a hrana je dvouprvkov´a mnoˇzina ˇ uzl˚ u u, v. R´ık´ame, ˇze hrana spojuje uzly. U orientovan´ ych graf˚ u na poˇrad´ı uzl˚ u z´aleˇz´ı a hrana je uspoˇra´dan´a dvojice uzl˚ u ˇ ık´ame, ˇze hrana vede z uzlu u do uzlu v. [u, v]. R´ Bludiˇstˇe se skl´ad´a z kˇriˇzovatek, konc˚ u a cest, kter´e vˇse spojuj´ı. V grafu hrany reprezentuj´ı cesty. Kˇriˇzovatky a konce cest pˇredstavuj´ı uzly grafu. V grafu pro dvoudimenzion´aln´ı ortogon´aln´ı bludiˇstˇe bude kaˇzd´a buˇ nka reprezentovan´a uzlem a cesta mezi buˇ nkami hranou d´elky 1. Zvol´ıme tak´e poˇca´teˇcn´ı a c´ılov´ y bod. Tento postup je pˇredstaven na Obr´azku 3.
Obr´azek 3. Bludiˇstˇe reprezentovan´e grafem.
4.2.
Pr˚ uchod grafem
Pro vytvoˇren´ı bludiˇstˇe je potˇreba pouˇz´ıt vhodn´ y algoritmus. Bludiˇstˇe je reprezentovan´e pomoc´ı grafu, pouˇzijeme tedy algoritmus pro pr˚ uchod grafem. To je u ´loha, kdy potˇrebujeme ve vˇsech uzlech grafu prov´est nˇejakou operaci, napˇr´ıklad uzly oznaˇcit a zahrnou do cesty bludiˇstˇem. Potˇrebujeme tedy proj´ıt vˇsechny uzly grafu. Existuj´ı dva systematick´e pr˚ uchody grafem – do hloubky a do ˇs´ıˇrky.
12
V t´eto pr´aci je pouˇzit´ y algoritmus pr˚ uchodu do hloubky. Podle tohoto algoritmu postupoval i Theseus pˇri hled´an´ı Minotaura. Algoritmus pr˚ uchodu do hloubky postupuje po jednotliv´ ych uzlech a pokraˇcuje u jejich soused˚ u. Kaˇzd´ y navˇst´ıven´ y uzel si oznaˇc´ı a vybere si v nˇem jednu moˇznou cestu/hranu k dalˇs´ımu uzlu. K doˇcasn´emu uloˇzen´ı uzl˚ u, kter´e v dan´e chv´ıli nem˚ uˇze navˇst´ıvit, pouˇz´ıv´a z´asobn´ık. Uveden´e obr´azky jsou pˇrevzaty z knihy Grafy a grafov´e algoritmy. [3] Obr´azek 4 ukazuje, v jak´em poˇrad´ı byly proch´azeny jednotliv´e uzly grafu. Pln´e ˇc´ary naznaˇcuj´ı pˇr´ım´ y pˇrechod k dalˇs´ımu uzlu, ˇc´arkovan´e ukazuj´ı pˇrechod k uzlu, kter´ y byl odebr´an ze z´asobn´ıku. [3]
Obr´azek 4. Pr˚ uchod grafu do hloubky. Algoritmus pr˚ uchodu do ˇs´ıˇrky postupuje obdobn´ ym zp˚ usobem po jednotliv´ ych uzlech a nenavˇst´ıven´e uzly si ukl´ad´a do fronty. Na rozd´ıl od pr˚ uchodu do hloubky se zde jako dalˇs´ı navˇstˇevovan´ y uzel nevyb´ır´a soused aktu´aln´ıho uzlu, ale vˇzdy se bere uzel z fronty.
13
4.3.
Generov´ an´ı bludiˇ stˇ e
Reprezentaci pomoc´ı grafu s v´ yhodou vyuˇzijeme pˇri generov´an´ı bludiˇstˇe. Bludiˇstˇe lze generovat r˚ uzn´ ymi zp˚ usoby a vyuˇz´ıvat pˇri tom vlastnost´ı bludiˇst’ a graf˚ u. Jak´ y zvolit algoritmus pro generov´an´ı bludiˇstˇe? Zamˇeˇr´ıme se na jednoduˇse propojen´e bludiˇstˇe a vyuˇzijeme jeho hlavn´ı v´ yhodu vych´azej´ıc´ı z grafov´e reprezentace propojen´ ych bunˇek a zvol´ıme pr˚ uchod do hloubky. Tento algoritmus projde cel´e bludiˇstˇe a nakonec se vr´at´ı do v´ ychoz´ıho bodu. Stejnˇe tak pˇri generov´an´ı bludiˇstˇe lze vyj´ıt z jednoho bodu, nal´ezt cestu v pravo´ uhl´e s´ıti, proj´ıt celou s´ıt´ı a zase se vr´atit zpˇet. Kolem t´eto cesty se vybuduj´ı zdi a bludiˇstˇe m´a fin´aln´ı podobu. Pˇri kaˇzd´em generov´an´ı by mˇelo b´ yt bludiˇstˇe jin´e, proto je vhodn´e zvolit n´ahodn´ y v´ ybˇer n´asleduj´ıc´ıho uzlu v pˇr´ıpadˇe, ˇze je moˇzn´e navˇst´ıvit v´ıce sousedn´ıch uzl˚ u. Algoritmus prohled´av´an´ı do hloubky budeme kombinovat s n´ahodn´ ym v´ ybˇerem uzlu. Na zaˇc´atku si pˇredstav´ıme ortogon´aln´ı bludiˇstˇe pouze s obvodov´ ymi zdmi a pˇrevedeme je do grafu. To je zn´azornˇeno na obr´azku 5. Tento graf lze vyuˇz´ıt jako vstup do algoritmu vytv´aˇrej´ıc´ı kostru grafu.
Obr´azek 5. Pr´azdn´e bludiˇstˇe s grafem.
4.4.
Prohled´ av´ an´ı do hloubky
Algoritmus pr˚ uchodu do hloubky je z teorie graf˚ u a slouˇz´ı k prohled´av´an´ı. Vstupn´ım parametrem je uzel, kter´ y bude poˇc´atkem. Tento uzel se oznaˇc´ı jako navˇst´ıven´ y a podle definovan´eho pravidla se postupnˇe vyb´ıraj´ı sousedn´ı uzly, kter´e jeˇstˇe nebyly navˇst´ıveny. Takov´ y postup se opakuje pro vybran´eho souseda. V pˇr´ıpadˇe, ˇze jsou vˇsechny sousedn´ı uzly oznaˇcen´e jako navˇst´ıven´e, prohled´av´an´ı souˇcasn´eho uzlu konˇc´ı a algoritmus se vrac´ı k pˇredchoz´ımu uzlu. Postup konˇc´ı v pˇr´ıpadˇe, ˇze se algortitmus nem´a kam vr´atit. Algoritmus vyuˇz´ıv´a z´asobn´ık, na kter´em je uloˇzena cesta od vstupn´ıho uzlu k souˇcasn´emu.
14
D˚ uleˇzitou ˇc´ast´ı algoritmu je zp˚ usob v´ ybˇeru sousedn´ıch uzl˚ u. Uzly grafu jsou ohodnoceny a vybr´an bude vˇzdy nenavˇst´ıven´ y uzel s minim´aln´ı hodnotou. [4] Algoritmus pouˇzijeme ke generov´an´ı bludiˇstˇe n´asleduj´ıc´ım zp˚ usobem. Je potˇreba, aby vˇsechny zdi v bludiˇsti byly postaveny a jednotliv´e buˇ nky znaly sv´e sousedy. Z hlediska teorie graf˚ u, to znamen´a, ˇze mezi buˇ nkami bude existovat hrana. Pot´e nastav´ıme pravidlo pro v´ ybˇer sousedn´ıch uzl˚ u neboli bunˇek bludiˇstˇe. Ty budou vyb´ır´any n´ahodnˇe a pˇri pˇrechodu na sousedn´ı buˇ nku bude zbouran´a ’ zed , kter´a buˇ nky oddˇeluje. T´ım vygenerujeme bludiˇstˇe. Pˇri spuˇstˇen´ı algoritmu se vstupn´ı buˇ nka uloˇz´ı na z´asobn´ık a d´ale se na z´asobn´ık uloˇz´ı vˇsechny naˇst´ıven´e buˇ nky. Z´asobn´ık tak bude reprezentovat cestu od poˇc´ateˇcn´ı k pr´avˇe prohled´avan´e buˇ nce. V pˇr´ıpadˇe, ˇze jsou vˇsechny sousedn´ı buˇ nky jiˇz navˇs´ıven´e, algoritmus odebere ze z´asobn´ıku posledn´ı buˇ nku a opakuje prohled´av´an´ı soused˚ u. Postup konˇc´ı v pˇr´ıpadˇe, ˇze dokonˇcil prohled´av´an´ı vstupn´ıho uzlu. Postup algoritmu je vidˇet na obr´azku 6.
Obr´azek 6. Algoritmus generov´an´ı bludiˇstˇe. Pˇredstaven´ y algoritmus je typu horn´ık, ale je moˇzn´e jej implementovat i jako zedn´ıka. Uzly, zpracov´avan´e algoritmem by byly tvoˇreny body, ve kter´ ych se potk´avaj´ı zdi bludiˇstˇe a postup algoritmu by byl podobn´ y jako v pˇr´ıpadˇe horn´ıka. Modifikac´ı pravidla pro v´ ybˇer sousedn´ıch uzl˚ u lze do urˇcit´e m´ıry dos´ahnout zmˇeny sloˇzitosti bludiˇstˇe. V´ ybˇer souseda rozhodne n´ahodn´e ˇc´ıslo pomoc´ı gener´atoru n´ahodn´ ych ˇc´ısel. Tuto ˇc´ast algoritmu lze upravovat a t´ım ovlivnit v´ ysledn´e generovan´e bludiˇstˇe. Pokud se bude n´ahodn´e ˇc´ıslo generovat jen po 15
urˇcit´em poˇctu krok˚ u a t´ım upˇrednostˇ novat jeden smˇer, bude m´ıt bludiˇstˇe delˇs´ı chodby a bude pˇrehlednˇejˇs´ı. Pˇri generov´an´ı n´ahodn´eho ˇc´ısla v kaˇzd´em kroku, bude v´ıce zmˇen smˇeru a bludiˇstˇe bude v´ıce spleten´e.
16
4.5.
Nalezen´ı cesty v bludiˇ sti
Algoritmy pro nalezen´ı cesty v bludiˇsti lze rozdˇelit na dva z´akladn´ı typy podle znalosti bludiˇstˇe. Bud’ algoritmus zn´a bludiˇstˇe, nad kter´ ym hled´a cestu nebo pˇredstavuje objekt proch´azej´ıc´ı bludiˇstˇem na z´akladˇe dan´ ych pravidel. Algoritmy pro nalezen´ı cesty v bludiˇsti jsou algoritmy pr˚ uchodu grafem. Algoritmem pr˚ uchodu do hloubky postupoval i Theseus, kdyˇz pouˇz´ıval Ariadninu nit v Kr´etsk´em labyrintu. • Pr˚ uchod do hloubky – s t´ımto algoritmem jsme se jiˇz sezn´amili pˇri generov´an´ı bludiˇstˇe. • Pravidlo jedn´e ruky – zajiˇst’uje, ˇze najdeme v´ ychod z bludiˇstˇe, zato nezaruˇcuje, ˇze v nˇem najdeme Minotaura. Nemus´ıme totiˇz proj´ıt cel´e bludiˇstˇe, pokud jsou v nˇem izolovan´e ˇc´asti. • Tr´emaux˚ uv algoritmus - spoˇc´ıv´a v pravidle, kdy kaˇzdou hranu m˚ uˇzeme v jednom smˇeru proj´ıt nejv´ yˇse jednou. • Vyplnˇen´ı slep´ ych konc˚ u – postupnˇe projde cel´e bludiˇstˇe a pokud naraz´ı na slep´ y konec, oznaˇc´ı celou cestu k nejbliˇzˇs´ı kˇriˇzovatce. Tato kˇriˇzovatka potom bude o stupeˇ n niˇzˇs´ı a jej´ı stupeˇ n se m˚ uˇze sniˇzovat, aˇz z n´ı bude cesta. T´ımto zp˚ usobem se oznaˇc´ı ˇc´ast bludiˇstˇe, aˇz z˚ ustane cesta nebo cesty vedouc´ı od zaˇca´tku k c´ıli. • N´ahodn´a myˇs – funguje podobnˇe jako myˇs v bludiˇsti. Pˇri vstupu do kaˇzd´e buˇ nky vybere n´ahodnou cestu, kterou bude pokraˇcovat. Pokud existuje cesta z poˇca´tku do c´ıle, algoritmus ji najde, ale m˚ uˇze to trvat dlouho.
17
5. 5.1.
Uˇ zivatelsk´ a dokumentace Poˇ zadavky na syst´ em
Bludiˇstˇe je navrˇzeno jako hra pro souˇcasn´e poˇc´ıtaˇcov´e syst´emy a nevyˇzaduje ˇz´adn´e zvl´aˇstn´ı n´aroky na grafick´e ˇci softwarov´e vybaven´ı poˇc´ıtaˇce koncov´eho uˇzivatele. Bludiˇstˇe je 32 bitov´a aplikace pro MS Windows XP, Windows Vista, Windows 7. Poˇzadavky na syst´em je minim´aln´ı rozliˇsen´ı monitoru 1280 x 720. Aplikace poˇzaduje Microsoft .NET Framework 3.5 nebo vyˇsˇs´ı.
5.2.
Spuˇ stˇ en´ı aplikace
Aplikaci je moˇzn´e spustit nainstalov´an´ım do poˇc´ıtaˇce a n´asledn´ ym dvojit´ ym kliknut´ım na soubor Labyrinth.exe.
Obr´azek 7. Z´akladn´ı obrazovka.
18
5.3.
Ovl´ ad´ an´ı
Cel´a hra Bludiˇstˇe je koncipov´ana tak, aby byla vhodn´a i pro dˇeti a tud´ıˇz uˇzivatelsky pˇr´ıvˇetiv´a. Ovl´ad´an´ı aplikace je snadn´e. Aplikaci lze ovl´adat dvˇema zp˚ usoby, pomoc´ı menu v horn´ı ˇca´sti nebo pomoc´ı tlaˇc´ıtek na tlaˇc´ıtkov´e liˇstˇe. Pouˇzit´ı tlaˇc´ıtek je uˇzivatelsky rychlejˇs´ı a pˇrehlednˇejˇs´ı. Ale vzhledem ke st´ale trvaj´ıc´ı oblibˇe nˇekter´ ych uˇzivatel˚ u pouˇz´ıvat nab´ıdku menu, je ovl´ad´an´ı navrˇzeno tak, aby vyhovovala i takov´ ym n´arok˚ um. 5.3.1.
Volby menu
V aplikaci je v menu pouˇzito celkem 5 moˇznost´ı. Vˇetˇsina jednotliv´ ych funkc´ı je podrobnˇeji pops´ana v samostatn´ ych kapitol´ach. Hra • Nov´a hra – ovl´ad´a spouˇstˇen´ı ˇci ukonˇcen´ı generov´an´ı bludiˇstˇe a jednoho pr˚ uchodu, proto byla zaˇrazena jako prvn´ı. • Generovan´a trasa – zobraz´ı trasu, kter´a vznikne algoritmem pˇri generov´an´ı bludiˇstˇe. Tato volba je vhodn´a pro anal´ yzu algoritmu generov´an´ı. • Konec – touto funkc´ı opust´ı uˇzivatel celou aplikaci. Dialogov´ ym oknem je jeˇstˇe dot´az´an, zda chce opravdu aplikaci ukonˇcit. Editace ˇ • Sablona – zobraz´ı podkladovou ˇsablonu pro vytvoˇren´ı bludiˇstˇe, kde pomoc´ı myˇsi lze editovat bludiˇstˇe. • V´ ymaz plochy – tato volba vymaˇze ˇsablonu i bludiˇstˇe. • Uloˇzit bludiˇstˇe – uloˇzen´ı bludiˇstˇe do souboru. N´azev souboru se pˇrednastav´ı tak, aby byl jednoznaˇcn´ y a nab´ıdne se adres´aˇr pro uloˇzen´ı souboru. • Otevˇr´ıt bludiˇstˇe – naˇcten´ı bludiˇstˇe ze souboru. Nab´ız´ı se adres´aˇr s naposled uloˇzen´ ymi soubory. N´astroje • Nastaven´ı bludiˇstˇe - slouˇz´ı uˇzivateli pro vlastn´ı nastaven´ı bludiˇstˇe dle pˇredstav uˇzivatele o stupni obt´ıˇznosti, velikosti bludiˇstˇe, mnoˇzstv´ı ˇzivot˚ u a nepˇr´atelsk´ ych poj´ıdaˇc˚ u. • Tisk - tisk vygenerovan´eho bludiˇstˇe. Tato volba nab´ıdne tisk´arnu a standardn´ı obrazovku pro nastaven´ı parametr˚ u tisku.
19
V´ ysledky • Pˇri volbˇe funkce V´ ysledky se uˇzivateli zobraz´ı v´ ysledky her pro jednotliv´e hr´aˇce, kter´e lze tˇr´ıdit, filtrovat a porovn´avat dle zvolen´eho krit´eria. N´apovˇeda • Dokumentace - tato volba zobraz´ı ve formˇe webov´e str´anky uˇzivatelskou dokumentaci k programu. • O aplikaci - Informace o verzi programu.
20
5.3.2.
Hra
Hra se spust´ı volbou menu Hra - Nov´a hra nebo tlaˇc´ıtkem Nov´a hra. Pˇri spuˇstˇen´ı se vygeneruje bludiˇstˇe podle parametr˚ u nastaven´ı ve volbˇe N´astroje - Nastaven´ı. Na poˇc´atku vstupu do bludiˇstˇe se objev´ı oranˇzov´ y m´ıˇc, kter´ y reaguje pohybem na ˇsipky na kl´avesnici. S m´ıˇcem je potˇreba pohybovat takov´ ym zp˚ usobem, aby se dostal do c´ıle na zv´ yraznˇen´e oranˇzov´e pole s vlajkou. Pˇri pr˚ uchodu bˇeˇz´ı ˇcas, kter´ y se zobrazuje na stavov´e liˇstˇe. Po dosaˇzen´ı c´ıle se zobraz´ı zpr´ava s celkov´ ym ˇcasem a v´ ysledek se zap´ıˇse do souboru dosaˇzen´ ych ˇcas˚ u. Tyto ˇcasy je moˇzn´e zobrazit volbou menu V´ ysledky. Hra se ukonˇc´ı tlaˇc´ıtkem Konec hry.
Obr´azek 8. Vygenerovan´e bludiˇstˇe a zaˇc´atek hry.
5.3.3.
Editace
ˇ Sablona 21
ˇ Editace bludiˇstˇe lze spustit dvˇema zp˚ usoby. Tlaˇc´ıtkem Sablona, coˇz je rychlejˇs´ı ˇ varianta nebo volbou menu Editace - Sablona. Pˇri spuˇstˇen´ı se vykresl´ı ˇsablona bludiˇstˇe s obvodov´ ymi zdmi a rastrem. Kliknut´ım myˇsi lze stavˇet zdi mezi jednotliv´ ymi body rastru a vytvoˇrit tak bludiˇstˇe dle vlastn´ıch pˇredstav uˇzivatele. Vymazat bludiˇstˇe lze volbou Editace - V´ ymaz v menu v horn´ı ˇca´sti aplikace nebo rychlejˇs´ı variantou pomoc´ı tlaˇc´ıtka V´ ymaz na tlaˇc´ıtkov´e liˇstˇe.
ˇ Obr´azek 9. Sablona pro editaci. Uloˇ zen´ı Volbou Uloˇzen´ı lze bludiˇstˇe uloˇzit do zvolen´eho adres´aˇre. N´azev souboru se pˇrednastav´ı sloˇzen´ım jm´ena hr´aˇce a aktu´aln´ıho data a ˇcasu. Nab´ıdne se dialogov´e okno, ve kter´em uˇzivatel m˚ uˇze zmˇenit jm´eno souboru a vybrat si adres´aˇr. Bludiˇstˇe se uloˇz´ı jako soubor XML. Volbou Otevˇren´ı je moˇzn´e naˇc´ıst ze souboru dˇr´ıve 22
uloˇzen´e bludiˇstˇe. 5.3.4.
N´ astroje
Tisk Tlaˇc´ıtko pro volbu tisku nalezne uˇzivatel na tlaˇc´ıtkov´e liˇstˇe nebo v menu. Pokud m´a uˇzivatel vygenerovan´e bludiˇstˇe, lze jej vytisknout. Pˇri t´eto volbˇe se zobraz´ı syst´emov´e okno s volbou tisk´arny a parametr˚ u tisku. Tisk lze pouˇz´ıt pro novˇe vygenerovan´e bludiˇstˇe, aby bylo moˇzn´e vyuˇz´ıt hru v pap´ırov´e podobˇe. Bludiˇstˇe na pap´ıˇre s v´ yhodou vyuˇzij´ı menˇs´ı dˇeti, kter´e jeˇstˇe neum´ı dostateˇcnˇe ovl´adat poˇc´ıtaˇc, pˇr´ıpadnˇe starˇs´ı dˇeti pˇredˇskoln´ıho vˇeku, kdy bludiˇstˇe sk´ yt´a moˇznost hrou zdokonalovat jejich psychomotorick´e dovednosti. Dˇeti se hrou uˇc´ı l´epe ovl´adat psac´ı potˇreby. Nastaven´ı Volbou nastaven´ı si uˇzivatel m˚ uˇze zvolit sv´e jm´eno, kter´e mu slouˇz´ı pˇri identifikaci sledov´an´ı dosaˇzen´ ych v´ ysledk˚ u nebo porovn´av´an´ı s protihr´aˇci. Tak´e vol´ı velikost bludiˇstˇe od 3 do 20, coˇz je poˇcet sloupc˚ u a ˇra´dk˚ u a jeho u ´roveˇ n v rozmez´ı 1 aˇz 3, kdy se vzr˚ ustaj´ıc´ım ˇc´ıslem vzr˚ ust´a obt´ıˇznost vygenerovan´eho bludiˇstˇe. Jednoduˇsˇs´ı bludiˇstˇe m´a v´ıce pˇr´ım´ ych chodeb, sloˇzitˇejˇs´ı bludiˇstˇe je spletit´e. D´ale v t´eto ˇc´asti aplikace uˇzivatel vol´ı poˇcet ˇzivot˚ u, kter´e m´a k dispozici a poˇcet nepˇra´telsk´ ych poj´ıdaˇc˚ u, kteˇr´ı ho ohroˇzuj´ı.
Obr´azek 10. Nastaven´ı bludiˇstˇe.
23
5.3.5.
V´ ysledky
Pokud chce uˇzivatel vidˇet sv´e dosaˇzen´e v´ ysledky, pˇr´ıpadnˇe porovnat je s protihr´aˇci, zvol´ı v menu volbu V´ ysledky. Zobrazuje se ˇcas, obt´ıˇznost a velikost bludiˇstˇe. V´ ysledky je moˇzn´e tˇr´ıdit vzestupnˇe a sestupnˇe podle jednotliv´ ych sloupc˚ u a filtrovat podle jm´ena hr´aˇce. Tlaˇc´ıtkem Vymazat se zruˇs´ı vˇsechny uloˇzen´e u ´daje.
Obr´azek 11. V´ ysledky hry.
5.3.6.
Stavov´ a liˇ sta
Stavov´a liˇsta se zobrazuje pˇri kaˇzd´em generov´an´ı bludiˇstˇe ve spodn´ım okraji aplikace. Poskytuje informace o nastaven´ı hry, jm´eno hr´aˇce, velikost a u ´roveˇ n bludiˇstˇe, kter´a byla pro danou hru vygenerov´ana. V pr˚ ubˇehu hry stavov´a liˇsta zobrazuje poˇcet zb´ yvaj´ıc´ıch ˇzivot˚ u a ˇcas uplynul´ y od poˇca´tku pˇr´ısluˇsn´e hry, ˇc´ımˇz umoˇzn ˇuje hr´aˇci sledovat ˇcasovou u ´spˇeˇsnost jiˇz v pr˚ ubˇehu hry samotn´e.
Obr´azek 12. Stavov´a liˇsta.
24
5.3.7.
Poj´ıdaˇ ci
Nastaven´ım poˇctu nepˇr´atelsk´ ych poj´ıdaˇc˚ u ve volbˇe Nastaven´ı m˚ uˇze hr´aˇc zpestˇrit hru. Poˇcet poj´ıdaˇc˚ u je moˇzn´e volit od 0 do 6. Pˇri vygenerov´an´ı bludiˇstˇe se poj´ıdaˇci objev´ı jako modr´e m´ıˇce na diagon´ale bludiˇstˇe. Pokud se hr´aˇc pˇri pr˚ uchodu bludiˇstˇem potk´a s poj´ıdaˇcem, ten ho m˚ uˇze zniˇcit a ubrat mu tak jeden ˇzivot. Pˇri ztr´atˇe vˇsech ˇzivot˚ u, hra konˇc´ı. Poj´ıdaˇci se v bludiˇsti pohybuj´ı n´ahodnˇe a je moˇzn´e jim uniknout.
Obr´azek 13. Poj´ıdaˇci v bludiˇsti.
25
5.4.
Generovan´ a trasa
Do programu byla vloˇzena moˇznost zobrazen´ı generovan´e trasy. Pˇri pouˇzit´ı volby v menuGenerovan´a trasa, spust´ıme uk´azku algoritmu, kter´ y bludiˇstˇe vygeneroval. Uˇzivatel tak m˚ uˇze vidˇet postup programu, jak´ ym bylo j´ım zvolen´e bludiˇstˇe vytvoˇreno. Pˇri v´ yvoji programu slouˇzila tato volba pro ladˇen´ı algoritmu.
Obr´azek 14. Generovan´a trasa.
26
6. 6.1.
Program´ atorsk´ a dokumentace Technologie
Aplikace je vytvoˇrena v programovac´ım jazyku C# s vyuˇzit´ım knihoven .NET Framework. Program Bludiˇstˇe byl vyvinut ve v´ yvojov´em prostˇred´ı Microsoft Visual Studio 2008. Data jsou ukl´ad´ana v souborech ve form´atu XML (Extensible Markup Language). 6.1.1.
Microsoft Visual Studio 2008
Microsoft Visual Studio je integrovan´e v´ yvojov´e prostˇred´ı. Obsahuje velk´e mnoˇzstv´ı v´ yvoj´aˇrsk´ ych n´astroj˚ u, designer webu a datab´az´ı a je v nˇem zahrnuto nˇekolik programovac´ıch jazyk˚ u. V tomto prostˇred´ı je moˇzn´e vytv´aˇret aplikace konzolov´e, grafick´e i webov´e. Obsahuje n´astroje pro ladˇen´ı a testov´an´ı. Tak´e podporuje XML/XSLT, HTML/XHTML, JavaScript a CSS. [5] 6.1.2.
C#
C# je modern´ı objektovˇe orientovan´ y jazyk, kter´ y umoˇzn ˇuje v´ yvoj´aˇr˚ um vytv´aˇret aplikace vyuˇz´ıvaj´ıc´ı .NET Framework. Aplikace nebˇeˇz´ı samostatnˇe, ale vyuˇz´ıvaj´ı runtime modul. V jazyku C# lze vytvoˇrit velk´e mnoˇzstv´ı program˚ u: konzolovou aplikaci, formul´aˇre syst´emu Windows, webov´e sluˇzby XML, distribuovan´e souˇca´sti, aplikace typu klient server, datab´azov´e aplikace a v posledn´ı dobˇe tak´e mobiln´ı aplikace. Visual C# obsahuje editor k´odu, rozˇs´ıˇren´e uˇzivatelsk´e rozhran´ı, integrovan´e ladic´ı a testovac´ı n´astroje a dalˇs´ıch n´astroje usnadˇ nuj´ı v´ yvoj aplikac´ı zaloˇzen´ ych na knihovn´ach .NET Framework. [6] 6.1.3.
.NET Framework
Rozhran´ı .NET Framework je platforma pro v´ yvoj aplikac´ı v prostˇred´ı Visual Studio. Sest´av´a z modulu CLR a knihovny tˇr´ıd .NET Framework. Modul CLR (Common Language Runtime) je z´akladem rozhran´ı .NET Framework. Runtime modul si lze pˇredstavit jako agenta, kter´ y spravuje k´od v dobˇe prov´adˇen´ı a poskytuje z´akladn´ı sluˇzby, jako je napˇr´ıklad spr´ava pamˇeti, spr´ava vl´aken, vzd´alen´a komunikace. Souˇcasnˇe tak´e zajiˇst’uje bezpeˇcnost typ˚ u a dalˇs´ı formy pˇresnosti k´odu, kter´e podporuj´ı bezpeˇcnost a robustnost program˚ u. Knihovna tˇr´ıd .NET Framework je vˇseobecn´ y, objektovˇe orientovan´ y soubor opakovanˇe pouˇziteln´ ych typ˚ u, kter´e lze pouˇz´ıt pro v´ yvoj aplikac´ı. Od tradiˇcn´ıch aplikac´ı pro pˇr´ıkazov´ y ˇr´adek nebo aplikac´ı s grafick´ ym uˇzivatelsk´ ym rozhran´ım (GUI) aˇz po nejnovˇejˇs´ı aplikace zaloˇzen´e na technologii ASP.NET, jako jsou napˇr´ıklad Webov´e formul´aˇre nebo webov´e sluˇzby XML. [7]
27
6.1.4.
XML (Extesible Markup Language)
XML je znaˇckovac´ı jazyk, kter´ y je zobecnˇen´ım znaˇckovac´ıch jazyk˚ u. Byl vyvinut a standardizov´an konsorciem W3C. Umoˇzn ˇuje jednoduch´e vytv´aˇren´ı konkr´etn´ıch znaˇckovac´ıch jazyk˚ u pro r˚ uzn´e u ´ˇcely a r˚ uzn´e typy u ´daj˚ u. Zpracov´an´ı XML je podporov´ano ˇradou n´astroj˚ u a programovac´ıch jazyk˚ u. Jazyk je urˇcen pro v´ ymˇenu dat mezi aplikacemi, pro publikov´an´ı dokument˚ u a jako u ´loˇziˇstˇe dat. Hlavn´ı v´ yhoda XML je v jeho hierarchick´e struktuˇre a v jednoduch´em zp˚ usobu z´apisu. Stejnˇe jako HTML pouˇz´ıv´a tagy a atributy, ale narozd´ıl od HTML nespecifikuje pˇresnˇe, co kter´ y tag znamen´a, pouˇz´ıv´a tagy pouze k ohraniˇcen´ı dat a zpracov´an´ı ponech´av´a na aplikaci. [8] Kaˇzd´ y HTML mus´ı dodrˇzovat syntaktick´a pravidla: • Obsah dokumentu mus´ı b´ yt uloˇzen v koˇrenov´em elemeny. • Kaˇzd´ y element je p´arov´ y. • Elementy se nesmˇej´ı kˇr´ıˇzit. 6.1.5.
Datov´ e zdroje
V programu jsou pouˇzity datov´e soubory XML verze 1.0 a k´odov´an´ı windows1250. V datov´ ych souborech je uloˇzeno nastaven´ı programu, v´ ysledky hry a jednotliv´a bludiˇstˇe. Soubory se naˇc´ıtaj´ı a ukl´adaj´ı metodami tˇr´ıdy FileIO.cs. Parsov´an´ı element˚ u zajiˇst’ujˇe tˇr´ıda XMLParser.cs.
28
6.2.
Aplikace
Programov´ y k´od v jazyku C# je zaloˇzen´ y na objektovˇe orientovan´em paradigmatu. Z´akladn´ıni stavebn´ımi kameny jsou tedy tˇr´ıdy a objekty. V pˇrehledu uv´ad´ım hlavn´ı tˇr´ıdy aplikace a v nich d˚ uleˇzit´e metody.
Obr´azek 15. Tˇr´ıdy.
6.2.1.
Tˇ r´ıdy
Tˇ r´ıda FormMain.cs Tˇr´ıda hlavn´ıho rodiˇcovsk´eho formul´aˇre aplikace, kter´a zobrazuje formul´aˇr. Obsahuje ovl´ad´an´ı aplikace a kontejner pro vykreslen´ı bludiˇstˇe a sdruˇzuje ostatn´ı tˇr´ıdy. Spuˇstˇen´ı hry. private void NewGame() Metoda pˇrevezme uˇzivatelsk´e nastaven´ı hry, vygeneruje podle nˇeho bludiˇstˇe a zavol´ a objekt tˇr´ıdy LabDraw pro vykreslen´ı bludiˇstˇe. Ukonˇcen´ı hry. private void StopGame() Metoda ukonˇc´ı hru a inicializuje objekty. Spuˇstˇen´ı ˇsablony. private void NewTemplate() Metoda nastav´ı ˇsablonu pro editaci bludiˇstˇe a zavol´a objekt tˇr´ıdy LabDraw pro vykreslen´ı ˇsablony.
29
Pohyb oranˇzov´eho m´ıˇce. private void PlayKeyStep(int KeyArrow) Metoda pˇrevezme vstup od uˇzivatele, rozhodne o pohybu m´ıˇce a zavol´a objekt tˇr´ıdy LabDraw pro vykreslen´ı bludiˇstˇe. Tˇ r´ıda LabDraw.cs Tˇr´ıda pro vykreslen´ı bludiˇstˇe. Pˇrevezme matici bludiˇstˇe z objektu tˇr´ıdy LabDiag a vykresl´ı bludiˇstˇe do kontejneru na tˇr´ıdy FormMain. Vytvoˇren´ı matice pro vykreslen´ı bludiˇstˇe. private void MakeMatrixD() Metoda na z´akladˇe vygenerovan´e matice v objektu tˇr´ıdy LabDiag vytvoˇr´ı matici pro vykreslen´ı bludiˇstˇe. Vykreslen´ı bludiˇstˇe. private void DrawAll(Graphics g) Metoda vykresl´ı bludiˇstˇe podle matice a um´ıst´ı oranˇzov´ y m´ıˇc. Vykreslen´ı generovan´e trasy. private void DrawRoute(Graphics g) Metoda vykresl´ı trasu, kter´a vznikne pˇri generov´an´ı bludiˇstˇe. Tˇ r´ıda LabDiag.cs Tˇr´ıda pro vygenerov´an´ı bludiˇstˇe. Obsahuje matici pro reprezentaci bludiˇstˇe grafem. Vytvoˇren´ı trasy. private void MakeRoute() Metoda vytvoˇr´ı trasu pro generov´an´ı bludiˇstˇe. Vytvoˇren´ı matice trasy. private void MakeRouteMatrix() Metoda ukl´ad´a generovanou trasu do matice. Nalezen´ı nov´e pozice. private void makeNewPosi(ref int x, ref int y, ref int[,] route, int exPosi) Metoda rozhoduje jak´a bude nov´a pozice pˇri generov´an´ı bludiˇstˇe. Tˇ r´ıda LabSave.cs Tˇr´ıda pro uloˇzen´ı a naˇcten´ı bludiˇstˇe. Uloˇzen´ı bludiˇstˇe. public void SaveRoute(int[,] inRoute) Metoda uloˇz´ı bludiˇstˇe do souboru XML.
30
Naˇcten´ı bludiˇstˇe. public void int[,] ReadRoute() Metoda naˇcte bludiˇstˇe ze souboru XML. Tˇ r´ıda Tˇ r´ıda FileIO.cs Tˇr´ıda pro vstupn´ı a v´ ystupn´ı rozhran´ı k soubor˚ um. Uloˇzen´ı nastaven´ı. private void SaveLabSetting(int DimX, int GenLevel, string NamePlayer) Metoda pˇrevezme nastaven´ı z objektu tˇr´ıdy FormSetting a uloˇz´ı do souboru XML. Naˇcten´ı nastaven´ı. private void ReadLabSetting(ref int DimX, ref int GenLevel, ref string NamePlayer) Metoda pˇreˇcte nastaven´ı ze souboru XML a pˇred´a je do objektu tˇr´ıdy FormSetting. Uloˇzen´ı hr´aˇce. private void SaveWinPlay(int DimX, int GenLevel, string NamePlayer, int FinishTime) Metoda pˇrevezme z objektu tˇr´ıdy FormMain u ´daje o nastaven´ı a dosaˇzen´em ˇcase a uloˇz´ı do souboru XML. Naˇcten´ı hr´aˇc˚ u. private void ReadWinPlayTab(ref Player[] tabPlayer) Metoda pˇreˇcte u ´daje o hr´aˇc´ıch ze souboru XML a pˇred´a je do objektu tˇr´ıdy FormResults. Tˇ r´ıda XMLParser.cs Tˇr´ıda pro parsov´an´ı XML ˇretˇezc˚ u. Naˇcten´ı hodnoty z elementu. public static void ElementToValue(string line, string element, ref string value) Metoda vybere hodnotu z dan´eho elementu XML a pˇred´a ji do objektu tˇr´ıdy FileIO. Uloˇzen´ı hodnoty do elementu. public static string ValueToElement(string value, string element) Metoda pˇrevezme hodnotu z objektu tˇr´ıdy FileIO a uloˇz´ı ji do elementu XML. Tˇ r´ıda Tˇ r´ıda FormResults.cs Tˇr´ıda pro zobrazen´ı v´ ysledk˚ u hry. Naˇcten´ı v´ ysledk˚ u. private void ReadWin() Metoda zavol´a objekt tˇr´ıdy FileIO a pˇrevezme objekty tˇr´ıdy Player.
31
Tˇ r´ıda Player.cs Tˇr´ıda hr´aˇc˚ u, kter´a v parametrech obsahuje uˇzivatelsk´e nastaven´ı a dosaˇzen´ y ˇcas pˇri pr˚ uchodu bludiˇstˇem. Uloˇzen´ı stavu hr´aˇce. public Player(string jmeno, int velikost, int uroven, int cas) Metoda pˇrevezme uˇzivatelsk´e nastaven´ı hr´aˇce a pˇred´a je do objektu tˇr´ıdy FileIO. Tˇ r´ıda Eaters.cs Tˇr´ıda poj´ıdaˇc˚ u. Nov´a pozice. public newPosi(int KeyArrow, Point p) Metoda nalezne novou pozici pro poj´ıdaˇce. Tˇ r´ıda FormSetting.cs Tˇr´ıda pro zobrazen´ı formul´aˇre nastaven´ı hry. Naˇcten´ı stavov´ ych parametr˚ u. public FormSetting(int DimX, int GenLevel, string NamePlayer) Metoda zavol´a objekt tˇr´ıdy FileIO a pˇrevezme uˇzivatelsk´e parametry.
32
6.3.
V´ yvoj aplikace
Stˇeˇzejn´ı ˇc´ast´ı v´ yvoje byla implementace algoritmu pro generov´an´ı bludiˇstˇe a jeho ladˇen´ı. Bylo potˇreba dos´ahnout toho, aby algoritmus v kaˇzd´em kroku vyb´ıral spr´avnˇe sousedn´ı uzly pravo´ uhl´e s´ıtˇe a aby tento v´ ybˇer byl n´ahodn´ y. V pˇr´ıpadˇe, ˇze pouˇzit´ y gener´ator n´ahodn´ ych ˇc´ısel vracel opakovanˇe stejn´a ˇc´ısla, generovan´a trasa si drˇzela jeden smˇer a bludiˇstˇe bylo pˇr´ıliˇs jednoduch´e. Na uk´azku lze tuto variantu v programu zvolit pomoc´ı u ´rovnˇe 1. Algoritmus mus´ı umˇet tak´e vygenerovat u ´pln´e bludiˇstˇe, mus´ı m´ıt koneˇcn´ y poˇcet krok˚ u a zpracov´an´ı nesm´ı trvat pˇr´ıliˇs dlouho. Dalˇs´ı d˚ uleˇzitou ˇc´ast´ı bylo vykreslen´ı bludiˇstˇe na obrazovce. Bylo potˇreba, aby algoritmus pro vykreslen´ı zpracoval bludiˇstˇe r˚ uzn´ ych velikost´ı. Program tedy pˇrepoˇc´ıt´av´ a parametricky vˇsechny souˇradnice pro vykreslen´ı a tak´e pohyb po bludiˇsti.
33
Z´ avˇ er ´ Ukolem t´eto bakal´aˇrsk´e pr´ace bylo vytvoˇren´ı poˇc´ıtaˇcov´e hry bludiˇstˇe, ve kter´em si uˇzivatel m˚ uˇze zadat vlastn´ı parametry. Program vykresl´ı bludiˇstˇe na obrazovku, pˇr´ıpadnˇe i vytiskne a umoˇzn´ı pr˚ uchod vygenerovan´ ym bludiˇstˇem. Aplikace je vhodn´a pro dˇeti pro svou uˇzivatelskou pˇr´ıvˇetivost a jednoduchost. Aplikaci je moˇzno do budoucna d´ale rozˇsiˇrovat a zdokonalovat. Jedn´ım z moˇzn´ ych smˇer˚ u dalˇs´ıho v´ yvoje aplikace jsem zvaˇzoval moˇznost paraleln´ı hry dvou hr´aˇc˚ u na dvou poˇc´ıtaˇc´ıch. Pˇr´ıpadnˇe generovat bludiˇstˇe i v jin´em neˇz pravo´ uhl´em tvaru a s jin´ ym propojen´ım cest v bludiˇsti. Rovnˇeˇz stoj´ı za zm´ınku moˇznost vyuˇzit´ı generovac´ıch algoritm˚ u i v jin´ ych aplikac´ıch. V neposledn´ı ˇradˇe lze aplikaci vyv´ıjet d´al pˇri pouˇzit´ı v´ ykonnˇejˇs´ıch grafick´ ych knihoven.
34
Conclusions The aim of this bachelor’s thesis was to create the computer game maze by userspecified parameters, render it to the screen or print out and enable the passage through the generated maze. The application is suitable for children for its user-friendliness and simplicity. In future, the application can be further expanded and improved. The possibility of the parallel play of two players on two computers is one of the considered possible directions of further development of the application. Alternatively, to generate a maze in the non-rectangular shape with a different connection of paths in the maze. The possibility of using generating algorithms also in other applications is also worth mentioning. Finally, the application can be developed further using more powerful graphics libraries.
35
Reference [1] Labyrint (bludiˇstˇe), posledn´ı revize 11.5.2013, citov´ano dne 2.6.2013 http://cs.wikipedia.org/wiki/Labyrint(bludiˇstˇe) ˇ [2] MYSLIVECEK Jarom´ır, Z´aklady neurovˇed, 2.vyd´an´ı, Triton, Praha, 2003 ISBN 978-80-7387-088-1 ˇ [3] VECERKA Arnoˇst: Grafy a grafov´e algoritmy, skripta PˇrF UP, 2007 [4] Z´akladn´ı grafov´e algoritmy, posledn´ı revize 2013, citov´ano dne 10.6.2013 http://algoritmy.eu/zga/ [5] Microsoft Visual Studio 2008, posledn´ı revize 2013, citov´ano dne 20.7.2013 http://www.microsoft.com/cze/msdn/ [6] Jazyk C#, posledn´ı revize 2013, citov´ano dne 20.7.2013 http://www.microsoft.com/cze/msdn/ [7] .NET Framework, posledn´ı revize 2013, citov´ano dne 20.7.2013 http://www.microsoft.com/cze/msdn/ [8] Jazyk XML, posledn´ı revize 4.5.2013, citov´ano dne 20.7.2013 http://sk.wikipedia.org/wiki/XML/ [9] Obr´azky ˇcerp´any z internetov´ ych str´anek: http://algoritmy.eu/zga/ http://cs.wikipedia.org/wiki/Labyrint(bludiˇstˇe) http://en.wikipedia.org/wiki/Mazegenerationalgorithm http://en.wikipedia.org/wiki/Maze [10] SELLS Chris: C# a WinForms, 1.vyd´an´ı, Zoner Press, 2005 ISBN 80-86815-25-0 [11] TROELSEN Andrew: C# a .NET 2.0, 1.vyd´an´ı, Zoner Press, 2006 ISBN 80-86815-42-0
36
7.
Pˇ r´ıloha A - Obsah pˇ riloˇ zen´ eho CD Souˇc´ast´ı bakal´aˇrsk´e pr´ace je i CD, kter´e obsahuje n´asleduj´ıc´ı adres´aˇre: • Adres´aˇr bin obsahuje aplikaci. • Adres´aˇr doc obsahuje dokumentaci bakal´aˇrsk´e pr´ace. • Adres´aˇr src obsahuje zdrojov´e k´ody. • Soubor readme.txt obsahuje postup pro spuˇstˇen´ı aplikace.
37
