X-Git-Url: http://git.pond.sub.org/?p=empserver;a=blobdiff_plain;f=src%2Futil%2Ffairland.c;h=30c66297a687add58c0f3a8e92a42b9c24b68ed2;hp=263b6e68adacc430127fd14d352c0f3f6f541744;hb=6642878d5f9d213d38531e1760e7f58838e38149;hpb=380d2e9f551499da8ddf2dcbe897416f98732623 diff --git a/src/util/fairland.c b/src/util/fairland.c index 263b6e68a..30c66297a 100644 --- a/src/util/fairland.c +++ b/src/util/fairland.c @@ -45,54 +45,72 @@ * * 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 - * 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 * - * Elevate islands one after the other. + * First, use a simple random hill algorithm to assign raw elevations: + * initialize elevation to zero, then randomly raise circular hills on + * land / lower circular depressions at sea. Their size and height + * depends on the distance to the coast. * - * First, place the specified number of mountains randomly. - * Probability increases with distance to sea. + * Then, elevate islands one after the other. * - * Last, elevate mountains and the capitals. Pick coastal mountain - * elevation randomly from an interval of medium elevations reserved - * for them. Pick non-coastal mountain elevation randomly from an - * interval of high elevation reserved for them. Set capital - * elevation to a fixed, medium value. + * Set the capitals' elevation to a fixed value. Process the + * remaining sectors in order of increasing raw elevation, first + * non-mountains, then mountains. Non-mountain elevation starts at 1, + * and increases linearly to just below "high" elevation. Mountain + * elevation starts at "high" elevation, and increases linearly. * - * In between, elevate the remaining land one by one, working from - * mountains towards the sea, and from the elevation just below the - * non-coastal mountains' interval linearly down to 1, avoiding the - * coastal mountains' interval. + * This gives islands of the same size the same set of elevations. + * Larger islands get more and taller mountains. * - * This gives islands of the same size the same set of elevations, - * except for mountains. - * - * Elevate sea: pick a random depth from an interval that deepens with - * the distance to land. + * Finally, elevate sea: normalize the raw elevations to [-127:-1]. * * 5. Set resources * * Sector resources are simple functions of elevation. You can alter - * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to - * customize them. + * iron_conf[], gold_conf[], fert_conf[], oil_conf[], and uran_conf[] + * to customize them. */ #include @@ -111,31 +129,64 @@ #include "version.h" #include "xy.h" -/* 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 - from 0 to 100 */ - -/* raise FERT_MAX for more fertility */ -#define FERT_MAX 56 - -/* raise OIL_MAX for more oil */ -#define OIL_MAX 33 +/* do not change these defines */ +#define LANDMIN 1 /* plate altitude for normal land */ +#define PLATMIN 36 /* plate altitude for plateau */ +#define HIGHMIN 98 /* plate altitude for mountains */ -/* lower IRON_MIN for more iron */ -#define IRON_MIN 22 +/* + * Resource configuration -/* lower GOLD_MIN for more gold */ -#define GOLD_MIN 36 + * Resources are determined by elevation. The map from elevation to + * resource is defined as a linear interpolation of resource data + * points (elev, res) defined in the tables below. Elevations range + * from -127 to 127, and resource values from 0 to 100. + */ -/* lower URAN_MIN for more uranium */ -#define URAN_MIN 56 +struct resource_point { + int elev, res; +}; -/* do not change these 4 defines */ -#define LANDMIN 1 /* plate altitude for normal land */ -#define HILLMIN 34 /* plate altitude for hills */ -#define PLATMIN 36 /* plate altitude for plateau */ -#define HIGHMIN 98 /* plate altitude for mountains */ +struct resource_point iron_conf[] = { + { -127, 0 }, + { 21, 0 }, + { 85, 100 }, + { HIGHMIN - 1, 100 }, + { HIGHMIN , 0 }, + { 127, 0 } }; + +struct resource_point gold_conf[] = { + { -127, 0 }, + { 35, 0 }, + { HIGHMIN - 1, 80 }, + { HIGHMIN, 80 }, + { 127, 85 } }; + +struct resource_point fert_conf[] = { + { -127, 100 }, + { -59, 100 }, + { LANDMIN - 1, 41 }, + { LANDMIN, 100 }, + { 10, 100 }, + { 56, 0 }, + { 127, 0 } }; + +struct resource_point oil_conf[] = { + { -127, 100 }, + { -49, 100 }, + { LANDMIN - 1, 2 }, + { LANDMIN, 100 }, + { 6, 100 }, + { 34, 0 }, + { 127, 0 } }; + +struct resource_point uran_conf[] = { + { -127, 0 }, + { 55, 0 }, + { 90, 100 }, + { 97, 100 }, + { 98, 0 }, + { 127, 0 } }; static void qprint(const char * const fmt, ...) ATTRIBUTE((format (printf, 1, 2))); @@ -162,16 +213,8 @@ static int quiet; static const char *outfile = DEFAULT_OUTFILE_NAME; #define STABLE_CYCLE 4 /* stability required for perterbed capitals */ -#define INFINITY 999 /* a number which means "BIG" */ - -/* 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 */ /* handy macros: */ @@ -179,19 +222,67 @@ static const char *outfile = DEFAULT_OUTFILE_NAME; #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 */ -static int **elev; /* elevation of the sectors */ + +/* + * 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; + +/* + * Elevation at x,y + * elev[XYOFFSET(x, y)] is x,y's elevation. + */ +static short *elev; + +/* + * 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() and + * init_distance_to_coast(). + */ +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 **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 */ #define NUMTRIES 10 /* keep trying to grow this many times */ @@ -210,16 +301,19 @@ static void write_sects(void); static void output(void); static int write_newcap_script(void); static int stable(int); +static void elevate_prep(void); 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); +void print_xzone_map(void); +void print_closest_map(void); +void print_distance_map(void); void print_elev_map(void); /**************************************************************************** @@ -292,15 +386,17 @@ main(int argc, char *argv[]) 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"); @@ -410,6 +506,12 @@ parse_args(int argc, char *argv[]) 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]); @@ -478,27 +580,26 @@ allocate_memory(void) capx = calloc(nc, sizeof(int)); capy = calloc(nc, sizeof(int)); own = calloc(WORLD_X, sizeof(int *)); - elev = calloc(WORLD_X, sizeof(int *)); + adj_land = malloc(WORLD_SZ() * sizeof(*adj_land)); + elev = calloc(WORLD_SZ(), sizeof(*elev)); + 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)); for (i = 0; i < WORLD_X; ++i) { own[i] = calloc(WORLD_Y, sizeof(int)); - elev[i] = calloc(WORLD_Y, sizeof(int)); } 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)); - dmoun = 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)); } } @@ -513,6 +614,7 @@ init(void) own[i][j] = -1; } } + memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land)); } /**************************************************************************** @@ -607,11 +709,15 @@ stable(int turns) 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; @@ -624,20 +730,11 @@ fl_move(int j) 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, j; - - 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) - sectc[c][i] = 1; - } + return adj_land[XYOFFSET(x, y)] + != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST); } struct hexagon_iter { @@ -678,123 +775,330 @@ hexagon_next(struct hexagon_iter *iter, int *x, int *y) 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, px, py; + int d, x1, y1, off; struct hexagon_iter hexit; - if (own[newx][newy] != -1) - return 0; + assert(xzone_ok(c, x, y)); - for (i = 1; i <= d; ++i) { - hexagon_first(&hexit, newx, newy, i, &px, &py); + xzone[XYOFFSET(x, y)] = c; + for (d = 1; d <= dist; d++) { + hexagon_first(&hexit, x, y, d, &x1, &y1); do { - if (own[px][py] != -1 && - own[px][py] != c && - (DISTINCT_ISLANDS || own[px][py] < nc)) - return 0; - } while (hexagon_next(&hexit, &px, &py)); + 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][isecs[c]] = newx; - secty[c][isecs[c]] = newy; - isecs[c]++; - 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 (isecs[c] == 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 (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 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) +{ + int c; + + bfs_init(); + 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 -new_try(int c, int spike) +is_in_sphere(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 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 +adj_land_update(int x, int y) +{ + int is_land = own[x][y] != -1; + int dir, nx, ny, noff; + + 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 (is_land) + adj_land[noff] |= 1u << DIR_BACK(dir); + else + 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 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, 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 (try_to_grow(c, newx, newy, c < nc ? di : id)) - 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; } /* @@ -807,13 +1111,17 @@ grow_continents(void) int done = 1; int c, secs; + xzone_init(0); + for (c = 0; c < nc; ++c) { isecs[c] = 0; - if (!try_to_grow(c, capx[c], capy[c], di) - || !try_to_grow(c, new_x(capx[c] + 2), capy[c], di)) { + 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) { @@ -823,19 +1131,14 @@ grow_continents(void) for (secs = 2; secs < sc && done; secs++) { for (c = 0; c < nc; ++c) { - find_coast(c); if (!grow_one_sector(c)) done = 0; } } - 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; } @@ -843,67 +1146,132 @@ grow_continents(void) 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 isiz) { - 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, 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)) { + 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; + } } - if (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 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, x, y, isiz; + int *island_size = size_islands(); + int xzone_valid = 0; + int carry = 0; + int i, j, c, done, secs, isiz, x, y; - for (c = nc; c < nc + ni; ++c) { - if (!place_island(c, &x, &y)) { - qprint("\nNo room for island #%d", c - nc + 1); - break; + init_spheres_of_influence(); + + 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; + } + } + + done = 1; + for (secs = 1; secs < isiz && done; secs++) { + for (j = 0; j < nc; j++) { + if (!grow_one_sector(c + j)) + done = 0; + } } - isiz = roll(is) + roll0(is); - for (secs = 1; secs < isiz; secs++) { - find_coast(c); - if (!grow_one_sector(c)) { - stunted_islands++; - break; + 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; } - find_coast(c); - qprint(" %d(%d)", c - nc + 1, secs); - ctot++; + 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; } /**************************************************************************** @@ -912,152 +1280,104 @@ grow_islands(void) 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] = -INFINITY; - } + elevate_prep(); elevate_land(); elevate_sea(); } -/* Generic function for finding the distance to the closest sea, land, or - mountain -*/ static int -distance_to_what(int x, int y, int flag) +elev_cmp(const void *p, const void *q) { - int d, px, py; - struct hexagon_iter hexit; + int a = *(int *)p; + int b = *(int *)q; + int delev = elev[a] - elev[b]; - for (d = 1; d < 5; ++d) { - hexagon_first(&hexit, x, y, d, &px, &py); - do { - switch (flag) { - case 0: /* distance to sea */ - if (own[px][py] == -1) - return d; - break; - case 1: /* distance to land */ - if (own[px][py] != -1) - return d; - break; - case 2: /* distance to mountain */ - if (elev[px][py] == INFINITY) - return d; - break; - } - } while (hexagon_next(&hexit, &px, &py)); - } - return d; + return delev ? delev : a - b; } -#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) +elevate_prep(void) { - int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk, - r, dk; - - for (c = 0; c < ctot; ++c) { - total = 0; - ns = isecs[c]; - nm = (pm * ns) / 100; - -/* Place the mountains */ + int n = WORLD_SZ() * 8; + int off0, r, sign, elevation, d, x1, y1, off1; + coord x0, y0; + struct hexagon_iter hexit; - for (i = 0; i < ns; ++i) { - dsea[i] = distance_to_sea(); - weight[i] = (total += (dsea[i] * dsea[i])); + init_distance_to_coast(); + + while (n > 0) { + off0 = roll0(WORLD_SZ()); + sctoff2xy(&x0, &y0, off0); + if (own[x0][y0] == -1) { + r = roll(MIN(3, distance[off0])); + sign = -1; + } else { + r = roll(MIN(3, distance[off0]) + 1); + sign = 1; } - - for (k = nm, mountain_search = 0; - k && mountain_search < MOUNTAIN_SEARCH_MAX; - ++mountain_search) { - r = roll0(total); - for (i = 0; i < ns; ++i) - if (r < weight[i] && ELEV == -INFINITY && - (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; - break; - } - --k; + elevation = elev[off0] + sign * r * r; + elev[off0] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX); + n--; + for (d = 1; d < r; d++) { + hexagon_first(&hexit, x0, y0, d, &x1, &y1); + do { + off1 = XYOFFSET(x1, y1); + elevation = elev[off1] + sign * (r * r - d * d); + elev[off1] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX); + n--; + } while (hexagon_next(&hexit, &x1, &y1)); } + } +} -/* Elevate land that is not mountain and not capital */ - - for (i = 0; i < ns; ++i) - dmoun[i] = distance_to_mountain(); - dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ? - (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) : - 100 * INFINITY; - for (k = 100 * (HIGHMIN - 1);; k -= dk) { - highest = 0; - where = -1; - for (i = 0; i < ns; ++i) { - if (ELEV == -INFINITY && - (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 (where == -1) - break; - newk = k / 100; - if (newk >= HILLMIN && newk < PLATMIN) - newk = PLATMIN; - if (newk < LANDMIN) - newk = LANDMIN; - elev[sectx[c][where]][secty[c][where]] = newk; +static void +elevate_land(void) +{ + int *off = malloc(MAX(sc, is * 2) * sizeof(*off)); + int max_nm = (pm * MAX(sc, is * 2)) / 100; + int c, nm, i0, n, i; + double elevation, delta; + + for (c = 0; c < nc + ni; c++) { + nm = (pm * isecs[c]) / 100; + i0 = c < nc ? 2 : 0; + n = isecs[c] - i0; + for (i = 0; i < i0; i++) + elev[XYOFFSET(sectx[c][i], secty[c][i])] = PLATMIN; + for (i = 0; i < n; i++) + off[i] = XYOFFSET(sectx[c][i0 + i], secty[c][i0 + i]); + qsort(off, n, sizeof(*off), elev_cmp); + delta = (double)(HIGHMIN - LANDMIN - 1) / (n - nm - 1); + elevation = LANDMIN; + for (i = 0; i < n - nm; i++) { + elev[off[i]] = (int)(elevation + 0.5); + elevation += delta; } - -/* Elevate the mountains and capitals */ - - for (i = 0; i < ns; ++i) { - if (ELEV == INFINITY) { - if (dsea[i] == 1) - ELEV = HILLMIN + roll0(PLATMIN - HILLMIN); - else - ELEV = 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; + elevation = HIGHMIN; + delta = (127.0 - HIGHMIN) / max_nm; + for (; i < n; i++) { + elevation += delta; + elev[off[i]] = (int)(elevation + 0.5); } } -} -#define distance_to_land() distance_to_what(x, y, 1) + free(off); +} static void elevate_sea(void) { - int x, y; + int i, min; - for (y = 0; y < WORLD_Y; ++y) { - for (x = y % 2; x < WORLD_X; x += 2) { - if (elev[x][y] == -INFINITY) - elev[x][y] = -roll(distance_to_land() * 20 + 27); - } + min = 0; + for (i = 0; i < WORLD_SZ(); i++) { + if (elev[i] < min) + min = elev[i]; + } + + for (i = 0; i < WORLD_SZ(); i++) { + if (elev[i] < 0) + elev[i] = -1 - 126 * elev[i] / min; } } @@ -1066,10 +1386,6 @@ 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; @@ -1079,77 +1395,35 @@ elev_to_sct_type(int elevation) ADD THE RESOURCES ****************************************************************************/ +/* + * Map elevation @elev to a resource value according to @conf. + * This is a linear interpolation on the data points in @conf. + */ static int -set_fert(int e) -{ - int fert = 0; - if (e < LANDMIN) - fert = LANDMIN - e + 40; - else if (e < FERT_MAX) - fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN); - if (fert > 100) - fert = 100; - return fert; -} - -static int -set_oil(int e) -{ - int oil = 0; - if (e < LANDMIN) - oil = (LANDMIN - e) * 2 + roll0(2); - else if (e <= OIL_MAX) - oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1); - if (oil > 100) - oil = 100; - return oil; -} - -static int -set_iron(int e) -{ - int iron = 0; - if (e >= IRON_MIN && e < HIGHMIN) - iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN); - if (iron > 100) - iron = 100; - return iron; -} - -static int -set_gold(int e) -{ - int gold = 0; - if (e >= GOLD_MIN) { - if (e < HIGHMIN) - gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN); - else - gold = 100 - 20 * HIGHMIN / e; - } - if (gold > 100) - gold = 100; - return gold; -} - -static int -set_uran(int e) +elev_to_resource(int elev, struct resource_point conf[]) { - int uran = 0; - if (e >= URAN_MIN && e < HIGHMIN) - uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN); - if (uran > 100) - uran = 100; - return uran; + int i, elev1, elev2, delev, res1, res2, dres; + + for (i = 1; elev > conf[i].elev; i++) ; + assert(conf[i - 1].elev <= elev); + + elev1 = conf[i - 1].elev; + elev2 = conf[i].elev; + delev = elev2 - elev1; + res1 = conf[i - 1].res; + res2 = conf[i].res; + dres = res2 - res1; + return (int)(res1 + (double)((elev - elev1) * dres) / delev); } static void add_resources(struct sctstr *sct) { - sct->sct_fertil = set_fert(sct->sct_elev); - sct->sct_oil = set_oil(sct->sct_elev); - sct->sct_min = set_iron(sct->sct_elev); - sct->sct_gmin = set_gold(sct->sct_elev); - sct->sct_uran = set_uran(sct->sct_elev); + sct->sct_min = elev_to_resource(sct->sct_elev, iron_conf); + sct->sct_gmin = elev_to_resource(sct->sct_elev, gold_conf); + sct->sct_fertil = elev_to_resource(sct->sct_elev, fert_conf); + sct->sct_oil = elev_to_resource(sct->sct_elev, oil_conf); + sct->sct_uran = elev_to_resource(sct->sct_elev, uran_conf); } /**************************************************************************** @@ -1165,14 +1439,14 @@ write_sects(void) for (y = 0; y < WORLD_Y; y++) { for (x = y % 2; x < WORLD_X; x += 2) { sct = getsectp(x, y); - sct->sct_elev = elev[x][y]; - sct->sct_type = elev_to_sct_type(elev[x][y]); + sct->sct_elev = elev[sct->sct_uid]; + sct->sct_type = elev_to_sct_type(sct->sct_elev); 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(); } /**************************************************************************** @@ -1181,7 +1455,7 @@ write_sects(void) static void output(void) { - int sx, sy, x, y, c, type; + int sx, sy, x, y, off, c, type; if (quiet == 0) { for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) { @@ -1191,8 +1465,9 @@ output(void) printf(" "); for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) { x = XNORM(sx); + off = XYOFFSET(x, y); c = own[x][y]; - type = elev_to_sct_type(elev[x][y]); + type = elev_to_sct_type(elev[off]); if (type == SCT_WATER) printf(". "); else if (type == SCT_MOUNT) @@ -1238,35 +1513,36 @@ print_own_map(void) } /* - * Print a map to help visualize elev[][]. + * Print a map to help visualize elev[]. * This is for debugging. It expects the terminal to understand * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m. */ void print_elev_map(void) { - int sx, sy, x, y, sat; + int sx, sy, x, y, off, sat; 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 (!elev[x][y]) + else if (!elev[off]) putchar(' '); - else if (elev[x][y] < 0) { - sat = 256 + elev[x][y] * 2; + else if (elev[off] < 0) { + sat = 256 + elev[off] * 2; printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255); - } else if (elev[x][y] < HIGHMIN / 2) { - sat = (HIGHMIN / 2 - elev[x][y]) * 4; + } else if (elev[off] < HIGHMIN / 2) { + sat = (HIGHMIN / 2 - elev[off]) * 4; printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat); - } else if (elev[x][y] < HIGHMIN) { - sat = 128 + (HIGHMIN - elev[x][y]) * 2; + } else if (elev[off] < HIGHMIN) { + sat = 128 + (HIGHMIN - elev[off]) * 2; printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4); } else { - sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5; + sat = 128 + (elev[off] - HIGHMIN) * 2; printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat); } } @@ -1274,6 +1550,93 @@ print_elev_map(void) } } +/* + * 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 ****************************************************************************/ @@ -1309,17 +1672,3 @@ qprint(const char *const fmt, ...) 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]; - } - } -}