Hledání nejkratší cesty v bludišti

Než se pustíme do bludišť, ukaž si dvě úplně základní věci, na kterých stojí všechny dnešní algoritmy.

Tady si ukážeme, že bludiště je vlastně jen tabulka políček. Počítač jde řádek po řádku a každému políčku přiřadí symbol, třeba zeď nebo volnou cestu. Když pak stejným způsobem zvýrazníš start a cíl, hned vidíš, kde cesta začíná a kam má vést. Je to jednoduchý základ, na kterém stojí všechny další ukázky.

Naivní brute-force zkouší jednu možnost za druhou, úplně všechny cesty, které v bludišti existují. Je to trochu jako člověk, který chodí skoro naslepo a postupně si pamatuje, kudy už šel. Nakonec na východ často narazí, ale mezitím vyzkouší hromadu slepých odboček. U trochu většího bludiště by to počítači trvalo mnohem déle, než bys čekal u obrazovky. Proto je fajn znát chytřejší postupy.

BFS se šíří od startu do všech stran najednou, jako kruhy na vodě nebo malý požár políčko po políčku. Nejdřív prozkoumá všechna políčka vzdálená o 1 krok, potom všechna o 2 kroky, pak o 3 a dál. Díky tomu jako první najde cestu, která je opravdu nejblíž v počtu kroků. Nemusí si pamatovat celé možné trasy dopředu, stačí si ukládat, odkud na které políčko přišel. Pak cestu jednoduše složí zpátky od cíle.

Dijkstra je podobná BFS, ale počítá s tím, že ne každý krok stojí stejně. Někde jdeš po normální cestě levně, jinde třeba přes bažinu za větší cenu. Algoritmus proto nepokračuje jen „dalším v řadě“, ale vždy z místa, které má zatím nejnižší cenu. Je to jako vybírat trasu, která tě stojí méně času nebo energie, ne jen trasu s nejmenším počtem ulic. Proto může vyhrát i delší cesta, pokud je levnější.

Zadání:

1. Dokonči funkci vykresli, aby zobrazila mapu pomocí emoji.
   💡 Poradit

   Projdi mapu dvěma cykly: vnější přes řádky, vnitřní přes sloupce. Pro každé políčko vyber emoji a nasbírej je do seznamu znaky.
   Jeden hotový řádek vyrobíš spojením znaků: radek = "".join(znaky).
   Hotové řádky si ukládej do seznamu radky.
2. Označ start zeleně a cíl červeně.
   💡 Poradit

   Barvu řeš pořadím podmínek: start a cíl testuj dřív než zeď a volné políčko, jinak je přebije.
   if p == start_pos: znaky.append("🟩")
elif p == cil_pos: znaky.append("🟥")
p je dvojice (r, c) aktuálního políčka.
3. (Volitelně navíc) Doplň sousedi a vypiš je pro políčko ze st.selectbox.
   💡 Poradit

   Soused je políčko o jeden krok nahoru, dolů, doleva nebo doprava — tedy 4 posuny (-1, 0), (1, 0), (0, -1), (0, 1).
   Pro každý posun spočítej nr = r + dr a nc = c + dc.
   Nech jen ta políčka, která jsou uvnitř mapy a nejsou zeď.

Očekávaný výsledek: na mapě je jasně vidět start/cíl a umíš zjistit dostupné kroky z vybraného místa.

def vykresli(maze, start_pos, cil_pos, navstivene=None):
    navstivene = navstivene or set()
    radky = []

    for r in range(len(maze)):
        znaky = []
        for c in range(len(maze[0])):
            p = (r, c)
            if p == start_pos:
                znaky.append("🟩")
            elif p == cil_pos:
                znaky.append("🟥")
            elif maze[r][c] == 1:
                znaky.append("⬛")
            elif p in navstivene:
                # ...doplň...
                pass
            else:
                znaky.append("⬜")
        radky.append("".join(znaky))

    return "\n".join(radky)


def sousedi(maze, pozice):
    r, c = pozice
    kroky = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    vysledek = []

    for dr, dc in kroky:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < len(maze) and 0 <= nc < len(maze[0]) and maze[nr][nc] == 0:
            # ...doplň...
            pass

    return vysledek

Zadání:

1. Doplň rekurzivní funkci, která zkouší cesty ze startu do cíle.
   💡 Poradit

   Udělej si vnořenou funkci rek(pozice, cesta, visited). Když jsi v cíli, cestu si zapamatuj a vrať se.
   Jinak zkoušej sousedy, kteří ještě nejsou ve visited — krok dočasně přidej a po návratu z rekurze ho zase vrať zpět (pop() a remove()).
