fairland: Track adjacent land sectors

[empserver] / src / util / fairland.c

diff --git a/src/util/fairland.c b/src/util/fairland.c
index 1978c35b3034ae2ceaa80bb289d5899d257bc268..563c2330a91fc6e24c0ffc33dbcf0f6a28d24e88 100644 (file)
--- a/src/util/fairland.c
+++ b/src/util/fairland.c
@@ -188,6 +188,13 @@ static int diry[] = { 0, -1, -1, 0, 1, 1 };
 
 static int **own;              /* owner of the sector.  -1 means water */
 
+/*
+ * Adjacent land sectors
+ * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
+ * to x, y in direction d is land.
+ */
+static unsigned char *adj_land;
+
 /*
  * Exclusive zones
  * Each island is surrounded by an exclusive zone where only it may
@@ -494,6 +501,7 @@ allocate_memory(void)
     capx = calloc(nc, sizeof(int));
     capy = calloc(nc, sizeof(int));
     own = calloc(WORLD_X, sizeof(int *));
+    adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
     xzone = malloc(WORLD_SZ() * sizeof(*xzone));
     elev = calloc(WORLD_X, sizeof(int *));
     for (i = 0; i < WORLD_X; ++i) {
@@ -530,6 +538,7 @@ init(void)
            own[i][j] = -1;
        }
     }
+    memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
 }
 
 /****************************************************************************
@@ -766,32 +775,40 @@ 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)
+static void
+adj_land_update(int x, int y)
 {
-    int d = c < nc ? di : id;
-    int i, px, py;
-    struct hexagon_iter hexit;
+    int dir, nx, ny, noff;
 
-    if (!can_grow_at(c, newx, newy))
-       return 0;
+    assert(own[x][y] != -1);
 
-    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 &&
-               (DISTINCT_ISLANDS || own[px][py] < nc))
-               return 0;
-       } while (hexagon_next(&hexit, &px, &py));
+    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);
     }
+}
 
-    xzone_around_sector(c, newx, newy,
-                       c < nc ? di : DISTINCT_ISLANDS ? id : 0);
-    sectx[c][isecs[c]] = newx;
-    secty[c][isecs[c]] = newy;
+static void
+add_sector(int c, int x, int y)
+{
+    assert(own[x][y] == -1);
+    xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
+    sectx[c][isecs[c]] = x;
+    secty[c][isecs[c]] = y;
     isecs[c]++;
-    own[newx][newy] = c;
+    own[x][y] = c;
+    adj_land_update(x, y);
+}
+
+static int
+try_to_grow(int c, int newx, int newy)
+{
+    if (!can_grow_at(c, newx, newy))
+       return 0;
+
+    add_sector(c, newx, newy);
     return 1;
 }
 
@@ -870,14 +887,14 @@ grow_one_sector(int c)
                if (n > 5 ||
                    (own[new_x(x+dirx[(i+5)%6])][new_y(y+diry[(i+5)%6])] == -1 &&
                     own[new_x(x+dirx[(i+1)%6])][new_y(y+diry[(i+1)%6])] == -1))
-                   if (try_to_grow(c, newx, newy, 0))
+                   if (try_to_grow(c, newx, newy))
                        done = 1;
            }
        } else
            for (i = roll0(6), n = 0; n < 6 && !done; i = (i + 1) % 6, ++n) {
                newx = new_x(x + dirx[i]);
                newy = new_y(y + diry[i]);
-               if (try_to_grow(c, newx, newy, 0))
+               if (try_to_grow(c, newx, newy))
                    done = 1;
            }
        next_coast(c, x, y, &x, &y);
@@ -902,8 +919,8 @@ grow_continents(void)
 
     for (c = 0; c < nc; ++c) {
        isecs[c] = 0;
-       if (!try_to_grow(c, capx[c], capy[c], 0)
-           || !try_to_grow(c, new_x(capx[c] + 2), capy[c], 0)) {
+       if (!try_to_grow(c, capx[c], capy[c])
+           || !try_to_grow(c, new_x(capx[c] + 2), capy[c])) {
            done = 0;
            continue;
        }
@@ -943,28 +960,25 @@ grow_continents(void)
 static int
 place_island(int c)
 {
-    int d, sx, sy, x, y;
-    int ssy = roll0(WORLD_Y);
-    int ssx = new_x(roll0(WORLD_X / 2) * 2 + ssy % 2);
-
-    if (ssx > WORLD_X - 2)
-       ssx = new_x(ssx + 2);
-    for (d = di; d >= 0; --d) {
-       sx = ssx;
-       sy = ssy;
-       x = new_x(sx + 2);
-       for (y = sy; x != sx || y != sy; x += 2) {
-           if (x >= WORLD_X) {
-               y = new_y(y + 1);
-               x = y % 2;
-               if (x == sx && y == sy)
-                   break;
+    int n, x, y, newx, newy;
+
+    n = 0;
+
+    for (y = 0; y < WORLD_Y; y++) {
+       for (x = y % 2; x < WORLD_X; x += 2) {
+           if (can_grow_at(c, x, y)) {
+               n++;
+               if (!roll0(n)) {
+                   newx = x;
+                   newy = y;
+               }
            }
-           if (try_to_grow(c, x, y, d))
-               return 1;
        }
     }
-    return 0;
+
+    if (n)
+       add_sector(c, newx, newy);
+    return n;
 }
 
 /* Grow all the islands