*
* 3. Place and grow additional islands
*
- * Place and grow islands one after the other. Place the first sector
- * randomly, pick an island size, then grow the island to that size.
+ * 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 with the same sizes.
+ *
+ * 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, using
+ * weighted random sampling with weights favoring sectors away from
+ * land and other spheres. 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
*
#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 */
/*
* Closest continent and "distance"
* closest[XYOFFSET(x, y)] is the closest continent's number.
- * distance[] is complicated; see init_spheres_of_influence().
+ * distance[] is complicated; see init_spheres_of_influence() and
+ * init_distance_to_coast().
*/
static natid *closest;
static unsigned short *distance;
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 int *weight; /* used for placing mountains */
static int *dsea, *dmoun; /* the dist to the ocean and mountain */
static int stable(int);
static void elevate_land(void);
static void elevate_sea(void);
-static void set_coastal_flags(void);
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);
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]);
}
sectx = calloc(nc + ni, sizeof(int *));
secty = calloc(nc + ni, sizeof(int *));
- sectc = calloc(nc + ni, sizeof(int *));
isecs = calloc(nc + ni, sizeof(int));
weight = calloc(MAX(sc, is * 2), sizeof(int));
dsea = calloc(MAX(sc, is * 2), sizeof(int));
for (i = 0; i < nc; ++i) {
sectx[i] = calloc(sc, sizeof(int));
secty[i] = calloc(sc, sizeof(int));
- sectc[i] = calloc(sc, sizeof(int));
}
for (i = nc; i < nc + ni; ++i) {
sectx[i] = calloc(is * 2, sizeof(int));
secty[i] = calloc(is * 2, sizeof(int));
- sectc[i] = calloc(is * 2, sizeof(int));
}
}
GROW THE CONTINENTS
****************************************************************************/
-/* Look for a coastal sector of continent c
-*/
-
-static void
-find_coast(int c)
+static int
+is_coastal(int x, int y)
{
- int i, dir, nx, ny;
-
- for (i = 0; i < isecs[c]; ++i) {
- sectc[c][i] = 0;
- 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;
- }
- }
+ return adj_land[XYOFFSET(x, y)]
+ != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
}
struct hexagon_iter {
int i;
for (i = 0; i < isecs[c]; i++) {
- if (sectc[c][i])
+ if (is_coastal(sectx[c][i], secty[c][i]))
bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
}
}
+/*
+ * Enqueue spheres of influence borders for breadth-first search.
+ */
+static void
+bfs_enqueue_border(void)
+{
+ int x, y, off, dir, nx, ny, noff;
+
+ for (y = 0; y < WORLD_Y; y++) {
+ for (x = y % 2; x < WORLD_X; x += 2) {
+ off = XYOFFSET(x, y);
+ if (distance[off] <= id + 1)
+ continue;
+ if (closest[off] == (natid)-1)
+ continue;
+ 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);
+ if (closest[noff] != closest[off]) {
+ bfs_enqueue(closest[off], x, y, id + 1);
+ break;
+ }
+ }
+ }
+ }
+}
+
/*
* 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.
+ * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
+ * closest coastal land sector and the distance to just outside the
+ * sphere of influence plus @id. For sea sectors within a continent's
+ * sphere of influence, distance[off] - id is the distance to the
+ * border of the area where additional islands can be placed.
*/
static void
init_spheres_of_influence(void)
for (c = 0; c < nc; c++)
bfs_enqueue_island(c);
bfs_run_queue();
+ bfs_enqueue_border();
+ bfs_run_queue();
+}
+
+/*
+ * Precompute distance to coast
+ * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
+ * land sector.
+ * Set closest[XYOFFSET(x, y)] to the closest continent's number,
+ * -1 if no single continent is closest.
+ */
+static void
+init_distance_to_coast(void)
+{
+ int c;
+
+ bfs_init();
+ for (c = 0; c < nc + ni; c++)
+ bfs_enqueue_island(c);
+ bfs_run_queue();
+}
+
+/*
+ * 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;
}
/*
static int
can_grow_at(int c, int x, int y)
{
- return own[x][y] == -1 && xzone_ok(c, x, y);
+ return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, 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));
}
}
int done = 1;
int c, secs;
- ctot = 0;
xzone_init(0);
for (c = 0; c < nc; ++c) {
}
}
- for (c = 0; c < nc; ++c)
- find_coast(c);
-
if (!done)
qprint("Only managed to grow %d out of %d sectors.\n",
secs - 1, sc);
- ctot = nc;
return done;
}
* Return 1 on success, 0 on error.
*/
static int
-place_island(int c)
+place_island(int c, int isiz)
{
- int n, x, y, newx, newy;
+ int n, x, y, d, w, 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)) {
+ d = distance[XYOFFSET(x, y)];
+ assert(d > id);
+ w = (d - id) * (d - id);
+ n += MIN(w, (isiz + 2) / 3);
+ if (roll0(n) < w) {
newx = x;
newy = y;
}
return n;
}
-/* Grow all the islands
-*/
+static int
+int_cmp(const void *a, const void *b)
+{
+ return *(int *)b - *(int *)a;
+}
-static void
+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.
+ */
+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) {
- if (!place_island(c)) {
- qprint("\nNo room for island #%d", c - nc + 1);
- break;
+ for (i = 0; i < ni / nc; i++) {
+ c = nc + i * nc;
+
+ 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, isiz)) {
+ 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);
- ctot++;
+ 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;
}
- if (stunted_islands)
- qprint("\n%d stunted island%s",
- stunted_islands, splur(stunted_islands));
+ free(island_size);
+ qprint("\n");
+
+ if (carry)
+ qprint("Only managed to grow %d out of %d island sectors.\n",
+ is * ni - carry * nc, is * ni);
+
+ return 1;
}
/****************************************************************************
static void
create_elevations(void)
{
- int i, j;
-
- for (i = 0; i < WORLD_X; i++) {
- for (j = 0; j < WORLD_Y; j++)
- elev[i][j] = -INFINITE_ELEVATION;
- }
+ init_distance_to_coast();
elevate_land();
elevate_sea();
}
return d;
}
-#define ELEV elev[sectx[c][i]][secty[c][i]]
-#define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
#define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
/* Decide where the mountains go
static void
elevate_land(void)
{
- int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
- r, dk;
+ int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
+ int highest, where, h, newk, dk;
- for (c = 0; c < ctot; ++c) {
+ for (c = 0; c < nc + ni; ++c) {
total = 0;
ns = isecs[c];
nm = (pm * ns) / 100;
/* Place the mountains */
for (i = 0; i < ns; ++i) {
- dsea[i] = distance_to_sea();
+ off = XYOFFSET(sectx[c][i], secty[c][i]);
+ dsea[i] = MIN(5, distance[off] + 1);
weight[i] = (total += (dsea[i] * dsea[i]));
}
k && mountain_search < MOUNTAIN_SEARCH_MAX;
++mountain_search) {
r = roll0(total);
- for (i = 0; i < ns; ++i)
- if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
+ for (i = 0; i < ns; ++i) {
+ x = sectx[c][i];
+ y = secty[c][i];
+ if (r < weight[i] && !elev[x][y] &&
(c >= nc ||
((!(capx[c] == sectx[c][i] &&
capy[c] == secty[c][i])) &&
(!(new_x(capx[c] + 2) == sectx[c][i] &&
capy[c] == secty[c][i]))))) {
- ELEV = INFINITE_ELEVATION;
+ elev[x][y] = INFINITE_ELEVATION;
break;
}
+ }
--k;
}
highest = 0;
where = -1;
for (i = 0; i < ns; ++i) {
- if (ELEV == -INFINITE_ELEVATION &&
+ x = sectx[c][i];
+ y = secty[c][i];
+ if (!elev[x][y] &&
(c >= nc || ((!(capx[c] == sectx[c][i] &&
capy[c] == secty[c][i])) &&
(!(new_x(capx[c] + 2) == sectx[c][i] &&
/* Elevate the mountains and capitals */
for (i = 0; i < ns; ++i) {
- if (ELEV == INFINITE_ELEVATION) {
+ x = sectx[c][i];
+ y = secty[c][i];
+ if (elev[x][y] == INFINITE_ELEVATION) {
if (dsea[i] == 1)
- ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
+ elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
else
- ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
+ elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
roll0((256 - HIGHMIN) / 2);
} else if (c < nc &&
(((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
((new_x(capx[c] + 2) == sectx[c][i] &&
capy[c] == secty[c][i]))))
- ELEV = PLATMIN;
+ elev[x][y] = PLATMIN;
}
}
}
-#define distance_to_land() distance_to_what(x, y, 1)
-
static void
elevate_sea(void)
{
- int x, y;
+ int x, y, off;
for (y = 0; y < WORLD_Y; ++y) {
for (x = y % 2; x < WORLD_X; x += 2) {
- if (elev[x][y] == -INFINITE_ELEVATION)
- elev[x][y] = -roll(distance_to_land() * 20 + 27);
+ off = XYOFFSET(x, y);
+ if (own[x][y] == -1)
+ elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
}
}
}
sct->sct_type = elev_to_sct_type(elev[x][y]);
sct->sct_newtype = sct->sct_type;
sct->sct_dterr = own[sct->sct_x][y] + 1;
+ sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
add_resources(sct);
}
}
- set_coastal_flags();
}
/****************************************************************************
va_end(ap);
}
}
-
-static void
-set_coastal_flags(void)
-{
- int i, j;
- struct sctstr *sp;
-
- for (i = 0; i < nc + ni; ++i) {
- for (j = 0; j < isecs[i]; j++) {
- sp = getsectp(sectx[i][j], secty[i][j]);
- sp->sct_coastal = sectc[i][j];
- }
- }
-}
projects / empserver / blobdiff