2. Počítej, kolikrát se rekurze zavolá.
   💡 Poradit

   Počitadlo si drž mimo rekurzi a uvnitř ho zvyš hned na začátku každého volání.
   Před rekurzí: pocet_volani = 0, uvnitř funkce nonlocal pocet_volani a pocet_volani += 1.
   Bez nonlocal by se ti hodnota ven nepropsala.
3. (Volitelně navíc) Ulož nejkratší nalezenou cestu.
   💡 Poradit

   Drž si proměnnou nejkratsi = None a v cíli porovnej délku právě nalezené cesty: když je nejkratsi ještě prázdné nebo je nová cesta kratší, ulož nejkratsi = list(cesta).
   Kopii (list(cesta)) uděláš proto, že se cesta dál mění.
4. (Volitelně navíc) Porovnej malou a větší mapu a přidej limit volání.
   💡 Poradit

   Stačí porovnat počty volání na malé a větší mapě — uvidíš, jak rychle číslo roste.
   Aby aplikace nezamrzla, přidej pojistku: když pocet_volani přesáhne limit, nastav zastaveno = True a z rekurze se rovnou vracej.

Očekávaný výsledek: na malé mapě najdeš cestu a na číslech uvidíš, proč brute-force rychle zpomaluje.

def najdi_bruteforce(maze, start_pos, cil_pos, limit=120000):
    nejkratsi = None
    pocet_volani = 0
    zastaveno = False

    def rek(pozice, cesta, visited):
        nonlocal nejkratsi, pocet_volani, zastaveno
        if zastaveno:
            return

        pocet_volani += 1
        if pocet_volani >= limit:
            zastaveno = True
            return

        if pozice == cil_pos:
            if nejkratsi is None or len(cesta) < len(nejkratsi):
                nejkratsi = cesta.copy()
            return

        for dalsi in sousedi(maze, pozice):
            if dalsi not in visited:
                visited.add(dalsi)
                cesta.append(dalsi)
                # ...doplň...
                cesta.pop()
                visited.remove(dalsi)

    # ...doplň...
    return nejkratsi, pocet_volani, zastaveno

Zadání:

1. Doplň BFS: frontu a množinu navštívených políček.
   💡 Poradit

   Do fronty dej start a do množiny navstivene také start. Pak ber vždy první prvek fronty.
   fronta = [start_pos]
navstivene = {start_pos}
aktualni = fronta.pop(0)
   Nové sousedy přidávej na konec fronty — díky tomu prohledáváš mapu po vrstvách.
2. Ukládej předchůdce, aby šla složit cesta.
   💡 Poradit

   U každého nově objeveného políčka si zapiš, odkud ses tam dostal: predchudce[dalsi] = aktualni.
   Zapisuj jen u políček, která ještě nejsou v navstivene, ať si nepřepíšeš kratší cestu.
3. (Volitelně navíc) Po nalezení cíle vypiš délku cesty.
   💡 Poradit

   Cestu slož od cíle: ber predchudce[pozice], dokud nedojdeš ke startu, a na konec seznam otoč (cesta.reverse()).
   Počet kroků je pak len(cesta) - 1, protože start se nepočítá jako krok.
4. (Volitelně navíc) Vykresli navštívené i finální trasu.
   💡 Poradit

   Vrať z BFS kromě cesty i množinu navstivene a při kreslení jí předej obojí.
   Ve vykresli pak stačí rozlišit jiné emoji pro navštívená políčka a jiné pro políčka na finální trase.

Očekávaný výsledek: BFS spolehlivě vrátí nejkratší cestu v počtu kroků.

def bfs(maze, start_pos, cil_pos):
    fronta = [start_pos]
    navstivene = {start_pos}
    predchudce = {}

    while fronta:
        aktualni = fronta.pop(0)
        if aktualni == cil_pos:
            break

        for dalsi in sousedi(maze, aktualni):
            if dalsi not in navstivene:
                navstivene.add(dalsi)
                # ...doplň...
                fronta.append(dalsi)

    if cil_pos not in navstivene:
        return None, navstivene

    cesta = [cil_pos]
    uzel = cil_pos
    while uzel != start_pos:
        # ...doplň...
        cesta.append(uzel)
    cesta.reverse()
    return cesta, navstivene

Zadání:

1. Doplň funkci dijkstra pro mapu s cenami (. = 1, ~ = 4).
   💡 Poradit

   Cena se neplatí za krok, ale za políčko, na které vstoupíš. Vezmi si ji ze slovníku CENY podle znaku terénu.
   cena = CENY[teren[r][c]]
nova = vzdalenost[aktualni] + cena
   Novou cenu ulož jen tehdy, když je nižší než ta dosud známá.
2. Vždy vyber nehotový uzel s nejnižší známou cenou.
   💡 Poradit

   Z nehotových uzlů vždy vyber ten s nejnižší zapsanou cenou.
   aktualni = min(nehotove, key=lambda x: vzdalenost[x])
