astar 0.1 → 0.2

raw patch · 2 files changed

+60/−1 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/Graph/AStar.hs +59/−0
• astar.cabal +1/−1

@@ -7,6 +7,7 @@ import qualified Data.PSQueue as PSQ import Data.PSQueue (PSQ, Binding(..), minView) import Data.List (foldl')+import Control.Monad (foldM)  data AStar a c = AStar { visited  :: !(Set a),                          waiting  :: !(PSQ a c),@@ -74,6 +75,64 @@       in case end s of             Nothing -> Nothing             Just e  -> Just (reverse . takeWhile (not . (== start)) . iterate (cameFrom s !) $ e)++runAStarM :: (Monad m, Ord a, Ord c, Num c) =>+          (a -> m (Set a))   -- adjacencies in graph+          -> (a -> a -> m c) -- distance function+          -> (a -> m c)      -- heuristic distance to goal+          -> (a -> m Bool)   -- goal+          -> a               -- starting vertex+          -> m (AStar a c)   -- final state++runAStarM graph dist heur goal start = aStar' (aStarInit start)+  where aStar' s+          = case minView (waiting s) of+              Nothing            -> return s+              Just (x :-> _, w') ->+                do g <- goal x+                   if g then return (s { end = Just x })+                        else do ns <- graph x+                                u <- foldM (expand x)+                                           (s { waiting = w',+                                                visited = Set.insert x (visited s)})+                                           (Set.toList (ns \\ visited s))+                                aStar' u+        expand x s y+          = do d <- dist x y+               let v = score s ! x + d+               case PSQ.lookup y (waiting s) of+                 Nothing -> do h <- heur y+                               return (link x y v (s { memoHeur = Map.insert y h (memoHeur s) }))+                 Just _  -> return $ if v < score s ! y+                                        then link x y v s+                                        else s+        link x y v s+           = s { cameFrom = Map.insert y x (cameFrom s),+                 score    = Map.insert y v (score s),+                 waiting  = PSQ.insert y (v + memoHeur s ! y) (waiting s) }++-- | This function computes an optimal (minimal distance) path through a graph in a best-first fashion,+-- starting from a given starting point.+aStarM :: (Monad m, Ord a, Ord c, Num c) =>+         (a -> m (Set a))   -- ^ The graph we are searching through, given as a function from vertices+                            -- to their neighbours.+         -> (a -> a -> m c) -- ^ Distance function between neighbouring vertices of the graph. This will+                            -- never be applied to vertices that are not neighbours, so may be undefined+                            -- on pairs that are not neighbours in the graph.+         -> (a -> m c)      -- ^ Heuristic distance to the (nearest) goal. This should never overestimate the+                            -- distance, or else the path found may not be minimal.+         -> (a -> m Bool)   -- ^ The goal, specified as a boolean predicate on vertices.+         -> m a             -- ^ The vertex to start searching from.+         -> m (Maybe [a])   -- ^ An optimal path, if any path exists. This excludes the starting vertex.+aStarM graph dist heur goal start+    = do sv <- start+         s <- runAStarM graph dist heur goal sv+         return $ case end s of+                    Nothing -> Nothing+                    Just e  -> Just (reverse . takeWhile (not . (== sv)) . iterate (cameFrom s !) $ e)+++  plane :: (Integer, Integer) -> Set (Integer, Integer) plane (x,y) = Set.fromList [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]

@@ -1,5 +1,5 @@ name:                astar-version:             0.1+version:             0.2 synopsis:            General A* search algorithm. description:         This is a data-structure independent implementation of A* search. category:            Data