[Freeciv-Dev] Re: I have written a new terrain generator

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 12:58 PM 02/05/06 +0200, Helge Hafting wrote:
>"Ross W. Wetmore" wrote:
>> >Thanks, I have uploaded tergen.tar.gz to incoming.
>> >Untar it and move source files to
>> >freeciv-1.12.0/common/ (it uses the registry routines)
>> >Helge Hafting

>> make_plains() converts roughly half of remaining grassland to plains in
>> mapgenerator1. The trick with height, temperature and wetness is to bias
such
>> selection so higher/colder/drier tiles are more likely to be plains, but
the
>> overall weights sum to 50%. There are some attempts to build such effects
>> into the existing module, but it would be trivial to use the per-tile
values
>> from your system vs the current computed ones to give a more sophisicated
>> flavour.
>> 
>My idea here is that the kind of world you get is controlled by
>tergen.conf.  My tergen.conf was quickly put together, so it has
>weaknesses like almost no forests.  It is ill-tuned - but that is
>fixable. It can be improved a lot.

Tergen.conf is pretty good in its basic ideas. Tweaking and refinement
is always an incomplete process :-).

But there are generally other constraints or selection rules that are not
so easily expressed in tergen.conf form. If some of the concepts in the
current generator modules can be reduced to data input to a generalized
processing algorithm, I'm all for it. But some are just more simply
handled in specialized code or by feedback iteration.

I like the goal of trying to make tergen do as much as possible, but 
hope the option to add some additional modules to deal with different
kinds of constraints is never completely ruled out.

>A "default" tergen.conf should generate all supported terrain types
>in realistic amounts. 

There are two problems with using local conditions for given terrain
types where the conditions are set by pseudo-random parameters.

The first is that realistic terrain is typically contiguous and slowly
varying, but can have occasional irregularities. It is difficult to
get the same underlying characteristics from the pseudo-random 
generation, i.e. balance smoothing and randomness.

The local conditions tend to be either-or choices, and not have good
regional feedback. Sometimes the only way to deal with the occasional
aesthetically bad results is by post-processing fixups.

>I didn't really plan on supporting percentages of this and that - if
>you raise global temperatures you won't get any arctic at all for
>example.

Percentages should be viewed as an additional constraint on your basic
system. What they do is remove some of the variability of a purely
random system, or simplify the process of achieving certain kinds of
balance when there are fairly complex interactions of tergen parameters.

>I could create a wetness statistic and dynamically determine tresholds
>for desert/grass/swamp, and use similiar statistics
>for choosing between mountain/grass/hill.

Lets use temperature as an example to see how tergen and percentages
might interact in a feedback model. 

First you generate a pure tergen (unconstrained) world. When you are
done though you find that there are no arctic regions and the equatorial
belt is almost non-existent so jungles and swamps are under represented.

What you do is apply a scaling function to temperatures that results in
heating at the equator and cooling at the poles. On the temperature
scale this reduces the large area under the moderate temperature range
and pushes it out to the wings - flattening the bell curve.

Repeat a tergen cycle with the "new" temperature scale and look at the 
results from a percentage standpoint. After an iteration or two when
you have the required percentages "close" you are done.

This in effect is changing some of the initial tergen linear inputs and 
rerunning the cycle. But rather than learning how to tweak tergen inputs 
to get the rough type of balance they are looking for (and these input 
paramters are significantly removed from the results), users can use 
the standard percentage system to dictate the outputs.

>But that sort of defeats the whole simulation.  If you don't want
>mountains, remove the mountain generation rule, _or_ change the max
>height to something lower than what the mountain rule specifies.

It usually isn't that easy to predict the distributions of a pseudo-
random generation process. It is easier to adjust the rules afterwards
to produce the distribution you want.

As an example, the corecleanup heightmap generation like CVS had a 
problem with the absolute scale of the heights after smoothing and
random hits. To solve this and make the rules (e.g. applying hill and
mountain elevations) more standard/predictable, there is an extra
adjust_map() that rescales the map heights from 0 (sea floor) to sea 
level (3000) to max_height (10000). This means smoothing functions
just do smoothing and do not affect the basic key elevation levels.

>Some of the existing settings don't map well to my way of generating
>terrains.  I may be able to take more input from the existing
>variables, but some of it just don't fit the model.  Instead, there
>are other ways of achieving the same.

Agreed. 

I'm not really suggesting that one convert inputs before running the
different algorithms, though where it is easy to do it may help. Rather 
it is scale/iterate the results so they conform to the current output 
oriented selection model.

Users easily see and will tend to demand given output distributions. 
Complex input tweaking to get this irritates most of them.

