Haskell routine allegedly written for WLHN 2014-03-20...

pathfinder.hs

import Data.List (minimumBy)
import Debug.Trace (trace)

data Node = Node {x::Int, y::Int} deriving (Show, Eq)

data Terrain = Terrain {startNode::Node, endNode::Node, obstacleNodes::[Node]} deriving (Show)

isBlocked :: Node -> Terrain -> Bool
isBlocked dest t = elem dest (obstacleNodes t)

distance :: Terrain -> Node -> Node -> Ordering
distance t a b =
  let
    dxA = (x a) - (x (endNode t))
    dyA = (y a) - (y (endNode t))
    dxB = (x b) - (x (endNode t))
    dyB = (y b) - (y (endNode t))
  in
    compare (sqrt $ fromIntegral (dxA * dxA + dyA * dyA)) (sqrt $ fromIntegral (dxB * dxB + dyB * dyB))

best :: [Node] -> Terrain -> Maybe Node
best [] _ = Nothing
best nodes t =
  Just (minimumBy (distance t) nodes)

getNextNode :: [Node] -> Terrain -> Maybe Node
getNextNode path t =
  let
    currentNode = last path
    adjacentNodes =
      [Node x (y currentNode) | x <- [x currentNode - 1 .. x currentNode + 1]]
      ++
      [Node (x currentNode) y | y <- [y currentNode - 1 .. y currentNode + 1]]
  in
    if ((endNode t) `elem` adjacentNodes)
      then Just (endNode t)
      else best [x | x <- adjacentNodes, not (isBlocked x t), not (x `elem` path)] t

getRoute :: [Node] -> Terrain -> [Node]
getRoute path t = 
  case getNextNode path t of
    Just node ->
      if (node == endNode t)
        then path ++ [node]
        else getRoute (path ++ [node]) t
    Nothing ->
      let lastNode = last path in
        getRoute (take (length path - 1) path) (Terrain (startNode t) (endNode t) (lastNode : (obstacleNodes t)))

main = do
  let startNode = Node 2 2
      endNode = Node 8 8
      obstacleNodes = [ (Node 5 2), (Node 5 5), (Node 7 7) ]
  print ("Start    : " ++ (show startNode))
  print ("End      : " ++ (show endNode))
  print ("Obstacles: " ++ (show obstacleNodes))
  print ("Path     : " ++ (show (getRoute [startNode] (Terrain startNode endNode obstacleNodes))))