Maze solver BFS in Haskell

Question

I am really excited that I just wrote my Haskell maze solution in bfs. This is my very first haskell (and I still haven't tried to build a maze in haskell so that maze is hard coded xD)

ANY suggestions all super welcome!!!

maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0], 
        [0, 2, 2, 2, 2, 2, 2, 2, 0], 
        [0, 2, 0, 0, 0, 0, 0, 0, 0], 
        [0, 2, 2, 2, 0, 2, 2, 2, 0], 
        [0, 0, 0, 2, 0, 2, 0, 2, 0], 
        [0, 2, 2, 2, 0, 2, 0, 2, 0], 
        [0, 2, 0, 0, 0, 2, 0, 2, 0], 
        [0, 2, 2, 2, 2, 2, 0, 2, 0], 
        [0, 0, 0, 0, 0, 0, 0, 0, 0]]
start = (7, 7)
end = (1, 7)

validPosition x y maze = (x >= 0) && (y >= 0) && (length maze) > y && (length (maze !! 0)) > x
getNode x y = if (validPosition x y maze) then Just ((maze !! y) !! x) else Nothing
getNeighborNode x y closed = filter (\(i, j) -> (getNode i j) == (Just 2) && (elem (i,j) closed) == False) [(x+a, y+b) | (a,b) <- [(0,-1),(0,1),(1,0),(-1,0)]]


bfsSolver ((i,j):xs) closed meta
    | ((i,j) /= end) = (bfsSolver (xs++neighbors) (closed++[(i,j)]) (meta++[((a,b), (i,j)) | (a,b)<-neighbors]))
    | otherwise = (constructPath (i,j) meta [])
    where neighbors = (getNeighborNode i j closed)


constructPath (i,j) meta route
    | (length points) > 0 = (constructPath (head points) meta (route++[(i,j)]))
    | otherwise = route++[(i,j)]
    where points = [(x,y) | ((a,b),(x,y)) <- meta, (a,b) == (i,j)]

-- bfsSolver [start] [] []

Answer 1

I've hardly done any Haskell - so it's probably a positive thing that I can easily understand your code - but since you've no answer yet, I'll have a go. Anyway, take everything I say with a pinch of salt, and it'll just be surface stuff since I don't have experience to draw on.

---

Currently you code uses a linear-time search to determine if an element is in the list of closed elements. Since Ord is implemented for tuples (e.g. (Int, Int)) you can use a Data.Set instead, which will provide logarithmic-time lookup, making your code more efficient on large problems. I'd also consider making meta a Data.Map so that you can efficiently query it as well, and will allow you to dispense with that head points in constructPath.

---

Though you have attempted to implement a graph-search, your closed system is inadequate, as it still allows the queuing of elements multiple times. Consider the case where the same node is queued by two different other nodes before it is itself expanded (this would occur any time you had a square of 4 cells, starting in one the cell diagonally opposite will be queued twice). The easiest way to solve this is probably to append all the neighbours to closed, and add start to closed from the outset.

---

I don't know how people do things normally in Haskell, but I hate tuples with a passion (when they leak outside functions), and would replace your coordinate tuples with a dedicated data type, e.g.

data Position = Pos { x :: Int, y :: Int } deriving (Eq, Ord, Show)

This makes the meaning of the 2 elements clear, and ensures that only values intended to be interpreted as a position can be used. It also means you can define meaningful instances over your new type without infecting code which uses tuples.

---

You are mixing usage for i j and x y; I'd stick with just one of them as best you can, and try to think of something better than a b for your temporaries (dx dy for offsets?) You don't need the coordinates in constructPath; I think something like this would be clearer, though I'll concede that it's no longer entirely clear that this is operating on positions (but it's also a more generic piece of code, meaning it will work for (x, y) or Pos x y):

constructPath position meta route
    | (length points) > 0 = (constructPath (head points) meta (position:route))
    | otherwise = position:route
    where points = [to | (from,to) <- meta, from == position]

(I have also here swapped the concatenation around, which means the route will start at start and end at end, which is what I'd normally expect from a route-finder)

---

Ideally your code wouldn't contain magic numbers like 0 and 2; much better to create a union or type-class for the types of cells in the grid, e.g.

data Cell = Wall | NotWall deriving (Eq)

NotWall isn't a great name, but it's better than 2, and will make the intention of the filtering code in getNeighborNode (should that be getNeighborNodes?) much clearer.

---

You can provide a much nicer and more useful API by passing the maze and end in as parameters along with start, and providing a convenience method which calls bfsSolver with the appropriate initial conditions, e.g.

bfs start = bfsSolver [start] [] []

It's so much harder to misuse, and your consumers would thank you for it.