Generování bludiště v Excelu

Bludiště lze generovat i v Excelu pomocí maker. Zde je doknoce jednodušší způsob vykreslování výsledného labiritnu, tj. pomocí orámování jednotlivých buněk, takže výsledný kód je celkem jednoduchý.

Nejprve si deklarujeme pomocné proměnné, které budeme opakovaně používat. Jejich hodnoty budou nastaveny až v hlavní metodě a všechny budou typu jednorozměrné pole (posloupnost), neboli Array o počtu členů 4, s indexy 0, 1, 2 a 3. Tyto indexy budou ve všech případech vztaženy k jednomu ze čtyř směrů a to od shora ve směru hodinových ručiček (0 = nahoru, 1 = vpravo, 2 = dolů, 3 = vlevo). Proměnná Ramy bude obsahovat konstanty pomocí kterých se dá v Excelu odkazovat na příslušné strany buňky, například pokud jim je třeba nastavit orámování (Border). Proměnná PosunX pro jednotlivé směry určuje posun po ose X (po sloupcích, -1 vlevo a +1 vpravo) a proměnná PosunY definuje totéž pro osu Y (po řádcích, -1 nahoru a +1 dolů).

Dim Ramy, PosunX, PosunY                    ' Pomocné proměnné na konstantní hodnoty typu 1D pole

Následně vytvoříme hlavní metodu VytvorBludiste, kterou se bude celý proces spouštět. Ta v první řadě nastaví generátor pseudonáhodných hodnot a definuje hodnoty pomocných proměnných. Následně připraví plochu pro generování bludiště a to tak, že nastaví barvu všech označených buněk na šedivou a orámuje je. Šedivá barva bude totiž použita jako příznak, že daná buňka této barvy dosud nebyla zpracována. Po zpracování se barva buňky změní zpět na bílou. Orámování pak signalizuje zdi bludiště, v nichž se postupně bude vytvářet cesta tak, že se některé z nich zruší. Nakonec se zahájí generování bludiště zpracováním první buňky (metodou ZpracujBunku), přičemž začátek bude určen aktivní buňkou (ActiveCell a souřadnicemi jejího řádku a sloupce).

Sub VytovrBludiste()                        ' Hlavní metoda zahajující generování bludiště
    Randomize                               ' Reset generátoru pseudonáhodných hodnot
    Ramy = Array(xlEdgeTop, xlEdgeRight, xlEdgeBottom, xlEdgeLeft) ' Jednotlivé typy stran buňky (pro orámování)
    PosunY = Array(-1, 0, 1, 0)             ' Posun po ose Y pro daný směr (NPDL)
    PosunX = Array(0, 1, 0, -1)             ' Posun po ose X pro daný směr (NPDL)

    Selection.Interior.Color = rgbSilver    ' Nastavení příznaku "nezpracovaní" všem označeným polím
    For Each ram In Ramy                                           ' Pro všechny hodnoty v posloupnosti Ramy...
        Selection.Borders(ram).LineStyle = xlContinuous            ' Nastavit plné orámování na příslušnou stranu buňky
    Next ram
    Selection.Borders(xlInsideVertical).LineStyle = xlContinuous   ' Nastavit plné vertikální orámování i buňkám uvnitř výběru
    Selection.Borders(xlInsideHorizontal).LineStyle = xlContinuous ' Nastavit plné horizontální orámování i buňkám uvnitř výběru
    
    Call ZpracujBunku(ActiveCell.Row, ActiveCell.Column)           ' Zahájit generování bludiště zpracováním prvního políčka na aktuální buňce
End Sub

