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, using
76 * weighted random sampling with weights favoring sectors away from
77 * land and other spheres. Add one sector to each island in turn,
78 * until they have the intended size. Repeat until the specified
79 * number of islands has been grown.
81 * If placement fails due to lack of room, start over, just like for
84 * Growing works as for continents, except the minimum distance for
85 * additional islands applies, and growing simply stops when any of
86 * the islands being grown lacks the room to grow further. The number
87 * of sectors not grown carries over to the next island size.
89 * 4. Compute elevation
91 * Elevate islands one after the other.
93 * First, place the specified number of mountains randomly.
94 * Probability increases with distance to sea.
96 * Last, elevate mountains and the capitals. Set mountain elevations
97 * starting at a "high" elevation, then increasing linearly. Set
98 * capital elevation to a fixed value.
100 * In between, elevate the remaining land one by one, working from
101 * mountains towards the sea, and from the elevation just below "high"
102 * elevation linearly down to 1.
104 * This gives islands of the same size the same set of elevations.
106 * Elevate sea: pick a random depth from an interval that deepens with
107 * the distance to land.
111 * Sector resources are simple functions of elevation. You can alter
112 * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
127 #include "prototypes.h"
132 /* The following five numbers refer to elevation under which (in the case of
133 fertility or oil) or over which (in the case of iron, gold, and uranium)
134 sectors with that elevation will contain that resource. Elevation ranges
137 /* raise FERT_MAX for more fertility */
140 /* raise OIL_MAX for more oil */
143 /* lower IRON_MIN for more iron */
146 /* lower GOLD_MIN for more gold */
149 /* lower URAN_MIN for more uranium */
152 /* do not change these defines */
153 #define LANDMIN 1 /* plate altitude for normal land */
154 #define PLATMIN 36 /* plate altitude for plateau */
155 #define HIGHMIN 98 /* plate altitude for mountains */
157 static void qprint(const char * const fmt, ...)
158 ATTRIBUTE((format (printf, 1, 2)));
161 * Program arguments and options
163 static char *program_name;
164 static int nc, sc; /* number and size of continents */
165 static int ni, is; /* number and size of islands */
166 #define DEFAULT_SPIKE 10
167 static int sp = DEFAULT_SPIKE; /* spike percentage */
168 #define DEFAULT_MOUNTAIN 0
169 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
170 #define DEFAULT_CONTDIST 2
171 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
172 #define DEFAULT_ISLDIST 1
173 static int id = DEFAULT_ISLDIST; /* ... continents and islands */
174 /* don't let the islands crash into each other.
175 1 = don't merge, 0 = merge. */
176 static int DISTINCT_ISLANDS = 1;
178 #define DEFAULT_OUTFILE_NAME "newcap_script"
179 static const char *outfile = DEFAULT_OUTFILE_NAME;
181 #define STABLE_CYCLE 4 /* stability required for perterbed capitals */
182 #define INFINITE_ELEVATION 999
184 /* these defines prevent infinite loops:
186 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
187 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
188 #define MOUNTAIN_SEARCH_MAX 1000 /* how long do we try to place mountains */
193 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
194 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
198 * isecs[i] is the size of the i-th island.
202 static int *capx, *capy; /* location of the nc capitals */
204 static int **own; /* owner of the sector. -1 means water */
207 * Adjacent land sectors
208 * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
209 * to x, y in direction d is land.
211 static unsigned char *adj_land;
215 * Each island is surrounded by an exclusive zone where only it may
216 * grow. The width of the zone depends on minimum distances.
217 * While growing continents, it is @di sectors wide.
218 * While growing additional islands, it is @id sectors wide.
219 * DISTINCT_ISLANDS nullifies the exclusive zone then.
220 * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
221 * zone, a (non-negative) island number when it is in that island's
222 * exclusive zone and no other, and -2 when it is in multiple
228 * Set of sectors seen already
229 * Increment @cur_seen to empty the set of sectors seen, set
230 * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
232 static unsigned *seen;
233 static unsigned cur_seen;
236 * Closest continent and "distance"
237 * closest[XYOFFSET(x, y)] is the closest continent's number.
238 * distance[] is complicated; see init_spheres_of_influence() and
239 * init_distance_to_coast().
241 static natid *closest;
242 static unsigned short *distance;
245 * Queue for breadth-first search
247 static int *bfs_queue;
248 static int bfs_queue_head, bfs_queue_tail;
250 static int **elev; /* elevation of the sectors */
251 static int **sectx, **secty; /* the sectors for each continent */
252 static int *weight; /* used for placing mountains */
253 static int *dsea, *dmoun; /* the dist to the ocean and mountain */
255 #define NUMTRIES 10 /* keep trying to grow this many times */
257 static const char *numletter =
258 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
260 static void help(char *);
261 static void usage(void);
262 static void parse_args(int argc, char *argv[]);
263 static void allocate_memory(void);
264 static void init(void);
265 static int drift(void);
266 static int grow_continents(void);
267 static void create_elevations(void);
268 static void write_sects(void);
269 static void output(void);
270 static int write_newcap_script(void);
271 static int stable(int);
272 static void elevate_land(void);
273 static void elevate_sea(void);
275 static void print_vars(void);
276 static void fl_move(int);
277 static int grow_islands(void);
279 /* Debugging aids: */
280 void print_own_map(void);
281 void print_xzone_map(void);
282 void print_closest_map(void);
283 void print_distance_map(void);
284 void print_elev_map(void);
286 /****************************************************************************
288 ****************************************************************************/
291 main(int argc, char *argv[])
294 char *config_file = NULL;
296 unsigned rnd_seed = 0;
299 program_name = argv[0];
301 while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
304 config_file = optarg;
307 DISTINCT_ISLANDS = 0;
313 rnd_seed = strtoul(optarg, NULL, 10);
323 printf("%s\n\n%s", version, legal);
332 rnd_seed = pick_seed();
335 if (emp_config(config_file) < 0)
339 parse_args(argc - optind, argv + optind);
344 qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
345 qprint("seed is %u\n", rnd_seed);
350 qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
351 qprint("placing capitals...\n");
353 qprint("unstable drift\n");
354 qprint("growing continents...\n");
355 done = grow_continents();
358 qprint("growing islands:");
359 done = grow_islands();
360 } while (!done && ++try < NUMTRIES);
362 fprintf(stderr, "%s: world not large enough for this much land\n",
366 qprint("elevating land...\n");
369 qprint("writing to sectors file...\n");
370 if (!write_newcap_script())
372 if (chdir(gamedir)) {
373 fprintf(stderr, "%s: can't chdir to %s (%s)\n",
374 program_name, gamedir, strerror(errno));
377 if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
380 if (!ef_close(EF_SECTOR))
384 qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
394 puts("Creating a planet with:\n");
395 printf("%d continents\n", nc);
396 printf("continent size: %d\n", sc);
397 printf("number of islands: %d\n", ni);
398 printf("average size of islands: %d\n", is);
399 printf("spike: %d%%\n", sp);
400 printf("%d%% of land is mountain (each continent will have %d mountains)\n",
401 pm, (pm * sc) / 100);
402 printf("minimum distance between continents: %d\n", di);
403 printf("minimum distance from islands to continents: %d\n", id);
404 printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
408 help(char *complaint)
411 fprintf(stderr, "%s: %s\n", program_name, complaint);
412 fprintf(stderr, "Try -h for help.\n");
418 printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
419 " -e CONFIG-FILE configuration file\n"
421 " -i islands may merge\n"
423 " -R SEED seed for random number generator\n"
424 " -s SCRIPT name of script to create (default %s)\n"
425 " -h display this help and exit\n"
426 " -v display version information and exit\n"
427 " NC number of continents\n"
428 " SC continent size\n"
429 " NI number of islands (default NC)\n"
430 " IS average island size (default SC/2)\n"
431 " SP spike percentage: 0 = round, 100 = snake (default %d)\n"
432 " PM percentage of land that is mountain (default %d)\n"
433 " DI minimum distance between continents (default %d)\n"
434 " ID minimum distance from islands to continents (default %d)\n",
435 program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
436 DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
440 parse_args(int argc, char *argv[])
442 int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
445 help("missing arguments");
449 help("too many arguments");
454 fprintf(stderr, "%s: number of continents must be > 0\n",
461 fprintf(stderr, "%s: size of continents must be > 1\n",
472 fprintf(stderr, "%s: number of islands must be >= 0\n",
477 fprintf(stderr, "%s: number of islands must be a multiple of"
478 " the number of continents\n",
486 fprintf(stderr, "%s: size of islands must be > 0\n",
493 if (sp < 0 || sp > 100) {
495 "%s: spike percentage must be between 0 and 100\n",
502 if (pm < 0 || pm > 100) {
504 "%s: mountain percentage must be between 0 and 100\n",
512 fprintf(stderr, "%s: distance between continents must be >= 0\n",
517 fprintf(stderr, "%s: distance between continents too large\n",
526 "%s: distance from islands to continents must be >= 0\n",
532 "%s: distance from islands to continents too large\n",
538 /****************************************************************************
539 VARIABLE INITIALIZATION
540 ****************************************************************************/
543 allocate_memory(void)
547 capx = calloc(nc, sizeof(int));
548 capy = calloc(nc, sizeof(int));
549 own = calloc(WORLD_X, sizeof(int *));
550 adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
551 xzone = malloc(WORLD_SZ() * sizeof(*xzone));
552 seen = calloc(WORLD_SZ(), sizeof(*seen));
553 closest = malloc(WORLD_SZ() * sizeof(*closest));
554 distance = malloc(WORLD_SZ() * sizeof(*distance));
555 bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
556 elev = calloc(WORLD_X, sizeof(int *));
557 for (i = 0; i < WORLD_X; ++i) {
558 own[i] = calloc(WORLD_Y, sizeof(int));
559 elev[i] = calloc(WORLD_Y, sizeof(int));
561 sectx = calloc(nc + ni, sizeof(int *));
562 secty = calloc(nc + ni, sizeof(int *));
563 isecs = calloc(nc + ni, sizeof(int));
564 weight = calloc(MAX(sc, is * 2), sizeof(int));
565 dsea = calloc(MAX(sc, is * 2), sizeof(int));
566 dmoun = calloc(MAX(sc, is * 2), sizeof(int));
567 for (i = 0; i < nc; ++i) {
568 sectx[i] = calloc(sc, sizeof(int));
569 secty[i] = calloc(sc, sizeof(int));
571 for (i = nc; i < nc + ni; ++i) {
572 sectx[i] = calloc(is * 2, sizeof(int));
573 secty[i] = calloc(is * 2, sizeof(int));
583 for (i = 0; i < WORLD_X; ++i) {
584 for (j = 0; j < WORLD_Y; ++j) {
588 memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
591 /****************************************************************************
592 DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
593 ****************************************************************************/
596 * How isolated is capital @j at @newx,@newy?
597 * Return the distance to the closest other capital.
600 iso(int j, int newx, int newy)
605 for (i = 0; i < nc; ++i) {
608 md = mapdist(capx[i], capy[i], newx, newy);
618 * Return 1 for a stable drift, 0 for an unstable one.
625 for (i = 0; i < nc; i++) {
626 capy[i] = (2 * i) / WORLD_X;
627 capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
628 if (capy[i] >= WORLD_Y) {
630 "%s: world not big enough for all the continents\n",
636 for (turns = 0; turns < DRIFT_MAX; ++turns) {
639 for (i = 0; i < nc; ++i)
646 * Has the drift stabilized?
647 * @turns is the number of turns so far.
652 static int mc[STABLE_CYCLE];
653 int i, isod, d = 0, stab = 1;
656 for (i = 0; i < STABLE_CYCLE; i++)
660 if (turns <= DRIFT_BEFORE_CHECK)
663 for (i = 0; i < nc; ++i) {
664 isod = iso(i, capx[i], capy[i]);
669 for (i = 0; i < STABLE_CYCLE; ++i)
673 mc[turns % STABLE_CYCLE] = d;
677 /* This routine does the actual drifting
683 int dir, i, newx, newy;
685 dir = DIR_L + roll0(6);
686 for (i = 0; i < 6; i++) {
689 newx = new_x(capx[j] + diroff[dir][0]);
690 newy = new_y(capy[j] + diroff[dir][1]);
692 if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
700 /****************************************************************************
702 ****************************************************************************/
705 is_coastal(int x, int y)
707 return adj_land[XYOFFSET(x, y)]
708 != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
711 struct hexagon_iter {
716 * Start iterating around @x0,@y0 at distance @d.
717 * Set *x,*y to coordinates of the first sector.
720 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
723 *x = new_x(x0 - 2 * n);
725 iter->dir = DIR_FIRST;
731 * Continue iteration started with hexagon_first().
732 * Set *x,*y to coordinates of the next sector.
733 * Return whether we're back at the first sector, i.e. iteration is
737 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
739 *x = new_x(*x + diroff[iter->dir][0]);
740 *y = new_y(*y + diroff[iter->dir][1]);
742 if (iter->i == iter->n) {
746 return iter->dir <= DIR_LAST;
750 * Is @x,@y in no exclusive zone other than perhaps @c's?
753 xzone_ok(int c, int x, int y)
755 int off = XYOFFSET(x, y);
757 return xzone[off] == c || xzone[off] == -1;
761 * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
764 xzone_around_sector(int c, int x, int y, int dist)
767 struct hexagon_iter hexit;
769 assert(xzone_ok(c, x, y));
771 xzone[XYOFFSET(x, y)] = c;
772 for (d = 1; d <= dist; d++) {
773 hexagon_first(&hexit, x, y, d, &x1, &y1);
775 off = XYOFFSET(x1, y1);
776 if (xzone[off] == -1)
778 else if (xzone[off] != c)
780 } while (hexagon_next(&hexit, &x1, &y1));
785 * Add sectors within distance @dist to island @c's exclusive zone.
788 xzone_around_island(int c, int dist)
792 for (i = 0; i < isecs[c]; i++)
793 xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
797 * Initialize exclusive zones around @n islands.
804 for (i = 0; i < WORLD_SZ(); i++)
807 for (c = 0; c < n; c++)
808 xzone_around_island(c, id);
812 * Initialize breadth-first search.
819 for (i = 0; i < WORLD_SZ(); i++) {
821 distance[i] = USHRT_MAX;
824 bfs_queue_head = bfs_queue_tail = 0;
828 * Add sector @x,@y to the BFS queue.
829 * It's closest to @c, with distance @dist.
832 bfs_enqueue(int c, int x, int y, int dist)
834 int off = XYOFFSET(x, y);
836 assert(dist < distance[off]);
838 distance[off] = dist;
839 bfs_queue[bfs_queue_tail] = off;
841 if (bfs_queue_tail >= WORLD_SZ())
843 assert(bfs_queue_tail != bfs_queue_head);
847 * Search breadth-first until the queue is empty.
852 int off, dist, i, noff, nx, ny;
855 while (bfs_queue_head != bfs_queue_tail) {
856 off = bfs_queue[bfs_queue_head];
858 if (bfs_queue_head >= WORLD_SZ())
860 dist = distance[off] + 1;
861 sctoff2xy(&x, &y, off);
862 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
863 nx = new_x(x + diroff[i][0]);
864 ny = new_y(y + diroff[i][1]);
865 noff = XYOFFSET(nx, ny);
866 if (dist < distance[noff]) {
867 bfs_enqueue(closest[off], nx, ny, dist);
868 } else if (distance[noff] == dist) {
869 if (closest[off] != closest[noff])
870 closest[noff] = (natid)-1;
872 assert(distance[noff] < dist);
878 * Add island @c's coastal sectors to the BFS queue, with distance 0.
881 bfs_enqueue_island(int c)
885 for (i = 0; i < isecs[c]; i++) {
886 if (is_coastal(sectx[c][i], secty[c][i]))
887 bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
892 * Enqueue spheres of influence borders for breadth-first search.
895 bfs_enqueue_border(void)
897 int x, y, off, dir, nx, ny, noff;
899 for (y = 0; y < WORLD_Y; y++) {
900 for (x = y % 2; x < WORLD_X; x += 2) {
901 off = XYOFFSET(x, y);
902 if (distance[off] <= id + 1)
904 if (closest[off] == (natid)-1)
906 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
907 nx = new_x(x + diroff[dir][0]);
908 ny = new_y(y + diroff[dir][1]);
909 noff = XYOFFSET(nx, ny);
910 if (closest[noff] != closest[off]) {
911 bfs_enqueue(closest[off], x, y, id + 1);
920 * Compute spheres of influence
921 * A continent's sphere of influence is the set of sectors closer to
922 * it than to any other continent.
923 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
924 * -1 if no single continent is closest.
925 * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
926 * closest coastal land sector and the distance to just outside the
927 * sphere of influence plus @id. For sea sectors within a continent's
928 * sphere of influence, distance[off] - id is the distance to the
929 * border of the area where additional islands can be placed.
932 init_spheres_of_influence(void)
937 for (c = 0; c < nc; c++)
938 bfs_enqueue_island(c);
940 bfs_enqueue_border();
945 * Precompute distance to coast
946 * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
948 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
949 * -1 if no single continent is closest.
952 init_distance_to_coast(void)
957 for (c = 0; c < nc + ni; c++)
958 bfs_enqueue_island(c);
963 * Is @x,@y in the same sphere of influence as island @c?
964 * Always true when @c is a continent.
967 is_in_sphere(int c, int x, int y)
969 return c < nc || closest[XYOFFSET(x, y)] == c % nc;
973 * Can island @c grow at @x,@y?
976 can_grow_at(int c, int x, int y)
978 return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
982 adj_land_update(int x, int y)
984 int is_land = own[x][y] != -1;
985 int dir, nx, ny, noff;
987 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
988 nx = new_x(x + diroff[dir][0]);
989 ny = new_y(y + diroff[dir][1]);
990 noff = XYOFFSET(nx, ny);
992 adj_land[noff] |= 1u << DIR_BACK(dir);
994 adj_land[noff] &= ~(1u << DIR_BACK(dir));
999 add_sector(int c, int x, int y)
1001 assert(own[x][y] == -1);
1002 xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1003 sectx[c][isecs[c]] = x;
1004 secty[c][isecs[c]] = y;
1007 adj_land_update(x, y);
1011 grow_weight(int c, int x, int y, int spike)
1016 * #Land neighbors is #bits set in adj_land[].
1017 * Count them Brian Kernighan's way.
1020 for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1022 assert(n > 0 && n < 7);
1025 return (6 - n) * (6 - n);
1031 grow_one_sector(int c)
1033 int spike = roll0(100) < sp;
1034 int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1036 assert(cur_seen < UINT_MAX);
1041 for (i = 0; i < isecs[c]; i++) {
1044 off = XYOFFSET(x, y);
1046 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1047 if (adj_land[off] & (1u << dir))
1049 nx = new_x(x + diroff[dir][0]);
1050 ny = new_y(y + diroff[dir][1]);
1051 noff = XYOFFSET(nx, ny);
1052 if (seen[noff] == cur_seen)
1054 assert(seen[noff] < cur_seen);
1055 seen[noff] = cur_seen;
1056 if (!can_grow_at(c, nx, ny))
1058 w = grow_weight(c, nx, ny, spike);
1059 assert(wsum < INT_MAX - w);
1061 if (roll0(wsum) < w) {
1071 add_sector(c, newx, newy);
1076 * Grow the continents.
1077 * Return 1 on success, 0 on error.
1080 grow_continents(void)
1087 for (c = 0; c < nc; ++c) {
1089 if (!can_grow_at(c, capx[c], capy[c])
1090 || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1094 add_sector(c, capx[c], capy[c]);
1095 add_sector(c, new_x(capx[c] + 2), capy[c]);
1099 qprint("No room for continents\n");
1103 for (secs = 2; secs < sc && done; secs++) {
1104 for (c = 0; c < nc; ++c) {
1105 if (!grow_one_sector(c))
1111 qprint("Only managed to grow %d out of %d sectors.\n",
1116 /****************************************************************************
1118 ****************************************************************************/
1121 * Place additional island @c's first sector.
1122 * Return 1 on success, 0 on error.
1125 place_island(int c, int isiz)
1127 int n, x, y, d, w, newx, newy;
1131 for (y = 0; y < WORLD_Y; y++) {
1132 for (x = y % 2; x < WORLD_X; x += 2) {
1133 if (can_grow_at(c, x, y)) {
1134 d = distance[XYOFFSET(x, y)];
1136 w = (d - id) * (d - id);
1137 n += MIN(w, (isiz + 2) / 3);
1147 add_sector(c, newx, newy);
1152 int_cmp(const void *a, const void *b)
1154 return *(int *)b - *(int *)a;
1161 int *isiz = malloc(n * sizeof(*isiz));
1166 for (i = 1; i < n; i++) {
1169 isiz[i] = is + r1 - r0;
1173 qsort(isiz, n, sizeof(*isiz), int_cmp);
1178 * Grow the additional islands.
1179 * Return 1 on success, 0 on error.
1184 int *island_size = size_islands();
1185 int xzone_valid = 0;
1187 int i, j, c, done, secs, isiz, x, y;
1189 init_spheres_of_influence();
1191 for (i = 0; i < ni / nc; i++) {
1197 carry += island_size[i];
1198 isiz = MIN(2 * is, carry);
1200 for (j = 0; j < nc; j++) {
1202 if (!place_island(c + j, isiz)) {
1203 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1210 for (secs = 1; secs < isiz && done; secs++) {
1211 for (j = 0; j < nc; j++) {
1212 if (!grow_one_sector(c + j))
1219 for (j = 0; j < nc; j++) {
1220 if (isecs[c + j] != secs) {
1222 assert(isecs[c + j] == secs);
1223 x = sectx[c + j][secs];
1224 y = secty[c + j][secs];
1226 adj_land_update(x, y);
1232 for (j = 0; j < nc; j++)
1233 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1242 qprint("Only managed to grow %d out of %d island sectors.\n",
1243 is * ni - carry * nc, is * ni);
1248 /****************************************************************************
1250 ****************************************************************************/
1252 create_elevations(void)
1254 init_distance_to_coast();
1259 /* Generic function for finding the distance to the closest sea, land, or
1263 distance_to_what(int x, int y, int flag)
1266 struct hexagon_iter hexit;
1268 for (d = 1; d < 5; ++d) {
1269 hexagon_first(&hexit, x, y, d, &px, &py);
1272 case 0: /* distance to sea */
1273 if (own[px][py] == -1)
1276 case 1: /* distance to land */
1277 if (own[px][py] != -1)
1280 case 2: /* distance to mountain */
1281 if (elev[px][py] == INFINITE_ELEVATION)
1285 } while (hexagon_next(&hexit, &px, &py));
1290 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1292 /* Decide where the mountains go
1297 int max_nm = (pm * MAX(sc, is * 2)) / 100;
1298 int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1299 int highest, where, h, newk, dk;
1300 double elevation, delta;
1302 for (c = 0; c < nc + ni; ++c) {
1305 nm = (pm * ns) / 100;
1307 /* Place the mountains */
1309 for (i = 0; i < ns; ++i) {
1310 off = XYOFFSET(sectx[c][i], secty[c][i]);
1311 dsea[i] = MIN(5, distance[off] + 1);
1312 weight[i] = (total += (dsea[i] * dsea[i]));
1315 for (k = nm, mountain_search = 0;
1316 k && mountain_search < MOUNTAIN_SEARCH_MAX;
1317 ++mountain_search) {
1319 for (i = 0; i < ns; ++i) {
1322 if (r < weight[i] && !elev[x][y] &&
1324 ((!(capx[c] == sectx[c][i] &&
1325 capy[c] == secty[c][i])) &&
1326 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1327 capy[c] == secty[c][i]))))) {
1328 elev[x][y] = INFINITE_ELEVATION;
1335 /* Elevate land that is not mountain and not capital */
1337 for (i = 0; i < ns; ++i)
1338 dmoun[i] = distance_to_mountain();
1339 dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1340 (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1341 100 * INFINITE_ELEVATION;
1342 for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1345 for (i = 0; i < ns; ++i) {
1349 (c >= nc || ((!(capx[c] == sectx[c][i] &&
1350 capy[c] == secty[c][i])) &&
1351 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1352 capy[c] == secty[c][i]))))) {
1353 h = 3 * (5 - dmoun[i]) + dsea[i];
1366 elev[sectx[c][where]][secty[c][where]] = newk;
1369 /* Elevate the mountains and capitals */
1371 elevation = HIGHMIN;
1372 delta = (127.0 - HIGHMIN) / max_nm;
1373 for (i = 0; i < ns; ++i) {
1376 if (elev[x][y] == INFINITE_ELEVATION) {
1378 elev[x][y] = (int)(elevation + 0.5);
1380 * Temporary "useless" die rolls to minimize
1381 * tests/fairland/ churn:
1386 roll0((256 - HIGHMIN) / 2);
1387 roll0((256 - HIGHMIN) / 2);
1389 } else if (c < nc &&
1390 (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1391 ((new_x(capx[c] + 2) == sectx[c][i] &&
1392 capy[c] == secty[c][i]))))
1393 elev[x][y] = PLATMIN;
1403 for (y = 0; y < WORLD_Y; ++y) {
1404 for (x = y % 2; x < WORLD_X; x += 2) {
1405 off = XYOFFSET(x, y);
1406 if (own[x][y] == -1)
1407 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1413 elev_to_sct_type(int elevation)
1415 if (elevation < LANDMIN)
1417 if (elevation < HIGHMIN)
1422 /****************************************************************************
1424 ****************************************************************************/
1431 fert = LANDMIN - e + 40;
1432 else if (e < FERT_MAX)
1433 fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1444 oil = (LANDMIN - e) * 2 + roll0(2);
1445 else if (e <= OIL_MAX)
1446 oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1456 if (e >= IRON_MIN && e < HIGHMIN)
1457 iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1467 if (e >= GOLD_MIN) {
1469 gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1471 gold = 100 - 20 * HIGHMIN / e;
1482 if (e >= URAN_MIN && e < HIGHMIN)
1483 uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1490 add_resources(struct sctstr *sct)
1492 sct->sct_fertil = set_fert(sct->sct_elev);
1493 sct->sct_oil = set_oil(sct->sct_elev);
1494 sct->sct_min = set_iron(sct->sct_elev);
1495 sct->sct_gmin = set_gold(sct->sct_elev);
1496 sct->sct_uran = set_uran(sct->sct_elev);
1499 /****************************************************************************
1500 DESIGNATE THE SECTORS
1501 ****************************************************************************/
1509 for (y = 0; y < WORLD_Y; y++) {
1510 for (x = y % 2; x < WORLD_X; x += 2) {
1511 sct = getsectp(x, y);
1512 sct->sct_elev = elev[x][y];
1513 sct->sct_type = elev_to_sct_type(elev[x][y]);
1514 sct->sct_newtype = sct->sct_type;
1515 sct->sct_dterr = own[sct->sct_x][y] + 1;
1516 sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1522 /****************************************************************************
1523 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1524 ****************************************************************************/
1528 int sx, sy, x, y, c, type;
1531 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1536 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1539 type = elev_to_sct_type(elev[x][y]);
1540 if (type == SCT_WATER)
1542 else if (type == SCT_MOUNT)
1547 assert(0 <= c && c < nc);
1548 if ((x == capx[c] || x == new_x(capx[c] + 2))
1550 printf("%c ", numletter[c % 62]);
1560 * Print a map to help visualize own[][].
1561 * This is for debugging.
1568 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1571 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1575 else if (own[x][y] == -1)
1578 putchar(numletter[own[x][y] % 62]);
1585 * Print a map to help visualize elev[][].
1586 * This is for debugging. It expects the terminal to understand
1587 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1590 print_elev_map(void)
1592 int sx, sy, x, y, sat;
1594 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1597 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1601 else if (!elev[x][y])
1603 else if (elev[x][y] < 0) {
1604 sat = 256 + elev[x][y] * 2;
1605 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1606 } else if (elev[x][y] < HIGHMIN / 2) {
1607 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1608 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1609 } else if (elev[x][y] < HIGHMIN) {
1610 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1611 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1613 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1614 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1622 * Print a map to help visualize xzone[].
1623 * This is for debugging.
1626 print_xzone_map(void)
1628 int sx, sy, x, y, off;
1630 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1633 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1635 off = XYOFFSET(x, y);
1638 else if (own[x][y] >= 0)
1640 else if (xzone[off] >= 0)
1641 putchar(numletter[xzone[off] % 62]);
1643 assert(own[x][y] == -1);
1644 putchar(xzone[off] == -1 ? '.' : '!');
1652 * Print a map to help visualize closest[].
1653 * This is for debugging.
1656 print_closest_map(void)
1658 int sx, sy, x, y, off;
1660 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1663 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1665 off = XYOFFSET(x, y);
1668 else if (closest[off] == (natid)-1)
1670 else if (!distance[off]) {
1671 assert(closest[off] == own[x][y]);
1674 putchar(numletter[closest[off] % 62]);
1682 print_distance_map(void)
1684 int sx, sy, x, y, off;
1686 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1689 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1691 off = XYOFFSET(x, y);
1694 else if (closest[off] == (natid)-1)
1696 else if (!distance[off]) {
1697 assert(closest[off] == own[x][y]);
1700 putchar(numletter[distance[off] % 62]);
1708 /***************************************************************************
1709 WRITE A SCRIPT FOR PLACING CAPITALS
1710 ****************************************************************************/
1712 write_newcap_script(void)
1715 FILE *script = fopen(outfile, "w");
1718 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1719 program_name, outfile, strerror(errno));
1723 for (c = 0; c < nc; ++c) {
1724 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1725 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1727 fprintf(script, "add %d visitor visitor v\n", c + 1);
1733 qprint(const char *const fmt, ...)
1739 vfprintf(stdout, fmt, ap);