I wrote a BFS implementation that walks a tile-based field. It takes a function that should return true for walkable tiles and false for walls. It also takes the start and end points. It currently takes about 5 seconds to find the shortest path from (0, 0) to (1000, 1000) which isn't bad, but it really isn't great.
import qualified Data.HashSet as H
import Data.Maybe (mapMaybe, isNothing)
import Data.List (foldl')
bfs ::
(Int -> Int -> Bool) -> -- The field function. Returns True if tile is empty, False if it's a wall
(Int, Int) -> -- Starting position
(Int, Int) -> -- Final position
Int -- Minimal steps
bfs field start end = minSteps H.empty [start] 0
where
minSteps visited queue steps
|end `elem` queue = steps + 1
|otherwise = minSteps newVisited newQueue (steps + 1)
where
(newVisited, newQueue) = foldl' aggr (visited, []) queue
aggr (vis, q) node = if H.member node vis
then (H.insert node vis, neighbors node ++ q)
else (vis, q)
neighbors (nx, ny) = filter (uncurry field) $ map (\(x, y) -> (nx + x, ny + y)) [(1, 0), (0, -1), (-1, 0), (0, 1)]
hugeField x y = x >= 0 && x <= 1000 && y >= 0 && y <= 1000
main = print $ bfs hugeField (0, 0) (1000, 1000)
then
andelse
parts of the condition \$\endgroup\$