[Haskell-cafe] Re: Zippers, Random Numbers & Terrain

[apfelmus]

Thomas Conway wrote:
> On 8/2/07, apfelmus <apfelmus at quantentunnel.de> wrote:
>> That concludes the infinite terrain generation for one dimension. For
>> higher dimension, one just needs to use 2D objects instead of intervals
>> to split into two or more pieces. For instance, one can divide
>> equilateral triangles into 4 smaller ones. In fact, it doesn't matter
>> whether the starting triangle is equilateral or not when using the
>> midpoints of the three sides to split it into four smaller triangles.
> 
> Nice. The issue of the RNG running backwards was what made me realize
> that rather than using StdGen in the nodes, if you simply number them
> (Hmmm - the nodes are countably infinite :-)), you can then [e.g.] use
> a cryptographic hash or similar to turn them into random numbers. You
> can seed the hash to generate different terrains.

Yes. The number of a node in the tree should be (related to) the path
from the top to the tree in binary representation. I.e. if

  node = zoomInLeft . zoomInLeft . zoomInRight $ top

then,

  number node = 112 in binary with digits 1 and 2

In contrast, breadth first numbering is a bad idea, since that would
mean numbering lots of nodes that aren't required when zooming in.


It's probably easiest to first create an infinite tree filled with
random numbers

  type Tree a = Branch (Tree a) a (Tree a)

  type Random = Double
  mkRandom :: Seed -> Tree Random

and then convert that to a landscape afterwards

  terrain :: Tree Random -> Tree (Height, Height)


Yet another option is available if you only use the zipper-operations to
navigate in the tree, i.e.

  data TreeRandom -- abstract and a zipper

  zoomInLeft, zoomInRight, zoomOut :: TreeRandom -> TreeRandom
  top :: TreeRandom -> Random

In that case, you can represent it by

  type TreeRandom = (StdGen, Zipper (Maybe Random))

Everytime you visit a node that has not been visited yet (=> Nothing),
it gets a new random number from the generator. When it's already been
visited (=> Just r), well then the random number associated to it won't
change. The resulting zipper may only be used in a single-threaded
fashion, however.

> You may be interested that in some of the code I wrote for the right
> angle isosceles triangle case, I got into precision problems. It turns
> out that all the vertices lie on positions with coordinates that are
> precisely sums of 2^-k (e.g. 0.5, 0.125, 0.625), yet each time you
> subdivide, the scaling factor on the side length is sqrt 2/2. The
> resultant rounding meant that instead of getting 0.5, I got
> 0.5000000003, or some such.
> 
> After pondering on this for a while, I realized instead of
> representing the scale of the triangle as a Double, I could use
> (Either Double Double), with Left x representing the scale x, and
> Right x representing the scale x * sqrt 2 / 2. That way, all the
> rounding problems can be made to go away.

Cool :) Of course, the representation with Either requires the knowledge
that a scale factor cannot contain both Double-multiples of 1 and
Double-multiples of sqrt 2 at the same time. While this is clearly the
case, you can avoid thinking about it by operating in the field Q[sqrt 2]:

  data QSqrt2 = !Double :+ !Double deriving (Eq,Read,Show)

  instance Nume QSqrt2 where
     (a :+ b) + (c :+ d) = (a+c) :+ (b+d)
     (a :+ b) * (c :+ d) = (a*c + 2*b*d) :+ (a*d + b*c)

     negate (a :+ b) = negate a :+ negate b
     abs (a :+ b)    = (a + sqrt 2 * b) :+ 0
     fromInteger n   = fromInteger n :+ 0

  sqrt2 = 0 :+ 1

Regards,
apfelmus