fairland: Precompute "exclusive zone" for speed

grow_one_sector() and place_island() pass candidate sectors to
try_to_grow() until it succeeds.

try_to_grow() fails when the candidate isn't water, or there are
sectors belonging to other islands within a minimum distance.
It does that the obvious way: it searches for such sectors.

When there is plenty of space, try_to_grow() rarely fails when it
searches.  For each land sector, we visit the sectors within minimum
distance, plus a little extra work for the rare failures.

In a more crowded setup, however, try_to_grow() fails a lot, and we
visit sectors many times more.

Example: Hvy Fever

    8 continents
    continent size: 60
    number of islands: 64
    average size of islands: 10
    spike: 0%
    0% of land is mountain (each continent will have 0 mountains)
    minimum distance between continents: 6
    minimum distance from islands to continents: 3
    World dimensions: 140x68

This is a crowded setup.  With -R 1, try_to_grow() fails almost
750,000 times due to minimum distance, and takes more than 18 Million
iterations.

With default minimum distances 2 and 1, it fails less than 700 times,
taking less than 14,000 iterations.

Instead of searching the surrounding sectors every time we check a
candidate, precompute an "exclusive zone" around each island where
only this island may grow the obvious way: when adding a sector, visit
the sectors within minimum distance and add them to the island's
exclusive zone.

When @extra_distance is non-zero, try_to_grow() still has to search,
Only place_island() passes non-zero @extra_distance.  The next few
commits will get rid of that.

Complication: since the minimum distance for growing islands may
differ from the minimum distance for growing continents, we have to
recompute exclusive zones between growing continents and islands.

For the Hvy Fever example above, this reduces the number of sector
visits by more than 90%, and run time by more than 70% for me.  With
default distances, it's a wash.

Of course, fairland performance is hardly an issue on today's
machines: it takes fairly impractical setups to push run time over a
second.

Signed-off-by: Markus Armbruster <armbru@pond.sub.org>

diff --git a/src/util/fairland.c b/src/util/fairland.c
index a57d8e7dd5c1ea643e809287aca72039981fc7d4..4787719d7cd8da5c94fbe9b1d66f31cf43db4c69 100644 (file)
--- a/src/util/fairland.c
+++ b/src/util/fairland.c
@@ -187,6 +187,21 @@ static int dirx[] = { -2, -1, 1, 2, 1, -1 }; /* gyujnb */
 static int diry[] = { 0, -1, -1, 0, 1, 1 };
 
 static int **own;              /* owner of the sector.  -1 means water */
+
+/*
+ * Exclusive zones
+ * Each island is surrounded by an exclusive zone where only it may
+ * grow.  The width of the zone depends on minimum distances.
+ * While growing continents, it is @di sectors wide.
+ * While growing additional islands, it is @id sectors wide.
+ * DISTINCT_ISLANDS nullifies the exclusive zone then.
+ * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
+ * zone, a (non-negative) island number when it is in that island's
+ * exclusive zone and no other, and -2 when it is in multiple
+ * exclusive zones.
+ */
+static short *xzone;
+
 static int **elev;             /* elevation of the sectors */
 static int **sectx, **secty;   /* the sectors for each continent */
 static int **sectc;            /* which sectors are on the coast? */
@@ -220,6 +235,7 @@ static void grow_islands(void);
 
 /* Debugging aids: */
 void print_own_map(void);