Metoda ZpracujBunku má za úkol zpracovat jednu buňku bludiště a "poslat to dál". Konkrétně v této buňce, určené souřadnicemi (vstupními parametry) x a y, zruší příznak, že dosud nebyla zpracovaná, tzn. zruší její šedivé obarvení zpět na bílé (bez výplně). Následně načte do proměnné smery prostřednictvím níže definované funkce NahodneSmery jednorozměrné pole obsahující čísla jednotlivých čtyř směrů (0-3), ovšem v náhodném (pokaždé jiném) pořadí. Pod indexem 0 tak může být kterýkoli ze směrů (0,1,2 nebo 3), ale každý z nich bude v posloupnosti smery pouze 1x. Tuto posloupnost pak cyklem For Each projdeme od prvního prvku (na indexu 0) do posledního (na indexu 3). Pro každý ze čtyř směrů určíme souřadnice buňky, na kterou bychom se tímto směrem dostaly, do proměnných nx a ny. Pro tyto nové souřadnice pomocí níže definované funkce VolnaBunka ověříme, zda je buňka na těchto souřadnicích platnou součástí bludiště a nebyla dosud zpracována. Pokud tomu tak je, tak zrušíme orámování v aktuální buňce tímto směrem (otevřeme průchod z buňky [x, y] do buňky [nx, ny]) a stejným způsobem zpracujeme i tuto sousední buňku. Toho docílíme rekurzivním voláním téže metody ZpacujBunku, ovšem tentokrát pro souřadnice nx a ny.

Ukázka zpomaleného generování bludiště v ExceluTímto způsobem se tedy bude zpracovávat neustále další a další buňka v náhodném směru od té předchozí, až se zpracování dostane do slepé uličky, neboli v žádném ze čtyř směrů již nebude žádná nezpracovaná buňka, která by byla součástí plochy bludiště. V tom případě se již žádné její orámování nezruší a ani zpracování dál nepředá. Řízení chodu programu tak bude vráceno předchozímu volání této metody, která se pokusí zpracovat další náhodný směr v pořadí. Toto volání tak může "vybublat" i o několik volání metody výše najednou, třeba klidně až k tomu prvnímu, které proběhlo z metody VytvorBludiste. Až ani toto první volání metody ZpracujBunku nebude mít možnost posunu žádným dosud nezpracovaným směrem, celá procedura generování skončí a bludiště bude hotovo. V takto generovaném bludišti by nemělo žádné z jeho políček zůstat nedostupné a zároveň by na žádné z nich neměla vést více než jedna cesta (pomineme-li vracení se), tzn. bludiště nebude obsahovat žádné smyčky, tj. útvary zdí neukotvené k celkové soustavě zdí.

Zakomentovaný řádek (Application.Wait...) skrývá funkci, kterou pokud aktivujete (odkomentujete), tak se celý proces po každém odbarvení aktuálně zpracovávané buňky na jednu sekundu zastaví. Můžete tak celý postup sledovat zpomaleně, např. za účelem lepšího pochopení jeho fungování. Použitá funkce ovšem pozastavuje celé hlavní vlákno aplikace, tzn. že okno celého Excelu čeká na kompletní dokončení operace a do té doby je jakoby zaseknuté (na nic nelze kliknout, kurzor myši naznačuje čekání na dokončení činnosti, makro nelze zastavit jinak než přes správce úloh vypnout celý Excel apod.). Není tedy dobré mít tento řádek odkomentovaný pro větší plochy bludiště, protože proces je pak velmi zdlouhavý.

Private Sub ZpracujBunku(y, x)                     ' Zpracuje jednu buňku bludiště a zpracování pošle dál do všech 4 směrů v náhodném pořadí
    Cells(y, x).Interior.Pattern = xlNone          ' Zrušení vybarvení buňky, tj. příznaku, že buňka dosud nebyla zpracována
    'Application.Wait (Now + TimeValue("0:00:01")) ' Pozastavení běhu programu na 1 sekundu
    smery = NahodneSmery()                         ' Načtení seznamu všech 4 směrů v náhodném pořadí (jako 1D pole s indexy i hodnotami 0-3)
    For Each smer In smery                         ' Pro všechny směry (náhdoně seřazené) v poli
        ny = y + PosunY(smer)                      ' Y souřadnice sousední buňky v daném směru
        nx = x + PosunX(smer)                      ' X souřadnice sousední buňky v daném směru
        If VolnaBunka(ny, nx) Then                 ' Je tato sousední buňka v mezích sešitu, rozsahu bludiště a nebyla ještě zpracována?
            Cells(y, x).Borders(Ramy(smer)).LineStyle = xlNone  ' Zrušení orámování mezi aktuální buňkou a buňkou sousednící v daném směru
            Call ZpracujBunku(ny, nx)              ' Rekurzivní volání této metody, aby stejným způsobem zpracovala i tuto sousední buňku
        End If
    Next smer
