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);
979 grow_weight(int c, int x, int y, int spike)
984 * #Land neighbors is #bits set in adj_land[].
985 * Count them Brian Kernighan's way.
988 for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
990 assert(n > 0 && n < 7);
993 return (6 - n) * (6 - n);
999 grow_one_sector(int c)
1001 int spike = roll0(100) < sp;
1002 int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1004 assert(cur_seen < UINT_MAX);
1009 for (i = 0; i < isecs[c]; i++) {
1012 off = XYOFFSET(x, y);
1014 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1015 if (adj_land[off] & (1u << dir))
1017 nx = new_x(x + diroff[dir][0]);
1018 ny = new_y(y + diroff[dir][1]);
1019 noff = XYOFFSET(nx, ny);
1020 if (seen[noff] == cur_seen)
1022 assert(seen[noff] < cur_seen);
1023 seen[noff] = cur_seen;
1024 if (!can_grow_at(c, nx, ny))
1026 w = grow_weight(c, nx, ny, spike);
1027 assert(wsum < INT_MAX - w);
1029 if (roll0(wsum) < w) {
1039 add_sector(c, newx, newy);
1044 * Grow the continents.
1045 * Return 1 on success, 0 on error.
1048 grow_continents(void)
1055 for (c = 0; c < nc; ++c) {
1057 if (!can_grow_at(c, capx[c], capy[c])
1058 || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1062 add_sector(c, capx[c], capy[c]);
1063 add_sector(c, new_x(capx[c] + 2), capy[c]);
1067 qprint("No room for continents\n");
1071 for (secs = 2; secs < sc && done; secs++) {
1072 for (c = 0; c < nc; ++c) {
1073 if (!grow_one_sector(c))
1078 for (c = 0; c < nc; ++c)
1082 qprint("Only managed to grow %d out of %d sectors.\n",
1087 /****************************************************************************
1089 ****************************************************************************/
1092 * Place additional island @c's first sector.
1093 * Return 1 on success, 0 on error.
1098 int n, x, y, newx, newy;
1102 for (y = 0; y < WORLD_Y; y++) {
1103 for (x = y % 2; x < WORLD_X; x += 2) {
1104 if (can_grow_at(c, x, y)) {
1115 add_sector(c, newx, newy);
1120 int_cmp(const void *a, const void *b)
1122 return *(int *)b - *(int *)a;
1129 int *isiz = malloc(n * sizeof(*isiz));
1134 for (i = 1; i < n; i++) {
1137 isiz[i] = is + r1 - r0;
1141 qsort(isiz, n, sizeof(*isiz), int_cmp);
1146 * Grow the additional islands.
1147 * Return 1 on success, 0 on error.
1152 int *island_size = size_islands();
1153 int xzone_valid = 0;
1155 int i, j, c, done, secs, isiz, x, y;
1157 init_spheres_of_influence();
1159 for (i = 0; i < ni / nc; i++) {
1165 carry += island_size[i];
1166 isiz = MIN(2 * is, carry);
1168 for (j = 0; j < nc; j++) {
1170 if (!place_island(c + j)) {
1171 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1178 for (secs = 1; secs < isiz && done; secs++) {
1179 for (j = 0; j < nc; j++) {
1180 if (!grow_one_sector(c + j))
1187 for (j = 0; j < nc; j++) {
1188 if (isecs[c + j] != secs) {
1190 assert(isecs[c + j] == secs);
1191 x = sectx[c + j][secs];
1192 y = secty[c + j][secs];
1194 adj_land_update(x, y);
1200 for (j = 0; j < nc; j++)
1201 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1210 qprint("Only managed to grow %d out of %d island sectors.\n",
1211 is * ni - carry * nc, is * ni);
1213 for (c = nc; c < nc + ni; c++)
1219 /****************************************************************************
1221 ****************************************************************************/
1223 create_elevations(void)
1227 for (i = 0; i < WORLD_X; i++) {
1228 for (j = 0; j < WORLD_Y; j++)
1229 elev[i][j] = -INFINITE_ELEVATION;
1235 /* Generic function for finding the distance to the closest sea, land, or
1239 distance_to_what(int x, int y, int flag)
1242 struct hexagon_iter hexit;
1244 for (d = 1; d < 5; ++d) {
1245 hexagon_first(&hexit, x, y, d, &px, &py);
1248 case 0: /* distance to sea */
1249 if (own[px][py] == -1)
1252 case 1: /* distance to land */
1253 if (own[px][py] != -1)
1256 case 2: /* distance to mountain */
1257 if (elev[px][py] == INFINITE_ELEVATION)
1261 } while (hexagon_next(&hexit, &px, &py));
1266 #define ELEV elev[sectx[c][i]][secty[c][i]]
1267 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1268 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1270 /* Decide where the mountains go
1275 int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
1278 for (c = 0; c < nc + ni; ++c) {
1281 nm = (pm * ns) / 100;
1283 /* Place the mountains */
1285 for (i = 0; i < ns; ++i) {
1286 dsea[i] = distance_to_sea();
1287 weight[i] = (total += (dsea[i] * dsea[i]));
1290 for (k = nm, mountain_search = 0;
1291 k && mountain_search < MOUNTAIN_SEARCH_MAX;
1292 ++mountain_search) {
1294 for (i = 0; i < ns; ++i)
1295 if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
1297 ((!(capx[c] == sectx[c][i] &&
1298 capy[c] == secty[c][i])) &&
1299 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1300 capy[c] == secty[c][i]))))) {
1301 ELEV = INFINITE_ELEVATION;
1307 /* Elevate land that is not mountain and not capital */
1309 for (i = 0; i < ns; ++i)
1310 dmoun[i] = distance_to_mountain();
1311 dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1312 (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1313 100 * INFINITE_ELEVATION;
1314 for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1317 for (i = 0; i < ns; ++i) {
1318 if (ELEV == -INFINITE_ELEVATION &&
1319 (c >= nc || ((!(capx[c] == sectx[c][i] &&
1320 capy[c] == secty[c][i])) &&
1321 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1322 capy[c] == secty[c][i]))))) {
1323 h = 3 * (5 - dmoun[i]) + dsea[i];
1334 if (newk >= HILLMIN && newk < PLATMIN)
1338 elev[sectx[c][where]][secty[c][where]] = newk;
1341 /* Elevate the mountains and capitals */
1343 for (i = 0; i < ns; ++i) {
1344 if (ELEV == INFINITE_ELEVATION) {
1346 ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1348 ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1349 roll0((256 - HIGHMIN) / 2);
1350 } else if (c < nc &&
1351 (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1352 ((new_x(capx[c] + 2) == sectx[c][i] &&
1353 capy[c] == secty[c][i]))))
1359 #define distance_to_land() distance_to_what(x, y, 1)
1366 for (y = 0; y < WORLD_Y; ++y) {
1367 for (x = y % 2; x < WORLD_X; x += 2) {
1368 if (elev[x][y] == -INFINITE_ELEVATION)
1369 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1375 elev_to_sct_type(int elevation)
1377 if (elevation < LANDMIN)
1379 if (elevation < HILLMIN)
1381 if (elevation < PLATMIN)
1383 if (elevation < HIGHMIN)
1388 /****************************************************************************
1390 ****************************************************************************/
1397 fert = LANDMIN - e + 40;
1398 else if (e < FERT_MAX)
1399 fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1410 oil = (LANDMIN - e) * 2 + roll0(2);
1411 else if (e <= OIL_MAX)
1412 oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1422 if (e >= IRON_MIN && e < HIGHMIN)
1423 iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1433 if (e >= GOLD_MIN) {
1435 gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1437 gold = 100 - 20 * HIGHMIN / e;
1448 if (e >= URAN_MIN && e < HIGHMIN)
1449 uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1456 add_resources(struct sctstr *sct)
1458 sct->sct_fertil = set_fert(sct->sct_elev);
1459 sct->sct_oil = set_oil(sct->sct_elev);
1460 sct->sct_min = set_iron(sct->sct_elev);
1461 sct->sct_gmin = set_gold(sct->sct_elev);
1462 sct->sct_uran = set_uran(sct->sct_elev);
1465 /****************************************************************************
1466 DESIGNATE THE SECTORS
1467 ****************************************************************************/
1475 for (y = 0; y < WORLD_Y; y++) {
1476 for (x = y % 2; x < WORLD_X; x += 2) {
1477 sct = getsectp(x, y);
1478 sct->sct_elev = elev[x][y];
1479 sct->sct_type = elev_to_sct_type(elev[x][y]);
1480 sct->sct_newtype = sct->sct_type;
1481 sct->sct_dterr = own[sct->sct_x][y] + 1;
1485 set_coastal_flags();
1488 /****************************************************************************
1489 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1490 ****************************************************************************/
1494 int sx, sy, x, y, c, type;
1497 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1502 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1505 type = elev_to_sct_type(elev[x][y]);
1506 if (type == SCT_WATER)
1508 else if (type == SCT_MOUNT)
1513 assert(0 <= c && c < nc);
1514 if ((x == capx[c] || x == new_x(capx[c] + 2))
1516 printf("%c ", numletter[c % 62]);
1526 * Print a map to help visualize own[][].
1527 * This is for debugging.
1534 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1537 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1541 else if (own[x][y] == -1)
1544 putchar(numletter[own[x][y] % 62]);
1551 * Print a map to help visualize elev[][].
1552 * This is for debugging. It expects the terminal to understand
1553 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1556 print_elev_map(void)
1558 int sx, sy, x, y, sat;
1560 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1563 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1567 else if (!elev[x][y])
1569 else if (elev[x][y] < 0) {
1570 sat = 256 + elev[x][y] * 2;
1571 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1572 } else if (elev[x][y] < HIGHMIN / 2) {
1573 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1574 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1575 } else if (elev[x][y] < HIGHMIN) {
1576 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1577 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1579 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1580 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1588 * Print a map to help visualize xzone[].
1589 * This is for debugging.
1592 print_xzone_map(void)
1594 int sx, sy, x, y, off;
1596 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1599 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1601 off = XYOFFSET(x, y);
1604 else if (own[x][y] >= 0)
1606 else if (xzone[off] >= 0)
1607 putchar(numletter[xzone[off] % 62]);
1609 assert(own[x][y] == -1);
1610 putchar(xzone[off] == -1 ? '.' : '!');
1618 * Print a map to help visualize closest[].
1619 * This is for debugging.
1622 print_closest_map(void)
1624 int sx, sy, x, y, off;
1626 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1629 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1631 off = XYOFFSET(x, y);
1634 else if (closest[off] == (natid)-1)
1636 else if (!distance[off]) {
1637 assert(closest[off] == own[x][y]);
1640 putchar(numletter[closest[off] % 62]);
1648 print_distance_map(void)
1650 int sx, sy, x, y, off;
1652 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1655 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1657 off = XYOFFSET(x, y);
1660 else if (closest[off] == (natid)-1)
1662 else if (!distance[off]) {
1663 assert(closest[off] == own[x][y]);
1666 putchar(numletter[distance[off] % 62]);
1674 /***************************************************************************
1675 WRITE A SCRIPT FOR PLACING CAPITALS
1676 ****************************************************************************/
1678 write_newcap_script(void)
1681 FILE *script = fopen(outfile, "w");
1684 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1685 program_name, outfile, strerror(errno));
1689 for (c = 0; c < nc; ++c) {
1690 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1691 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1693 fprintf(script, "add %d visitor visitor v\n", c + 1);
1699 qprint(const char *const fmt, ...)
1705 vfprintf(stdout, fmt, ap);
1711 set_coastal_flags(void)
1716 for (i = 0; i < nc + ni; ++i) {
1717 for (j = 0; j < isecs[i]; j++) {
1718 sp = getsectp(sectx[i][j], secty[i][j]);
1719 sp->sct_coastal = sectc[i][j];