+void print_xzone_map(void);
 void print_elev_map(void);
 
 /****************************************************************************
@@ -478,6 +494,7 @@ allocate_memory(void)
     capx = calloc(nc, sizeof(int));
     capy = calloc(nc, sizeof(int));
     own = calloc(WORLD_X, sizeof(int *));
+    xzone = malloc(WORLD_SZ() * sizeof(*xzone));
     elev = calloc(WORLD_X, sizeof(int *));
     for (i = 0; i < WORLD_X; ++i) {
        own[i] = calloc(WORLD_Y, sizeof(int));
@@ -678,18 +695,89 @@ hexagon_next(struct hexagon_iter *iter, int *x, int *y)
     return iter->dir <= DIR_LAST;
 }
 
+/*
+ * Is @x,@y in no exclusive zone other than perhaps @c's?
+ */
+static int
+xzone_ok(int c, int x, int y)
+{
+    int off = XYOFFSET(x, y);
+
+    return xzone[off] == c || xzone[off] == -1;
+}
+
+/*
+ * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
+ */
+static void
+xzone_around_sector(int c, int x, int y, int dist)
+{
+    int d, x1, y1, off;
+    struct hexagon_iter hexit;
+
+    assert(xzone_ok(c, x, y));
+
+    xzone[XYOFFSET(x, y)] = c;
+    for (d = 1; d <= dist; d++) {
+       hexagon_first(&hexit, x, y, d, &x1, &y1);
+       do {
+           off = XYOFFSET(x1, y1);
+           if (xzone[off] == -1)
+               xzone[off] = c;
+           else if (xzone[off] != c)
+               xzone[off] = -2;
+       } while (hexagon_next(&hexit, &x1, &y1));
+    }
+}
+
+/*
+ * Add sectors within distance @dist to island @c's exclusive zone.
+ */
+static void
+xzone_around_island(int c, int dist)
+{
+    int i;
+
+    for (i = 0; i < isecs[c]; i++)
+       xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
+}
+
+/*
+ * Initialize exclusive zones around @n islands.
+ */
+static void
+xzone_init(int n)
+{
+    int i, c;
+
+    for (i = 0; i < WORLD_SZ(); i++)
+       xzone[i] = -1;
+
+    for (c = 0; c < n; c++)
+       xzone_around_island(c, id);
+}
+
+/*
+ * Can island @c grow at @x,@y?
+ */
+static int
+can_grow_at(int c, int x, int y)
+{
+    return own[x][y] == -1 && xzone_ok(c, x, y);
+}
+
 static int
 try_to_grow(int c, int newx, int newy, int extra_dist)
 {
-    int d = (c < nc ? di : id) + extra_dist;
+    int d = c < nc ? di : id;
     int i, px, py;
     struct hexagon_iter hexit;
 
-    if (own[newx][newy] != -1)
+    if (!can_grow_at(c, newx, newy))
        return 0;
 
-    for (i = 1; i <= d; ++i) {
-       hexagon_first(&hexit, newx, newy, i, &px, &py);
+    for (i = 1; i <= extra_dist; i++) {
+       hexagon_first(&hexit, newx, newy, d + i, &px, &py);
        do {
            if (own[px][py] != -1 &&
                own[px][py] != c &&
@@ -697,6 +785,9 @@ try_to_grow(int c, int newx, int newy, int extra_dist)
                return 0;
        } while (hexagon_next(&hexit, &px, &py));
     }
+
+    xzone_around_sector(c, newx, newy,
+                       c < nc ? di : DISTINCT_ISLANDS ? id : 0);
     sectx[c][isecs[c]] = newx;
     secty[c][isecs[c]] = newy;
     isecs[c]++;
@@ -806,6 +897,9 @@ grow_continents(void)
     int done = 1;
     int c, secs;
 
+    ctot = 0;
+    xzone_init(0);
+
     for (c = 0; c < nc; ++c) {
        isecs[c] = 0;
        if (!try_to_grow(c, capx[c], capy[c], 0)
@@ -880,6 +974,8 @@ grow_islands(void)
     int stunted_islands = 0;
     int c, secs, x, y, isiz;
 
+    xzone_init(nc);
+
     for (c = nc; c < nc + ni; ++c) {
        if (!place_island(c, &x, &y)) {
            qprint("\nNo room for island #%d", c - nc + 1);
@@ -1273,6 +1369,37 @@ print_elev_map(void)
     }
 }
 
+/*
+ * Print a map to help visualize xzone[].
+ * This is for debugging.
+ */
+void
+print_xzone_map(void)
+{
+    int sx, sy, x, y, off;
+
+    for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
+       y = YNORM(sy);
+       printf("%4d ", sy);
+       for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
+           x = XNORM(sx);
+           off = XYOFFSET(x, y);
+           if ((x + y) & 1)
+               putchar(' ');
+           else if (own[x][y] >= 0)
+               putchar('-');
+           else if (xzone[off] >= 0)
+               putchar(numletter[xzone[off] % 62]);
+           else {
+               assert(own[x][y] == -1);
+               putchar(xzone[off] == -1 ? '.' : '!');
+           }
+       }
+       putchar('\n');
+    }
+}
+
+
 /***************************************************************************
   WRITE A SCRIPT FOR PLACING CAPITALS
 ****************************************************************************/