[Freeciv-Dev] Re: (PR#2749) mapgen patch 2 of 3 - land placement

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

Karen Yeats wrote:
> Hello,
> 
> Here is the modification Ross requested.  I hope it will be sufficient
> to satisfy his concerns.

It is a start ...

> The main problem it seeks to address is the fact that a function which
> is calculated just at each point and must be independant of adjacent
> points can't introduce truly local effects.  The only way to fake them
> is to iterate the procedure as I had done for forests and jungles. 

The flaw in this is that you are doing a global iteration of a global
distribution to try and get local effects. Wrong end of the horse to
get behind ...

> Ross' idea was to calculate the values of the placement functions in
> advance and store them.  This way the effect at a point can influence
> adjacent points while still permitting us to calculate a nice
> deterministic distribution.
> 
> The cost is two extra whole_map_iterates in speed and the actual
> structure which stores the calculated values in space.  The result is
> the potential for true local effects, see the forest code in this patch
> for a simple example.

Actually, I think you saved calculating the function distribution twice
by storing it the first time. This can become a significant part, while
whole_map indexing and lookup becomes trivial in comparison.

> Ross, I hope you will see that though I chose a very simple version of
> local effects to use for forests much more is now possible, including
> recursive stuff like current cvs.

Well, not quite up to CVS capabilities yet ...

> Karen

    A few illustrated points, by no means a full review, though.

+  function_map = fc_calloc (map.ysize * map.xsize, sizeof(int));

+  /* initialize */
+  whole_map_iterate(x, y) {
+    fmap(x, y) = 0;
+  } whole_map_iterate_end;
    This is unnecessary if you use calloc. I think GB already pointed
this out. Besides, memset is faster for block clears.

+  /* calculate */
+  whole_map_iterate(x, y) {
+    function(x, y, function_map);
+  } whole_map_iterate_end;

This does provide something of a hook, but it is very hard to figure out
how to duplicate CVS using it. To duplicate CVS, you need to make all
tiles have the same value that match your local pattern, i.e. in cvs,
surround this one in a pattern that you get by recursive adjacent
iteration with both a random and damping factor.

There are two problems. The first is that every tile now generates its
local pattern and they cannot all be represented simultaneously. In CVS
only the selected pattern is needed as you are selecting at the time.
Here you haven't yet done the selection. The second is a feedback effect.
You cannot depend on the values at fmap during the iteration because
your iteration would then impose a very obnoxious order dependency.
But the first implies you have to to get the patterns right.

It probably works better if you first generate the single-valued
function(x,y) map, then do a random order localization/smoothing function.
using it as input. This is sort of the code flavour in smooth_map()
and in fact is how height_maps are generated with feedback effects in
CVS. Helga also used this sort of technique to generate rainfall
patterns.

+  /* make the distribution of the placing function */
+  dist = fc_calloc (max + 1, sizeof(int));

+  for (i = 0; i <= max; i++) {
+    dist[i]=0;
+  }
    Again, this is unnecessary if you use calloc.

+    whole_map_iterate(x, y){
+      if ((fmap(x, y) < level) && not_placed(x, y)){
+       map_set_terrain(x, y, ter);
+      }
+      else if ((fmap(x, y) == level) && (myrand(100) < percent)
+              && not_placed(x, y)) {
+       map_set_terrain(x, y, ter);
+      }
+    } whole_map_iterate_end;
+  }

    Note, you again have an order dependency in the above because
while the <level part is rigorously defined, the ==level is not.
This is also a source of error in your placement accuracy since
there is no guarantee you will place all tiles, and you can even
place more than allowed.

    Normally this would not be a problem, but the only real advantage
you claim is an accurate numerical placement and this code makes
that claim somewhat less than truthful. CVS may actually be better
in that it usually tracks the actual counts.

   Note, this is actually starting to get a lot more expensive than
CVS, since in many CVS algorithms you only have to iterate until you
have allocated an appropriate number of tiles. If the number of tiles
is small, you only have to do any expensive function evaluations for a
fraction of the whole_map.

   It is trivial to fix a lot of the really piggish CVS algorithms
by doing a whole_map loop to fast select possible tiles and then
randomly pick off the required number after any expensive distribution
functional massaging of this submap list. In most cases, you are really
only concerned about a small subset of the whole_map.

   You can probably do something like this to collect the set of
valid indicies/coordinates in the first pass as well. In the final
distribution, you then don't need to do a whole_map, nor call things
like not_placed().

   In fact, you probably shouldn't even be calculating values for
tiles that are not_placed(). It is generally poor style to rely on all
the passed in functions to do this. If your distribution counts tiles
you can't place that will also screw things up in weird and wonderful
ways.


+  fmap(x, y) += val * parameter / 100;
+  adjc_iterate(x, y, x1, y1) {
+    fmap(x1, y1) += val * (100 - parameter) / 3200;
+  } adjc_iterate_end;
+
+  square_iterate(x, y, 2, x1, y1) {
+    fmap(x1, y1) += val * (100 - parameter) / 3200;
+  } square_iterate_end;

    You should probably comment the magic numbers to make it clear
that the 20-80 split is averaged with 1/8 th of every adjacent
tile ((100-20)/32 == 20/8). I suspect that the 25 tile square
iterate will mean you might be slightly overbudgetted if the
distribution is to be a percent-like value, i.e. 0-100. This
will lead to array overflows. At least check the value before
or after returning and again, make comments about the dangers.

    This is just a smoothing function. It does not generate the
sort of N-S elongated forest tracks that CVS does, since the
final hard distribution choice you use in the last step may
still only select a few bumps in the smoothed distribution.

    The hard coded distribution is a global selection. That is
why you need to set all the values to a nearly equivalent
number to generate a local effect.

    This also shows how the fundamental bias in your algorithm is
very much against local effects. It is very hard to do them and
harder to do them right.

    But at least it is now recognizing and starting to provide
some ways correct this deficiency.

Cheers,
RossW
=====