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 9f28769c1891fd0cb063fee72d56384bdb3f5f10..9530d986b20d7ca36a878e5f3651aaa6bac6651b 100644 (file)
--- a/src/util/fairland.c
+++ b/src/util/fairland.c
@@ -65,17 +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.
  *
- * Place and grow islands in spheres in turn.  Place the first sector
- * randomly, pick an island size, then grow the island to that size.
+ * 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 there is
- * no room.
+ * additional islands applies, and growing simply stops when any of
+ * 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
  *
@@ -942,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));
     }
 }
 
@@ -1106,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.
@@ -1113,40 +1148,70 @@ place_island(int c)
 static int
 grow_islands(void)
 {
-    int stunted_islands = 0;
-    int c, 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 (c = nc; c < nc + ni; ++c) {
-       isecs[c] = 0;
+    for (i = 0; i < ni / nc; i++) {
+       c = nc + i * nc;
 
-       if (!place_island(c)) {
-           qprint("\nNo room for island #%d", c - nc + 1);
-           break;
+       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;
+           }
        }
 
-       isiz = roll(is) + roll0(is);
-       for (secs = 1; secs < isiz; secs++) {
-           if (!grow_one_sector(c)) {
-               stunted_islands++;
-               break;
+       done = 1;
+       for (secs = 1; secs < isiz && done; secs++) {
+           for (j = 0; j < nc; j++) {
+               if (!grow_one_sector(c + j))
+                   done = 0;
            }
        }
 
-       find_coast(c);
-       qprint(" %d(%d)", c - nc + 1, secs);
+       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 (c < nc + ni)
-       return 0;
+    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);
 
-    if (stunted_islands)
-       qprint("%d stunted island%s\n",
-              stunted_islands, splur(stunted_islands));
     return 1;
 }