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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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. */
+  whole_map_iterate(x1, y1) {
+    if (filter(x1, y1)) {
+      count++;
+    }
+  } whole_map_iterate_end;
+
+  if (count == 0) {
+    return FALSE;
+  }
+
+  count = myrand(count);
+  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;
+}
+
+/**************************************************************************
 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.156
diff -u -r1.156 map.h
--- common/map.h        2003/09/29 17:42:37     1.156
+++ common/map.h        2003/09/29 21:54:45
@@ -335,6 +335,7 @@
 
 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, bool (*filter)(int x, int y));
 
 bool is_water_adjacent_to_tile(int x, int y);
 bool is_tiles_adjacent(int x0, int y0, int x1, int y1);
Index: server/barbarian.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/barbarian.c,v
retrieving revision 1.68
diff -u -r1.68 barbarian.c
--- server/barbarian.c  2003/09/19 14:14:45     1.68
+++ server/barbarian.c  2003/09/29 21:54:45
@@ -302,8 +302,57 @@
   return FALSE;
 }
 
+/* Variables used in checking for barbarian uprising positions. */
+static int uprise_civ_check, uprise_gov_check;
+
+/****************************************************************************
+  Return TRUE iff this is a valid position for barbarians.  See
+  try_summon_barbarian().  This function is fairly slow, given that it may
+  have to be called many times.
+****************************************************************************/
+static bool is_valid_barbarian_pos(int x, int y)
+{
+  struct city *pcity;
+  int xu, yu, dist;
+
+  /* FIXME: replace with appropriate terrain flag. */
+  if (map_get_terrain(x, y) == T_TUNDRA
+      || map_get_terrain(x, y) == T_ARCTIC) {
+    return FALSE;
+  }
+
+  if (!(pcity = dist_nearest_city(NULL, x, y, TRUE, FALSE))) {
+    /* any city */
+    return FALSE;
+  }
+
+  dist = real_map_distance(x, y, pcity->x, pcity->y);
+  if (dist > MAX_UNREST_DIST || dist < MIN_UNREST_DIST) {
+    return FALSE;
+  }
+
+  /* Sea Raiders can come out of unknown sea territory. */
+  if (!find_empty_tile_nearby(x, y, &xu, &yu)
+      || (!map_is_known(xu, yu, city_owner(pcity))
+         && !is_ocean(map_get_terrain(xu, yu)))
+      || !is_near_land(xu, yu)) {
+    return FALSE;
+  }
+
+  /* Do not harass small civs (or too early in the game). */
+  if (uprise_civ_check > (city_list_size(&city_owner(pcity)->cities) -
+                        UPRISE_CIV_SIZE / (game.barbarianrate - 1))
+      || uprise_gov_check > get_gov_pcity(pcity)->civil_war) {
+    return FALSE;
+  }
+
+  /* Looks like this is a good place for barbarians! */
+  return TRUE;
+}
+
 /**************************************************************************
   The barbarians are summoned at a randomly chosen place if:
+  0. The terrain is not tundra or arctic.
   1. It's not closer than MIN_UNREST_DIST and not further than 
      MAX_UNREST_DIST from the nearest city. City owner is called 'victim' 
      here.
@@ -323,46 +372,25 @@
 static void try_summon_barbarians(void)
 {
   int x, y, xu, yu;
-  int i, boat, cap, dist, unit;
+  int i, boat, cap, unit;
   int uprise = 1;
+  struct player *victim, *barbarians;
   struct city *pc;
-  struct player *barbarians, *victim;
+  static int uprisings = 0;
 
-  /* No uprising on North or South Pole */
-  do {
-    rand_map_pos(&x, &y);
-  } while (y == 0 || y == map.ysize - 1);
-
-  if (!(pc = dist_nearest_city(NULL, x, y, TRUE, FALSE))) {
-    /* any city */
-    return;
-  }
-
-  victim = city_owner(pc);
-
-  dist = real_map_distance(x, y, pc->x, pc->y);
-  freelog(LOG_DEBUG,"Closest city to %d %d is %s at %d %d which is %d far", 
-          x, y, pc->name, pc->x, pc->y, dist);
-  if (dist > MAX_UNREST_DIST || dist < MIN_UNREST_DIST) {
-    return;
+  /* Pick random values for this barbarian check. */
+  uprise_civ_check = myrand(UPRISE_CIV_MORE);
+  uprise_gov_check = myrand(100);
+  if (!rand_map_pos_filtered(&x, &y, is_valid_barbarian_pos)) {
+    return; /* No barbarians this time. */
   }
 
-  /* I think Sea Raiders can come out of unknown sea territory */
-  if (!find_empty_tile_nearby(x,y,&xu,&yu)
-      || (!map_is_known(xu, yu, victim)
-         && !is_ocean(map_get_terrain(xu, yu)))
-      || !is_near_land(xu, yu)) {
-    return;
-  }
+  freelog(LOG_NORMAL, "%d: uprising %d at %d,%d",
+         game.year, ++uprisings, x, y);
 
-  /* do not harass small civs - in practice: do not uprise at the beginning */
-  if ((int)myrand(UPRISE_CIV_MORE) >
-           (int)city_list_size(&victim->cities) -
-                UPRISE_CIV_SIZE/(game.barbarianrate-1)
-      || myrand(100) > get_gov_pcity(pc)->civil_war) {
-    return;
-  }
-  freelog(LOG_DEBUG, "Barbarians are willing to fight");
+  pc = dist_nearest_city(NULL, x, y, TRUE, FALSE);
+  victim = city_owner(pc);
+  find_empty_tile_nearby(x, y, &xu, &yu);
 
   if (map_has_special(x, y, S_HUT)) { /* remove the hut in place of uprising */
     map_clear_special(x,y,S_HUT);
@@ -425,23 +453,15 @@
 **************************************************************************/
 void summon_barbarians(void)
 {
-  int i, n;
-
-  if (game.barbarianrate == 0) {
-    return;
-  }
+  int i;
 
   if (game.year < game.onsetbarbarian) {
     return;
   }
 
-  n = map_num_tiles() / MAP_FACTOR;
-  if (n == 0) {
-    /* Allow barbarians on maps smaller than MAP_FACTOR */
-    n = 1;
-  }
-
-  for (i = 0; i < n * (game.barbarianrate - 1); i++) {
-    try_summon_barbarians();
+  for (i = 0; i < game.barbarianrate; i++) {
+    if (myrand(BARB_FACTOR) == 0) {
+      try_summon_barbarians();
+    }
   }
 }
Index: server/barbarian.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/barbarian.h,v
retrieving revision 1.9
diff -u -r1.9 barbarian.h
--- server/barbarian.h  2003/05/05 12:41:39     1.9
+++ server/barbarian.h  2003/09/29 21:54:45
@@ -25,7 +25,9 @@
 #define UPRISE_CIV_MORE  30
 #define UPRISE_CIV_MOST  50
 
-#define MAP_FACTOR     2000  /* adjust this to get a good uprising frequency */
+/* Adjust this to get a good uprising frequency.  Barbarians are summoned
+ * every 1/BARB_FACTOR attempts. */
+#define BARB_FACTOR 10
 
 bool unleash_barbarians(int x, int y);
 void summon_barbarians(void);

Index: server/barbarian.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/barbarian.c,v
retrieving revision 1.68
diff -u -r1.68 barbarian.c
--- server/barbarian.c  2003/09/19 14:14:45     1.68
+++ server/barbarian.c  2003/09/29 21:59:28
@@ -331,7 +331,8 @@
   /* No uprising on North or South Pole */
   do {
     rand_map_pos(&x, &y);
-  } while (y == 0 || y == map.ysize - 1);
+  } while (map_get_terrain(x, y) == T_TUNDRA
+          || map_get_terrain(x, y) == T_ARCTIC);
 
   if (!(pc = dist_nearest_city(NULL, x, y, TRUE, FALSE))) {
     /* any city */