End Sub

Funkce NahodneSmery, použitá v předchozí metodě ZbracujBunku, tedy vrací posloupnost (jednorozměrné pole) se čtyřmi (indexy 0-3) náhodně zamíchanými celými čísly v rozsahu 0-3, přičemž každé z nich je tam právě jednou. Hodnoty členů této posloupnosti přitom vyjadřují jednotlivé směry dle výše popsaného mechanizmu. Funkce nejprve definuje jednorozměrné pole (Array) se čtyřmi členy, což jsou hodnoty jednotlivých směrů v klasickém pořadí (0-3) a ty pak následně zamíchá. Míchání hodnot v posloupnosti probíhá tak, že se pro každého jejího člena vygeneruje nový náhodný index (v rozsahu 0-3), který pokud je jiný než stávající, tak se hodnoty členů na indexu stávajícím (i) a náhodně vygenerovaném (Index) prohodí, s využitím pomocné (odkládací) proměnné p.

Ve for cyklu jsou použity funkce LBound, která vrací nejnižší index zadané posloupnosti (0) a UBound, která vrací nejvyšší index zadané posloupnosti (v tomto případě 3). Náhodný index je generovaný pomocí funkce Rnd (zkratka od random number = náhodné číslo), která vrací náhodné desetinné číslo v otevřeném intervalu (0, 1). Vynásobením této hodnoty s číslem 4 tak získáme desetinné číslo mezi 0 a 3,99999... Useknutím desetin funkcí Int (zkratka od integer = celé číslo) tak získáme jedno z celých čísel 0, 1, 2 nebo 3, tj. index pro prohození aktuálně zpracovávaného člena posloupnosti. Převedení na celé číslo "useknutím" desetin je v tomto případě vhodnější než zaokrouhlením, protože při useknutí mají všechna výsledná náhodná čísla stejnou pravděpodobnost vybrání (maní tzv. rovnoměrné rozdělení). Při zaokrouhlení by se ovšem musela jednak snížit horní hranice (násobitel) na 3,5 a navíc by číslo 0 mělo pouze poloviční pravděpodobnost vygenerování oproti ostatním číslům (pro 0 by byla pouze čísla v intervalu 0-0,4999, kdežto pro např. 1 by byl tento interval dvojnásobný: 0,5-1,4999).

Private Function NahodneSmery()             ' Vygeneruje 1D pole (posloupnost) čísel čtyř směrů (0-3) v náhodném pořadí (např. 2310 nebo 1032 apod.)
    smery = Array(0, 1, 2, 3)               ' Vytvoření 1D pole s hodnotami odpovídajícími jejich indexům (0=Nahoru, 1=Vpravo, 2=Dolů, 3=Vlevo)
    For i = LBound(smery) To UBound(smery)  ' Projít všechny členy tohoto pole se směry
        Index = Int(Rnd * 4)                ' Vygeneruje náhodné celé číslo v rozsahu 0-3
        If (Index <> i) Then                ' Pokud je číslo jiné než index aktuálně zpracovávaného člena posloupnosti, tak prohoď jejich hodnoty
            p = smery(i)                    ' Uložit si hodnotu člena na indexu "i" do pomocné proměnné "p"
            smery(i) = smery(Index)         ' Zkopírování hodnoty člena z indexu "index" do člena na indexu "i"
            smery(Index) = p                ' Hodnotu z pomocné proměnné "p" nastavit členovi posloupnosti na indexu "index"
        End If
    Next i
    NahodneSmery = smery                    ' Nastavení výstupní hodnoty funkce na vygenerovanou posloupnost
