*
* 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.
#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"
#include "xy.h"
-/* define ORE 1 to add resources, define ORE 0 if you want to use another
- program to add the resources */
-static int ORE = 1;
-static int quiet = 0;
-
-/* If you don't specify these command line arguments, then these are the
- defaults */
-#define DEFAULT_SPIKE 10
-#define DEFAULT_MOUNTAIN 0
-#define DEFAULT_CONTDIST 2
-#define DEFAULT_ISLDIST 1
-
/* The following five numbers refer to elevation under which (in the case of
fertility or oil) or over which (in the case of iron, gold, and uranium)
sectors with that elevation will contain that resource. Elevation ranges
static void qprint(const char * const fmt, ...)
ATTRIBUTE((format (printf, 1, 2)));
-#define DEFAULT_OUTFILE_NAME "newcap_script"
-static const char *outfile = DEFAULT_OUTFILE_NAME;
-
+/*
+ * Program arguments and options
+ */
+static char *program_name;
+static int nc, sc; /* number and size of continents */
+static int ni, is; /* number and size of islands */
+#define DEFAULT_SPIKE 10
+static int sp = DEFAULT_SPIKE; /* spike percentage */
+#define DEFAULT_MOUNTAIN 0
+static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
+#define DEFAULT_CONTDIST 2
+static int di = DEFAULT_CONTDIST; /* min. distance between continents */
+#define DEFAULT_ISLDIST 1
+static int id = DEFAULT_ISLDIST; /* ... continents and islands */
/* don't let the islands crash into each other.
1 = don't merge, 0 = merge. */
static int DISTINCT_ISLANDS = 1;
-
-static char *program_name;
+static int quiet;
+#define DEFAULT_OUTFILE_NAME "newcap_script"
+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 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 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 nc, sc, di, sp, pm, ni, is, id; /* the 8 args to this program */
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 */
+
+/*
+ * 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
+ * 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;
+
+/*
+ * 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 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 int map_symbol(int x, int y);
static void set_coastal_flags(void);
static void print_vars(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);
/****************************************************************************
{
int opt;
char *config_file = NULL;
- int i = 0;
+ int try, done;
unsigned rnd_seed = 0;
int seed_set = 0;
program_name = argv[0];
- while ((opt = getopt(argc, argv, "e:hioqR:s:v")) != EOF) {
+ while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
switch (opt) {
case 'e':
config_file = optarg;
case 'i':
DISTINCT_ISLANDS = 0;
break;
- case 'o':
- ORE = 0;
- break;
case 'q':
quiet = 1;
break;
exit(1);
}
}
- parse_args(argc - optind, argv + optind);
if (!seed_set)
rnd_seed = pick_seed();
exit(1);
empfile_fixup();
+ parse_args(argc - optind, argv + optind);
+
allocate_memory();
print_vars();
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("fairland: unstable drift -- try increasing DRIFT_MAX\n");
+ qprint("unstable drift\n");
qprint("growing continents...\n");
- grow_continents();
- } while (fl_status && ++i < NUMTRIES);
- if (fl_status) {
- fputs("ERROR: World not large enough to hold continents\n",
- stderr);
+ done = grow_continents();
+ } while (!done && ++try < NUMTRIES);
+ if (!done) {
+ fprintf(stderr, "%s: world not large enough to hold continents\n",
+ program_name);
exit(1);
}
qprint("growing islands:");
grow_islands();
qprint("\nelevating land...\n");
create_elevations();
- qprint("designating sectors...\n");
- if (ORE)
- qprint("adding resources...\n");
+
+ qprint("writing to sectors file...\n");
if (!write_newcap_script())
exit(1);
-
if (chdir(gamedir)) {
- fprintf(stderr, "Can't chdir to %s (%s)\n", gamedir, strerror(errno));
- exit(EXIT_FAILURE);
+ fprintf(stderr, "%s: can't chdir to %s (%s)\n",
+ program_name, gamedir, strerror(errno));
+ exit(1);
}
if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
exit(1);
write_sects();
- qprint("writing to sectors file...\n");
if (!ef_close(EF_SECTOR))
exit(1);
output();
qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
outfile);
- if (!ORE)
- qprint("\t*** Resources have not been added ***\n");
exit(0);
}
printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
}
-static int
-my_sqrt(int n)
-{
- int i;
-
- for (i = 1; i * i < n * 10000; ++i) ;
- return (i + 50) / 100;
-}
-
-/****************************************************************************
- PARSE COMMAND LINE ARGUMENTS
-****************************************************************************/
-
static void
help(char *complaint)
{
" -e CONFIG-FILE configuration file\n"
" (default %s)\n"
" -i islands may merge\n"
- " -o don't set resources\n"
" -q quiet\n"
" -R SEED seed for random number generator\n"
" -s SCRIPT name of script to create (default %s)\n"
static void
parse_args(int argc, char *argv[])
{
+ int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
+
if (argc < 2) {
help("missing arguments");
exit(1);
}
nc = atoi(argv[0]);
if (nc < 1) {
- puts("fairland: error -- number of continents must be > 0");
+ fprintf(stderr, "%s: number of continents must be > 0\n",
+ program_name);
exit(1);
}
sc = atoi(argv[1]);
- if (sc < 1) {
- puts("fairland: error -- size of continents must be > 0");
+ if (sc < 2) {
+ fprintf(stderr, "%s: size of continents must be > 1\n",
+ program_name);
exit(1);
}
+ ni = nc;
+ is = sc / 2;
+
if (argc > 2)
ni = atoi(argv[2]);
- else
- ni = nc;
+ if (ni < 0) {
+ fprintf(stderr, "%s: number of islands must be >= 0\n",
+ program_name);
+ exit(1);
+ }
if (argc > 3)
is = atoi(argv[3]);
- else
- is = sc / 2;
- if (is < 1)
- is = 1;
+ if (is < 1) {
+ fprintf(stderr, "%s: size of islands must be > 0\n",
+ program_name);
+ exit(1);
+ }
if (argc > 4)
sp = atoi(argv[4]);
- else
- sp = DEFAULT_SPIKE;
- sp = LIMIT_TO(sp, 0, 100);
+ if (sp < 0 || sp > 100) {
+ fprintf(stderr,
+ "%s: spike percentage must be between 0 and 100\n",
+ program_name);
+ exit(1);
+ }
if (argc > 5)
pm = atoi(argv[5]);
- else
- pm = DEFAULT_MOUNTAIN;
- if (pm < 0)
- pm = 0;
+ if (pm < 0 || pm > 100) {
+ fprintf(stderr,
+ "%s: mountain percentage must be between 0 and 100\n",
+ program_name);
+ exit(1);
+ }
if (argc > 6)
di = atoi(argv[6]);
- else
- di = DEFAULT_CONTDIST;
-
if (di < 0) {
- puts("fairland: error -- distance between continents must be >= 0");
+ fprintf(stderr, "%s: distance between continents must be >= 0\n",
+ program_name);
exit(1);
}
- if (di > WORLD_X / 2 || di > WORLD_Y / 2) {
- puts("fairland: error -- distance between continents too large");
+ if (di > dist_max) {
+ fprintf(stderr, "%s: distance between continents too large\n",
+ program_name);
exit(1);
}
if (argc > 7)
id = atoi(argv[7]);
- else
- id = DEFAULT_ISLDIST;
if (id < 0) {
- puts("fairland: error -- distance from islands to continents must be >= 0");
+ fprintf(stderr,
+ "%s: distance from islands to continents must be >= 0\n",
+ program_name);
exit(1);
}
- if (id > WORLD_X || id > WORLD_Y) {
- puts("fairland: error -- distance from islands to continents too large");
+ if (id > dist_max) {
+ fprintf(stderr,
+ "%s: distance from islands to continents too large\n",
+ program_name);
exit(1);
}
- if (nc * sc + nc * my_sqrt(sc) * 2 * (di + 1) > WORLD_X * WORLD_Y) {
- puts("fairland: warning -- world might be too small to fit continents.");
- puts("arguments should satisfy:");
- puts("nc*sc*sc + nc*sqrt(sc)*2*(di+1) < WORLD_X * WORLD_Y");
- }
}
/****************************************************************************
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 *));
+ 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));
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) {
- puts("fairland error: world not big enough for all the continents.\n");
- exit(1);
- }
- }
- capx[i] = xx;
- capy[i] = yy;
- xx += 2;
- }
- for (i = 0; i < STABLE_CYCLE; ++i)
- mc[i] = i;
+ memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
}
/****************************************************************************
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
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 < 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)
+ 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;
+ }
}
}
-/* 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 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 i, j, px, py;
+ int d, x1, y1, off;
+ struct hexagon_iter hexit;
+
+ assert(xzone_ok(c, x, y));
- for (i = 1; i <= d; ++i) {
- for (j = 0; j < i; ++j)
- vector[j] = 0;
+ 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;
- return 1;
}
-/* Move along the coast in a clockwise direction.
-*/
+/*
+ * 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
-next_coast(int c, int x, int y, int *xp, int *yp)
+xzone_init(int n)
{
- int i, nx, ny, wat = 0;
+ int i, c;
- if (secs == 1) {
- *xp = x;
- *yp = y;
- return;
+ for (i = 0; i < WORLD_SZ(); i++)
+ xzone[i] = -1;
+
+ for (c = 0; c < n; c++)
+ xzone_around_island(c, id);
+}
+
+/*
+ * Initialize breadth-first search.
+ */
+static void
+bfs_init(void)
+{
+ int i;
+
+ for (i = 0; i < WORLD_SZ(); i++) {
+ closest[i] = -1;
+ distance[i] = USHRT_MAX;
}
- 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;
+ 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
+bfs_enqueue(int c, int x, int y, int dist)
+{
+ 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);
+}
+
+/*
+ * Search breadth-first until the queue is empty.
+ */
+static void
+bfs_run_queue(void)
+{
+ 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);
}
}
}
-/* Choose a sector to grow from
-*/
+/*
+ * Add island @c's coastal sectors to the BFS queue, with distance 0.
+ */
+static void
+bfs_enqueue_island(int c)
+{
+ int i;
+
+ for (i = 0; i < isecs[c]; i++) {
+ if (sectc[c][i])
+ bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
+ }
+}
+
+/*
+ * 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();
+}
+/*
+ * Can island @c grow at @x,@y?
+ */
static int
-new_try(int c)
+can_grow_at(int c, int x, int y)
{
- int i, starti;
+ return own[x][y] == -1 && xzone_ok(c, x, y);
+}
- 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;
+static void
+adj_land_update(int x, int y)
+{
+ 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);
}
- return -1;
}
-/* Grow continent c by 1 sector
-*/
+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;
+ adj_land_update(x, y);
+}
+
+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 done, coast_search, try1, x, y, newx, newy, i, n, sx, sy;
-
- spike = roll0(100) < sp;
- if ((try1 = new_try(c)) == -1)
- 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 (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))
- 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;
+ int spike = roll0(100) < sp;
+ 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;
}
- 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) {
- qprint("fairland: error -- continent %c had no room to grow!\n",
- numletter[c % 62]);
- fl_status |= STATUS_NO_ROOM;
+ }
}
- return done;
+
+ if (!wsum)
+ return 0;
+
+ add_sector(c, newx, newy);
+ return 1;
}
-/* 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 (!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]);
}
- 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);
+ init_spheres_of_influence();
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;
- find_coast(c);
- } while (secs < isiz && grow_one_sector(c));
+ for (secs = 1; secs < isiz; secs++) {
+ 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);
}
}
}
+static int
+elev_to_sct_type(int elevation)
+{
+ if (elevation < LANDMIN)
+ return SCT_WATER;
+ if (elevation < HILLMIN)
+ return SCT_RURAL;
+ if (elevation < PLATMIN)
+ return SCT_MOUNT;
+ if (elevation < HIGHMIN)
+ return SCT_RURAL;
+ return SCT_MOUNT;
+}
+
/****************************************************************************
ADD THE RESOURCES
****************************************************************************/
write_sects(void)
{
struct sctstr *sct;
- int x, y, total;
+ int x, y;
for (y = 0; y < WORLD_Y; y++) {
for (x = y % 2; x < WORLD_X; x += 2) {
sct = getsectp(x, y);
- total = elev[x][y];
- if (total < LANDMIN) {
- sct->sct_type = SCT_WATER;
- } else if (total < HILLMIN)
- sct->sct_type = SCT_RURAL;
- else if (total < PLATMIN)
- sct->sct_type = SCT_MOUNT;
- else if (total < HIGHMIN)
- sct->sct_type = SCT_RURAL;
- else
- sct->sct_type = SCT_MOUNT;
- sct->sct_elev = total;
+ sct->sct_elev = elev[x][y];
+ 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;
- if (ORE)
- add_resources(sct);
+ add_resources(sct);
}
}
set_coastal_flags();
static void
output(void)
{
- int sx, sy, x, y;
+ int sx, sy, x, y, c, type;
if (quiet == 0) {
for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
printf(" ");
for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
x = XNORM(sx);
- if (own[x][y] == -1)
+ c = own[x][y];
+ type = elev_to_sct_type(elev[x][y]);
+ if (type == SCT_WATER)
printf(". ");
+ else if (type == SCT_MOUNT)
+ printf("^ ");
+ else if (c >= nc)
+ printf("%% ");
else {
- printf("%c ", map_symbol(x, y));
+ assert(0 <= c && c < nc);
+ if ((x == capx[c] || x == new_x(capx[c] + 2))
+ && y == capy[c])
+ printf("%c ", numletter[c % 62]);
+ else
+ printf("# ");
}
}
}
}
}
-static int
-map_symbol(int x, int y)
-{
- int c;
-
- for (c = 0; c < nc; ++c)
- if ((x == capx[c] && y == capy[c])
- || (x == new_x(capx[c] + 2) && y == capy[c]))
- return numletter[own[x][y] % 62];
- if ((elev[x][y] >= HILLMIN && elev[x][y] < PLATMIN)
- || elev[x][y] >= HIGHMIN)
- return '^';
- return own[x][y] >= nc ? '%' : '#';
-}
-
/*
* Print a map to help visualize own[][].
* This is for debugging.
}
}
+/*
+ * 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');
+ }
+}
+
+/*
+ * 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
****************************************************************************/
FILE *script = fopen(outfile, "w");
if (!script) {
- printf("fairland: error, unable to write to %s.\n", outfile);
+ fprintf(stderr, "%s: unable to write to %s (%s)\n",
+ program_name, outfile, strerror(errno));
return 0;
}
int i, j;
struct sctstr *sp;
- qprint("setting coastal flags...\n");
- 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];
projects / empserver / blobdiff