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. Pick coastal mountain
97 * elevation randomly from an interval of medium elevations reserved
98 * for them. Pick non-coastal mountain elevation randomly from an
99 * interval of high elevation reserved for them. Set capital
100 * elevation to a fixed, medium value.
102 * In between, elevate the remaining land one by one, working from
103 * mountains towards the sea, and from the elevation just below the
104 * non-coastal mountains' interval linearly down to 1, avoiding the
105 * coastal mountains' interval.
107 * This gives islands of the same size the same set of elevations,
108 * except for mountains.
110 * Elevate sea: pick a random depth from an interval that deepens with
111 * the distance to land.
115 * Sector resources are simple functions of elevation. You can alter
116 * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
131 #include "prototypes.h"
136 /* The following five numbers refer to elevation under which (in the case of
137 fertility or oil) or over which (in the case of iron, gold, and uranium)
138 sectors with that elevation will contain that resource. Elevation ranges
141 /* raise FERT_MAX for more fertility */
144 /* raise OIL_MAX for more oil */
147 /* lower IRON_MIN for more iron */
150 /* lower GOLD_MIN for more gold */
153 /* lower URAN_MIN for more uranium */
156 /* do not change these 4 defines */
157 #define LANDMIN 1 /* plate altitude for normal land */
158 #define HILLMIN 34 /* plate altitude for hills */
159 #define PLATMIN 36 /* plate altitude for plateau */
160 #define HIGHMIN 98 /* plate altitude for mountains */
162 static void qprint(const char * const fmt, ...)
163 ATTRIBUTE((format (printf, 1, 2)));
166 * Program arguments and options
168 static char *program_name;
169 static int nc, sc; /* number and size of continents */
170 static int ni, is; /* number and size of islands */
171 #define DEFAULT_SPIKE 10
172 static int sp = DEFAULT_SPIKE; /* spike percentage */
173 #define DEFAULT_MOUNTAIN 0
174 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
175 #define DEFAULT_CONTDIST 2
176 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
177 #define DEFAULT_ISLDIST 1
178 static int id = DEFAULT_ISLDIST; /* ... continents and islands */
179 /* don't let the islands crash into each other.
180 1 = don't merge, 0 = merge. */
181 static int DISTINCT_ISLANDS = 1;
183 #define DEFAULT_OUTFILE_NAME "newcap_script"
184 static const char *outfile = DEFAULT_OUTFILE_NAME;
186 #define STABLE_CYCLE 4 /* stability required for perterbed capitals */
187 #define INFINITE_ELEVATION 999
189 /* these defines prevent infinite loops:
191 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
192 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
193 #define MOUNTAIN_SEARCH_MAX 1000 /* how long do we try to place mountains */
198 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
199 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
203 * isecs[i] is the size of the i-th island.
207 static int *capx, *capy; /* location of the nc capitals */
209 static int **own; /* owner of the sector. -1 means water */
212 * Adjacent land sectors
213 * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
214 * to x, y in direction d is land.
216 static unsigned char *adj_land;
220 * Each island is surrounded by an exclusive zone where only it may
221 * grow. The width of the zone depends on minimum distances.
222 * While growing continents, it is @di sectors wide.
223 * While growing additional islands, it is @id sectors wide.
224 * DISTINCT_ISLANDS nullifies the exclusive zone then.
225 * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
226 * zone, a (non-negative) island number when it is in that island's
227 * exclusive zone and no other, and -2 when it is in multiple
233 * Set of sectors seen already
234 * Increment @cur_seen to empty the set of sectors seen, set
235 * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
237 static unsigned *seen;
238 static unsigned cur_seen;
241 * Closest continent and "distance"
242 * closest[XYOFFSET(x, y)] is the closest continent's number.
243 * distance[] is complicated; see init_spheres_of_influence() and
244 * init_distance_to_coast().
246 static natid *closest;
247 static unsigned short *distance;
250 * Queue for breadth-first search
252 static int *bfs_queue;
253 static int bfs_queue_head, bfs_queue_tail;
255 static int **elev; /* elevation of the sectors */
256 static int **sectx, **secty; /* the sectors for each continent */
257 static int *weight; /* used for placing mountains */
258 static int *dsea, *dmoun; /* the dist to the ocean and mountain */
260 #define NUMTRIES 10 /* keep trying to grow this many times */
262 static const char *numletter =
263 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
265 static void help(char *);
266 static void usage(void);
267 static void parse_args(int argc, char *argv[]);
268 static void allocate_memory(void);
269 static void init(void);
270 static int drift(void);
271 static int grow_continents(void);
272 static void create_elevations(void);
273 static void write_sects(void);
274 static void output(void);
275 static int write_newcap_script(void);
276 static int stable(int);
277 static void elevate_land(void);
278 static void elevate_sea(void);
280 static void print_vars(void);
281 static void fl_move(int);
282 static int grow_islands(void);
284 /* Debugging aids: */
285 void print_own_map(void);
286 void print_xzone_map(void);
287 void print_closest_map(void);
288 void print_distance_map(void);
289 void print_elev_map(void);
291 /****************************************************************************
293 ****************************************************************************/
296 main(int argc, char *argv[])
299 char *config_file = NULL;
301 unsigned rnd_seed = 0;
304 program_name = argv[0];
306 while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
309 config_file = optarg;
312 DISTINCT_ISLANDS = 0;
318 rnd_seed = strtoul(optarg, NULL, 10);
328 printf("%s\n\n%s", version, legal);
337 rnd_seed = pick_seed();
340 if (emp_config(config_file) < 0)
344 parse_args(argc - optind, argv + optind);
349 qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
350 qprint("seed is %u\n", rnd_seed);
355 qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
356 qprint("placing capitals...\n");
358 qprint("unstable drift\n");
359 qprint("growing continents...\n");
360 done = grow_continents();
363 qprint("growing islands:");
364 done = grow_islands();
365 } while (!done && ++try < NUMTRIES);
367 fprintf(stderr, "%s: world not large enough for this much land\n",
371 qprint("elevating land...\n");
374 qprint("writing to sectors file...\n");
375 if (!write_newcap_script())
377 if (chdir(gamedir)) {
378 fprintf(stderr, "%s: can't chdir to %s (%s)\n",
379 program_name, gamedir, strerror(errno));
382 if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
385 if (!ef_close(EF_SECTOR))
389 qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
399 puts("Creating a planet with:\n");
400 printf("%d continents\n", nc);
401 printf("continent size: %d\n", sc);
402 printf("number of islands: %d\n", ni);
403 printf("average size of islands: %d\n", is);
404 printf("spike: %d%%\n", sp);
405 printf("%d%% of land is mountain (each continent will have %d mountains)\n",
406 pm, (pm * sc) / 100);
407 printf("minimum distance between continents: %d\n", di);
408 printf("minimum distance from islands to continents: %d\n", id);
409 printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
413 help(char *complaint)
416 fprintf(stderr, "%s: %s\n", program_name, complaint);
417 fprintf(stderr, "Try -h for help.\n");
423 printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
424 " -e CONFIG-FILE configuration file\n"
426 " -i islands may merge\n"
428 " -R SEED seed for random number generator\n"
429 " -s SCRIPT name of script to create (default %s)\n"
430 " -h display this help and exit\n"
431 " -v display version information and exit\n"
432 " NC number of continents\n"
433 " SC continent size\n"
434 " NI number of islands (default NC)\n"
435 " IS average island size (default SC/2)\n"
436 " SP spike percentage: 0 = round, 100 = snake (default %d)\n"
437 " PM percentage of land that is mountain (default %d)\n"
438 " DI minimum distance between continents (default %d)\n"
439 " ID minimum distance from islands to continents (default %d)\n",
440 program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
441 DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
445 parse_args(int argc, char *argv[])
447 int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
450 help("missing arguments");
454 help("too many arguments");
459 fprintf(stderr, "%s: number of continents must be > 0\n",
466 fprintf(stderr, "%s: size of continents must be > 1\n",
477 fprintf(stderr, "%s: number of islands must be >= 0\n",
482 fprintf(stderr, "%s: number of islands must be a multiple of"
483 " the number of continents\n",
491 fprintf(stderr, "%s: size of islands must be > 0\n",
498 if (sp < 0 || sp > 100) {
500 "%s: spike percentage must be between 0 and 100\n",
507 if (pm < 0 || pm > 100) {
509 "%s: mountain percentage must be between 0 and 100\n",
517 fprintf(stderr, "%s: distance between continents must be >= 0\n",
522 fprintf(stderr, "%s: distance between continents too large\n",
531 "%s: distance from islands to continents must be >= 0\n",
537 "%s: distance from islands to continents too large\n",
543 /****************************************************************************
544 VARIABLE INITIALIZATION
545 ****************************************************************************/
548 allocate_memory(void)
552 capx = calloc(nc, sizeof(int));
553 capy = calloc(nc, sizeof(int));
554 own = calloc(WORLD_X, sizeof(int *));
555 adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
556 xzone = malloc(WORLD_SZ() * sizeof(*xzone));
557 seen = calloc(WORLD_SZ(), sizeof(*seen));
558 closest = malloc(WORLD_SZ() * sizeof(*closest));
559 distance = malloc(WORLD_SZ() * sizeof(*distance));
560 bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
561 elev = calloc(WORLD_X, sizeof(int *));
562 for (i = 0; i < WORLD_X; ++i) {
563 own[i] = calloc(WORLD_Y, sizeof(int));
564 elev[i] = calloc(WORLD_Y, sizeof(int));
566 sectx = calloc(nc + ni, sizeof(int *));
567 secty = 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));
576 for (i = nc; i < nc + ni; ++i) {
577 sectx[i] = calloc(is * 2, sizeof(int));
578 secty[i] = calloc(is * 2, sizeof(int));
588 for (i = 0; i < WORLD_X; ++i) {
589 for (j = 0; j < WORLD_Y; ++j) {
593 memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
596 /****************************************************************************
597 DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
598 ****************************************************************************/
601 * How isolated is capital @j at @newx,@newy?
602 * Return the distance to the closest other capital.
605 iso(int j, int newx, int newy)
610 for (i = 0; i < nc; ++i) {
613 md = mapdist(capx[i], capy[i], newx, newy);
623 * Return 1 for a stable drift, 0 for an unstable one.
630 for (i = 0; i < nc; i++) {
631 capy[i] = (2 * i) / WORLD_X;
632 capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
633 if (capy[i] >= WORLD_Y) {
635 "%s: world not big enough for all the continents\n",
641 for (turns = 0; turns < DRIFT_MAX; ++turns) {
644 for (i = 0; i < nc; ++i)
651 * Has the drift stabilized?
652 * @turns is the number of turns so far.
657 static int mc[STABLE_CYCLE];
658 int i, isod, d = 0, stab = 1;
661 for (i = 0; i < STABLE_CYCLE; i++)
665 if (turns <= DRIFT_BEFORE_CHECK)
668 for (i = 0; i < nc; ++i) {
669 isod = iso(i, capx[i], capy[i]);
674 for (i = 0; i < STABLE_CYCLE; ++i)
678 mc[turns % STABLE_CYCLE] = d;
682 /* This routine does the actual drifting
688 int dir, i, newx, newy;
690 dir = DIR_L + roll0(6);
691 for (i = 0; i < 6; i++) {
694 newx = new_x(capx[j] + diroff[dir][0]);
695 newy = new_y(capy[j] + diroff[dir][1]);
697 if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
705 /****************************************************************************
707 ****************************************************************************/
710 is_coastal(int x, int y)
712 return adj_land[XYOFFSET(x, y)]
713 != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
716 struct hexagon_iter {
721 * Start iterating around @x0,@y0 at distance @d.
722 * Set *x,*y to coordinates of the first sector.
725 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
728 *x = new_x(x0 - 2 * n);
730 iter->dir = DIR_FIRST;
736 * Continue iteration started with hexagon_first().
737 * Set *x,*y to coordinates of the next sector.
738 * Return whether we're back at the first sector, i.e. iteration is
742 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
744 *x = new_x(*x + diroff[iter->dir][0]);
745 *y = new_y(*y + diroff[iter->dir][1]);
747 if (iter->i == iter->n) {
751 return iter->dir <= DIR_LAST;
755 * Is @x,@y in no exclusive zone other than perhaps @c's?
758 xzone_ok(int c, int x, int y)
760 int off = XYOFFSET(x, y);
762 return xzone[off] == c || xzone[off] == -1;
766 * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
769 xzone_around_sector(int c, int x, int y, int dist)
772 struct hexagon_iter hexit;
774 assert(xzone_ok(c, x, y));
776 xzone[XYOFFSET(x, y)] = c;
777 for (d = 1; d <= dist; d++) {
778 hexagon_first(&hexit, x, y, d, &x1, &y1);
780 off = XYOFFSET(x1, y1);
781 if (xzone[off] == -1)
783 else if (xzone[off] != c)
785 } while (hexagon_next(&hexit, &x1, &y1));
790 * Add sectors within distance @dist to island @c's exclusive zone.
793 xzone_around_island(int c, int dist)
797 for (i = 0; i < isecs[c]; i++)
798 xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
802 * Initialize exclusive zones around @n islands.
809 for (i = 0; i < WORLD_SZ(); i++)
812 for (c = 0; c < n; c++)
813 xzone_around_island(c, id);
817 * Initialize breadth-first search.
824 for (i = 0; i < WORLD_SZ(); i++) {
826 distance[i] = USHRT_MAX;
829 bfs_queue_head = bfs_queue_tail = 0;
833 * Add sector @x,@y to the BFS queue.
834 * It's closest to @c, with distance @dist.
837 bfs_enqueue(int c, int x, int y, int dist)
839 int off = XYOFFSET(x, y);
841 assert(dist < distance[off]);
843 distance[off] = dist;
844 bfs_queue[bfs_queue_tail] = off;
846 if (bfs_queue_tail >= WORLD_SZ())
848 assert(bfs_queue_tail != bfs_queue_head);
852 * Search breadth-first until the queue is empty.
857 int off, dist, i, noff, nx, ny;
860 while (bfs_queue_head != bfs_queue_tail) {
861 off = bfs_queue[bfs_queue_head];
863 if (bfs_queue_head >= WORLD_SZ())
865 dist = distance[off] + 1;
866 sctoff2xy(&x, &y, off);
867 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
868 nx = new_x(x + diroff[i][0]);
869 ny = new_y(y + diroff[i][1]);
870 noff = XYOFFSET(nx, ny);
871 if (dist < distance[noff]) {
872 bfs_enqueue(closest[off], nx, ny, dist);
873 } else if (distance[noff] == dist) {
874 if (closest[off] != closest[noff])
875 closest[noff] = (natid)-1;
877 assert(distance[noff] < dist);
883 * Add island @c's coastal sectors to the BFS queue, with distance 0.
886 bfs_enqueue_island(int c)
890 for (i = 0; i < isecs[c]; i++) {
891 if (is_coastal(sectx[c][i], secty[c][i]))
892 bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
897 * Enqueue spheres of influence borders for breadth-first search.
900 bfs_enqueue_border(void)
902 int x, y, off, dir, nx, ny, noff;
904 for (y = 0; y < WORLD_Y; y++) {
905 for (x = y % 2; x < WORLD_X; x += 2) {
906 off = XYOFFSET(x, y);
907 if (distance[off] <= id + 1)
909 if (closest[off] == (natid)-1)
911 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
912 nx = new_x(x + diroff[dir][0]);
913 ny = new_y(y + diroff[dir][1]);
914 noff = XYOFFSET(nx, ny);
915 if (closest[noff] != closest[off]) {
916 bfs_enqueue(closest[off], x, y, id + 1);
925 * Compute spheres of influence
926 * A continent's sphere of influence is the set of sectors closer to
927 * it than to any other continent.
928 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
929 * -1 if no single continent is closest.
930 * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
931 * closest coastal land sector and the distance to just outside the
932 * sphere of influence plus @id. For sea sectors within a continent's
933 * sphere of influence, distance[off] - id is the distance to the
934 * border of the area where additional islands can be placed.
937 init_spheres_of_influence(void)
942 for (c = 0; c < nc; c++)
943 bfs_enqueue_island(c);
945 bfs_enqueue_border();
950 * Precompute distance to coast
951 * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
953 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
954 * -1 if no single continent is closest.
957 init_distance_to_coast(void)
962 for (c = 0; c < nc + ni; c++)
963 bfs_enqueue_island(c);
968 * Is @x,@y in the same sphere of influence as island @c?
969 * Always true when @c is a continent.
972 is_in_sphere(int c, int x, int y)
974 return c < nc || closest[XYOFFSET(x, y)] == c % nc;
978 * Can island @c grow at @x,@y?
981 can_grow_at(int c, int x, int y)
983 return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
987 adj_land_update(int x, int y)
989 int is_land = own[x][y] != -1;
990 int dir, nx, ny, noff;
992 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
993 nx = new_x(x + diroff[dir][0]);
994 ny = new_y(y + diroff[dir][1]);
995 noff = XYOFFSET(nx, ny);
997 adj_land[noff] |= 1u << DIR_BACK(dir);
999 adj_land[noff] &= ~(1u << DIR_BACK(dir));
1004 add_sector(int c, int x, int y)
1006 assert(own[x][y] == -1);
1007 xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1008 sectx[c][isecs[c]] = x;
1009 secty[c][isecs[c]] = y;
1012 adj_land_update(x, y);
1015 static int grow_weight(int c, int x, int y, int spike)
1020 * #Land neighbors is #bits set in adj_land[].
1021 * Count them Brian Kernighan's way.
1024 for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1026 assert(n > 0 && n < 7);
1029 return (6 - n) * (6 - n);
1035 grow_one_sector(int c)
1037 int spike = roll0(100) < sp;
1038 int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1040 assert(cur_seen < UINT_MAX);
1045 for (i = 0; i < isecs[c]; i++) {
1048 off = XYOFFSET(x, y);
1050 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1051 if (adj_land[off] & (1u << dir))
1053 nx = new_x(x + diroff[dir][0]);
1054 ny = new_y(y + diroff[dir][1]);
1055 noff = XYOFFSET(nx, ny);
1056 if (seen[noff] == cur_seen)
1058 assert(seen[noff] < cur_seen);
1059 seen[noff] = cur_seen;
1060 if (!can_grow_at(c, nx, ny))
1062 w = grow_weight(c, nx, ny, spike);
1063 assert(wsum < INT_MAX - w);
1065 if (roll0(wsum) < w) {
1075 add_sector(c, newx, newy);
1080 * Grow the continents.
1081 * Return 1 on success, 0 on error.
1084 grow_continents(void)
1091 for (c = 0; c < nc; ++c) {
1093 if (!can_grow_at(c, capx[c], capy[c])
1094 || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1098 add_sector(c, capx[c], capy[c]);
1099 add_sector(c, new_x(capx[c] + 2), capy[c]);
1103 qprint("No room for continents\n");
1107 for (secs = 2; secs < sc && done; secs++) {
1108 for (c = 0; c < nc; ++c) {
1109 if (!grow_one_sector(c))
1115 qprint("Only managed to grow %d out of %d sectors.\n",
1120 /****************************************************************************
1122 ****************************************************************************/
1125 * Place additional island @c's first sector.
1126 * Return 1 on success, 0 on error.
1129 place_island(int c, int isiz)
1131 int n, x, y, d, w, newx, newy;
1135 for (y = 0; y < WORLD_Y; y++) {
1136 for (x = y % 2; x < WORLD_X; x += 2) {
1137 if (can_grow_at(c, x, y)) {
1138 d = distance[XYOFFSET(x, y)];
1140 w = (d - id) * (d - id);
1141 n += MIN(w, (isiz + 2) / 3);
1151 add_sector(c, newx, newy);
1156 int_cmp(const void *a, const void *b)
1158 return *(int *)b - *(int *)a;
1165 int *isiz = malloc(n * sizeof(*isiz));
1170 for (i = 1; i < n; i++) {
1173 isiz[i] = is + r1 - r0;
1177 qsort(isiz, n, sizeof(*isiz), int_cmp);
1182 * Grow the additional islands.
1183 * Return 1 on success, 0 on error.
1188 int *island_size = size_islands();
1189 int xzone_valid = 0;
1191 int i, j, c, done, secs, isiz, x, y;
1193 init_spheres_of_influence();
1195 for (i = 0; i < ni / nc; i++) {
1201 carry += island_size[i];
1202 isiz = MIN(2 * is, carry);
1204 for (j = 0; j < nc; j++) {
1206 if (!place_island(c + j, isiz)) {
1207 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1214 for (secs = 1; secs < isiz && done; secs++) {
1215 for (j = 0; j < nc; j++) {
1216 if (!grow_one_sector(c + j))
1223 for (j = 0; j < nc; j++) {
1224 if (isecs[c + j] != secs) {
1226 assert(isecs[c + j] == secs);
1227 x = sectx[c + j][secs];
1228 y = secty[c + j][secs];
1230 adj_land_update(x, y);
1236 for (j = 0; j < nc; j++)
1237 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1246 qprint("Only managed to grow %d out of %d island sectors.\n",
1247 is * ni - carry * nc, is * ni);
1252 /****************************************************************************
1254 ****************************************************************************/
1256 create_elevations(void)
1260 for (i = 0; i < WORLD_X; i++) {
1261 for (j = 0; j < WORLD_Y; j++)
1262 elev[i][j] = -INFINITE_ELEVATION;
1264 init_distance_to_coast();
1269 /* Generic function for finding the distance to the closest sea, land, or
1273 distance_to_what(int x, int y, int flag)
1276 struct hexagon_iter hexit;
1278 for (d = 1; d < 5; ++d) {
1279 hexagon_first(&hexit, x, y, d, &px, &py);
1282 case 0: /* distance to sea */
1283 if (own[px][py] == -1)
1286 case 1: /* distance to land */
1287 if (own[px][py] != -1)
1290 case 2: /* distance to mountain */
1291 if (elev[px][py] == INFINITE_ELEVATION)
1295 } while (hexagon_next(&hexit, &px, &py));
1300 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1302 /* Decide where the mountains go
1307 int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1308 int highest, where, h, newk, dk;
1310 for (c = 0; c < nc + ni; ++c) {
1313 nm = (pm * ns) / 100;
1315 /* Place the mountains */
1317 for (i = 0; i < ns; ++i) {
1318 off = XYOFFSET(sectx[c][i], secty[c][i]);
1319 dsea[i] = MIN(5, distance[off] + 1);
1320 weight[i] = (total += (dsea[i] * dsea[i]));
1323 for (k = nm, mountain_search = 0;
1324 k && mountain_search < MOUNTAIN_SEARCH_MAX;
1325 ++mountain_search) {
1327 for (i = 0; i < ns; ++i) {
1330 if (r < weight[i] && elev[x][y] == -INFINITE_ELEVATION &&
1332 ((!(capx[c] == sectx[c][i] &&
1333 capy[c] == secty[c][i])) &&
1334 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1335 capy[c] == secty[c][i]))))) {
1336 elev[x][y] = INFINITE_ELEVATION;
1343 /* Elevate land that is not mountain and not capital */
1345 for (i = 0; i < ns; ++i)
1346 dmoun[i] = distance_to_mountain();
1347 dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1348 (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1349 100 * INFINITE_ELEVATION;
1350 for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1353 for (i = 0; i < ns; ++i) {
1356 if (elev[x][y] == -INFINITE_ELEVATION &&
1357 (c >= nc || ((!(capx[c] == sectx[c][i] &&
1358 capy[c] == secty[c][i])) &&
1359 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1360 capy[c] == secty[c][i]))))) {
1361 h = 3 * (5 - dmoun[i]) + dsea[i];
1372 if (newk >= HILLMIN && newk < PLATMIN)
1376 elev[sectx[c][where]][secty[c][where]] = newk;
1379 /* Elevate the mountains and capitals */
1381 for (i = 0; i < ns; ++i) {
1384 if (elev[x][y] == INFINITE_ELEVATION) {
1386 elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1388 elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1389 roll0((256 - HIGHMIN) / 2);
1390 } else if (c < nc &&
1391 (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1392 ((new_x(capx[c] + 2) == sectx[c][i] &&
1393 capy[c] == secty[c][i]))))
1394 elev[x][y] = PLATMIN;
1404 for (y = 0; y < WORLD_Y; ++y) {
1405 for (x = y % 2; x < WORLD_X; x += 2) {
1406 off = XYOFFSET(x, y);
1407 if (elev[x][y] == -INFINITE_ELEVATION)
1408 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1414 elev_to_sct_type(int elevation)
1416 if (elevation < LANDMIN)
1418 if (elevation < HILLMIN)
1420 if (elevation < PLATMIN)
1422 if (elevation < HIGHMIN)
1427 /****************************************************************************
1429 ****************************************************************************/
1436 fert = LANDMIN - e + 40;
1437 else if (e < FERT_MAX)
1438 fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1449 oil = (LANDMIN - e) * 2 + roll0(2);
1450 else if (e <= OIL_MAX)
1451 oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1461 if (e >= IRON_MIN && e < HIGHMIN)
1462 iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1472 if (e >= GOLD_MIN) {
1474 gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1476 gold = 100 - 20 * HIGHMIN / e;
1487 if (e >= URAN_MIN && e < HIGHMIN)
1488 uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1495 add_resources(struct sctstr *sct)
1497 sct->sct_fertil = set_fert(sct->sct_elev);
1498 sct->sct_oil = set_oil(sct->sct_elev);
1499 sct->sct_min = set_iron(sct->sct_elev);
1500 sct->sct_gmin = set_gold(sct->sct_elev);
1501 sct->sct_uran = set_uran(sct->sct_elev);
1504 /****************************************************************************
1505 DESIGNATE THE SECTORS
1506 ****************************************************************************/
1514 for (y = 0; y < WORLD_Y; y++) {
1515 for (x = y % 2; x < WORLD_X; x += 2) {
1516 sct = getsectp(x, y);
1517 sct->sct_elev = elev[x][y];
1518 sct->sct_type = elev_to_sct_type(elev[x][y]);
1519 sct->sct_newtype = sct->sct_type;
1520 sct->sct_dterr = own[sct->sct_x][y] + 1;
1521 sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1527 /****************************************************************************
1528 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1529 ****************************************************************************/
1533 int sx, sy, x, y, c, type;
1536 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1541 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1544 type = elev_to_sct_type(elev[x][y]);
1545 if (type == SCT_WATER)
1547 else if (type == SCT_MOUNT)
1552 assert(0 <= c && c < nc);
1553 if ((x == capx[c] || x == new_x(capx[c] + 2))
1555 printf("%c ", numletter[c % 62]);
1565 * Print a map to help visualize own[][].
1566 * This is for debugging.
1573 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1576 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1580 else if (own[x][y] == -1)
1583 putchar(numletter[own[x][y] % 62]);
1590 * Print a map to help visualize elev[][].
1591 * This is for debugging. It expects the terminal to understand
1592 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1595 print_elev_map(void)
1597 int sx, sy, x, y, sat;
1599 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1602 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1606 else if (!elev[x][y])
1608 else if (elev[x][y] < 0) {
1609 sat = 256 + elev[x][y] * 2;
1610 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1611 } else if (elev[x][y] < HIGHMIN / 2) {
1612 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1613 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1614 } else if (elev[x][y] < HIGHMIN) {
1615 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1616 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1618 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1619 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1627 * Print a map to help visualize xzone[].
1628 * This is for debugging.
1631 print_xzone_map(void)
1633 int sx, sy, x, y, off;
1635 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1638 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1640 off = XYOFFSET(x, y);
1643 else if (own[x][y] >= 0)
1645 else if (xzone[off] >= 0)
1646 putchar(numletter[xzone[off] % 62]);
1648 assert(own[x][y] == -1);
1649 putchar(xzone[off] == -1 ? '.' : '!');
1657 * Print a map to help visualize closest[].
1658 * This is for debugging.
1661 print_closest_map(void)
1663 int sx, sy, x, y, off;
1665 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1668 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1670 off = XYOFFSET(x, y);
1673 else if (closest[off] == (natid)-1)
1675 else if (!distance[off]) {
1676 assert(closest[off] == own[x][y]);
1679 putchar(numletter[closest[off] % 62]);
1687 print_distance_map(void)
1689 int sx, sy, x, y, off;
1691 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1694 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1696 off = XYOFFSET(x, y);
1699 else if (closest[off] == (natid)-1)
1701 else if (!distance[off]) {
1702 assert(closest[off] == own[x][y]);
1705 putchar(numletter[distance[off] % 62]);
1713 /***************************************************************************
1714 WRITE A SCRIPT FOR PLACING CAPITALS
1715 ****************************************************************************/
1717 write_newcap_script(void)
1720 FILE *script = fopen(outfile, "w");
1723 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1724 program_name, outfile, strerror(errno));
1728 for (c = 0; c < nc; ++c) {
1729 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1730 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1732 fprintf(script, "add %d visitor visitor v\n", c + 1);
1738 qprint(const char *const fmt, ...)
1744 vfprintf(stdout, fmt, ap);