Re: [pygame] [Pygame] Generating a map

["Dave LeCompte (really)" <dave@xxxxxxxxxxxx>]

"Kris Schnee" <kschnee@xxxxxxxxxx> wrote:
> Dave LeCompte (really) wrote:
>> Also, there's a pretty good paper about the tricks that the "Tribal
>> Trouble" guys used to make their terrain here:
>> http://oddlabs.com/download/terrain_generation.pdf
>
> That paper was really useful. I was able to implement a version of the
> Voronoi (bubble/ridge thing) with some fiddling, and accidentally made
> what appears to be a fractal by accident. It's attached as
> "my_generation.py" if you want to see the messy code. The part that was
> hard to figure out was what the paper described as:
> height = (distance to nearest point)*(arbitrary constant 1)
> The distance ranges from 0 to many thousands, so what's a good way to
> convert that to a 0-255 range or the 0.0-1.0 range used in the paper? I
> ended up doing it in an arbitrary way.

I would probably have some sort of scale factor based on the scale of the
"bubble/ridge" features - perhaps scanning the map for average "bubble"
size.


> I see that <http://home.scarlet.be/zoetrope/voronoi/> has a Python
> implementation of Voronoi code as a "Crystalize" filter for images.

I adapted the Voronoi/Delaunay code from Graphics Gems IV, it was pretty
easy. I have yet to make heavy use of it, but I've already used it to draw
some "organic" looking diagrams.

Documentation here: http://www.meatengine.com/overview.html#math-voronoi
Download here: http://www.meatengine.com/


> I also tried to implement a diamond-square algorithm, but something's
> not quite right about it. If I force the squares to be higher than
> normal (adding 64 to the height values), I can see that it's calculating
> all the pixels in the image, but normally most of the image ends up
> black. The code for that is attached as "my_generation3.py"; anyone know
> how to fix it? The problem seems to be that I'm using a 256x256 bitmap,
> and the calculation of each cell's "neighbors" is off by one pixel or
> something where it wraps around the edges, so that it finds zeroed
> pixels instead of the already-calculated ones.

Yeah, you have to be careful with your indices - I haven't looked at your
code, but I typically make my diamond-square arrays 2^n+1, so 257x257 in
your case. I don't use wrap around, which you mention, so maybe you're OK
in starting with 256x256 - that additional column and row could wrap
around back to row or column #0.


Another thing that I struggled with for a long time was how to manage the
scale of my displacements with diamond-square. There are two steps in
diamond-square; the diamond and the square (of course). From one diamond
step to the next diamond step, and from one square step to the next square
step, the linear distances that you're working with goes down by a factor
of two - so, if you're trying to get the most self-similar landscapes, the
displacement scale should also go down by a factor of two.

The insight that I was missing, though, is that really the diamond and the
square steps are closely related, and should be considered as doing the
same operation, but with a 45 degree rotation. Once you see that, you can
see that the linear distances go down by a factor of sqrt(2) between steps
(diamond to square or square to diamond), with a combined factor of two
over a pair of steps. So, in order for the features to scale properly, the
displacement scale should be divided by root two. When I wasn't doing
this, I was getting really nasty seams aligned with the x and y axes - not
immediately noticeable, but when I lit the terrain, I'd see a ridge
running right along the middle of my data set, straight up the y axis.

Your mileage will vary, but this was something I've seen over and over
again, not only in my own fractal subdivision (diamond-square)
implementations, but other peoples', as well. An example is here:

http://www.bigdicegames.com/SpareTime/Images/Terrain/fracsubdseams.png

Just to be clear: the data in that image come from one of my own (failed)
experiments, but I'm using Terragen to render it. Terragen's own terrain
generation doesn't suffer from that bug.

-Dave LeCompte