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

[Jon Harrop]

On Monday 30 July 2007 09:51:48 apfelmus wrote:
> Thomas Conway wrote:
> > To amuse myself while waiting for test-runs to complete, I was
> > thinking about random terrain generation. I came across a bunch of
> > nice posts by Torben Mogensen, where he describes a neat way of
> > constructing random terrains by recursively subdividing right angled
> > isosceles triangles. It got me thinking - it's all well and good
> > subdividing to give more detail as you zoom in, but what about when
> > you zoom out?
>
> Can you post a hyperlink for an exact description of the algorithm?

Maybe this:

  http://www.geocities.com/Area51/6902/t_torben.html

> > This got me thinking that it would be cool to make an infinite terrain
> > generator using a zipper, so you can zoom in/out infinitely, and by
> > implication, infinitely in any direction.
>
> An infinite random terrain sounds like great fun :) I can't say whether
> it's possible or whether zippers are needed without knowing the details,
> though.

I wrote a real-time infinite-detail random planet renderer along similar lines 
in C++ many years ago.

Thomas' description makes it sound ROAM based (isosceles triangles) but mine 
subdivided and perturbed an icosahedron into roughly-equilateral triangles.

This is a good task for a functional programming language. It is based upon 
graph theory and you must consider splitting and joining triangles to keep 
the subdivision suitably accurate in the region currently in view. The 
perturbations and split/join metric can be made up and tinkered with. For a 
real time implementation, you maintain a priority queue of splits and joins, 
doing a few each frame.

All in all, a very fun project.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e