[Freeciv-Dev] (PR#7311) rewrite create_start_positions

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7311 >

This patch rewrites create_start_positions to use rand_map_pos_filtered.

The main advantage is that it fails more consistently: we don't have to
loop 10 million times to be sure that there's no remaining valid map
position; rand_map_pos_filtered just returns FALSE and we know.  Thus it
is many, many times faster when there is no available starting position.

There are still a couple of biases, however.

(1) The minimum distance is decreased over the course of the loop (if
there are too many start positions).  This means some players may be
given more advantageous positions than other players.  Of course we knew
that already.

(2) We only try to place players once.  Once a player is in position,
they won't be moved.  This means sometimes even if there is a valid set
of start positions, it won't be found.  We'll try repeatedly to place
the next player (until we find a good start position) but we never
consider moving a player once he's already in place.

These are related in that it would be "cleanest" to restart placing
players when the distance is decreased.

[Digression]
To be sure of finding a start position, if one exists, will take C(M, N)
= M! / (N!(M-N)!) checks, where M is the number of valid
(grassland/plains) starter positions and N is the number of players. 
This value can be very large: on a 200x100 map with 10,000 valid start
positions and 30 players, the value C(10,000, 30) is impossibly large. 
Although when the island's "starter" value is taken into account, it may
get a bit better: with 2 players per island and equal-sized islands it
would take
  C(10,000 / 15, 30 / 15) ^ 15 = C(666, 2) ^ 15
                               > (2 * 10^5) ^ 15
                               > 10^105
which is still impossibly large.

jason

Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.157
diff -u -r1.157 map.c
--- common/map.c        2004/01/24 23:19:26     1.157
+++ common/map.c        2004/01/25 02:15:10
@@ -1399,6 +1399,47 @@
 }
 
 /**************************************************************************
+  Give a random square anywhere on the map for which the 'filter' function
+  returns TRUE.  Return FALSE if none can be found.  The filter may be
+  NULL if any position is okay; if non-NULL it shouldn't have any side
+  effects.
+**************************************************************************/
+bool rand_map_pos_filtered(int *x, int *y, void *data,
+                          bool (*filter)(int x, int y, void *data))
+{
+  int tries = 0;
+  const int max_tries = map.xsize * map.ysize / 10;
+
+  /* First do a few quick checks to find a spot.  The limit on number of
+   * tries could use some tweaking. */
+  do {
+    index_to_map_pos(x, y, myrand(map.xsize * map.ysize));
+  } while (filter && !filter(*x, *y, data) && ++tries < max_tries);
+
+  /* If that fails, count all available spots and pick one.
+   * Slow but reliable. */
+  if (tries == max_tries) {
+    int count = 0, positions[map.xsize * map.ysize];
+
+    whole_map_iterate(x1, y1) {
+      if (filter(x1, y1, data)) {
+       positions[count] = map_pos_to_index(x1, y1);
+       count++;
+      }
+    } whole_map_iterate_end;
+
+    if (count == 0) {
+      return FALSE;
+    }
+
+    count = myrand(count);
+    index_to_map_pos(x, y, count);
+  }
+
+  return TRUE;
+}
+
+/**************************************************************************
 Return the debugging name of the direction.
 **************************************************************************/
 const char *dir_get_name(enum direction8 dir)
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.170
diff -u -r1.170 map.h
--- common/map.h        2004/01/24 23:19:26     1.170
+++ common/map.h        2004/01/25 02:15:10
@@ -284,6 +284,8 @@
 
 void rand_neighbour(int x0, int y0, int *x, int *y);
 void rand_map_pos(int *x, int *y);
+bool rand_map_pos_filtered(int *x, int *y, void *data,
+                          bool (*filter)(int x, int y, void *data));
 
 bool is_water_adjacent_to_tile(int x, int y);
 bool is_tiles_adjacent(int x0, int y0, int x1, int y1);
Index: server/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.126
diff -u -r1.126 mapgen.c
--- server/mapgen.c     2004/01/24 23:19:27     1.126
+++ server/mapgen.c     2004/01/25 02:15:11
@@ -1091,7 +1091,23 @@
   return FALSE;
 }
 
+struct start_filter_data {
+  int count; /* Number of existing start positions. */
+  int dist; /* Minimum distance between starting positions. */
+};
+
 /**************************************************************************
+  Return TRUE if this is a valid starting position.
+**************************************************************************/
+static bool is_valid_start_pos(int x, int y, void *dataptr)
+{
+  struct start_filter_data *data = dataptr;
+
+  return (islands[(int)map_get_continent(x, y)].starters != 0
+         && !is_illegal_start_pos(x, y, data->count, data->dist));
+}
+
+/**************************************************************************
   where do the different races start on the map? well this function tries
   to spread them out on the different islands.
 
@@ -1102,18 +1118,14 @@
 #define MAXTRIES 10000000
 void create_start_positions(void)
 {
-  int nr=0;
-  int dist=40;
-  int x, y, j=0, k, sum;
-  int counter = 0;
+  int x, y, k, sum;
+  struct start_filter_data data;
 
   if (!islands)                /* already setup for generators 2,3, and 4 */
     setup_isledata();
 
-  if(dist>= map.xsize/2)
-    dist= map.xsize/2;
-  if(dist>= map.ysize/2)
-    dist= map.ysize/2;
+  data.count = 0;
+  data.dist = MIN(40, MIN(map.xsize / 2, map.ysize / 2));
 
   sum=0;
   for (k=0; k<=map.num_continents; k++) {
@@ -1122,36 +1134,27 @@
       freelog(LOG_VERBOSE, "starters on isle %i", k);
     }
   }
-  assert(game.nplayers<=nr+sum);
+  assert(game.nplayers <= data.count + sum);
 
   map.start_positions = fc_realloc(map.start_positions,
                                   game.nplayers
                                   * sizeof(*map.start_positions));
-  while (nr<game.nplayers) {
-    rand_map_pos(&x, &y);
-    if (islands[(int)map_get_continent(x, y)].starters != 0) {
-      j++;
-      if (!is_illegal_start_pos(x, y, nr, dist)) {
-       islands[(int)map_get_continent(x, y)].starters--;
-       map.start_positions[nr].x=x;
-       map.start_positions[nr].y=y;
-       nr++;
-      }else{
-       if (j>900-dist*9) {
-         if(dist>1)
-           dist--;               
-         j=0;
-       }
+  while (data.count < game.nplayers) {
+    if (rand_map_pos_filtered(&x, &y, &data, is_valid_start_pos)) {
+      islands[(int)map_get_continent(x, y)].starters--;
+      map.start_positions[data.count].x = x;
+      map.start_positions[data.count].y = y;
+      data.count++;
+    } else {
+      data.dist--;
+      if (data.dist == 0) {
+       char filename[] = "map_core.sav";
+       save_game(filename);
+       die(_("The server appears to have gotten into an infinite loop "
+             "in the allocation of starting positions, and will abort.\n"
+             "The map has been saved into %s.\n"
+             "Please report this bug at %s."), filename, WEBSITE_URL);
       }
-    }
-    counter++;
-    if (counter > MAXTRIES) {
-      char filename[] = "map_core.sav";
-      save_game(filename);
-      die(_("The server appears to have gotten into an infinite loop "
-           "in the allocation of starting positions, and will abort.\n"
-           "The map has been saved into %s.\n"
-           "Please report this bug at %s."), filename, WEBSITE_URL);
     }
   }
   map.num_start_positions = game.nplayers;