[Freeciv-Dev] Re: PATCH: rand_pos function and usage (PR#1017)

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

"Ross W. Wetmore" wrote:
> 
> Mistake ...
> 
> You really want to let the code do its own randomization, and not
> provide a generic function with *extremely* limited characteristics.
> 
> At 10:01 PM 01/10/17 -0700, jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
> >@@ -257,14 +256,16 @@
> >-    y=myrand(map.ysize*10/180)+map.ysize*110/180;
> >-    x=myrand(map.xsize);
> >+    do {
> >+      rand_pos(&x, &y);
> >+    } while (y < map.ysize * 110/180 || y >= map.ysize * 2/3);
> 
> This, for example is just incredibly stupid. Moreso when the whole
> operation is really a very specialized action. Let the code deal
> with this itself and not have to screen for a small fraction of the
> total map randomization in essentially open ended loops.

Map generation with arbitrary topologies is a tricky and ugly topic, I'll
grant you, but I'd like to make the current map generation code generalize
to any of the topologies we've discussed.  New map generators need not be
restricted in this way.

The loop can be made non-open-ended:

count = 0;
do {
  rand_pos(&x, &y);
  if (count > 1000) break;
} while (y < map.ysize * 110/180 || y >= map.ysize * 120/180);

This will give good results in the general case, but is pretty ugly compared
to the solution below.

> To get "sensible" maps, you should plan on having lots of special
> generators or sub generators that really do know the topology and can
> properly deal with the sorts of things like "desert latitudes". You
> then select the elements you want, rather than trying to make one
> humongous routine try to do it all.

I'd rather avoid that for now.  The mapgen changes I've proposed will have
no noticable effect with the current topology and should work fairly
sensibly for most other topologies.  What's wrong with that?

> Also, for cases where you are making any significant number of
> selections from the set it is far better to generate a randomized
> list of the set, and walk through it.
> 
>   /* build a random list of valid desert latitude locations */
>   k = 0;
>   block_xy_iterate(x, y, 0, xsize, (ysize*110)/180, (ysize*120)/180) {
>     if( <any additional invalidation checks e.g. MAP_TYPE(x,y) != T_OCEAN> )
>       continue;
>     j = myrand(++k), yx[k-1] = yx[j], yx[j] = xy;
>   } block_xy_iterate_end;
> 
>   /* select "n" unique elements from the list */
>   for( j = map.deserts; k-- > 0 && j-- > 0; ) {
>     xy = yx[k], x = xy % xsize, y = xy/xsize;
>      ...
>   }
> 
> This sort of construct both ensures correct locations, and does no double
> or worse counting as frequently happens in spin loops.
> 
> This has finite cost as opposed to being open ended. Depending on how
> sophisticated the invalidation checks are, or the chance of succeeding
> in a purely random way, it may be 1/4, 1/10th or maybe even fewer
> selection elements compared to the total list that is the break even point.

Yes, for map generation something like this would make sense.  Note that
this will be much, much slower in the general case, but since this is just
map generation that's acceptable.  For stuff like barbarian generation
(which is currently restricted so as to not be on the poles), I believe
rand_pos nested inside a while loop is the most general and fastest
implementation.

Your block_xy_iterate loop is exactly the opposite of what I want, since it
assumes arbitrary information about the topology; I'd rather have a
whole_map_iterate with a filter on valid positions.  I would implement this
as a macro:

#define RAND_POS_CHECKED(x, y, pos_check)
{
  int x_vals[map.xsize*map.ysize];
  int y_vals[map.xsize*map.ysize];
  int count = 0;
  whole_map_iterate(x, y) {
    if (! (pos_check) )
      continue;
    y_vals[count] = y;
    x_vals[count] = x;
    count++;
  } whole_map_iterate_end;
  count = myrand(count);
  x = x_vals[count];
  y = y_vals[count];
}

This just yields one value from the chosen map area, but could easily be
modified to give n values.


I would also like to avoid a topology-specific rand_pos (like the one Raimar
has suggested).  I think such a function will be much more trouble than it's
worth.

> Some of the loops that have been increased from 10,000 to 100,000 so that
> they "terminate" successfully, should really be looked at.

From mapgen.c:

/**************************************************************************
  where do the different races start on the map? well this function tries
  to spread them out on the different islands.

  FIXME: MAXTRIES used to be 1.000.000, but has been raised to 10.000.000
         because a set of values hit the limit. At some point we want to
         make a better solution.
**************************************************************************/

but that's really outside the scope of my experience at this point, as are
the other high-limit loops I see on a cursory glance.

jason