nehotove.remove(aktualni)
   Hotový uzel si dej do navstivene, ať ho nezpracováváš znovu.
3. (Volitelně navíc) Spočítej celkovou cenu do cíle.
   💡 Poradit

   Celková cena už ti v tabulce leží — je to vzdalenost[cil_pos].
   Vrať ji vedle cesty a vypiš ji, aby bylo vidět, kolik energie výprava stála.
4. (Volitelně navíc) Zobraz trasu a porovnej ji s kratší, ale dražší cestou přes bažinu.
   💡 Poradit

   Vykresli nalezenou trasu stejně jako u BFS a vedle ní zkus i trasu z BFS na stejné mapě.
   Porovnej dvě čísla: počet kroků a celkovou cenu. Uvidíš, že kratší cesta přes bažinu vyjde dráž.

Očekávaný výsledek: zjistíš, že nejlevnější cesta nemusí mít nejméně kroků.

def dijkstra(teren, start_pos, cil_pos):
    nehotove = [start_pos]
    navstivene = set()
    vzdalenost = {start_pos: 0}
    predchudce = {}

    while nehotove:
        aktualni = min(nehotove, key=lambda x: vzdalenost[x])
        nehotove.remove(aktualni)
        navstivene.add(aktualni)

        if aktualni == cil_pos:
            break

        for dalsi in sousedi(teren, aktualni):
            cena = CENY[teren[dalsi[0]][dalsi[1]]]
            nova = vzdalenost[aktualni] + cena

            if dalsi not in vzdalenost or nova < vzdalenost[dalsi]:
                vzdalenost[dalsi] = nova
                # ...doplň...
                if dalsi not in navstivene and dalsi not in nehotove:
                    nehotove.append(dalsi)

    # ...doplň složení cesty a návrat ceny...

Zadání:

1. Použij BFS a najdi nejkratší trasu hrdiny ke truhle.
   💡 Poradit

   Použij hotové BFS z předchozího cvičení — jen mu předej mapu dungeonu, pozici hrdiny a pozici truhly.
   cesta, navstivene = bfs(DUNGEON, start, cil)
   Nezapomeň ošetřit případ, kdy cesta neexistuje (cesta je prázdná nebo None).
2. Ulož hrdinu ve tvaru {"jmeno", "zivoty", "zlato", "inventar"} ve st.session_state.hrdina.
   💡 Poradit

   Hrdinu založ jen jednou, při prvním spuštění, aby se ti stav nepřepisoval po každém kliknutí.
   if "hrdina" not in st.session_state:
st.session_state.hrdina = {"jmeno": "Arkon", "zivoty": 100, "zlato": 40, "inventar": []}
   Dál už pracuj s st.session_state.hrdina.
3. (Volitelně navíc) Každý krok vezme 2 životy a uprav zlato podle délky cesty.
   💡 Poradit

   Spočítej kroky = len(cesta) - 1 a podle toho uprav hodnoty hrdiny.
   hrdina["zivoty"] -= kroky * 2
hrdina["zlato"] += 30 - kroky
   Hlídej, aby životy neklesly pod nulu (max(0, ...)).
4. (Volitelně navíc) Přidej deník výprav a tlačítko pro novou hru.
   💡 Poradit

   Deník je jen seznam v st.session_state.denik — po každé výpravě do něj přidej krátkou větu a vypiš ho.
   Nová hra znamená smazat klíče ze session_state a hrdinu založit znovu.

Očekávaný výsledek: PyQuest naplánuje trasu a stav hrdiny se po výpravě správně změní.

# inicializace stavu
if "hrdina" not in st.session_state:
    st.session_state.hrdina = {
        "jmeno": "Arkon",
        "zivoty": 100,
        "zlato": 40,
        "inventar": ["meč"],
    }
if "denik" not in st.session_state:
    st.session_state.denik = []

# po kliknutí spusť cestu
if st.button("🧭 Naplánovat a projít trasu"):
    cesta, navstivene = bfs(DUNGEON, start, cil)
    if cesta:
        kroky = len(cesta) - 1
        ztrata = kroky * 2
        odmena = max(10, 90 - kroky * 8)

        # ...doplň úpravy hrdiny...
        # ...doplň zápis do deníku...
    else:
        # ...doplň větev pro neúspěch...
        pass

Vytvoř appku „Navigátor dungeonu“, kde si hráč vybere algoritmus: BFS (nejméně kroků) nebo Dijkstra (nejnižší cena při bažinách). Vypiš délku cesty, cenu cesty a počet navštívených políček. Na stejné mapě porovnej, kdy vyhraje BFS a kdy Dijkstra.