fairland: Try harder to deliver the requested amount of land

[empserver] / src / util / fairland.c

diff --git a/src/util/fairland.c b/src/util/fairland.c
index 501f52b658df0d8dac1693879f66eb3e4661e573..9530d986b20d7ca36a878e5f3651aaa6bac6651b 100644 (file)
--- a/src/util/fairland.c
+++ b/src/util/fairland.c
@@ -65,19 +65,24 @@
  * Each continent has a "sphere of influence": the set of sectors
  * closer to it than to any other continent.  Each island is entirely
  * in one such sphere, and each sphere contains the same number of
- * islands.
+ * islands with the same sizes.
  *
- * Pick an island size, and place one island's first sector into each
- * sphere, randomly.  Then add one sector to each island in turn,
- * until they have the intended size.  Repeat until the specified
- * number of islands has been grown.
+ * First, split the specified number of island sectors per continent
+ * randomly into the island sizes.  Sort by size so that larger
+ * islands are grown before smaller ones, to give the large ones the
+ * best chance to grow to their planned size.
+ *
+ * Then place one island's first sector into each sphere, randomly.
+ * Add one sector to each island in turn, until they have the intended
+ * size.  Repeat until the specified number of islands has been grown.
  *
  * If placement fails due to lack of room, start over, just like for
  * continents.
  *
  * Growing works as for continents, except the minimum distance for
  * additional islands applies, and growing simply stops when any of
- * the islands being grown lacks the room to grow further.
+ * the islands being grown lacks the room to grow further.  The number
+ * of sectors not grown carries over to the next island size.
  *
  * 4. Compute elevation
  *
@@ -944,15 +949,17 @@ can_grow_at(int c, int x, int y)
 static void
 adj_land_update(int x, int y)
 {
+    int is_land = own[x][y] != -1;
     int dir, nx, ny, noff;
 
-    assert(own[x][y] != -1);
-
     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
        nx = new_x(x + diroff[dir][0]);
        ny = new_y(y + diroff[dir][1]);
        noff = XYOFFSET(nx, ny);
-       adj_land[noff] |= 1u << DIR_BACK(dir);
+       if (is_land)
+           adj_land[noff] |= 1u << DIR_BACK(dir);
+       else
+           adj_land[noff] &= ~(1u << DIR_BACK(dir));
     }
 }
 
@@ -1108,6 +1115,32 @@ place_island(int c)
     return n;
 }
 
+static int
+int_cmp(const void *a, const void *b)
+{
+    return *(int *)b - *(int *)a;
+}
+
+static int *
+size_islands(void)
+{
+    int n = ni / nc;
+    int *isiz = malloc(n * sizeof(*isiz));
+    int r0, r1, i;
+
+    isiz[0] = n * is;
+    r1 = roll0(is);
+    for (i = 1; i < n; i++) {
+       r0 = r1;
+       r1 = roll0(is);
+       isiz[i] = is + r1 - r0;
+       isiz[0] -= isiz[i];
+    }
+
+    qsort(isiz, n, sizeof(*isiz), int_cmp);
+    return isiz;
+}
+
 /*
  * Grow the additional islands.
  * Return 1 on success, 0 on error.
@@ -1115,21 +1148,27 @@ place_island(int c)
 static int
 grow_islands(void)
 {
-    int n = ni / nc;
-    int stunted_islands = 0;
-    int i, j, c, done, secs, isiz;
+    int *island_size = size_islands();
+    int xzone_valid = 0;
+    int carry = 0;
+    int i, j, c, done, secs, isiz, x, y;
 
-    xzone_init(nc);
     init_spheres_of_influence();
 
-    for (i = 0; i < n; i++) {
+    for (i = 0; i < ni / nc; i++) {
        c = nc + i * nc;
-       isiz = roll(is) + roll0(is);
+
+       if (!xzone_valid)
+           xzone_init(c);
+
+       carry += island_size[i];
+       isiz = MIN(2 * is, carry);
 
        for (j = 0; j < nc; j++) {
            isecs[c + j] = 0;
            if (!place_island(c + j)) {
                qprint("\nNo room for island #%d\n", c - nc + j + 1);
+               free(island_size);
                return 0;
            }
        }
@@ -1142,18 +1181,33 @@ grow_islands(void)
            }
        }
 
-       for (j = 0; j < nc; j++)
-           stunted_islands += isecs[c + j] != isiz;
+       if (!done) {
+           secs--;
+           for (j = 0; j < nc; j++) {
+               if (isecs[c + j] != secs) {
+                   isecs[c + j]--;
+                   assert(isecs[c + j] == secs);
+                   x = sectx[c + j][secs];
+                   y = secty[c + j][secs];
+                   own[x][y] = -1;
+                   adj_land_update(x, y);
+               }
+           }
+           xzone_valid = 0;
+       }
 
        for (j = 0; j < nc; j++)
            qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
+
+       carry -= secs;
     }
 
+    free(island_size);
     qprint("\n");
 
-    if (stunted_islands)
-       qprint("%d stunted island%s\n",
-              stunted_islands, splur(stunted_islands));
+    if (carry)
+       qprint("Only managed to grow %d out of %d island sectors.\n",
+              is * ni - carry * nc, is * ni);
 
     for (c = nc; c < nc + ni; c++)
        find_coast(c);