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):
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.