[Freeciv-Dev] (PR#10511) infinite loop in creating starting positions

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

The infinite loop problem has been reported more often.  If you have a 
high aifill (30) with a small map size (1) and low landmass (15), there 
isn't enough room to place starting positions.

This patch improves that.  I'd be rather surprised if starting position 
placement ever fails after this.  Of course you may end up with a game 
that's not playable.  But at least you'll have learned your lesson, and 
won't blame the game.  It should be applied to both branches.

Changes:

- When decreasing "dist", restart the placement from scratch.  This is 
needed for fairness (the current method isn't fair), particularly when 
we start dropping restrictions.  This change necessitates a 
data->starters value.

- When decreasing "dist", it may be decreased to or below 0.  When this 
happens the minimum distance doesn't actually drop any more, but instead 
we start dropping restrictions.  Note there is a special case added to 
prevent two starters from being on the same tile (otherwise with dist<=0 
this would be possible).

* First we allow starting positions to be placed on huts.  This is easy 
enough; we just remove the huts afterwards.  Unfortunately huts are 
pretty rare so it doesn't help in most games.

* Then we allow starting positions to be placed on any terrain. 
Normally only grassland and plains are eligible; when the restriction is 
dropped any non-ocean terrain is eligible.  This may include arctic, 
except that polar continents generally aren't eligible if you have 
separatepoles (see below).  In every case I've tested, dropping this 
restriction allows placement to complete.

* Then we allow starting positions to be on any continent.  Normally the 
number of starters per continent is set at the beginning, but when this 
restriction is dropped players can be put on any continent.  Of course 
this allows all land tiles to be eligible starters, and there are at 
least 150 land tiles (landmass 15% with size 1000 tiles), so it should 
never fail.  But the game will be unplayable because players will be all 
over the poles.

For each dropped restriction an error message is sent.  If none of the 
restriction-droppings helps we'll still end up with an error.  However I 
changed this so it doesn't dump core (this is a user error not a code 
error) but just does an exit().

Note several translatable strings are changed by this patch.

I know marcelo had some code to improve starting positions.  But those 
patches are 10x larger than this and probably shouldn't be committed to 
the stable branch.  This patch addresses only this one very serious problem.

jason

? newtiles
Index: server/generator/startpos.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/startpos.c,v
retrieving revision 1.3
diff -u -r1.3 startpos.c
--- server/generator/startpos.c 29 Sep 2004 02:24:24 -0000      1.3
+++ server/generator/startpos.c 13 Oct 2004 18:30:38 -0000
@@ -20,6 +20,7 @@
 #include "map.h"
 
 #include "maphand.h"
+#include "plrhand.h"
 
 #include "mapgen_topology.h"
 #include "startpos.h"
@@ -174,7 +175,17 @@
 
 struct start_filter_data {
   int count; /* Number of existing start positions. */
-  int dist; /* Minimum distance between starting positions. */
+
+  /* Minimum distance between starting positions.  If 0 or negative, then
+   * we start dropping restrictions on the starting positions. */
+#define NO_HUT_CHECK 0
+#define NO_TERRAIN_CHECK -1
+#define NO_CONTINENT_CHECK -2
+#define STARTPOS_ERROR -3
+  int dist;
+
+  /* Number of starting positions on each continent. */
+  int *starters;
 };
 
 /**************************************************************************
@@ -194,22 +205,24 @@
   const struct start_filter_data *data = dataptr;
   int i;
   Terrain_type_id t = map_get_terrain(ptile);
+  int continent = map_get_continent(ptile);
 
   if (is_ocean(map_get_terrain(ptile))) {
     return FALSE;
   }
 
-  if (islands[(int)map_get_continent(ptile)].starters == 0) {
+  if (data->dist > NO_CONTINENT_CHECK
+      && data->starters[continent] >= islands[continent].starters) {
     return FALSE;
   }
 
   /* Only start on certain terrain types. */
-  if (!terrain_has_flag(t, TER_STARTER)) {
+  if (data->dist > NO_TERRAIN_CHECK && !terrain_has_flag(t, TER_STARTER)) {
     return FALSE;
   }
   
   /* Don't start on a hut. */
-  if (map_has_special(ptile, S_HUT)) {
+  if (data->dist > NO_HUT_CHECK && map_has_special(ptile, S_HUT)) {
     return FALSE;
   }
   
@@ -219,6 +232,11 @@
   for (i = 0; i < data->count; i++) {
     struct tile *tile1 = map.start_positions[i].tile;
 
+    if (tile1 == ptile) {
+      /* Never allow two starting positions on the same tile. */
+      return FALSE;
+    }
+
     if (map_get_continent(ptile) == map_get_continent(tile1)
        && real_map_distance(ptile, tile1) < data->dist) {
       return FALSE;
@@ -237,6 +255,7 @@
   struct tile *ptile;
   int k, sum;
   struct start_filter_data data;
+  int starters[map.num_continents];
   
   if (!islands) {
     /* Isle data is already setup for generators 2, 3, and 4. */
@@ -255,12 +274,15 @@
   }
   assert(game.nplayers <= data.count + sum);
 
+  data.starters = starters;
+  memset(starters, 0, sizeof(starters));
+
   map.start_positions = fc_realloc(map.start_positions,
                                   game.nplayers
                                   * sizeof(*map.start_positions));
   while (data.count < game.nplayers) {
     if ((ptile = rand_map_pos_filtered(&data, is_valid_start_pos))) {
-      islands[(int)map_get_continent(ptile)].starters--;
+      data.starters[(int)map_get_continent(ptile)]++;
       map.start_positions[data.count].tile = ptile;
       map.start_positions[data.count].nation = NO_NATION_SELECTED;
       freelog(LOG_DEBUG, "Adding %d,%d as starting position %d.",
@@ -268,17 +290,55 @@
       data.count++;
 
     } else {
-      
       data.dist--;
-      if (data.dist == 0) {
-       die(_("The server appears to have gotten into an infinite loop "
-             "in the allocation of starting positions, and will abort.\n"
-             "Maybe the numbers of players/ia is too much for this map.\n"
-             "Please report this bug at %s."), WEBSITE_URL);
+
+      /* Reset everything so we start from scratch. */
+      data.count = 0;
+      memset(starters, 0, sizeof(starters));
+
+      if (data.dist == NO_HUT_CHECK) {
+       const char *msg = _("There are too many players in the game, so "
+                           "players may be placed on tiles with huts.");
+
+       notify_player_ex(NULL, NULL, E_NOEVENT, "%s", msg);
+       freelog(LOG_ERROR, "%s", msg);
+      }
+
+      if (data.dist == NO_CONTINENT_CHECK) {
+       const char *msg = _("There are too many players in the game, so "
+                           "players may be placed on any continent "
+                           "(including poles).");
+
+       notify_player_ex(NULL, NULL, E_NOEVENT, "%s", msg);
+       freelog(LOG_ERROR, "%s", msg);
+      }
+
+      if (data.dist == NO_TERRAIN_CHECK) {
+       const char *msg = _("There are too many players in the game, so "
+                           "players may be placed on any terrain.");
+
+       notify_player_ex(NULL, NULL, E_NOEVENT, "%s", msg);
+       freelog(LOG_ERROR, "%s", msg);
+      }
+
+      if (data.dist == STARTPOS_ERROR) {
+       const char *msg = _("The game cannot place enough starting "
+                           "positions because the number of players/aifill "
+                           "is too high.");
+
+       notify_player_ex(NULL, NULL, E_NOEVENT, "%s", msg);
+       freelog(LOG_FATAL, "%s", msg);
+       /* TODO: should just return to pregame. */
+       exit(EXIT_FAILURE);
       }
     }
   }
   map.num_start_positions = game.nplayers;
+  for (k = 0; k < game.nplayers; k++) {
+    /* In rare cases starting positions may be placed on huts.  See
+     * NO_HUT_CHECK above. */
+    map_clear_special(map.start_positions[k].tile, S_HUT);
+  }
 
   free(islands);
   islands = NULL;