[glob2-devel] the random map generator (big)

[Nuage]

Andrew Sayers wrote:
> Before we talk about gradients, I've remembered some of the more
> important things I need to ask you about...
>
> First, the random map generator.  Could you tell me a bit about how it
> works?  It seems to be based on quite a complex algorithm - is it
> something you made yourself, or based on known ideas?  If it's your own,
> could you explain some of the theory?  If it's someone else's, could you
> give me some information I can use to look up explanations?


* the random map generator:

The random map generator is an algorithm of mine.

As you most probably know, the "undemap" is a map which can contain either
water, sand or grass. This is an array shifted by half a "case" on both axis
compare to the tile "case" grid.
This is a convenient tool, because you can draw on the undermap, like you paint
pixels on a bitmap. Then, for each tile, you just convert a 4-under-map value
into a tile value.

Here is the way the random map generator *did* work:
1) Randomly write into the undermap, water, sand or grass, given the provided
ratios.
2) Apply a simple blur filter on the undermap, as many times at the "smoothing"
parameter.
3) Filter the undermap to add sand between the water and grass where it is
needed. This is because we don't have tiles for direct transition from water to
grass.
4) Generate the tile-map from the undermap.
5) Add some stuff on the tile-map, like resources and teams.


The idea is to use a blurring effect to make islands-like areas, instead of
having white-blur-looking maps. And I found it to make natural-looking shapes.

The problem is that, the blurring will completely destroy the originally given
ratios of water, sand and grass. The more blurring levels there are, the more
important the distortion is.

Let's take an example. Let's only use sand and grass. We start with 1/4 sand and
3/4 grass. The actual blur is more complex, but let's take the most simple blur,
with 2 bitmaps, the old bitmap and the new bitmap. Take 4 pixels in a square,
make the majority, and draw the result in the new map. Bases on the 4 possible
pixels, there are 16 possible cases: (s==sand, g=grass, x=undefined)
ssss, maj = s, prob =  1/256
sssg, maj = s, prob =  3/256
ssgs, maj = s, prob =  3/256
ssgg, maj = x, prob =  9/256

sgss, maj = s, prob =  3/256
sgsg, maj = x, prob =  9/256
sggs, maj = x, prob =  9/256
sggg, maj = g, prob = 27/256

gsss, maj = s, prob =  3/256
gssg, maj = x, prob =  9/256
gsgs, maj = x, prob =  9/256
gsgg, maj = g, prob = 27/256

ggss, maj = x, prob =  9/256
ggsg, maj = g, prob = 27/256
gggs, maj = g, prob = 27/256
gggg, maj = g, prob = 81/256

Overall, we have a such probability:
maj = g, prob = 189/256 = 73.8%
maj = x, prob =  54/256 = 21.1%
max = s, prob =  13/256 =  5.1%
If the undefined is shared, 1/4 sand and 3/4 grass, like originally aimed, we 
get:
maj = g, prob =  89.8%
max = s, prob =  10.2%

Which, as you can see is not equal to the original ratios of 75% grass, and 25%
sand. Worse, this effect is exponential, given the number of blurring levels.
After 8 blurring, you will get 100% grass by all chances.

The only case where you don't have this effect, is when you have equal ratios of
all lands. For instance 1/3 water, 1/3 sand and 1/3 grass, will mostly end up
into the same ratios after blurring.


Now, to fix this problem you have to setup a small theory. Here is the way I
remember it works:
The goal is to find the starting ratios which will end up into the requested
ration, after all blurring levels.
You can visualise the problem into an unity cube. Each axis is one of the
land-type: water, sand or grass. On each axis, 0 means 0% and 1 means 100% of
each resource. One dot into the cube represents a probability of each land-type.
Each blurring level is a math transformation of one point into the cube into
another.
To find how to go from one point to another, we can use the simulateRandomMap(),
which will actually make a map, blur it and report final ratios, but into
smaller (1/16) scale. The problem is that it's not reversible. That mean that
you can only find the ending-ratios from the starting-ratios.
We also have a math expression, but it is not really accurate, due to discrete
effects. But it has the advantage to be formula-based, so we can get the
starting-ratios from the desired ending-ratios, tough it is not accurate.
Now, using both the math formula and the pragmatic simulateRandomMap(), we
evolve using a newton-like algorithm, from the final-requested-ratios, to the
starting-actual-ratios.
The line 342 to 440, into bool Map::makeRandomMap(MapGenerationDescriptor
&descriptor) of MapGenerator.cpp, are doing it (the for (int r=1; r<=smooth;
r++) loop).

Once found, the ratios are displayed into the console. For instance:
makeRandomMap::old-base=(0.100000, 0.000000, 0.900000)
makeRandomMap::new-base =(0.392261, 0.000000, 0.607739)
Means that I want 90% grass and 10% water. The algorithm finds out that we need
to start with 60.8% grass and 39.8% water. Once the
A bit lower we can read:
makeRandomMap::beforeCount=(0.385681, 0.000000, 0.614319)
makeRandomMap::final count=(0.043945, 0.000000, 0.956055)
Once created the map actually started with 38.6% of water instead of the 39.8%.
This is because the random is random! The land-type is selected randomly for
each of them. As a result, the map will actually end up with 4.4% of water
instead of 10%. Oppositely, on another run, you can get ends up with higher
ratio of water. Getting better results is possible, but it will need more
computation.

Still, the algorithm "cheats" during the blurring process in order to stabilize
the exponential effect. To achieve this smoothly, it does bias the probability
to make unwanted changes. That mean that the further we are of our ratios goals,
the less likely a change is to occur.

There is good chance that a better theory, could end up into a more simple
algorithm. For instance, if someone finds the exact math expression to go from
the wished-ration and number of blurring steps to the starting-ratios, then it
would be faster and better.


Is it all clear ?

Luc-Olivier