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

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

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.

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.

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.

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

Cheers,
RossW
=====