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

Thomas Conway wrote:

On 8/2/07, apfelmus 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