Personally I like playing with your inputs, though. But I'm generally
atypical.

>> The map structure appears to be quite blocky. I suspect this is just a
matter
>> of playing with the smoothing algorithms, or substituting calls to things
>> like
>> adjust_map()/smooth_map() in the corecleanup mapgen.c to make the heightmap
>> more uniform/contiguous and/or round off some of the edges so their
original
>> NxN character isn't quite so apparent. 
>The NxM stuff is a weakness indeed.  
>The "best" way would be a (simple) simulation of plate tectonics and
>erosion, but I don't even have simplified knowledge about plate
>movement.  So I couldn't do that.  I guess raising circular regions
>would help a _lot_ though.  Rectangles has this nasty property
>that edges for different rectangles often overlap, creating
>straight coastlines and mountain ranges.  Circles almost never
>overlap perfectly, there's much more intersections.

Using different shapes can help. The smoothing functions should take
care of most things by building in some randomness to their smoothing.
                                         +
I used a directionally oriented splash  - X  where the head points 
randomly in any of the eight directions. +

>Real mountain ranges are often long and narrow because they really
>are plate crash zones.  So a combination of circles and lines in
>random direction would improve things.  This is one of my next
>planned improvements unless someone have an idea for a
>real tectonic algorithm.

I haven't tried it, but my wishlist flavour involves drawing various
smooth curve segments on the map. Then applying a shear effect by 
adding to one side and subtracting equal amounts from the other. The
shear might have a height and a decreasing spread as variables.

One might actually get something more continentally based by doing a
standard heightmap and applying some heuristic for where the shear
lines would be added. But coming up with a simple yet realistic 
heuristic is not a trivial task.

>> The area where this blockiness may be a more severe problem is in the
terrain
>> allocation. All terrain above a certain height is not a mountain, but quite
>> often high level plateau, or a fertile river valley. Some of the simplicity
>> here might be modified to detect "roughness" or changing elevations, or
>> conversely find a way to un-smooth mountains into thin linear chains rather
>> than blocks. 
>Good point.  The current generation looks at a single tile at a time,
>that's
>good for simplicity.  I could create a "roughness map" from the height
>map,
>where "roughness" is based on how different a tile is from its
>neighbours.
>This could be a fourth parameter to the terrain type rules, allowing
>things like:
>
>mountain if tall & rough, plain if tall & smooth
>hill if rough & low, grass/jungle/swamp otherwise and so on.

That is what I mean by "regional" vs "local" paramters and rules. But
you have the practical picture right on, here.

>> Your big continents tend to uniformly mountainous interiors or be composed
>> of a central height mass with peripheral lowlying blocks, i.e. dome shaped.
>> Note, there is a similar tendency in CVS, so you are no worse at this
aspect
>> of heightmap generation and usage.
>
>This is the result of un-realistic height map generation.  Fixes may
>be tacked on to the current stuff, or a better algorithm used.
>The roughness stuff might cut down on the central mountains, turning
>some of them into plains instead.

I used additional "rules" that detected surrounding terrain characteristics
and a random factor to change the simple height-based mountain selection
to things like arctic (i.e. icefields/glacier), desert, plains. My rules
or random factors are all hardcoded though and would benefit from a more 
tergen-like ruleset flavour.

>> Inland lakes and seas should be possible with your system, but I didn't see
>> that many. It might be that restricting outflows and setting a threshold
for
>> combining adjacent rivers into swamps and lakes would give this effect. I
>> suspect that your seas are of the Dead Sea type, i.e. below true sea level.
>
>Any "lakes" bigger than 1 square you see is just a low region that
>happened to
>be trapped between higher region.  There is no concept of continent
>or sea other than height above or below 0.
>
>A river with no lower square to flow to will create a inland lake,
>currently
>size 1x1.  I have planned an improvement where such lakes fill up,
>repeatedly 
>spill into the lowest neighbour square until the closed valley fill up
>and the river spill into lower terrain and eventually the sea.

I used height to change swamps to lakes, so large high swamps are
inland seas, and asking for swampy worlds gives lots of waterways.
It is a disgusting hack, but it actually works quite well :-).

A "Lake" terrain type, or additional rules for OCEAN along these
lines would be nice.

>> Rivers should flow through drylands. There seems to be a tendency for a lot
>> of short rivers on the windward slopes, and nothing flowing to leeward.
Long
>> river systems are typically found in the latter case.  
>
>This could be a weakness in the weather algorithm.  Water fall from
>clouds
>whenever they get over higher or colder terrain, sometimes _all_ of the
>cloud rain down and nothing's left to drift further inland.  The
>rain_divisor
>helps here, setting it high and also increasing the rain_passes a lot
>will
>wet a lot more terrain.  You may have to increase the river treshold and
>change wetness limits to get good terrain, but this might give better
>water distribution.  If it don't, please give more suggestions 
>about algorithm improvements.

