Moje nová hra! Bludišťovka Anny’s Lab

Když jsem se letos (rok 2012) někdy koncem června vrhl na C++ s tím, že se jej přes prázdniny naučím, ať toho nemám poté v zimním semestru moc, opět jsem plánoval jaký to větší projekt si v něm napíši. Původně jsem si chtěl reimplementovat knihovnu clmg (Common Lisp Micro Graphics) sloužící k jednoduché grafice na základě objektové struktury, kterou jsem používali v Předmětu Paradigmata Programování 2.

Logo Anny's Lab
Logo Anny’s Lab

Ale přecházet z okenního rozhraní do klasického textového terminálu není u grafické knihovny úplně to nejideálnější a tak mi z clmg zůstala jen třída Point. Poté jsem si k ní začal dopisovat další tři třídy a bludišťovka se pomalu začala rýsovat.

Pod původním názvem Labyrinth tak začala vznikat obyčejná konzolová bludišťovka pro večery na chatě, kde nemám internet, nebo na přednášky, kde internet obvykle mám, ale zase mi většinou nestačí baterie notebooku na nějaké náročnější grafické hry.

Postupem času mi název Labyrinth přišel poněkud nevhodný a obyčejný (i když se zpětně zamyslím nad názvy Drag race a Předměstí Simulátor, nebylo by to nic neobvyklého). Vzhledem k tomu, že postavička, která se v labyrintu pohybuje je reprezentována zavináčem, vznikl návrh na zakomponování nějakého jména začínajícího na ‚A‘ do názvu programu. Když jsem hledal vhodný  znak, kterým se budou vykreslovat zdi, mi ze spousty znaků, které jsem zkoušel, padlo do oka velké písmeno W, které až náramně připomíná nějakou rostlinu nebo keřík.

Naštve
Naštve

A bylo jasno.  Mí skalní fanoušci navíc totiž ví, že do každého svého programu zakomponovávám nějakou osobu ženského pohlaví z mého okolí. A není proto divu, že předmětem kampaně Anny’s Lab se stala bioložka Anny pracující ve své laboratoři, které se poněkud přemnožil zmutovaný a geneticky upravený jinak úplně obyčejný trávník, který podobně jako v pohádce o Šípkové Růžence zaroste celým areálem (a vytvoří tak labyrint, kterým se musí Anny dostat ven). Od té doby jsem Anny’s Lab nenazýval jinak, než „Anča a Lenča“.

Kampaň je však jen jedna z mála funkcí, kterou Anny’s Lab nabízí. Celá hra je vlastně založená na tom, že se zvolí tzv. číslo labyrintu, podle kterého je poté labyrint náhodně vygenerován. Můžete tak hrát téměř nekonečný počet různých náhodných a pseudonáhodných labyrintů, různých velikostí a uspořádání.

Jednoduchý labyrint
Labyrint s jednoduchou strukturou

Vzhledem k tomu, že hra byla komplet vyvíjena na platformě GNU/Linux, je linuxu přímo šita na míru. Naopak na Windows s ní byly nemalé komplikace. Bohužel právě proto si nebudete moct pořádně užít hru Anny’s s použitím knihovny ncurses, kdy se hra vůbec neseká, každou klávesu nemusíte potvrzovat Enterem a dokonce se setkáte i se skromným barevným provedením.

Program používá starou knihovnu z MS DOS, kterou však na Windows za boha neseženete, zatímco na Linuxu ji nainstalujete jedním příkazem.

Střeva programu

Program je sice oficiálně psán v jazyce C++, já osbně bych spíš použil označení C/C++. Když jsem totiž chtěl načítat stisknuté klávesy bez potvrzování Enterem, vygooglil jsem funkci getch() z knihovny ncurses. Jenže tato knihovna byla určená pro jazyk C a nikoliv C++, takže většina vstupně-výstupních operací je realizována funkcemi jako printw a getch, držel jsem se standartu a kde nebyla použita knihovna ncurses, používal jsem funkce z knihovny cstdio – printf, getchar  a podob.

Čistého času jsem na Anny’s Lab pracoval něco kolem dvou a půl měsíce, kde z toho jsem ale fyzicky pracoval v průměru tak hodinu až dvě denně (to víte, prázdniny). Asi vás nepřekvapí, že nejvíce času padlo na jádro celé aplikace – metoda třídy Map na generování labyrintu.  Chtěl jsem být profesionální a najít si nějaký slušný algoritmus na generování. Tato diplomová práce věnující se přesně této problematice  mě však pouze přesvědčila, že opravdu nejlepším řešením bude úplně obyčejný hloubkově rekurzivní algoritmus typu „horník“.

První hra
První dohraná hra (17. srpna), můžete vidět tuny ladících výpisů

Nicméně pořád jsem je v reálném čase nedostal na Labyrint větší než 800×800. A bylo mi naprosto jasné proč. Ta metoda, která se starala o průchod jedním uzlem je sice na pochopení velmi jednoduchá, ale implementačně poněkud složitější. Neustálé kopírování konstantních parametrů a vytváření stále nových proměnných, jako iterační proměnná i na začátku každého volání zkrátka zbytečně žerou obrovské množství času.

