Rosetta Code

Maze generation: Difference between revisions

Page Discussion

Maze generation (view source)

Revision as of 20:03, 18 October 2019

21 bytes removed ,  4 years ago
→‎{{header|Haskell}}: Specified imports, applied hlint hindent, simplified a Boolean chain with 'bool'
(Added Fōrmulæ)
(→‎{{header|Haskell}}: Specified imports, applied hlint hindent, simplified a Boolean chain with 'bool')
Line 3,504:
{-# LANGUAGE TypeFamilies #-}
 
import Control.Monad▼
import Control.Monad.ST▼
import Data.Array▼
import Data.Array.ST
(STArray, freeze, newArray, readArray, writeArray)
import Data.STRef
import Data.STRef (STRef, newSTRef, readSTRef, writeSTRef)
import System.Random
import System.Random (Random(..), getStdGen, StdGen)
▲import Control.Monad (forM_, unless)
▲import Control.Monad.ST (ST, stToIO)
import Data.Array (Array, (!), bounds)
▲import Data.ArrayBool (bool)
 
rand
rand :: Random a => (a, a) -> STRef s StdGen -> ST s a▼
:: Random a
▲rand :: Random a => (a, a) -> STRef s StdGen -> ST s a
rand range gen = do
(a, g) <- liftM (randomR range) <$> readSTRef gen
gen `writeSTRef` g
return a
 
data Maze = Maze {rightWalls, belowWalls :: Array (Int, Int) Bool}
{ rightWalls, belowWalls :: Array (Int, Int) Bool
}
 
maze :: Int -> Int -> StdGen -> ST s Maze
maze width height gen = do
visited <- mazeArray False
rWalls <- mazeArray True
bWalls <- mazeArray True
gen <- newSTRef gen
liftM2 (,) (<$> rand (0, maxX) gen) (<*> rand (0, maxY) gen) >>=
visit gen visited rWalls bWalls
Maze <$> liftM2 Maze (freeze rWalls) (<*> freeze bWalls)
where
where visit gen visited rWalls bWalls here = do
writeArray visited here True
let ns = neighbors here
i <- rand (0, lengthlet ns -= 1)neighbors genhere
i <- forM_rand (ns0, !! i : take ilength ns ++ drop (i +- 1) ns) $ \there -> dogen
forM_ (ns !! i : take i ns ++ drop seen(i <-+ readArray1) visitedns) there$
\there unless seen $-> do
seen <- readArray removeWall herevisited there
unless seen $
visit gen visited rWalls bWalls there
where removeWall (x1,do y1) (x2, y2) =removeWall writeArrayhere there
visit gen visited (if x1 == x2 thenrWalls bWalls else rWalls)there
where
(min x1 x2, min y1 y2)▼
removeWall (x1, y1) (x2, y2) False=
▲ writeArray (bool rWalls bWalls (x1 == x2)) (min x1 x2, min y1 y2) False
 
neighbors (x, y) =
(if x == 0 then [] elsebool [(x - 1, y)] [] (0 == )]x) ++
(if x == maxX then [] elsebool [(x + 1, y)] [] (maxX == )]x) ++
bool [(x, y - 1)] [] (if y0 == 0y) ++ then [] elsebool [(x, y -+ 1)]) ++[] (maxY == y)
maxX = width - 1
(if y == maxY then [] else [(x, y + 1)])
maxY = height - 1
 
maxXmazeArray = width - 1
newArray ((0, 0), (maxX, maxY)) =:: heightBool -> ST s (STArray s (Int, Int) 1Bool)
 
mazeArray = newArray ((0, 0), (maxX, maxY))
:: Bool -> ST s (STArray s (Int, Int) Bool)
 
printMaze :: Maze -> IO ()
printMaze (Maze rWalls bWalls) = do
putStrLn $ '+' : (concat $ (replicate (maxX + 1) "---+")
forM_ [0 .. maxY] $ \y -> do
\y -> putStr "|"do
putStr "|"
forM_ [0 .. maxX] $ \x -> do▼
forM_ [0 .. maxX] putStr " "$
\x -> do
putStr $ if rWalls ! (x, y) then "|" else " "
putStrLn putStr " "
forM_ [0 .. maxX]putStr $ \xbool ->" " "|" (rWalls ! (x, doy))
putStrputStrLn "+"
▲ forM_ [0 .. maxX] $ \x -> do
putStr $ if bWalls ! (x, y) then "---" else " "
putStrLn\x "+"-> do
where maxX = fst (snd $ bounds rWalls) putStr "+"
maxY = sndputStr $ bool " " "---" (sndbWalls $! bounds(x, rWallsy))
putStrLn "+"
where
maxX = fst (snd $ bounds rWalls)
maxY = snd (snd $ bounds rWalls)
 
main :: IO ()
main = getStdGen >>= stToIO . maze 11 8 >>= printMaze</lang>
{{out|Sample output}}
Hout
9,659

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/167676"