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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Mon, Oct 22, 2001 at 07:04:18PM -0400, Jason Dorje Short wrote:
> "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;
> >      ...
> >   }

The idea of such a filter is nice.

> > 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.

It looks like the filter approach and the "classical" approach both
have cases were one is faster. What do you think about a general
interface:

#define RAND_POS(x, y, pos_check,max_count)
   if(max_count==0)
      RAND_POS_CHECKED(x,y,pos_check);
   else
   {
    do {
      x=myrand(map.xsize);
      y=myrand(map.ysize);
    } while (!(pos_check(x,y)) && max_count-->0);
   }

Now the programmer can choose based on number he collected which
approach he uses.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  "brand memory are for windows users that think their stability
   problems come from the memory"
    -- bomek in #freeciv