#include <assert.h>
#include <errno.h>
+#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <unistd.h>
#include "chance.h"
#include "optlist.h"
+#include "path.h"
#include "prototypes.h"
#include "sect.h"
#include "version.h"
static const char *outfile = DEFAULT_OUTFILE_NAME;
#define STABLE_CYCLE 4 /* stability required for perterbed capitals */
-#define INFINITY 999 /* a number which means "BIG" */
+#define INFINITE_ELEVATION 999
/* these defines prevent infinite loops:
*/
#define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
#define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
-static int secs; /* number of sectors grown */
static int ctot; /* total number of continents and islands grown */
static int *isecs; /* array of how large each island is */
static int *capx, *capy; /* location of the nc capitals */
-static int *mc, mcc; /* array and counter used for stability
- check when perturbing */
-static int spike; /* are we spiking? */
-static int mind; /* the final distance between capitals that
- we achieved */
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? */
-static int *vector; /* used for measuring distances */
static int *weight; /* used for placing mountains */
static int *dsea, *dmoun; /* the dist to the ocean and mountain */
-static int fl_status; /* is anything wrong? */
-#define STATUS_NO_ROOM 1 /* there was no room to grow */
+
#define NUMTRIES 10 /* keep trying to grow this many times */
static const char *numletter =
static void allocate_memory(void);
static void init(void);
static int drift(void);
-static void grow_continents(void);
+static int grow_continents(void);
static void create_elevations(void);
static void write_sects(void);
static void output(void);
static int write_newcap_script(void);
-static int stable(void);
+static int stable(int);
static void elevate_land(void);
static void elevate_sea(void);
static void set_coastal_flags(void);
/* Debugging aids: */
void print_own_map(void);
+void print_xzone_map(void);
void print_elev_map(void);
/****************************************************************************
{
int opt;
char *config_file = NULL;
- int i = 0;
+ int try, done;
unsigned rnd_seed = 0;
int seed_set = 0;
qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
qprint("seed is %u\n", rnd_seed);
+ try = 0;
do {
init();
- if (i)
- qprint("\ntry #%d (out of %d)...\n", i + 1, NUMTRIES);
+ if (try)
+ qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
qprint("placing capitals...\n");
if (!drift())
qprint("unstable drift\n");
qprint("growing continents...\n");
- grow_continents();
- } while (fl_status && ++i < NUMTRIES);
- if (fl_status) {
+ done = grow_continents();
+ } while (!done && ++try < NUMTRIES);
+ if (!done) {
fprintf(stderr, "%s: world not large enough to hold continents\n",
program_name);
exit(1);
capx = calloc(nc, sizeof(int));
capy = calloc(nc, sizeof(int));
- vector = calloc(WORLD_X + WORLD_Y, sizeof(int));
- mc = calloc(STABLE_CYCLE, 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));
static void
init(void)
{
- int i, j, xx = 0, yy = 0;
-
- mcc = 0;
- fl_status = 0;
+ int i, j;
for (i = 0; i < WORLD_X; ++i) {
for (j = 0; j < WORLD_Y; ++j) {
own[i][j] = -1;
- elev[i][j] = -INFINITY;
- }
- }
-
- for (i = 0; i < nc; ++i) {
- if (xx >= WORLD_X) {
- ++yy;
- xx = yy % 2;
- if (yy == WORLD_Y) {
- fprintf(stderr,
- "%s: world not big enough for all the continents\n",
- program_name);
- exit(1);
- }
}
- capx[i] = xx;
- capy[i] = yy;
- xx += 2;
}
- for (i = 0; i < STABLE_CYCLE; ++i)
- mc[i] = i;
}
/****************************************************************************
DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
****************************************************************************/
-/* How isolated is capital j?
-*/
+/*
+ * How isolated is capital @j at @newx,@newy?
+ * Return the distance to the closest other capital.
+ */
static int
iso(int j, int newx, int newy)
{
- int i, md, d = WORLD_X + WORLD_Y;
+ int d = INT_MAX;
+ int i, md;
for (i = 0; i < nc; ++i) {
if (i == j)
return d;
}
-/* Drift all the capitals
-*/
+/*
+ * Drift the capitals
+ * Return 1 for a stable drift, 0 for an unstable one.
+ */
static int
drift(void)
{
- int i, turns;
+ int turns, i;
+
+ for (i = 0; i < nc; i++) {
+ capy[i] = (2 * i) / WORLD_X;
+ capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
+ if (capy[i] >= WORLD_Y) {
+ fprintf(stderr,
+ "%s: world not big enough for all the continents\n",
+ program_name);
+ exit(1);
+ }
+ }
for (turns = 0; turns < DRIFT_MAX; ++turns) {
- if (turns > DRIFT_BEFORE_CHECK && (mind = stable()))
+ if (stable(turns))
return 1;
for (i = 0; i < nc; ++i)
fl_move(i);
return 0;
}
-/* Check to see if we have stabilized--can we stop drifting the capitals?
-*/
-
+/*
+ * Has the drift stabilized?
+ * @turns is the number of turns so far.
+ */
static int
-stable(void)
+stable(int turns)
{
+ static int mc[STABLE_CYCLE];
int i, isod, d = 0, stab = 1;
+ if (!turns) {
+ for (i = 0; i < STABLE_CYCLE; i++)
+ mc[i] = i;
+ }
+
+ if (turns <= DRIFT_BEFORE_CHECK)
+ return 0;
+
for (i = 0; i < nc; ++i) {
isod = iso(i, capx[i], capy[i]);
if (isod > d)
d = isod;
}
+
for (i = 0; i < STABLE_CYCLE; ++i)
if (d != mc[i])
stab = 0;
- mc[mcc] = d;
- mcc = (mcc + 1) % STABLE_CYCLE;
- return stab ? d : 0;
+
+ mc[turns % STABLE_CYCLE] = d;
+ return stab;
}
/* This routine does the actual drifting
{
int i, j;
- for (i = 0; i < secs; ++i) {
+ 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)
}
}
-/* Used for measuring distances
-*/
-static int
-next_vector(int n)
+struct hexagon_iter {
+ int dir, i, n;
+};
+
+/*
+ * Start iterating around @x0,@y0 at distance @d.
+ * Set *x,*y to coordinates of the first sector.
+ */
+static inline void
+hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
+ int *x, int *y)
{
- int i;
+ *x = new_x(x0 - 2 * n);
+ *y = y0;
+ iter->dir = DIR_FIRST;
+ iter->i = 0;
+ iter->n = n;
+}
- if (n == 1) {
- vector[0] += 1;
- vector[0] %= 6;
- return vector[0];
+/*
+ * Continue iteration started with hexagon_first().
+ * Set *x,*y to coordinates of the next sector.
+ * Return whether we're back at the first sector, i.e. iteration is
+ * complete.
+ */
+static inline int
+hexagon_next(struct hexagon_iter *iter, int *x, int *y)
+{
+ *x = new_x(*x + diroff[iter->dir][0]);
+ *y = new_y(*y + diroff[iter->dir][1]);
+ iter->i++;
+ if (iter->i == iter->n) {
+ iter->i = 0;
+ iter->dir++;
}
- for (i = 1; i < n && vector[i] == vector[i - 1]; ++i) ;
- vector[i - 1] += 1;
- vector[i - 1] %= 6;
- return i > 1 || vector[0] > 0;
+ return iter->dir <= DIR_LAST;
}
-/* Test to see if we're allowed to grow there: the arguments di and id
-*/
+/*
+ * Is @x,@y in no exclusive zone other than perhaps @c's?
+ */
static int
-try_to_grow(int c, int newx, int newy, int d)
+xzone_ok(int c, int x, int y)
{
- int i, j, px, py;
+ int off = XYOFFSET(x, y);
+
+ return xzone[off] == c || xzone[off] == -1;
+}
- for (i = 1; i <= d; ++i) {
- for (j = 0; j < i; ++j)
- vector[j] = 0;
+/*
+ * 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 {
- px = newx;
- py = newy;
- for (j = 0; j < i; ++j) {
- px = new_x(px + dirx[vector[j]]);
- py = new_y(py + diry[vector[j]]);
- }
- if (own[px][py] != -1 &&
- own[px][py] != c &&
- (DISTINCT_ISLANDS || own[px][py] < nc))
- return 0;
- } while (next_vector(i));
+ 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));
}
- sectx[c][secs] = newx;
- secty[c][secs] = newy;
- own[newx][newy] = c;
+}
+
+/*
+ * 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 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[x][y] = c;
+}
+
+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;
}
{
int i, nx, ny, wat = 0;
- if (secs == 1) {
+ if (isecs[c] == 1) {
*xp = x;
*yp = y;
return;
*/
static int
-new_try(int c)
+new_try(int c, int spike)
{
+ int secs = isecs[c];
int i, starti;
if (secs == 1) {
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;
- spike = roll0(100) < sp;
- if ((try1 = new_try(c)) == -1)
+ if ((try1 = new_try(c, spike)) == -1)
return 0;
x = sx = sectx[c][try1];
y = sy = secty[c][try1];
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 (own[newx][newy] == -1 &&
- (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, c < nc ? di : id))
+ 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))
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 (own[newx][newy] == -1)
- if (try_to_grow(c, newx, newy, c < nc ? di : id))
- done = 1;
+ if (try_to_grow(c, newx, newy))
+ done = 1;
}
next_coast(c, x, y, &x, &y);
++coast_search;
} while (!done && coast_search < COAST_SEARCH_MAX &&
- (secs == 1 || x != sx || y != sy));
- if (!done && c < nc)
- fl_status |= STATUS_NO_ROOM;
+ (isecs[c] == 1 || x != sx || y != sy));
return done;
}
-/* Grow all the continents
-*/
-static void
+/*
+ * Grow the continents.
+ * Return 1 on success, 0 on error.
+ */
+static int
grow_continents(void)
{
- int c;
+ int done = 1;
+ int c, secs;
+
+ ctot = 0;
+ xzone_init(0);
for (c = 0; c < nc; ++c) {
- sectx[c][0] = capx[c];
- secty[c][0] = capy[c];
- own[sectx[c][0]][secty[c][0]] = c;
- sectx[c][1] = new_x(capx[c] + 2);
- secty[c][1] = capy[c];
- own[sectx[c][1]][secty[c][1]] = c;
+ isecs[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;
+ }
}
- for (secs = 2; secs < sc && !fl_status; ++secs) {
+ if (!done) {
+ qprint("No room for continents\n");
+ return 0;
+ }
+
+ for (secs = 2; secs < sc && done; secs++) {
for (c = 0; c < nc; ++c) {
find_coast(c);
- grow_one_sector(c);
+ if (!grow_one_sector(c))
+ done = 0;
}
}
+
for (c = 0; c < nc; ++c)
find_coast(c);
- if (fl_status)
- qprint("Only managed to grow %d out of %d sectors.\n", secs, sc);
+ if (!done)
+ qprint("Only managed to grow %d out of %d sectors.\n",
+ secs - 1, sc);
ctot = nc;
+ return done;
}
/****************************************************************************
GROW THE ISLANDS
****************************************************************************/
-/* Choose a place to start growing an island from
-*/
+/*
+ * Place additional island @c's first sector.
+ * Return 1 on success, 0 on error.
+ */
static int
-place_island(int c, int *xp, int *yp)
+place_island(int c)
{
- int d, sx, sy;
- 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 + id; d >= id; --d) {
- sx = ssx;
- sy = ssy;
- *xp = new_x(sx + 2);
- for (*yp = sy; *xp != sx || *yp != sy; *xp += 2) {
- if (*xp >= WORLD_X) {
- *yp = new_y(*yp + 1);
- *xp = *yp % 2;
- if (*xp == sx && *yp == 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 (own[*xp][*yp] == -1 && try_to_grow(c, *xp, *yp, d))
- return 1;
}
}
- return 0;
+
+ if (n)
+ add_sector(c, newx, newy);
+ return n;
}
/* Grow all the islands
static void
grow_islands(void)
{
- int c, x, y, isiz;
+ int stunted_islands = 0;
+ int c, secs, isiz;
+
+ xzone_init(nc);
for (c = nc; c < nc + ni; ++c) {
- secs = 0;
- if (!place_island(c, &x, &y))
- return;
+ if (!place_island(c)) {
+ qprint("\nNo room for island #%d", c - nc + 1);
+ break;
+ }
+
isiz = roll(is) + roll0(is);
- do {
- ++secs;
+ for (secs = 1; secs < isiz; secs++) {
find_coast(c);
- } while (secs < isiz && grow_one_sector(c));
+ if (!grow_one_sector(c)) {
+ stunted_islands++;
+ break;
+ }
+ }
+
find_coast(c);
qprint(" %d(%d)", c - nc + 1, secs);
- isecs[c] = secs;
ctot++;
}
+
+ if (stunted_islands)
+ qprint("\n%d stunted island%s",
+ stunted_islands, splur(stunted_islands));
}
/****************************************************************************
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;
+ }
elevate_land();
elevate_sea();
}
static int
distance_to_what(int x, int y, int flag)
{
- int j, d, px, py;
+ int d, px, py;
+ struct hexagon_iter hexit;
for (d = 1; d < 5; ++d) {
- for (j = 0; j < d; ++j)
- vector[j] = 0;
+ hexagon_first(&hexit, x, y, d, &px, &py);
do {
- px = x;
- py = y;
- for (j = 0; j < d; ++j) {
- px = new_x(px + dirx[vector[j]]);
- py = new_y(py + diry[vector[j]]);
- }
switch (flag) {
case 0: /* distance to sea */
if (own[px][py] == -1)
return d;
break;
case 2: /* distance to mountain */
- if (elev[px][py] == INFINITY)
+ if (elev[px][py] == INFINITE_ELEVATION)
return d;
break;
}
- } while (next_vector(d));
+ } while (hexagon_next(&hexit, &px, &py));
}
return d;
}
for (c = 0; c < ctot; ++c) {
total = 0;
- ns = (c < nc) ? sc : isecs[c];
+ ns = isecs[c];
nm = (pm * ns) / 100;
/* Place the mountains */
++mountain_search) {
r = roll0(total);
for (i = 0; i < ns; ++i)
- if (r < weight[i] && ELEV == -INFINITY &&
+ if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
(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 = INFINITY;
+ ELEV = INFINITE_ELEVATION;
break;
}
--k;
dmoun[i] = distance_to_mountain();
dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
(100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
- 100 * INFINITY;
+ 100 * INFINITE_ELEVATION;
for (k = 100 * (HIGHMIN - 1);; k -= dk) {
- highest = -INFINITY;
+ highest = 0;
where = -1;
for (i = 0; i < ns; ++i) {
- if (ELEV != INFINITY &&
+ if (ELEV == -INFINITE_ELEVATION &&
(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]))))) {
h = 3 * (5 - dmoun[i]) + dsea[i];
+ assert(h > 0);
if (h > highest) {
highest = h;
where = i;
if (newk < LANDMIN)
newk = LANDMIN;
elev[sectx[c][where]][secty[c][where]] = newk;
- dsea[where] = -INFINITY;
- dmoun[where] = INFINITY;
}
/* Elevate the mountains and capitals */
for (i = 0; i < ns; ++i) {
- if (ELEV == INFINITY) {
+ if (ELEV == INFINITE_ELEVATION) {
if (dsea[i] == 1)
ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
else
for (y = 0; y < WORLD_Y; ++y) {
for (x = y % 2; x < WORLD_X; x += 2) {
- if (elev[x][y] == -INFINITY)
+ if (elev[x][y] == -INFINITE_ELEVATION)
elev[x][y] = -roll(distance_to_land() * 20 + 27);
}
}
}
}
+/*
+ * 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
****************************************************************************/
int i, j;
struct sctstr *sp;
- for (i = 0; i < nc; ++i) {
- for (j = 0; j < sc; j++) {
- sp = getsectp(sectx[i][j], secty[i][j]);
- sp->sct_coastal = sectc[i][j];
- }
- }
- for (i = nc; i < nc + ni; ++i) {
+ 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];