[Freeciv-Dev] Re: barbarians on the poles (PR#6183)

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

The problem below is a generic one, the standard solution is to cache
the results of the test collection loop, and not duplicate the expense
of looping twice.

Some optimizations inserted to show how this is typically done, within
the given code.


Note, in the case of a repeated call, one would want to always use the
second (slower) solution, reusing the collected cached array. This means
that after the first call the code is effectively just the last few lines.

   if (count <= 0) {
     return FALSE;
   }
   kk = myrand(count--);
   *x = xy[kk][1], xy[kk][1] = xy[count][1], xy[count][1] = *x;
   *y = xy[kk][2], xy[kk][2] = xy[count][2], xy[count][2] = *y;
   return TRUE;

This probably means a slight rearrangement into two functions a fast and
a slow with the (slow) caching solution having a reentrant flag to indicate
whether the cache should be rebuilt or not.


Otherwise the solution is quite reasonable and definitely a good tool
for handling this sort of generic problem where much of the uniqueness
is encapsulated in the (*filter)().

Cheers,
RossW
=====

Jason Short wrote:
> Here's a full patch to fix this.
> 
> - A new function, rand_map_pos_filtered, is used.
> 
> - This function is used to find a _valid_ spot for barbarians.
> 
> - Barbarians are now summoned a fixed 1/10 of the time when 
> summon_barbarians() is called.
> 
> - Barbarians will never be summoned on arctic or tundra.
> 
> - If there are no valid positions for summoning, the server won't fail.
> 
> This does change the behavior.  Barbarian summoning is still random, but 
> with a different distribution.  In my tests the average # summoned was 
> about the same.
> 
> The only advantage of the new method is that it is robust.  If this is 
> not a concern we can use a much simpler fix (also attached).  Note that 
> we have the exact same dilemma in several other places, however.
> 
> Comments?
> 
> jason
> 
> ------------------------------------------------------------------------
> 
> ? core.19462
> Index: common/map.c
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
> retrieving revision 1.146
> diff -u -r1.146 map.c
> --- common/map.c      2003/09/29 02:42:15     1.146
> +++ common/map.c      2003/09/29 21:54:45
> @@ -1497,6 +1497,51 @@
>  }
>  
>  /**************************************************************************
> + Random square anywhere on the map for which the 'filter' function
> + returns true.  return FALSE if none can be found.
> +**************************************************************************/
> +bool rand_map_pos_filtered(int *x, int *y, bool (*filter)(int x, int y))
> +{
> +  int tries = 0, count = 0;
> +  const int max_tries = map.xsize * map.ysize / 10;
> +
> +  /* First do a few quick checks to find a spot. */
> +  do {
> +    rand_map_pos(x, y);
> +    if (filter(*x, *y)) {
> +      return TRUE;
> +    }
> +  } while (++tries < max_tries);
> +
> +  /* If that fails, count all available spots and pick one.
> +   * Slow but reliable. */
      int xy[map.xsize*map.ysize][2];
> +  whole_map_iterate(x1, y1) {
> +    if (filter(x1, y1)) {
          xy[count][1] = x1;
          xy[count][2] = y1;
> +      count++;
> +    }
> +  } whole_map_iterate_end;
> +
> +  if (count == 0) {
> +    return FALSE;
> +  }
> +
> +  count = myrand(count);
      *x = xy[count][1];
      *y = xy[count][2];
      return TRUE;

> +  whole_map_iterate(x1, y1) {
> +    if (filter(x1, y1)) {
> +      if (count == 0) {
> +     *x = x1;
> +     *y = y1;
> +     return TRUE;
> +      }
> +      count--;
> +    }
> +  } whole_map_iterate_end;
> +
> +  assert(0);
> +  return FALSE;
> +}