How do I stop randomness from pervading my code in Haskell?

Question

I am attempting to implement the following algorithm, as detailed here.

1. Start with a flat terrain (initialize all height values to zero).

2. Pick a random point on or near the terrain, and a random radius between some predetermined minimum and maximum. Carefully choosing this min and max will make a terrain rough and rocky or smooth and rolling.

3. Raise a hill on the terrain centered at the point, having the given radius.

4. Go back to step 2, and repeat as many times as necessary. The number of iterations chosen will affect the appearance of the terrain.

However, I start to struggle once I get to the point where I have to select a random point on the terrain. This random point is wrapped in an IO monad, which is then passed up my chain of functions.

Can I cut the IO off at a certain point and, if so, how do I find that point?

The following is my (broken) code. I would appreciate any suggestions on improving it / stopping the randomness from infecting everything.

type Point = (GLfloat, GLfloat, GLfloat)
type Terrain = [Point]

flatTerrain :: Double -> Double -> Double -> Double -> Terrain
flatTerrain width length height spacing =
    [(realToFrac x, realToFrac y, realToFrac z)
         | x <- [-width,-1+spacing..width], y <- [height], z <- [-length,-1+spacing..length]]

hill :: Terrain -> Terrain
hill terrain = hill' terrain 100
               where hill' terrain 0 = terrain
                     hill' terrain iterations = do
                       raised <- raise terrain
                       hill' (raise terrain) (iterations - 1)
                     raise terrain = do
                       point <- pick terrain
                       map (raisePoint 0.1 point) terrain
                     raisePoint r (cx,cy,cz) (px,py,pz) = 
                         (px, r^2 - ((cx - px)^2 + (cz - pz)^2), pz)

pick :: [a] -> IO a
pick xs = randomRIO (0, (length xs - 1)) >>= return . (xs !!)

Answer 1

One of the most useful features of haskell is to know a function is deterministic just based on its type - it makes testing much easier. For this reason, I would base my design on limiting randomness as much as possible, and wrapping the core non random functions with a random variant. This is easily done with the MonadRandom type class, which is the best way of writing code in haskell that requires random values.

For fun, I wrote a console version of that hill generator. It is pretty basic, with a lot of hard coded constants. However, it does provide a pretty cool ascii terrain generator :)

Note with my solution all of the calculations are isolated in pure, non random functions. This could then be tested easily, as the result is deterministic. As little as possible occurs in the IO monad.

import Control.Monad
import Control.Monad.Random
import Data.List
import Data.Function (on)

type Point = (Double, Double, Double)
type Terrain = [Point]

-- Non random code

flatTerrain :: Double -> Double -> Double -> Double -> Terrain
flatTerrain width length height spacing = [(realToFrac x, realToFrac y, realToFrac z)
         | x <- [-width,-width+spacing..width], y <- [height], z <- [-length,-length+spacing..length]]

-- simple terrain displayer, uses ascii to render the area.
-- assumes the terrain points are all separated by the same amount
showTerrain :: Terrain -> String
showTerrain terrain = unlines $ map (concat . map showPoint) pointsByZ where
  pointsByZ = groupBy ((==) `on` getZ) $ sortBy (compare `on` getZ) terrain
  getZ (_, _, z) = z
  getY (_, y, _) = y

  largest = getY $ maximumBy (compare `on` getY) terrain
  smallest = getY $ minimumBy (compare `on` getY) terrain
  atPC percent = (largest - smallest) * percent + smallest

  showPoint (_, y, _)
    | y < atPC (1/5) = " "
    | y < atPC (2/5) = "."
    | y < atPC (3/5) = "*"
    | y < atPC (4/5) = "^"
    | otherwise = "#"

addHill :: Double -- Radius of hill
        -> Point -- Position of hill
        -> Terrain -> Terrain
addHill radius point = map (raisePoint radius point) where
  raisePoint :: Double -> Point -> Point -> Point
  -- I had to add max py here, otherwise new hills destroyed the
  -- old hills with negative values.
  raisePoint r (cx,cy,cz) (px,py,pz) = (px, max py (r^2 - ((cx - px)^2 + (cz - pz)^2)), pz)

-- Some random variants. IO is an instance of MonadRandom, so these function can be run in IO. They
-- can also be run in any other monad that has a MonadRandom instance, so they are pretty flexible.

-- creates a random point. Note that the ranges are hardcoded - an improvement would
-- be to be able to specify them, either through parameters, or through reading from a Reader
-- monad or similar
randomPoint :: (MonadRandom m) => m Point
randomPoint = do
  x <- getRandomR (-30, 30)
  y <- getRandomR (0,10)
  z <- getRandomR (-30, 30)
  return (x, y, z)

addRandomHill :: (MonadRandom m) => Terrain -> m Terrain
addRandomHill terrain = do
  radius <- getRandomR (0, 8) -- hardcoded again
  position <- randomPoint
  return $ addHill radius position terrain

-- Add many random hills to the Terrain
addRandomHills :: (MonadRandom m) => Int -> Terrain -> m Terrain
addRandomHills count = foldr (>=>) return $ replicate count addRandomHill

-- testing code

test hillCount = do
  let terrain = flatTerrain 30 30 0 2
  withHills <- addRandomHills hillCount terrain
  -- let oneHill = addHill 8 (0, 3, 0) terrain
  -- putStrLn $ showTerrain oneHill
  putStrLn $ showTerrain withHills

main = test 200

Example output:

... ..     ..*.  .***^^^***.   
... ...   .***.  .***^^^*^^*.  
... ..    .*^**......*^*^^^^.  
       .  .***.***.  ..*^^^*.  
      ....*^^***^*.   .^##^*.  
     ..*.*^^^*****.   .^###^..*
      .**^^^^.***...  .*^#^*.**
     .***^##^**..*^^*.*****..**
  ....***^^##^*.*^##^****.   ..
  .......*^###^.*###^****.     
.*********^###^**^##^***....   
*^^^*^##^^^^###^.^^^*. .****.. 
*^^^^####*^####^..**.  .******.
*^^^*####**^###*. ..   .*******
*^#^^^##^***^^*. ...........***
*^^^**^^*..*... ..*******...***
.***..*^^*...  ..*^^#^^^*......
  ...*^##^**.  .*^^#####*.     
    .*^##^**....**^^####*. .***
.. ..*^^^*...*...**^^###^* *^#^
..****^^*. .... ...**###^*.^###
..*******.**.  ..**^^^#^^..^###
 .*****..*^^* ..**^##^**...*^##
.^^^^....*^^*..*^^^##^* ..**^^^
*###^*. .*^**..^###^^^*...*****
^####*.*..*^^*.^###^**.....*.. 
*###^**^**^^^*.*###^. ..   .   
.^^^***^^^^#^*.**^^**.         
 .....***^##^**^^^*^^*.        
      .*^^##^*^##^^^^^.        
      .*^^^^*.^##^*^^*.        

Answer 2

The algorithm says that you need to iterate and in each iteration select a random number and update the terrain which can be viewed as generate a list of random points and use this list to update the terrain i.e iteration to generate random numbers == list of random numbers.

So you can do something like:

selectRandomPoints :: [Points] -> Int -> IO [Points] -- generate Int times random points
updateTerrain :: Terrain -> [Points] -> Terrain

-- somewhere in IO
do
  pts <- selectRandomPoints allPts iterationCount
  let newTerrain = updateTerrain t pts   

Answer 3

Nope, you can't escape IO. Perhaps you can do all your randomness up front and rewrite your functions to take that randomness as a parameter; if not, you can use MonadRandom or similar to track a random seed or just put everything in IO.