End Function

Funkce VolnaBunka, taktéž použitá v předchozí metodě ZbracujBunku, vrací logickou hodnotu (true - pravda nebo false - nepravda), jež vyjadřuje, je-li buňka na souřadnicích zadaných vstupními parametry funkce (x a y) volná či nikoli. Konkrétně se testuje, jestli souřadnice neukazují za hranice Excelového listu (resp. za jeho levý či horní okraj) a jsou-li stále uvnitř (obě souřadnice jsou větší či rovné 1). Pak je buňka volná pouze v případě, že je její barva pozadí šedivá (rgbSilver), tj. taková, jak jsme si ji v rámci přípravné fáze v metodě VytvorBludiste obarvili.

Private Function VolnaBunka(y, x)      ' Ověření buňky na daných souřadnicích, je-li v mezích sešitu, rozsahu bludiště a nebyla-li ještě zpracována
    If (x >= 1 And y >= 1) Then        ' Nepřesahují dané souřadnice okraj sešitu?
        VolnaBunka = Cells(y, x).Interior.Color = rgbSilver  ' Výsledek = True, pokud je buňka šedivá, tj. má příznak, že dosud nebyla zpracována
    Else
        VolnaBunka = False             ' Buňka mimo hranice není nikdy volná (dotupná pro zpracování)
    End If
End Function

Pro vygenerování bludiště je tedy třeba označit určitou oblast buněk a spustit makro VytvorBludiste (mělo by být jediné nabízené pro přímé spuštění ze seznamu maker). Aby bludiště lépe vypadalo, resp. vůbec vypadalo jako bludiště, je také třeba sloupcům a řádkům nastavit přibližně stejný rozměr (v pixelech), aby místo obdélníkových buněk vznikly buňky čtvercové. Zdi bludiště také lépe vyniknou, skryje-li se mřížka (na záložce Zobrazení). Výběr oblasti (označení buněk), ve které se bude generovat bludiště přitom nemusí být jen obyčejný obdélník. Pomocí klávesy Ctrl (Control) a myši lze vybírat více takovýchto obdélníkových oblastí, které by na sebe však měly navazovat. Kliknutím do již označené oblasti s držením klávesy Ctrl také lze změnit aktivní buňku v rámci této označené oblasti. Z této buňky pak generování bludiště začne, takže jde o dobrého kandidáta na začátek pro následné hledání cesty bludištěm. Cíl (buňku kam se má z té výchozí hráč dostat) pak lze zvolit libovolně, buď intuitivně, nebo nalezením buňky nejvzdálenější od té počáteční. S tím by mohl pomoci algoritmus pro její nalezení (podnebný tomu generovacímu), který si ukážeme třeba zase někdy příště.

Postup generování 1 Postup generování 2 Postup generování 3

Pozn.: Microsoft Excel a jeho makra mají celkem znatelně omezený zásobník pro adresaci rekurzivního volání metod a funkcí. Proto se při generování bludiště do větších ploch může stát, že po chvíli makro skončí zaseknutím s chybou "Out of stack space" (nedostatek místa v zásobníku). To je možné obejít např. vytvářením menších bludišťových ploch, které lze následně propojit odebráním jedné z příček dělících obě sousedící plochy dvou bludišť.

Bludiště vygenerované v Excelu Bludiště vygenerované v Excelu

Bludiště vygenerované v Excelu Bludiště postupně vygenerovaná v Excelu

Generování bludiště v Excelu - nepravydelný výběr 1a Generování bludiště v Excelu - nepravydelný výběr 1b

Generování bludiště v Excelu - nepravydelný výběr 2a Generování bludiště v Excelu - nepravydelný výběr 2b

Bludiště vygenerované v Excelu

Bludiště vygenerované v Excelu

on 19 březen 2016