River flow should largely be determined by their headwater rainfall, and 
most if not all moisture (up to say a river size threshold) flow into the
next lower tile. This means that rivers once started will flow to some
sea. The next trick is making sure that sufficient rainfall does make it
to the leeward sides of a continental divide to get them started.

Rivers should not depend much on local rainfall except at their headwaters.
Conversely, starting rivers anywhere the rainfall levels pass a given
threshold is probably a useful rule. There might be a lessened threshold
for rainfall to start a river at higher elevations so they tend to have
a normal appearance.

>> I'm not sure if this
>> can be tweaked by increasing flow-through values and/or a greater wetness
>> distribution area that extends 2-3 tiles with at least some major
rainfall on
>> the immediate leeward slopes. The mountain heights need to be narrower or a
>> change in height be used as the moisture squeezing operation on clouds,
maybe.
>> Rivers also appear to have multiple outflows in some cases, or be joined at
>> their headwaters. Random rivers without constraints can be very unrealistic
>> but this is difficult to get right.
>
>The generated rivers are quite good, but there is a freeciv limitation
>at play:
>a tile either has river or it don't, and this river join all adjacent
>river tiles.   this would be much better if I could specify things like
>"for this tile, the river flows downhill in direction X".  
>That would avoid joining two rivers who happens to flow in parallel.
>
>Or I could work around this limitation by considering rivers only for
>groups of 3x3 tiles.  Then they would join only when I really
>want them to.

Rivers that run around in a loop and bite their tails are a major 
headache. Simple NxN checks don't really work.

The corecleanup river algorithm is pretty complex, but it does generate
quite extensive and reasonable inland watersheds. It uses height (with a
little random fudge factor) and joining rules to run down to the sea. 
All water tiles like OCEAN and rivers have an (ocean==continent) number.
River tiles with the same number can't join. and when two with different
numbers join the smaller number propagates back through the watershed.
Rivers end at OCEAN tiles and push through inland lakes to drain them.

There are seldom more than a half dozen watersheds at the end, and often
just one (everything runs down to the single world ocean).

A real headache is getting the rivers started though.

>I have though of adding randomness.  For each tile, the algorithm could
>determine how well each terrain type fit, and then use a random
>number to select using that distribution.

I always like this sort of system. Sort a list by weight, choose a number
between one and the weight-sum and find the one chosen. If you use biased
number selection (i.e. the lowest of two random rolls) you can generate
fairly consistent distributions of the larger weights with an occasional
oddball case thrown in.

With terrain, there would need to be a regional component to the weight
that biased against incompatibilities in adjacent terrain, i.e. desert
in the middle of a swampy region.

>As you have seen, my generator needs quite a few parameters of its own
>to work.
>Hardcoding some might be ok, but I want to keep much of it open for
>tweaking.  People should be able to play strange worlds if they want to.
>Such as a world without mountains or no arctic.  Or possibly
>a nuclear winter world with frozen seas and mostly tundra/arctic.

Hardcoding usually means fallback defaults. But it is nice to be able
to override any such parameter if you want.

The current system allows one to have zero of a given terrain type. One
criticism of the corecleanup mapgen was that I had terrain leakage and 
0% wasn't zero. I had to fix this.

>I am open for using more of the standard parameters, but not in ways
>that are squarely against the idea, which is a world created by
>simulation.

Agreed. 

But you can still develop the world via simulation, and meet output
parameter constraints, so the two aren't really mutually exclusive.
One may have to be clever to keep everyone happy, though.

>> I guess a followup question is what would you like to see happen next. Are
>> you interested in enhancing or upgrading your system? breaking it down and
>> integrating it into current modules? discussing and/or working with others
>> to do any or all of the above? having others take over and do such things?
>> working on a design proposal for discussion and presentation?
>
>I am interested in improving the my system, and get it integrated
>into freeciv so it gets usable for all.  I can put in some time myself,
>but I have work to do too.  Others who want to help with this
>are certainly welcome.
>
>I got the impression that freeciv went into a code freeze recently, so
>I don't know if integration is possible at the moment?

It will likely be a while till it gets integrated, but it might take
awhile to get something in a form or complete enough to be seriously
considered.

>The first improvements I plan to try is the terrain/mountain roughness
>stuff
>you suggested, and the use of something other than NxM rectangles for
>height generation.

Sounds good ...

>Helge Hafting
>Helge Hafting

Cheers,
RossW
=====