Jste zde

Hledání cesty z bludiště v Haskellu

Hledání cesty ven z bludiště patří mezi klasické programátorské úlohy. V tomto příspěvku bych vám chtěl ukázat, jak si lze takový jednoduchý "maze solver" bez větších obtíží naprogramovat v Haskellu.

Typů bludišť a algoritmů hledání cesty existuje obrovské množství (viz tento web). Já se zaměřím pouze na jeden z nejjednodušších typů bludišť, a to dvourozměrné ASCII bludiště, kde symbol # značí stěnu, . značí průchozí místo, S značí start, G značí cíl, a + bude označovat část nalezené cesty. Viz ukázkový příklad níže:

###########################G##
##....###...........#######..#
##.##....#.########.##....##.#
##..####..........#.##.##.##.#
###.##.###.#.####.#....##.##.#
S.####.#######.##.#######.#..#
#.#.....###....##.#####.....##
#...###.#.#.##.##.###...##.###
#####.......##....###.#.##...#
##############################

Bludiště bude reprezentováno jako 2D matice (v případě hyperbludišť by se jednalo o vícerozměrnou matici):

import Array
 
type Maze = Array (Int, Int) Char

Levý horní roh matice má souřadnice (0, 0). Prvky v matici budou znaky dle uvedeného značení ('#' je stěna atd.). Jako algoritmus hledání cesty jsem zvolil klasické slepé prohledávání do hloubky (depth-first search), které bude implementováno (chvíle napětí) rekurzivně. Hlavní (vnější) funkce vypadá takto:

findWayThrough :: Maze -> Maybe Maze
findWayThrough maze = solveMaze maze i j
    where (i, j) = findStart maze

Vstupem je bludiště a výstupem je buď Just Maze, pokud byla cesta nalezena (pak je ve výsledku vyznačena symboly +), nebo Nothing, pokud cesta v bludišti neexistuje. Začíná se vyhledáním místa, odkud se prohledávání zahájí (tj. místo hned vedle startu), který má souřadnice (i, j). Funkci findStart lze nalézt v programu. Podívejme se nyní na hlavní funkci solveMaze, která se rekurzivně pokusí v zadaném bludišti z pozice (i, j) vyhledat cestu ven.

solveMaze :: Maze -> Int -> Int -> Maybe Maze
solveMaze maze i j | currCell == 'G' = Just maze
                   | currCell == '.' = nextMove
                   | otherwise       = Nothing
    where currCell = maze!(i, j)
          nextMove | isOk goU  = goU
                   | isOk goR  = goR
                   | isOk goD  = goD
                   | otherwise = goL
          goU = solveMaze newMaze (i-1) j
          goD = solveMaze newMaze (i+1) j
          goR = solveMaze newMaze i (j+1)
          goL = solveMaze newMaze i (j-1)
          newMaze = maze // [((i, j), '+')]
          isOk (Just _) = True
          isOk Nothing  = False

Typ výstupu funkce je identický s typem výstupu funkce findWayThrough. Funguje to tak, že se podíváme, co se nachází v aktuální buňce. Pokud je to 'G', tak jsme v cíli. Pokud je to ., tak se pokusíme provést další krok v pořadí nahoru, doprava, dolů a doleva (čili pokud se vydáme nahoru a tam v některém z dalších volání funkce cestu nenalezneme, tak po návratu z rekurze zkusíme cestu doprava atd.). Před přechodem do další buňky si aktuální buňku označíme pomocí +, což slouží ke zvýraznění cesty z bludiště.

Pokud programu předhodíme náš příklad, dostaneme následující výsledek:

###########################G##
###...###.++++++++++#######++#
#####....#+########+##++++##+#
########..++++++++#+##+##+##+#
###.##.##########+#++++##+##+#
S+####.#######.##+#######+#++#
#+#+++++###++++##+#####..+++##
#+++###+#.#+##+##+###...######
#####..+++++##++++###.#.######
##############################

Zdrojáky

Kompletní zdrojáky jsou ke stažení zde.

Přidat komentář