Začal jsem tedy vzpomínat na cvičení z algoritmiky, jak přepsat hloubkovou rekurzi. Nejdřív jsem si ji přepsal použitím fronty na průchod do šířky, dokázal jsem generovat labyrint až do velikosti asi 12000×12000, nicméně vypadal jak hvězdice se středem ve startu. Po několika dnech intenzivního algoritmování jsem na to přišel.

Na zásobník si bude ukládat vždy čtveřici uzlů, do kterých se vydat (v pospřeházeném pořadí), také uzel, ze kterého se do tohoto „aktuálního“  došlo a ukazatel (index i), kterým z těch směrů se má nyní vydat. Pokud došel do validního uzlu, vytvořil si posloupnost s ním sousedících, spolu s ní na zásobník uložil bod, ze kterého tam došel, a index prvního z nich, načeš se do něj hned vydá. Pokud validní uzel nenašel, šel na další v pořadí (zvýšil index aktuálního uzlu o 1) a pokud další takový nebyl (byl poslední), odebere tuto celou skupinu ze zásobníku a jde o úroveň výš.

Toto řešení je taktéž celkem elegantní (obzvlášť, když je v C++ zásobník implementován ve standartní knihovně), a především velmi efektivní. Paměť mi většinu dojde, až když se snažím generovat labyrint větší než 14000×14000.

Až nebudu mít týden co dělat, nakoupím energiťáky, nachystám si rozvoz pizzy na rychlou volbu, vygeneruju si labyrint 10000×10000 a budu hrát…

Zbytek už byl celkem hračka. Až na pár drobností, jako třeba metoda, která k uzlu vrátila některý náhodný sousední uzel tak, aby ležel na mapě. Nejdřív jsem se snažil testovat, jestli není moc blízko okraji mapy, ale kraje mapy jsou 4 a navíc se můžou kombinovat (rohy), takže po asi 20 řádkách testování a ifování, jsem skončil tím, že jsem náhodně vygeneroval některý z okolích bodů (na to stačily 2 řádky) a to opakoval, dokud se tento náhodný uzel nenacházel v mapě.

Docela mě překvapilo i parsování argumentů z příkazové řádky. Když jsem si uvědomil, jako všelijaké kombinace chybných stavů můžou nastat, sáhl jsem až na dno kapsy a vytáhl výjimky a díky nim se kód rozrostl o pouhých 240 řádků.

A úplně zabilo, když jsem vlastně poprvé tvořil program rozdělený do více souborů (což jsem poněkud nešikovně dělal úplně nakonec), a vůbec to nechtělo fungovat. Nedošlo mi, že se soubory (a tedy i bloky funkcí celého programu) na sobě sice závisí, ale víceméně řetězovitě a ne každý na všech ostatních. Takže soubor s deklaracemi maker je naprosto nezávislý a tak jde zkompilovat rovnou. Na něm závisí soubor s deklaracemi všech funkcí, na něm pak definice pomocných funkcí, díky ní pak půjdou zkompilovat třídy Point a DrawabePoint, … až přes definice hlavních, „jaderních“ funkcí (a z nich ta úplně nejhlavnější – Hlavní Menu) až po samotnou funkci main.

Pak už stačilo jen napsat Makefile (a dva dny řešit, proč to nelinkuje knihovnu ncurses, ikdyž ji jistojistě inkluduji), zabalit, zkompilovat i na Windows (i to byla celkem estráda) no a napsat to, co si nyní čtete.

Ke stažení

Ke stažení dodávám jak zkompilované verze pro MS Windows, tak i balíčky zdrojových kódů pro obě platformy.

Anny’s Lab Verze pro Windows 32bit (.exe)

Anny’s Lab Verze pro Windows 64bit (.exe)

Kdo má koule na labyrint 5000x5000?
Kdo má koule na labyrint 5000×5000?

Anny’s Lab je totiž distribuován pod licencí GNU/GPL a je Open Source, tedy je volně ke stažení včetně zdrojových kódů.

Zdrojové kódy Pro Windows (Přibalen soubor pro Microsoft (c) Visual Studio)

Zdrojové kódy Pro Linux (Přibalen Makefile)

Ty předkládám především pro uživatele operačního systému GNU/Linux – v programu je přibalen také Makefile a tak si jej prostě zkompilujete pomocí programu make.

Pokud nemáte nainstalovanou knihovnu ncurses, musíte programu make říct, že Anny’s Lab funkce z ncurses nemá používat a to:

Nebo zakomentováním řádku

v souboru declarations.cpp. Více o používání knihovny v souboru COMPILATION a v hlavičkových komentářích souborů declarations.cpp a main.cpp.

 

 

2 thoughts on “Moje nová hra! Bludišťovka Anny’s Lab

  1. Hezké! 🙂 … Jen se mi moc nelíbí nepřehlednost bludiště. Je to možná stylové, patří to ke konzolové hře, možná to byl záměr, ale do příští verze bych se přimlouval k použití rámečkových „box“ znaků – ═══╗╚═══ ░▒▓▎▍▆ a podobných 😉

    1. jasně no… On už docela neesteticky vypadá i poměr výšky a šířky jednoho znaku (a s tím nenaděláš téměř opravdu nic). Ale až rozchodím ncurses i na windows, šel bych určitě do vere 1.1 (už mám pár dalších nápadů na vylepšení) 😉

Napsat komentář: m@rtlin Zrušit odpověď na komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *

Tato stránka používá Akismet k omezení spamu. Podívejte se, jak vaše data z komentářů zpracováváme..