2 * Empire - A multi-player, client/server Internet based war game.
3 * Copyright (C) 1986-2020, Dave Pare, Jeff Bailey, Thomas Ruschak,
4 * Ken Stevens, Steve McClure, Markus Armbruster
6 * Empire is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
21 * See files README, COPYING and CREDITS in the root of the source
22 * tree for related information and legal notices. It is expected
23 * that future projects/authors will amend these files as needed.
27 * fairland.c: Create a nice, new world
29 * Known contributors to this file:
32 * Markus Armbruster, 2004-2020
40 * Place the capitals on the torus in such a way so as to maximize
41 * their distances from one another. This uses the perturbation
42 * technique of calculus of variations.
44 * 2. Grow start islands ("continents")
46 * For all continents, add the first sector at the capital's location,
47 * and the second right to it. These are the capital sectors. Then
48 * add one sector to each continent in turn, until they have the
51 * Growth uses weighted random sampling to pick one sector from the
52 * set of adjacent sea sectors that aren't too close to another
53 * continent. Growth operates in spiking mode with a chance given by
54 * the spike percentage. When "spiking", a sector's weight increases
55 * with number of adjacent sea sectors. This directs the growth away
56 * from land, resulting in spikes. When not spiking, the weight
57 * increases with the number of adjacent land sectors. This makes the
58 * island more rounded.
60 * If growing fails due to lack of room, start over. If it fails too
61 * many times, give up and terminate unsuccessfully.
63 * 3. Place and grow additional islands
65 * Each continent has a "sphere of influence": the set of sectors
66 * closer to it than to any other continent. Each island is entirely
67 * in one such sphere, and each sphere contains the same number of
68 * islands with the same sizes.
70 * First, split the specified number of island sectors per continent
71 * randomly into the island sizes. Sort by size so that larger
72 * islands are grown before smaller ones, to give the large ones the
73 * best chance to grow to their planned size.
75 * Then place one island's first sector into each sphere, randomly.
76 * Add one sector to each island in turn, until they have the intended
77 * size. Repeat until the specified number of islands has been grown.
79 * If placement fails due to lack of room, start over, just like for
82 * Growing works as for continents, except the minimum distance for
83 * additional islands applies, and growing simply stops when any of
84 * the islands being grown lacks the room to grow further. The number
85 * of sectors not grown carries over to the next island size.
87 * 4. Compute elevation
89 * Elevate islands one after the other.
91 * First, place the specified number of mountains randomly.
92 * Probability increases with distance to sea.
94 * Last, elevate mountains and the capitals. Pick coastal mountain
95 * elevation randomly from an interval of medium elevations reserved
96 * for them. Pick non-coastal mountain elevation randomly from an
97 * interval of high elevation reserved for them. Set capital
98 * elevation to a fixed, medium value.
100 * In between, elevate the remaining land one by one, working from
101 * mountains towards the sea, and from the elevation just below the
102 * non-coastal mountains' interval linearly down to 1, avoiding the
103 * coastal mountains' interval.
105 * This gives islands of the same size the same set of elevations,
106 * except for mountains.
108 * Elevate sea: pick a random depth from an interval that deepens with
109 * the distance to land.
113 * Sector resources are simple functions of elevation. You can alter
114 * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
129 #include "prototypes.h"
134 /* The following five numbers refer to elevation under which (in the case of
135 fertility or oil) or over which (in the case of iron, gold, and uranium)
136 sectors with that elevation will contain that resource. Elevation ranges
139 /* raise FERT_MAX for more fertility */
142 /* raise OIL_MAX for more oil */
145 /* lower IRON_MIN for more iron */
148 /* lower GOLD_MIN for more gold */
151 /* lower URAN_MIN for more uranium */
154 /* do not change these 4 defines */
155 #define LANDMIN 1 /* plate altitude for normal land */
156 #define HILLMIN 34 /* plate altitude for hills */
157 #define PLATMIN 36 /* plate altitude for plateau */
158 #define HIGHMIN 98 /* plate altitude for mountains */
160 static void qprint(const char * const fmt, ...)
161 ATTRIBUTE((format (printf, 1, 2)));
164 * Program arguments and options
166 static char *program_name;
167 static int nc, sc; /* number and size of continents */
168 static int ni, is; /* number and size of islands */
169 #define DEFAULT_SPIKE 10
170 static int sp = DEFAULT_SPIKE; /* spike percentage */
171 #define DEFAULT_MOUNTAIN 0
172 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
173 #define DEFAULT_CONTDIST 2
174 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
175 #define DEFAULT_ISLDIST 1
176 static int id = DEFAULT_ISLDIST; /* ... continents and islands */
177 /* don't let the islands crash into each other.
178 1 = don't merge, 0 = merge. */
179 static int DISTINCT_ISLANDS = 1;
181 #define DEFAULT_OUTFILE_NAME "newcap_script"
182 static const char *outfile = DEFAULT_OUTFILE_NAME;
184 #define STABLE_CYCLE 4 /* stability required for perterbed capitals */
185 #define INFINITE_ELEVATION 999
187 /* these defines prevent infinite loops:
189 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
190 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
191 #define MOUNTAIN_SEARCH_MAX 1000 /* how long do we try to place mountains */
196 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
197 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
201 * isecs[i] is the size of the i-th island.
205 static int *capx, *capy; /* location of the nc capitals */
207 static int **own; /* owner of the sector. -1 means water */
210 * Adjacent land sectors
211 * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
212 * to x, y in direction d is land.
214 static unsigned char *adj_land;
218 * Each island is surrounded by an exclusive zone where only it may
219 * grow. The width of the zone depends on minimum distances.
220 * While growing continents, it is @di sectors wide.
221 * While growing additional islands, it is @id sectors wide.
222 * DISTINCT_ISLANDS nullifies the exclusive zone then.
223 * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
224 * zone, a (non-negative) island number when it is in that island's
225 * exclusive zone and no other, and -2 when it is in multiple
231 * Set of sectors seen already
232 * Increment @cur_seen to empty the set of sectors seen, set
233 * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
235 static unsigned *seen;
236 static unsigned cur_seen;
239 * Closest continent and "distance"
240 * closest[XYOFFSET(x, y)] is the closest continent's number.
241 * distance[] is complicated; see init_spheres_of_influence().
243 static natid *closest;
244 static unsigned short *distance;
247 * Queue for breadth-first search
249 static int *bfs_queue;
250 static int bfs_queue_head, bfs_queue_tail;
252 static int **elev; /* elevation of the sectors */
253 static int **sectx, **secty; /* the sectors for each continent */
254 static int **sectc; /* which sectors are on the coast? */
255 static int *weight; /* used for placing mountains */
256 static int *dsea, *dmoun; /* the dist to the ocean and mountain */
258 #define NUMTRIES 10 /* keep trying to grow this many times */
260 static const char *numletter =
261 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
263 static void help(char *);
264 static void usage(void);
265 static void parse_args(int argc, char *argv[]);
266 static void allocate_memory(void);
267 static void init(void);
268 static int drift(void);
269 static int grow_continents(void);
270 static void create_elevations(void);
271 static void write_sects(void);
272 static void output(void);
273 static int write_newcap_script(void);
274 static int stable(int);
275 static void elevate_land(void);
276 static void elevate_sea(void);
277 static void set_coastal_flags(void);
279 static void print_vars(void);
280 static void fl_move(int);
281 static int grow_islands(void);
283 /* Debugging aids: */
284 void print_own_map(void);
285 void print_xzone_map(void);
286 void print_closest_map(void);
287 void print_distance_map(void);
288 void print_elev_map(void);
290 /****************************************************************************
292 ****************************************************************************/
295 main(int argc, char *argv[])
298 char *config_file = NULL;
300 unsigned rnd_seed = 0;
303 program_name = argv[0];
305 while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
308 config_file = optarg;
311 DISTINCT_ISLANDS = 0;
317 rnd_seed = strtoul(optarg, NULL, 10);
327 printf("%s\n\n%s", version, legal);
336 rnd_seed = pick_seed();
339 if (emp_config(config_file) < 0)
343 parse_args(argc - optind, argv + optind);
348 qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
349 qprint("seed is %u\n", rnd_seed);
354 qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
355 qprint("placing capitals...\n");
357 qprint("unstable drift\n");
358 qprint("growing continents...\n");
359 done = grow_continents();
362 qprint("growing islands:");
363 done = grow_islands();
364 } while (!done && ++try < NUMTRIES);
366 fprintf(stderr, "%s: world not large enough for this much land\n",
370 qprint("elevating land...\n");
373 qprint("writing to sectors file...\n");
374 if (!write_newcap_script())
376 if (chdir(gamedir)) {
377 fprintf(stderr, "%s: can't chdir to %s (%s)\n",
378 program_name, gamedir, strerror(errno));
381 if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
384 if (!ef_close(EF_SECTOR))
388 qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
398 puts("Creating a planet with:\n");
399 printf("%d continents\n", nc);
400 printf("continent size: %d\n", sc);
401 printf("number of islands: %d\n", ni);
402 printf("average size of islands: %d\n", is);
403 printf("spike: %d%%\n", sp);
404 printf("%d%% of land is mountain (each continent will have %d mountains)\n",
405 pm, (pm * sc) / 100);
406 printf("minimum distance between continents: %d\n", di);
407 printf("minimum distance from islands to continents: %d\n", id);
408 printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
412 help(char *complaint)
415 fprintf(stderr, "%s: %s\n", program_name, complaint);
416 fprintf(stderr, "Try -h for help.\n");
422 printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
423 " -e CONFIG-FILE configuration file\n"
425 " -i islands may merge\n"
427 " -R SEED seed for random number generator\n"
428 " -s SCRIPT name of script to create (default %s)\n"
429 " -h display this help and exit\n"
430 " -v display version information and exit\n"
431 " NC number of continents\n"
432 " SC continent size\n"
433 " NI number of islands (default NC)\n"
434 " IS average island size (default SC/2)\n"
435 " SP spike percentage: 0 = round, 100 = snake (default %d)\n"
436 " PM percentage of land that is mountain (default %d)\n"
437 " DI minimum distance between continents (default %d)\n"
438 " ID minimum distance from islands to continents (default %d)\n",
439 program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
440 DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
444 parse_args(int argc, char *argv[])
446 int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
449 help("missing arguments");
453 help("too many arguments");
458 fprintf(stderr, "%s: number of continents must be > 0\n",
465 fprintf(stderr, "%s: size of continents must be > 1\n",
476 fprintf(stderr, "%s: number of islands must be >= 0\n",
481 fprintf(stderr, "%s: number of islands must be a multiple of"
482 " the number of continents\n",
490 fprintf(stderr, "%s: size of islands must be > 0\n",
497 if (sp < 0 || sp > 100) {
499 "%s: spike percentage must be between 0 and 100\n",
506 if (pm < 0 || pm > 100) {
508 "%s: mountain percentage must be between 0 and 100\n",
516 fprintf(stderr, "%s: distance between continents must be >= 0\n",
521 fprintf(stderr, "%s: distance between continents too large\n",
530 "%s: distance from islands to continents must be >= 0\n",
536 "%s: distance from islands to continents too large\n",
542 /****************************************************************************
543 VARIABLE INITIALIZATION
544 ****************************************************************************/
547 allocate_memory(void)
551 capx = calloc(nc, sizeof(int));
552 capy = calloc(nc, sizeof(int));
553 own = calloc(WORLD_X, sizeof(int *));
554 adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
555 xzone = malloc(WORLD_SZ() * sizeof(*xzone));
556 seen = calloc(WORLD_SZ(), sizeof(*seen));
557 closest = malloc(WORLD_SZ() * sizeof(*closest));
558 distance = malloc(WORLD_SZ() * sizeof(*distance));
559 bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
560 elev = calloc(WORLD_X, sizeof(int *));
561 for (i = 0; i < WORLD_X; ++i) {
562 own[i] = calloc(WORLD_Y, sizeof(int));
563 elev[i] = calloc(WORLD_Y, sizeof(int));
565 sectx = calloc(nc + ni, sizeof(int *));
566 secty = calloc(nc + ni, sizeof(int *));
567 sectc = calloc(nc + ni, sizeof(int *));
568 isecs = calloc(nc + ni, sizeof(int));
569 weight = calloc(MAX(sc, is * 2), sizeof(int));
570 dsea = calloc(MAX(sc, is * 2), sizeof(int));
571 dmoun = calloc(MAX(sc, is * 2), sizeof(int));
572 for (i = 0; i < nc; ++i) {
573 sectx[i] = calloc(sc, sizeof(int));
574 secty[i] = calloc(sc, sizeof(int));
575 sectc[i] = calloc(sc, sizeof(int));
577 for (i = nc; i < nc + ni; ++i) {
578 sectx[i] = calloc(is * 2, sizeof(int));
579 secty[i] = calloc(is * 2, sizeof(int));
580 sectc[i] = calloc(is * 2, sizeof(int));
590 for (i = 0; i < WORLD_X; ++i) {
591 for (j = 0; j < WORLD_Y; ++j) {
595 memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
598 /****************************************************************************
599 DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
600 ****************************************************************************/
603 * How isolated is capital @j at @newx,@newy?
604 * Return the distance to the closest other capital.
607 iso(int j, int newx, int newy)
612 for (i = 0; i < nc; ++i) {
615 md = mapdist(capx[i], capy[i], newx, newy);
625 * Return 1 for a stable drift, 0 for an unstable one.
632 for (i = 0; i < nc; i++) {
633 capy[i] = (2 * i) / WORLD_X;
634 capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
635 if (capy[i] >= WORLD_Y) {
637 "%s: world not big enough for all the continents\n",
643 for (turns = 0; turns < DRIFT_MAX; ++turns) {
646 for (i = 0; i < nc; ++i)
653 * Has the drift stabilized?
654 * @turns is the number of turns so far.
659 static int mc[STABLE_CYCLE];
660 int i, isod, d = 0, stab = 1;
663 for (i = 0; i < STABLE_CYCLE; i++)
667 if (turns <= DRIFT_BEFORE_CHECK)
670 for (i = 0; i < nc; ++i) {
671 isod = iso(i, capx[i], capy[i]);
676 for (i = 0; i < STABLE_CYCLE; ++i)
680 mc[turns % STABLE_CYCLE] = d;
684 /* This routine does the actual drifting
690 int dir, i, newx, newy;
692 dir = DIR_L + roll0(6);
693 for (i = 0; i < 6; i++) {
696 newx = new_x(capx[j] + diroff[dir][0]);
697 newy = new_y(capy[j] + diroff[dir][1]);
699 if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
707 /****************************************************************************
709 ****************************************************************************/
711 /* Look for a coastal sector of continent c
719 for (i = 0; i < isecs[c]; ++i) {
721 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
722 nx = new_x(sectx[c][i] + diroff[dir][0]);
723 ny = new_y(secty[c][i] + diroff[dir][1]);
724 if (own[nx][ny] == -1)
730 struct hexagon_iter {
735 * Start iterating around @x0,@y0 at distance @d.
736 * Set *x,*y to coordinates of the first sector.
739 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
742 *x = new_x(x0 - 2 * n);
744 iter->dir = DIR_FIRST;
750 * Continue iteration started with hexagon_first().
751 * Set *x,*y to coordinates of the next sector.
752 * Return whether we're back at the first sector, i.e. iteration is
756 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
758 *x = new_x(*x + diroff[iter->dir][0]);
759 *y = new_y(*y + diroff[iter->dir][1]);
761 if (iter->i == iter->n) {
765 return iter->dir <= DIR_LAST;
769 * Is @x,@y in no exclusive zone other than perhaps @c's?
772 xzone_ok(int c, int x, int y)
774 int off = XYOFFSET(x, y);
776 return xzone[off] == c || xzone[off] == -1;
780 * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
783 xzone_around_sector(int c, int x, int y, int dist)
786 struct hexagon_iter hexit;
788 assert(xzone_ok(c, x, y));
790 xzone[XYOFFSET(x, y)] = c;
791 for (d = 1; d <= dist; d++) {
792 hexagon_first(&hexit, x, y, d, &x1, &y1);
794 off = XYOFFSET(x1, y1);
795 if (xzone[off] == -1)
797 else if (xzone[off] != c)
799 } while (hexagon_next(&hexit, &x1, &y1));
804 * Add sectors within distance @dist to island @c's exclusive zone.
807 xzone_around_island(int c, int dist)
811 for (i = 0; i < isecs[c]; i++)
812 xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
816 * Initialize exclusive zones around @n islands.
823 for (i = 0; i < WORLD_SZ(); i++)
826 for (c = 0; c < n; c++)
827 xzone_around_island(c, id);
831 * Initialize breadth-first search.
838 for (i = 0; i < WORLD_SZ(); i++) {
840 distance[i] = USHRT_MAX;
843 bfs_queue_head = bfs_queue_tail = 0;
847 * Add sector @x,@y to the BFS queue.
848 * It's closest to @c, with distance @dist.
851 bfs_enqueue(int c, int x, int y, int dist)
853 int off = XYOFFSET(x, y);
855 assert(dist < distance[off]);
857 distance[off] = dist;
858 bfs_queue[bfs_queue_tail] = off;
860 if (bfs_queue_tail >= WORLD_SZ())
862 assert(bfs_queue_tail != bfs_queue_head);
866 * Search breadth-first until the queue is empty.
871 int off, dist, i, noff, nx, ny;
874 while (bfs_queue_head != bfs_queue_tail) {
875 off = bfs_queue[bfs_queue_head];
877 if (bfs_queue_head >= WORLD_SZ())
879 dist = distance[off] + 1;
880 sctoff2xy(&x, &y, off);
881 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
882 nx = new_x(x + diroff[i][0]);
883 ny = new_y(y + diroff[i][1]);
884 noff = XYOFFSET(nx, ny);
885 if (dist < distance[noff]) {
886 bfs_enqueue(closest[off], nx, ny, dist);
887 } else if (distance[noff] == dist) {
888 if (closest[off] != closest[noff])
889 closest[noff] = (natid)-1;
891 assert(distance[noff] < dist);
897 * Add island @c's coastal sectors to the BFS queue, with distance 0.
900 bfs_enqueue_island(int c)
904 for (i = 0; i < isecs[c]; i++) {
906 bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
911 * Compute spheres of influence
912 * A continent's sphere of influence is the set of sectors closer to
913 * it than to any other continent.
914 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
915 * -1 if no single continent is closest.
916 * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
920 init_spheres_of_influence(void)
925 for (c = 0; c < nc; c++)
926 bfs_enqueue_island(c);
931 * Is @x,@y in the same sphere of influence as island @c?
932 * Always true when @c is a continent.
935 is_in_sphere(int c, int x, int y)
937 return c < nc || closest[XYOFFSET(x, y)] == c % nc;
941 * Can island @c grow at @x,@y?
944 can_grow_at(int c, int x, int y)
946 return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
950 adj_land_update(int x, int y)
952 int is_land = own[x][y] != -1;
953 int dir, nx, ny, noff;
955 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
956 nx = new_x(x + diroff[dir][0]);
957 ny = new_y(y + diroff[dir][1]);
958 noff = XYOFFSET(nx, ny);
960 adj_land[noff] |= 1u << DIR_BACK(dir);
962 adj_land[noff] &= ~(1u << DIR_BACK(dir));
967 add_sector(int c, int x, int y)
969 assert(own[x][y] == -1);
970 xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
971 sectx[c][isecs[c]] = x;
972 secty[c][isecs[c]] = y;
975 adj_land_update(x, y);
978 static int grow_weight(int c, int x, int y, int spike)
983 * #Land neighbors is #bits set in adj_land[].
984 * Count them Brian Kernighan's way.
987 for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
989 assert(n > 0 && n < 7);
992 return (6 - n) * (6 - n);
998 grow_one_sector(int c)
1000 int spike = roll0(100) < sp;
1001 int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1003 assert(cur_seen < UINT_MAX);
1008 for (i = 0; i < isecs[c]; i++) {
1011 off = XYOFFSET(x, y);
1013 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1014 if (adj_land[off] & (1u << dir))
1016 nx = new_x(x + diroff[dir][0]);
1017 ny = new_y(y + diroff[dir][1]);
1018 noff = XYOFFSET(nx, ny);
1019 if (seen[noff] == cur_seen)
1021 assert(seen[noff] < cur_seen);
1022 seen[noff] = cur_seen;
1023 if (!can_grow_at(c, nx, ny))
1025 w = grow_weight(c, nx, ny, spike);
1026 assert(wsum < INT_MAX - w);
1028 if (roll0(wsum) < w) {
1038 add_sector(c, newx, newy);
1043 * Grow the continents.
1044 * Return 1 on success, 0 on error.
1047 grow_continents(void)
1054 for (c = 0; c < nc; ++c) {
1056 if (!can_grow_at(c, capx[c], capy[c])
1057 || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1061 add_sector(c, capx[c], capy[c]);
1062 add_sector(c, new_x(capx[c] + 2), capy[c]);
1066 qprint("No room for continents\n");
1070 for (secs = 2; secs < sc && done; secs++) {
1071 for (c = 0; c < nc; ++c) {
1072 if (!grow_one_sector(c))
1077 for (c = 0; c < nc; ++c)
1081 qprint("Only managed to grow %d out of %d sectors.\n",
1086 /****************************************************************************
1088 ****************************************************************************/
1091 * Place additional island @c's first sector.
1092 * Return 1 on success, 0 on error.
1097 int n, x, y, newx, newy;
1101 for (y = 0; y < WORLD_Y; y++) {
1102 for (x = y % 2; x < WORLD_X; x += 2) {
1103 if (can_grow_at(c, x, y)) {
1114 add_sector(c, newx, newy);
1119 int_cmp(const void *a, const void *b)
1121 return *(int *)b - *(int *)a;
1128 int *isiz = malloc(n * sizeof(*isiz));
1133 for (i = 1; i < n; i++) {
1136 isiz[i] = is + r1 - r0;
1140 qsort(isiz, n, sizeof(*isiz), int_cmp);
1145 * Grow the additional islands.
1146 * Return 1 on success, 0 on error.
1151 int *island_size = size_islands();
1152 int xzone_valid = 0;
1154 int i, j, c, done, secs, isiz, x, y;
1156 init_spheres_of_influence();
1158 for (i = 0; i < ni / nc; i++) {
1164 carry += island_size[i];
1165 isiz = MIN(2 * is, carry);
1167 for (j = 0; j < nc; j++) {
1169 if (!place_island(c + j)) {
1170 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1177 for (secs = 1; secs < isiz && done; secs++) {
1178 for (j = 0; j < nc; j++) {
1179 if (!grow_one_sector(c + j))
1186 for (j = 0; j < nc; j++) {
1187 if (isecs[c + j] != secs) {
1189 assert(isecs[c + j] == secs);
1190 x = sectx[c + j][secs];
1191 y = secty[c + j][secs];
1193 adj_land_update(x, y);
1199 for (j = 0; j < nc; j++)
1200 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1209 qprint("Only managed to grow %d out of %d island sectors.\n",
1210 is * ni - carry * nc, is * ni);
1212 for (c = nc; c < nc + ni; c++)
1218 /****************************************************************************
1220 ****************************************************************************/
1222 create_elevations(void)
1226 for (i = 0; i < WORLD_X; i++) {
1227 for (j = 0; j < WORLD_Y; j++)
1228 elev[i][j] = -INFINITE_ELEVATION;
1234 /* Generic function for finding the distance to the closest sea, land, or
1238 distance_to_what(int x, int y, int flag)
1241 struct hexagon_iter hexit;
1243 for (d = 1; d < 5; ++d) {
1244 hexagon_first(&hexit, x, y, d, &px, &py);
1247 case 0: /* distance to sea */
1248 if (own[px][py] == -1)
1251 case 1: /* distance to land */
1252 if (own[px][py] != -1)
1255 case 2: /* distance to mountain */
1256 if (elev[px][py] == INFINITE_ELEVATION)
1260 } while (hexagon_next(&hexit, &px, &py));
1265 #define ELEV elev[sectx[c][i]][secty[c][i]]
1266 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1267 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1269 /* Decide where the mountains go
1274 int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
1277 for (c = 0; c < nc + ni; ++c) {
1280 nm = (pm * ns) / 100;
1282 /* Place the mountains */
1284 for (i = 0; i < ns; ++i) {
1285 dsea[i] = distance_to_sea();
1286 weight[i] = (total += (dsea[i] * dsea[i]));
1289 for (k = nm, mountain_search = 0;
1290 k && mountain_search < MOUNTAIN_SEARCH_MAX;
1291 ++mountain_search) {
1293 for (i = 0; i < ns; ++i)
1294 if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
1296 ((!(capx[c] == sectx[c][i] &&
1297 capy[c] == secty[c][i])) &&
1298 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1299 capy[c] == secty[c][i]))))) {
1300 ELEV = INFINITE_ELEVATION;
1306 /* Elevate land that is not mountain and not capital */
1308 for (i = 0; i < ns; ++i)
1309 dmoun[i] = distance_to_mountain();
1310 dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1311 (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1312 100 * INFINITE_ELEVATION;
1313 for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1316 for (i = 0; i < ns; ++i) {
1317 if (ELEV == -INFINITE_ELEVATION &&
1318 (c >= nc || ((!(capx[c] == sectx[c][i] &&
1319 capy[c] == secty[c][i])) &&
1320 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1321 capy[c] == secty[c][i]))))) {
1322 h = 3 * (5 - dmoun[i]) + dsea[i];
1333 if (newk >= HILLMIN && newk < PLATMIN)
1337 elev[sectx[c][where]][secty[c][where]] = newk;
1340 /* Elevate the mountains and capitals */
1342 for (i = 0; i < ns; ++i) {
1343 if (ELEV == INFINITE_ELEVATION) {
1345 ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1347 ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1348 roll0((256 - HIGHMIN) / 2);
1349 } else if (c < nc &&
1350 (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1351 ((new_x(capx[c] + 2) == sectx[c][i] &&
1352 capy[c] == secty[c][i]))))
1358 #define distance_to_land() distance_to_what(x, y, 1)
1365 for (y = 0; y < WORLD_Y; ++y) {
1366 for (x = y % 2; x < WORLD_X; x += 2) {
1367 if (elev[x][y] == -INFINITE_ELEVATION)
1368 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1374 elev_to_sct_type(int elevation)
1376 if (elevation < LANDMIN)
1378 if (elevation < HILLMIN)
1380 if (elevation < PLATMIN)
1382 if (elevation < HIGHMIN)
1387 /****************************************************************************
1389 ****************************************************************************/
1396 fert = LANDMIN - e + 40;
1397 else if (e < FERT_MAX)
1398 fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1409 oil = (LANDMIN - e) * 2 + roll0(2);
1410 else if (e <= OIL_MAX)
1411 oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1421 if (e >= IRON_MIN && e < HIGHMIN)
1422 iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1432 if (e >= GOLD_MIN) {
1434 gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1436 gold = 100 - 20 * HIGHMIN / e;
1447 if (e >= URAN_MIN && e < HIGHMIN)
1448 uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1455 add_resources(struct sctstr *sct)
1457 sct->sct_fertil = set_fert(sct->sct_elev);
1458 sct->sct_oil = set_oil(sct->sct_elev);
1459 sct->sct_min = set_iron(sct->sct_elev);
1460 sct->sct_gmin = set_gold(sct->sct_elev);
1461 sct->sct_uran = set_uran(sct->sct_elev);
1464 /****************************************************************************
1465 DESIGNATE THE SECTORS
1466 ****************************************************************************/
1474 for (y = 0; y < WORLD_Y; y++) {
1475 for (x = y % 2; x < WORLD_X; x += 2) {
1476 sct = getsectp(x, y);
1477 sct->sct_elev = elev[x][y];
1478 sct->sct_type = elev_to_sct_type(elev[x][y]);
1479 sct->sct_newtype = sct->sct_type;
1480 sct->sct_dterr = own[sct->sct_x][y] + 1;
1484 set_coastal_flags();
1487 /****************************************************************************
1488 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1489 ****************************************************************************/
1493 int sx, sy, x, y, c, type;
1496 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1501 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1504 type = elev_to_sct_type(elev[x][y]);
1505 if (type == SCT_WATER)
1507 else if (type == SCT_MOUNT)
1512 assert(0 <= c && c < nc);
1513 if ((x == capx[c] || x == new_x(capx[c] + 2))
1515 printf("%c ", numletter[c % 62]);
1525 * Print a map to help visualize own[][].
1526 * This is for debugging.
1533 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1536 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1540 else if (own[x][y] == -1)
1543 putchar(numletter[own[x][y] % 62]);
1550 * Print a map to help visualize elev[][].
1551 * This is for debugging. It expects the terminal to understand
1552 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1555 print_elev_map(void)
1557 int sx, sy, x, y, sat;
1559 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1562 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1566 else if (!elev[x][y])
1568 else if (elev[x][y] < 0) {
1569 sat = 256 + elev[x][y] * 2;
1570 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1571 } else if (elev[x][y] < HIGHMIN / 2) {
1572 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1573 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1574 } else if (elev[x][y] < HIGHMIN) {
1575 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1576 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1578 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1579 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1587 * Print a map to help visualize xzone[].
1588 * This is for debugging.
1591 print_xzone_map(void)
1593 int sx, sy, x, y, off;
1595 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1598 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1600 off = XYOFFSET(x, y);
1603 else if (own[x][y] >= 0)
1605 else if (xzone[off] >= 0)
1606 putchar(numletter[xzone[off] % 62]);
1608 assert(own[x][y] == -1);
1609 putchar(xzone[off] == -1 ? '.' : '!');
1617 * Print a map to help visualize closest[].
1618 * This is for debugging.
1621 print_closest_map(void)
1623 int sx, sy, x, y, off;
1625 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1628 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1630 off = XYOFFSET(x, y);
1633 else if (closest[off] == (natid)-1)
1635 else if (!distance[off]) {
1636 assert(closest[off] == own[x][y]);
1639 putchar(numletter[closest[off] % 62]);
1647 print_distance_map(void)
1649 int sx, sy, x, y, off;
1651 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1654 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1656 off = XYOFFSET(x, y);
1659 else if (closest[off] == (natid)-1)
1661 else if (!distance[off]) {
1662 assert(closest[off] == own[x][y]);
1665 putchar(numletter[distance[off] % 62]);
1673 /***************************************************************************
1674 WRITE A SCRIPT FOR PLACING CAPITALS
1675 ****************************************************************************/
1677 write_newcap_script(void)
1680 FILE *script = fopen(outfile, "w");
1683 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1684 program_name, outfile, strerror(errno));
1688 for (c = 0; c < nc; ++c) {
1689 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1690 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1692 fprintf(script, "add %d visitor visitor v\n", c + 1);
1698 qprint(const char *const fmt, ...)
1704 vfprintf(stdout, fmt, ap);
1710 set_coastal_flags(void)
1715 for (i = 0; i < nc + ni; ++i) {
1716 for (j = 0; j < isecs[i]; j++) {
1717 sp = getsectp(sectx[i][j], secty[i][j]);
1718 sp->sct_coastal = sectc[i][j];