This is a problem that I can easily enough solve in a non-functional manner.
But solving it in Haskell is giving me big problems. Me being inexperienced when it comes to functional programming is surely a reason.
The problem:
I have a 2D field divided into rectangles of equal size. A simple grid. Some rectangles are empty space (and can be passed through) while others are impassable. Given a starting rectangle A and a destination rectangle B, how would I calculate the shortest path between the two? Movement is possible only vertically and horizontally, in steps a single rectangle large.
How would I go about accomplishing this in Haskell? Code snippets certainly welcome, but also certainly not neccessary. And links to further resources also very welcome!
Thanks!
I'd represent the grid as a list of lists, type [[Bool]]
. And I'd define a function to know if a grid element is full:
type Grid = [[Bool]]
isFullAt :: Grid -> (Int, Int) -> Bool -- returns True for anything off-grid
Then I'd define a function to find neighbors:
neighbors :: (Int, Int) -> [(Int, Int)]
To find non-full neighbors of point
you can filter with filter (not . isFullAt) $ neighbors point
.
At this point I'd define two data structures:
Maybe Cost
Initialize with only the start square A in the heap, with cost zero.
Then loop as follows:
c
, and add all the non-full neighbors to the heap with cost c+1
.When the heap is empty, you will have the costs of all reachable points and can look up B in the finite map. (This algorithm may be called "Dijkstra's algorithm"; I've forgotten.)
You can find finite maps in Data.Map
. I assume there's a heap (aka priority queue) somewhere in the vast library, but I don't know where.
I hope this is enough to get you started.