[Freeciv-Dev] (PR#9741) Problem inside setup_isledata() (not really important)

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

> [mstefek - Fri Aug 20 07:03:17 2004]:

> Example: Suppose we have three players and two islands. The first one  
> with goodies = 2000 and the second with goodies = 1000. The first one  
> will get 3 starting positions and the second only one.

This patch uses Hamilton's method (from the distribute() function, see
PR#9755) to distribute starting positions.  In the above case it should
work fine and give 2 starters on the big island with 1 on the smaller. 
This may not be more fair in all situations but at least the algorithm
is guaranteed (the algorithm in use looks kindof like Webster's
algorithm which can in very rare cases entirely fail).

jason

? diff
? freeciv-1.14.99-devel.tar.gz
? orig
? server/civmanual.c
Index: server/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.144
diff -u -r1.144 mapgen.c
--- server/mapgen.c     19 Aug 2004 07:34:25 -0000      1.144
+++ server/mapgen.c     21 Aug 2004 05:03:40 -0000
@@ -1309,9 +1309,8 @@
 **************************************************************************/
 static void setup_isledata(void)
 {
-  int starters = 0;
-  int min,  i;
-  
+  int ratios[map.num_continents], results[map.num_continents], i;
+
   assert(map.num_continents > 0);
   
   /* allocate + 1 so can use continent number as index */
@@ -1356,56 +1355,15 @@
   } whole_map_iterate_end;
   
   /* now divide the number of desired starting positions among
-   * the continents so that the minimum number of resources per starting 
-   * position is as large as possible */
-  
-  /* set minimum number of resources per starting position to be value of
-   * the best continent */
-  min = 0;
+   * the continents. */
   for (i = 1; i <= map.num_continents; i++) {
-    if (min < islands[i].goodies) {
-      min = islands[i].goodies;
-    }
-  }
-  
-  /* place as many starting positions as possible with the current minumum
-   * number of resources, if not enough are placed, decrease the minimum */
-  while ((starters < game.nplayers) && (min > 0)) {
-    int nextmin = 0;
-    
-    starters = 0;
-    for (i = 1; i <= map.num_continents; i++) {
-      int value = islands[i].goodies;
-      
-      starters += value / min;
-      if (nextmin < (value / (value / min + 1))) {
-        nextmin = value / (value / min + 1);
-      }
-    }
-    
-    freelog(LOG_VERBOSE,
-           "%d starting positions allocated with\n"
-            "at least %d resouces per starting position; \n",
-            starters, min);
-
-    assert(nextmin < min);
-    /* This choice of next min guarantees that there will be at least 
-     * one more starter on one of the continents */
-    min = nextmin;
+    ratios[i - 1] = islands[i].goodies;
   }
-  
-  if (min == 0) {
-    freelog(LOG_VERBOSE,
-            "If we continue some starting positions will have to have "
-            "access to zero resources (as defined in get_tile_value). \n");
-    freelog(LOG_FATAL,
-            "Cannot create enough starting position and will abort.\n"
-            "Please report this bug at " WEBSITE_URL);
-    abort();
-  } else {
-    for (i = 1; i <= map.num_continents; i++) {
-      islands[i].starters = islands[i].goodies / min;
-    }
+
+  distribute(game.nplayers, map.num_continents, ratios, results);
+
+  for (i = 1; i <= map.num_continents; i++) {
+    islands[i].starters = results[i - 1];
   }
 }
 
Index: utility/shared.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/shared.c,v
retrieving revision 1.115
diff -u -r1.115 shared.c
--- utility/shared.c    20 Jul 2004 14:34:32 -0000      1.115
+++ utility/shared.c    21 Aug 2004 05:03:40 -0000
@@ -1320,3 +1320,101 @@
   }
   return group;
 }
+
+/****************************************************************************
+  Distribute "number" elements into "groups" groups with ratios given by
+  the elements in "ratios".  The resulting division is put into the "result"
+  array.
+
+  For instance this code is used to distribute trade among science, tax, and
+  luxury.  In this case "number" is the amount of trade, "groups" is 3,
+  and ratios[3] = {sci_rate, tax_rate, lux_rate}.
+
+  The algorithm used to determine the distribution is Hamilton's Method.
+****************************************************************************/
+void distribute(int number, int groups, int *ratios, int *result)
+{
+  int i, sum = 0, rest[groups], max_groups[groups], max_count, max;
+  const int original_number = number;
+
+  /* 
+   * Distribution of a number of items into a number of groups with a given
+   * ratio.  This follows a modified Hare/Niemeyer algorithm (also known
+   * as "Hamilton's Method"):
+   *
+   * 1) distribute the whole-numbered part of the targets
+   * 2) sort the remaining fractions (called rest[])
+   * 3) divide the remaining source among the targets starting with the
+   *    biggest fraction. (If two targets have the same fraction the
+   *    target with the smaller whole-numbered value is chosen.  If two
+   *    values are still equal it is the _first_ group which will be given
+   *    the item.)
+   */
+
+  for (i = 0; i < groups; i++) {
+    assert(ratios[i] >= 0);
+    sum += ratios[i];
+  }
+
+  /* 1.  Distribute the whole-numbered part of the targets. */
+  for (i = 0; i < groups; i++) {
+    result[i] = number * ratios[i] / sum;
+  }
+
+  /* 2a.  Determine the remaining fractions. */
+  for (i = 0; i < groups; i++) {
+    rest[i] = number * ratios[i] - result[i] * sum;
+  }
+
+  /* 2b. Find how much source is left to be distributed. */
+  for (i = 0; i < groups; i++) {
+    number -= result[i];
+  }
+
+  while (number > 0) {
+    max = max_count = 0;
+
+    /* Find the largest remaining fraction(s). */
+    for (i = 0; i < groups; i++) {
+      if (rest[i] > max) {
+       max_count = 1;
+       max_groups[0] = i;
+       max = rest[i];
+      } else if (rest[i] == max) {
+       max_groups[max_count] = i;
+       max_count++;
+      }
+    }
+
+    if (max_count == 1) {
+      /* Give an extra source to the target with largest remainder. */
+      result[max_groups[0]]++;
+      rest[max_groups[0]] = 0;
+      number--;
+    } else {
+      int min = result[max_groups[0]], which_min = max_groups[0];
+
+      /* Give an extra source to the target with largest remainder and
+       * smallest whole number. */
+      assert(max_count > 1);
+      for (i = 1; i < max_count; i++) {
+       if (result[max_groups[i]] < min) {
+         min = result[max_groups[i]];
+         which_min = max_groups[i];
+       }
+      }
+      result[which_min]++;
+      rest[which_min] = 0;
+      number--;
+    }
+  }
+
+#ifndef NDEBUG
+  number = original_number;
+  for (i = 0; i < groups; i++) {
+    assert(result[i] >= 0);
+    number -= result[i];
+  }
+  assert(number == 0);
+#endif
+}
Index: utility/shared.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/shared.h,v
retrieving revision 1.128
diff -u -r1.128 shared.h
--- utility/shared.h    24 Jul 2004 12:26:07 -0000      1.128
+++ utility/shared.h    21 Aug 2004 05:03:40 -0000
@@ -243,4 +243,6 @@
 
 char *get_multicast_group(void);
 
+void distribute(int number, int groups, int *ratios, int *result);
+
 #endif  /* FC__SHARED_H */