*
* For all continents, add the first sector at the capital's location,
* and the second right to it. These are the capital sectors. Then
- * add one sector to each continent in turn, obeying the minimum
- * distance between continents, until they have the specified size.
+ * add one sector to each continent in turn, until they have the
+ * specified size.
*
- * The kind of shape they grow into is determined by the "spike
- * percentage" --- the higher the spike, the more spindly they will
- * be. If you lower the spike, the continents will be more round.
+ * Growth uses weighted random sampling to pick one sector from the
+ * set of adjacent sea sectors that aren't too close to another
+ * continent. Growth operates in spiking mode with a chance given by
+ * the spike percentage. When "spiking", a sector's weight increases
+ * with number of adjacent sea sectors. This directs the growth away
+ * from land, resulting in spikes. When not spiking, the weight
+ * increases with the number of adjacent land sectors. This makes the
+ * island more rounded.
*
* If growing fails due to lack of room, start over. If it fails too
* many times, give up and terminate unsuccessfully.
*
* 3. Place and grow additional islands
*
- * Place and grow islands one after the other. Place the first sector
+ * 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.
+ *
+ * Place and grow islands in spheres in turn. Place the first sector
* randomly, pick an island size, then grow the island to that size.
*
+ * 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.
/* these defines prevent infinite loops:
*/
-
-#define COAST_SEARCH_MAX 200 /* how many times do we look for a coast sector
- when growing continents and islands */
#define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
#define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
#define MOUNTAIN_SEARCH_MAX 1000 /* how long do we try to place mountains */
#define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
#define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
-static int ctot; /* total number of continents and islands grown */
-static int *isecs; /* array of how large each island is */
+/*
+ * Island sizes
+ * isecs[i] is the size of the i-th island.
+ */
+static int *isecs;
static int *capx, *capy; /* location of the nc capitals */
-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 */
+/*
+ * 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
*/
static short *xzone;
+/*
+ * Set of sectors seen already
+ * Increment @cur_seen to empty the set of sectors seen, set
+ * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
+ */
+static unsigned *seen;
+static unsigned cur_seen;
+
+/*
+ * Closest continent and "distance"
+ * closest[XYOFFSET(x, y)] is the closest continent's number.
+ * distance[] is complicated; see init_spheres_of_influence().
+ */
+static natid *closest;
+static unsigned short *distance;
+
+/*
+ * Queue for breadth-first search
+ */
+static int *bfs_queue;
+static int bfs_queue_head, bfs_queue_tail;
+
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? */
static void print_vars(void);
static void fl_move(int);
-static void grow_islands(void);
+static int grow_islands(void);
/* Debugging aids: */
void print_own_map(void);
void print_xzone_map(void);
+void print_closest_map(void);
+void print_distance_map(void);
void print_elev_map(void);
/****************************************************************************
qprint("unstable drift\n");
qprint("growing continents...\n");
done = grow_continents();
+ if (!done)
+ continue;
+ qprint("growing islands:");
+ done = grow_islands();
} while (!done && ++try < NUMTRIES);
if (!done) {
- fprintf(stderr, "%s: world not large enough to hold continents\n",
+ fprintf(stderr, "%s: world not large enough for this much land\n",
program_name);
exit(1);
}
- qprint("growing islands:");
- grow_islands();
- qprint("\nelevating land...\n");
+ qprint("elevating land...\n");
create_elevations();
qprint("writing to sectors file...\n");
program_name);
exit(1);
}
+ if (ni % nc) {
+ fprintf(stderr, "%s: number of islands must be a multiple of"
+ " the number of continents\n",
+ program_name);
+ exit(1);
+ }
if (argc > 3)
is = atoi(argv[3]);
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));
+ seen = calloc(WORLD_SZ(), sizeof(*seen));
+ closest = malloc(WORLD_SZ() * sizeof(*closest));
+ distance = malloc(WORLD_SZ() * sizeof(*distance));
+ bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
elev = calloc(WORLD_X, sizeof(int *));
for (i = 0; i < WORLD_X; ++i) {
own[i] = calloc(WORLD_Y, sizeof(int));
own[i][j] = -1;
}
}
+ memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
}
/****************************************************************************
static void
fl_move(int j)
{
- int i, n, newx, newy;
-
- for (i = roll0(6), n = 0; n < 6; i = (i + 1) % 6, ++n) {
- newx = new_x(capx[j] + dirx[i]);
- newy = new_y(capy[j] + diry[i]);
+ int dir, i, newx, newy;
+
+ dir = DIR_L + roll0(6);
+ for (i = 0; i < 6; i++) {
+ if (dir > DIR_LAST)
+ dir -= 6;
+ newx = new_x(capx[j] + diroff[dir][0]);
+ newy = new_y(capy[j] + diroff[dir][1]);
+ dir++;
if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
capx[j] = newx;
capy[j] = newy;
static void
find_coast(int c)
{
- int i, j;
+ int i, dir, nx, ny;
for (i = 0; i < isecs[c]; ++i) {
sectc[c][i] = 0;
- for (j = 0; j < 6; ++j)
- if (own[new_x(sectx[c][i] + dirx[j])][new_y(secty[c][i] + diry[j])] == -1)
+ for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
+ nx = new_x(sectx[c][i] + diroff[dir][0]);
+ ny = new_y(secty[c][i] + diroff[dir][1]);
+ if (own[nx][ny] == -1)
sectc[c][i] = 1;
+ }
}
}
}
/*
- * Can island @c grow at @x,@y?
+ * Initialize breadth-first search.
*/
-static int
-can_grow_at(int c, int x, int y)
+static void
+bfs_init(void)
{
- return own[x][y] == -1 && xzone_ok(c, x, y);
+ int i;
+
+ for (i = 0; i < WORLD_SZ(); i++) {
+ closest[i] = -1;
+ distance[i] = USHRT_MAX;
+ }
+
+ bfs_queue_head = bfs_queue_tail = 0;
}
+/*
+ * Add sector @x,@y to the BFS queue.
+ * It's closest to @c, with distance @dist.
+ */
static void
-add_sector(int c, int x, int y)
+bfs_enqueue(int c, int x, int y, int dist)
{
- 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[x][y] = c;
+ int off = XYOFFSET(x, y);
+
+ assert(dist < distance[off]);
+ closest[off] = c;
+ distance[off] = dist;
+ bfs_queue[bfs_queue_tail] = off;
+ bfs_queue_tail++;
+ if (bfs_queue_tail >= WORLD_SZ())
+ bfs_queue_tail = 0;
+ assert(bfs_queue_tail != bfs_queue_head);
}
-static int
-try_to_grow(int c, int newx, int newy, int extra_dist)
+/*
+ * Search breadth-first until the queue is empty.
+ */
+static void
+bfs_run_queue(void)
{
- int d = c < nc ? di : id;
- int i, px, py;
- struct hexagon_iter hexit;
+ int off, dist, i, noff, nx, ny;
+ coord x, y;
+
+ while (bfs_queue_head != bfs_queue_tail) {
+ off = bfs_queue[bfs_queue_head];
+ bfs_queue_head++;
+ if (bfs_queue_head >= WORLD_SZ())
+ bfs_queue_head = 0;
+ dist = distance[off] + 1;
+ sctoff2xy(&x, &y, off);
+ for (i = DIR_FIRST; i <= DIR_LAST; i++) {
+ nx = new_x(x + diroff[i][0]);
+ ny = new_y(y + diroff[i][1]);
+ noff = XYOFFSET(nx, ny);
+ if (dist < distance[noff]) {
+ bfs_enqueue(closest[off], nx, ny, dist);
+ } else if (distance[noff] == dist) {
+ if (closest[off] != closest[noff])
+ closest[noff] = (natid)-1;
+ } else
+ assert(distance[noff] < dist);
+ }
+ }
+}
- if (!can_grow_at(c, newx, newy))
- return 0;
+/*
+ * Add island @c's coastal sectors to the BFS queue, with distance 0.
+ */
+static void
+bfs_enqueue_island(int c)
+{
+ int i;
- 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 (i = 0; i < isecs[c]; i++) {
+ if (sectc[c][i])
+ bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
}
+}
- add_sector(c, newx, newy);
- return 1;
+/*
+ * Compute spheres of influence
+ * A continent's sphere of influence is the set of sectors closer to
+ * it than to any other continent.
+ * Set closest[XYOFFSET(x, y)] to the closest continent's number,
+ * -1 if no single continent is closest.
+ * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
+ * land sector.
+ */
+static void
+init_spheres_of_influence(void)
+{
+ int c;
+
+ bfs_init();
+ for (c = 0; c < nc; c++)
+ bfs_enqueue_island(c);
+ bfs_run_queue();
}
-/* Move along the coast in a clockwise direction.
-*/
+/*
+ * Is @x,@y in the same sphere of influence as island @c?
+ * Always true when @c is a continent.
+ */
+static int
+is_in_sphere(int c, int x, int y)
+{
+ return c < nc || closest[XYOFFSET(x, y)] == c % nc;
+}
+
+/*
+ * 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) && is_in_sphere(c, x, y);
+}
static void
-next_coast(int c, int x, int y, int *xp, int *yp)
+adj_land_update(int x, int y)
{
- int i, nx, ny, wat = 0;
+ int dir, nx, ny, noff;
- if (isecs[c] == 1) {
- *xp = x;
- *yp = y;
- return;
- }
+ assert(own[x][y] != -1);
- for (i = 0; i < 12; ++i) {
- nx = new_x(x + dirx[i % 6]);
- ny = new_y(y + diry[i % 6]);
- if (own[nx][ny] == -1)
- wat = 1;
- if (wat && own[nx][ny] == c) {
- *xp = nx;
- *yp = ny;
- return;
- }
+ 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);
}
}
-/* Choose a sector to grow from
-*/
-
-static int
-new_try(int c, int spike)
+static void
+add_sector(int c, int x, int y)
{
- int secs = isecs[c];
- int i, starti;
-
- if (secs == 1) {
- if (sectc[c][0])
- return 0;
- } else {
- i = starti = (spike && sectc[c][secs - 1]) ? secs - 1 : roll0(secs);
- do {
- if (sectc[c][i])
- return i;
- i = (i + 1) % secs;
- } while (i != starti);
- assert(c >= nc);
- return -1;
- }
- return -1;
+ 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[x][y] = c;
+ adj_land_update(x, y);
}
-/* Grow continent c by 1 sector
-*/
+static int grow_weight(int c, int x, int y, int spike)
+{
+ int n, b;
+
+ /*
+ * #Land neighbors is #bits set in adj_land[].
+ * Count them Brian Kernighan's way.
+ */
+ n = 0;
+ for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
+ n++;
+ assert(n > 0 && n < 7);
+
+ if (spike)
+ return (6 - n) * (6 - n);
+
+ return n * n * n;
+}
static int
grow_one_sector(int c)
{
int spike = roll0(100) < sp;
- int done, coast_search, try1, x, y, newx, newy, i, n, sx, sy;
+ int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
+
+ assert(cur_seen < UINT_MAX);
+ cur_seen++;
+ wsum = 0;
+ newx = newy = -1;
+
+ for (i = 0; i < isecs[c]; i++) {
+ x = sectx[c][i];
+ y = secty[c][i];
+ off = XYOFFSET(x, y);
+
+ for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
+ if (adj_land[off] & (1u << dir))
+ continue;
+ nx = new_x(x + diroff[dir][0]);
+ ny = new_y(y + diroff[dir][1]);
+ noff = XYOFFSET(nx, ny);
+ if (seen[noff] == cur_seen)
+ continue;
+ assert(seen[noff] < cur_seen);
+ seen[noff] = cur_seen;
+ if (!can_grow_at(c, nx, ny))
+ continue;
+ w = grow_weight(c, nx, ny, spike);
+ assert(wsum < INT_MAX - w);
+ wsum += w;
+ if (roll0(wsum) < w) {
+ newx = nx;
+ newy = ny;
+ }
+ }
+ }
- if ((try1 = new_try(c, spike)) == -1)
+ if (!wsum)
return 0;
- x = sx = sectx[c][try1];
- y = sy = secty[c][try1];
- coast_search = 0;
- done = 0;
- do {
- if (spike) {
- for (i = roll0(6), n = 0; n < 12 && !done; i = (i + 1) % 6, ++n) {
- newx = new_x(x + dirx[i]);
- newy = new_y(y + diry[i]);
- 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))
- 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))
- done = 1;
- }
- next_coast(c, x, y, &x, &y);
- ++coast_search;
- } while (!done && coast_search < COAST_SEARCH_MAX &&
- (isecs[c] == 1 || x != sx || y != sy));
- return done;
+
+ add_sector(c, newx, newy);
+ return 1;
}
/*
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)
- || !try_to_grow(c, new_x(capx[c] + 2), capy[c], 0)) {
+ if (!can_grow_at(c, capx[c], capy[c])
+ || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
done = 0;
continue;
}
+ add_sector(c, capx[c], capy[c]);
+ add_sector(c, new_x(capx[c] + 2), capy[c]);
}
if (!done) {
for (secs = 2; secs < sc && done; secs++) {
for (c = 0; c < nc; ++c) {
- find_coast(c);
if (!grow_one_sector(c))
done = 0;
}
if (!done)
qprint("Only managed to grow %d out of %d sectors.\n",
secs - 1, sc);
- ctot = nc;
return done;
}
return n;
}
-/* Grow all the islands
-*/
-
-static void
+/*
+ * Grow the additional islands.
+ * Return 1 on success, 0 on error.
+ */
+static int
grow_islands(void)
{
int stunted_islands = 0;
int c, secs, isiz;
xzone_init(nc);
+ init_spheres_of_influence();
for (c = nc; c < nc + ni; ++c) {
+ isecs[c] = 0;
+
if (!place_island(c)) {
qprint("\nNo room for island #%d", c - nc + 1);
break;
isiz = roll(is) + roll0(is);
for (secs = 1; secs < isiz; secs++) {
- find_coast(c);
if (!grow_one_sector(c)) {
stunted_islands++;
break;
find_coast(c);
qprint(" %d(%d)", c - nc + 1, secs);
- ctot++;
}
+ qprint("\n");
+
+ if (c < nc + ni)
+ return 0;
+
if (stunted_islands)
- qprint("\n%d stunted island%s",
+ qprint("%d stunted island%s\n",
stunted_islands, splur(stunted_islands));
+ return 1;
}
/****************************************************************************
int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
r, dk;
- for (c = 0; c < ctot; ++c) {
+ for (c = 0; c < nc + ni; ++c) {
total = 0;
ns = isecs[c];
nm = (pm * ns) / 100;
}
}
+/*
+ * Print a map to help visualize closest[].
+ * This is for debugging.
+ */
+void
+print_closest_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 (closest[off] == (natid)-1)
+ putchar('.');
+ else if (!distance[off]) {
+ assert(closest[off] == own[x][y]);
+ putchar('-');
+ } else {
+ putchar(numletter[closest[off] % 62]);
+ }
+ }
+ printf("\n");
+ }
+}
+
+void
+print_distance_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 (closest[off] == (natid)-1)
+ putchar('.');
+ else if (!distance[off]) {
+ assert(closest[off] == own[x][y]);
+ putchar('-');
+ } else {
+ putchar(numletter[distance[off] % 62]);
+ }
+ }
+ printf("\n");
+ }
+}
+
/***************************************************************************
WRITE A SCRIPT FOR PLACING CAPITALS