Finding the shortest path between two points on a grid, using Haskell.

Question

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!

Answer 1

Well, your types will determine your algorithms.

What data type do you want to use to represent the grid? A two-dimensional array? A list of lists? A tree? A graph?

If you just want shortest path in a directed graph, using something from the FGL (functional graph package) would be best.

Answer 2

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:

• Map each point to Maybe Cost
• Store all points with known cost in a heap

Initialize with only the start square A in the heap, with cost zero.

Then loop as follows:

• Remove a min-cost square from the heap.
• If it's not already in the finite map, add it and its cost 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.