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.
103 * TODO This still avoids the elevations formerly reserved for coastal
106 * This gives islands of the same size the same set of elevations.
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() and
242 * init_distance_to_coast().
244 static natid *closest;
245 static unsigned short *distance;
248 * Queue for breadth-first search
250 static int *bfs_queue;
251 static int bfs_queue_head, bfs_queue_tail;
253 static int **elev; /* elevation of the sectors */
254 static int **sectx, **secty; /* the sectors for each continent */
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);
278 static void print_vars(void);
279 static void fl_move(int);
280 static int grow_islands(void);
282 /* Debugging aids: */
283 void print_own_map(void);
284 void print_xzone_map(void);
285 void print_closest_map(void);
286 void print_distance_map(void);
287 void print_elev_map(void);
289 /****************************************************************************
291 ****************************************************************************/
294 main(int argc, char *argv[])
297 char *config_file = NULL;
299 unsigned rnd_seed = 0;
302 program_name = argv[0];
304 while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
307 config_file = optarg;
310 DISTINCT_ISLANDS = 0;
316 rnd_seed = strtoul(optarg, NULL, 10);
326 printf("%s\n\n%s", version, legal);
335 rnd_seed = pick_seed();
338 if (emp_config(config_file) < 0)
342 parse_args(argc - optind, argv + optind);
347 qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
348 qprint("seed is %u\n", rnd_seed);
353 qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
354 qprint("placing capitals...\n");
356 qprint("unstable drift\n");
357 qprint("growing continents...\n");
358 done = grow_continents();
361 qprint("growing islands:");
362 done = grow_islands();
363 } while (!done && ++try < NUMTRIES);
365 fprintf(stderr, "%s: world not large enough for this much land\n",
369 qprint("elevating land...\n");
372 qprint("writing to sectors file...\n");
373 if (!write_newcap_script())
375 if (chdir(gamedir)) {
376 fprintf(stderr, "%s: can't chdir to %s (%s)\n",
377 program_name, gamedir, strerror(errno));
380 if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
383 if (!ef_close(EF_SECTOR))
387 qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
397 puts("Creating a planet with:\n");
398 printf("%d continents\n", nc);
399 printf("continent size: %d\n", sc);
400 printf("number of islands: %d\n", ni);
401 printf("average size of islands: %d\n", is);
402 printf("spike: %d%%\n", sp);
403 printf("%d%% of land is mountain (each continent will have %d mountains)\n",
404 pm, (pm * sc) / 100);
405 printf("minimum distance between continents: %d\n", di);
406 printf("minimum distance from islands to continents: %d\n", id);
407 printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
411 help(char *complaint)
414 fprintf(stderr, "%s: %s\n", program_name, complaint);
415 fprintf(stderr, "Try -h for help.\n");
421 printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
422 " -e CONFIG-FILE configuration file\n"
424 " -i islands may merge\n"
426 " -R SEED seed for random number generator\n"
427 " -s SCRIPT name of script to create (default %s)\n"
428 " -h display this help and exit\n"
429 " -v display version information and exit\n"
430 " NC number of continents\n"
431 " SC continent size\n"
432 " NI number of islands (default NC)\n"
433 " IS average island size (default SC/2)\n"
434 " SP spike percentage: 0 = round, 100 = snake (default %d)\n"
435 " PM percentage of land that is mountain (default %d)\n"
436 " DI minimum distance between continents (default %d)\n"
437 " ID minimum distance from islands to continents (default %d)\n",
438 program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
439 DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
443 parse_args(int argc, char *argv[])
445 int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
448 help("missing arguments");
452 help("too many arguments");
457 fprintf(stderr, "%s: number of continents must be > 0\n",
464 fprintf(stderr, "%s: size of continents must be > 1\n",
475 fprintf(stderr, "%s: number of islands must be >= 0\n",
480 fprintf(stderr, "%s: number of islands must be a multiple of"
481 " the number of continents\n",
489 fprintf(stderr, "%s: size of islands must be > 0\n",
496 if (sp < 0 || sp > 100) {
498 "%s: spike percentage must be between 0 and 100\n",
505 if (pm < 0 || pm > 100) {
507 "%s: mountain percentage must be between 0 and 100\n",
515 fprintf(stderr, "%s: distance between continents must be >= 0\n",
520 fprintf(stderr, "%s: distance between continents too large\n",
529 "%s: distance from islands to continents must be >= 0\n",
535 "%s: distance from islands to continents too large\n",
541 /****************************************************************************
542 VARIABLE INITIALIZATION
543 ****************************************************************************/
546 allocate_memory(void)
550 capx = calloc(nc, sizeof(int));
551 capy = calloc(nc, sizeof(int));
552 own = calloc(WORLD_X, sizeof(int *));
553 adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
554 xzone = malloc(WORLD_SZ() * sizeof(*xzone));
555 seen = calloc(WORLD_SZ(), sizeof(*seen));
556 closest = malloc(WORLD_SZ() * sizeof(*closest));
557 distance = malloc(WORLD_SZ() * sizeof(*distance));
558 bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
559 elev = calloc(WORLD_X, sizeof(int *));
560 for (i = 0; i < WORLD_X; ++i) {
561 own[i] = calloc(WORLD_Y, sizeof(int));
562 elev[i] = calloc(WORLD_Y, sizeof(int));
564 sectx = calloc(nc + ni, sizeof(int *));
565 secty = calloc(nc + ni, sizeof(int *));
566 isecs = calloc(nc + ni, sizeof(int));
567 weight = calloc(MAX(sc, is * 2), sizeof(int));
568 dsea = calloc(MAX(sc, is * 2), sizeof(int));
569 dmoun = calloc(MAX(sc, is * 2), sizeof(int));
570 for (i = 0; i < nc; ++i) {
571 sectx[i] = calloc(sc, sizeof(int));
572 secty[i] = calloc(sc, sizeof(int));
574 for (i = nc; i < nc + ni; ++i) {
575 sectx[i] = calloc(is * 2, sizeof(int));
576 secty[i] = calloc(is * 2, sizeof(int));
586 for (i = 0; i < WORLD_X; ++i) {
587 for (j = 0; j < WORLD_Y; ++j) {
591 memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
594 /****************************************************************************
595 DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
596 ****************************************************************************/
599 * How isolated is capital @j at @newx,@newy?
600 * Return the distance to the closest other capital.
603 iso(int j, int newx, int newy)
608 for (i = 0; i < nc; ++i) {
611 md = mapdist(capx[i], capy[i], newx, newy);
621 * Return 1 for a stable drift, 0 for an unstable one.
628 for (i = 0; i < nc; i++) {
629 capy[i] = (2 * i) / WORLD_X;
630 capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
631 if (capy[i] >= WORLD_Y) {
633 "%s: world not big enough for all the continents\n",
639 for (turns = 0; turns < DRIFT_MAX; ++turns) {
642 for (i = 0; i < nc; ++i)
649 * Has the drift stabilized?
650 * @turns is the number of turns so far.
655 static int mc[STABLE_CYCLE];
656 int i, isod, d = 0, stab = 1;
659 for (i = 0; i < STABLE_CYCLE; i++)
663 if (turns <= DRIFT_BEFORE_CHECK)
666 for (i = 0; i < nc; ++i) {
667 isod = iso(i, capx[i], capy[i]);
672 for (i = 0; i < STABLE_CYCLE; ++i)
676 mc[turns % STABLE_CYCLE] = d;
680 /* This routine does the actual drifting
686 int dir, i, newx, newy;
688 dir = DIR_L + roll0(6);
689 for (i = 0; i < 6; i++) {
692 newx = new_x(capx[j] + diroff[dir][0]);
693 newy = new_y(capy[j] + diroff[dir][1]);
695 if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
703 /****************************************************************************
705 ****************************************************************************/
708 is_coastal(int x, int y)
710 return adj_land[XYOFFSET(x, y)]
711 != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
714 struct hexagon_iter {
719 * Start iterating around @x0,@y0 at distance @d.
720 * Set *x,*y to coordinates of the first sector.
723 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
726 *x = new_x(x0 - 2 * n);
728 iter->dir = DIR_FIRST;
734 * Continue iteration started with hexagon_first().
735 * Set *x,*y to coordinates of the next sector.
736 * Return whether we're back at the first sector, i.e. iteration is
740 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
742 *x = new_x(*x + diroff[iter->dir][0]);
743 *y = new_y(*y + diroff[iter->dir][1]);
745 if (iter->i == iter->n) {
749 return iter->dir <= DIR_LAST;
753 * Is @x,@y in no exclusive zone other than perhaps @c's?
756 xzone_ok(int c, int x, int y)
758 int off = XYOFFSET(x, y);
760 return xzone[off] == c || xzone[off] == -1;
764 * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
767 xzone_around_sector(int c, int x, int y, int dist)
770 struct hexagon_iter hexit;
772 assert(xzone_ok(c, x, y));
774 xzone[XYOFFSET(x, y)] = c;
775 for (d = 1; d <= dist; d++) {
776 hexagon_first(&hexit, x, y, d, &x1, &y1);
778 off = XYOFFSET(x1, y1);
779 if (xzone[off] == -1)
781 else if (xzone[off] != c)
783 } while (hexagon_next(&hexit, &x1, &y1));
788 * Add sectors within distance @dist to island @c's exclusive zone.
791 xzone_around_island(int c, int dist)
795 for (i = 0; i < isecs[c]; i++)
796 xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
800 * Initialize exclusive zones around @n islands.
807 for (i = 0; i < WORLD_SZ(); i++)
810 for (c = 0; c < n; c++)
811 xzone_around_island(c, id);
815 * Initialize breadth-first search.
822 for (i = 0; i < WORLD_SZ(); i++) {
824 distance[i] = USHRT_MAX;
827 bfs_queue_head = bfs_queue_tail = 0;
831 * Add sector @x,@y to the BFS queue.
832 * It's closest to @c, with distance @dist.
835 bfs_enqueue(int c, int x, int y, int dist)
837 int off = XYOFFSET(x, y);
839 assert(dist < distance[off]);
841 distance[off] = dist;
842 bfs_queue[bfs_queue_tail] = off;
844 if (bfs_queue_tail >= WORLD_SZ())
846 assert(bfs_queue_tail != bfs_queue_head);
850 * Search breadth-first until the queue is empty.
855 int off, dist, i, noff, nx, ny;
858 while (bfs_queue_head != bfs_queue_tail) {
859 off = bfs_queue[bfs_queue_head];
861 if (bfs_queue_head >= WORLD_SZ())
863 dist = distance[off] + 1;
864 sctoff2xy(&x, &y, off);
865 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
866 nx = new_x(x + diroff[i][0]);
867 ny = new_y(y + diroff[i][1]);
868 noff = XYOFFSET(nx, ny);
869 if (dist < distance[noff]) {
870 bfs_enqueue(closest[off], nx, ny, dist);
871 } else if (distance[noff] == dist) {
872 if (closest[off] != closest[noff])
873 closest[noff] = (natid)-1;
875 assert(distance[noff] < dist);
881 * Add island @c's coastal sectors to the BFS queue, with distance 0.
884 bfs_enqueue_island(int c)
888 for (i = 0; i < isecs[c]; i++) {
889 if (is_coastal(sectx[c][i], secty[c][i]))
890 bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
895 * Enqueue spheres of influence borders for breadth-first search.
898 bfs_enqueue_border(void)
900 int x, y, off, dir, nx, ny, noff;
902 for (y = 0; y < WORLD_Y; y++) {
903 for (x = y % 2; x < WORLD_X; x += 2) {
904 off = XYOFFSET(x, y);
905 if (distance[off] <= id + 1)
907 if (closest[off] == (natid)-1)
909 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
910 nx = new_x(x + diroff[dir][0]);
911 ny = new_y(y + diroff[dir][1]);
912 noff = XYOFFSET(nx, ny);
913 if (closest[noff] != closest[off]) {
914 bfs_enqueue(closest[off], x, y, id + 1);
923 * Compute spheres of influence
924 * A continent's sphere of influence is the set of sectors closer to
925 * it than to any other continent.
926 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
927 * -1 if no single continent is closest.
928 * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
929 * closest coastal land sector and the distance to just outside the
930 * sphere of influence plus @id. For sea sectors within a continent's
931 * sphere of influence, distance[off] - id is the distance to the
932 * border of the area where additional islands can be placed.
935 init_spheres_of_influence(void)
940 for (c = 0; c < nc; c++)
941 bfs_enqueue_island(c);
943 bfs_enqueue_border();
948 * Precompute distance to coast
949 * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
951 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
952 * -1 if no single continent is closest.
955 init_distance_to_coast(void)
960 for (c = 0; c < nc + ni; c++)
961 bfs_enqueue_island(c);
966 * Is @x,@y in the same sphere of influence as island @c?
967 * Always true when @c is a continent.
970 is_in_sphere(int c, int x, int y)
972 return c < nc || closest[XYOFFSET(x, y)] == c % nc;
976 * Can island @c grow at @x,@y?
979 can_grow_at(int c, int x, int y)
981 return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
985 adj_land_update(int x, int y)
987 int is_land = own[x][y] != -1;
988 int dir, nx, ny, noff;
990 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
991 nx = new_x(x + diroff[dir][0]);
992 ny = new_y(y + diroff[dir][1]);
993 noff = XYOFFSET(nx, ny);
995 adj_land[noff] |= 1u << DIR_BACK(dir);
997 adj_land[noff] &= ~(1u << DIR_BACK(dir));
1002 add_sector(int c, int x, int y)
1004 assert(own[x][y] == -1);
1005 xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1006 sectx[c][isecs[c]] = x;
1007 secty[c][isecs[c]] = y;
1010 adj_land_update(x, y);
1013 static int grow_weight(int c, int x, int y, int spike)
1018 * #Land neighbors is #bits set in adj_land[].
1019 * Count them Brian Kernighan's way.
1022 for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1024 assert(n > 0 && n < 7);
1027 return (6 - n) * (6 - n);
1033 grow_one_sector(int c)
1035 int spike = roll0(100) < sp;
1036 int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1038 assert(cur_seen < UINT_MAX);
1043 for (i = 0; i < isecs[c]; i++) {
1046 off = XYOFFSET(x, y);
1048 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1049 if (adj_land[off] & (1u << dir))
1051 nx = new_x(x + diroff[dir][0]);
1052 ny = new_y(y + diroff[dir][1]);
1053 noff = XYOFFSET(nx, ny);
1054 if (seen[noff] == cur_seen)
1056 assert(seen[noff] < cur_seen);
1057 seen[noff] = cur_seen;
1058 if (!can_grow_at(c, nx, ny))
1060 w = grow_weight(c, nx, ny, spike);
1061 assert(wsum < INT_MAX - w);
1063 if (roll0(wsum) < w) {
1073 add_sector(c, newx, newy);
1078 * Grow the continents.
1079 * Return 1 on success, 0 on error.
1082 grow_continents(void)
1089 for (c = 0; c < nc; ++c) {
1091 if (!can_grow_at(c, capx[c], capy[c])
1092 || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1096 add_sector(c, capx[c], capy[c]);
1097 add_sector(c, new_x(capx[c] + 2), capy[c]);
1101 qprint("No room for continents\n");
1105 for (secs = 2; secs < sc && done; secs++) {
1106 for (c = 0; c < nc; ++c) {
1107 if (!grow_one_sector(c))
1113 qprint("Only managed to grow %d out of %d sectors.\n",
1118 /****************************************************************************
1120 ****************************************************************************/
1123 * Place additional island @c's first sector.
1124 * Return 1 on success, 0 on error.
1127 place_island(int c, int isiz)
1129 int n, x, y, d, w, newx, newy;
1133 for (y = 0; y < WORLD_Y; y++) {
1134 for (x = y % 2; x < WORLD_X; x += 2) {
1135 if (can_grow_at(c, x, y)) {
1136 d = distance[XYOFFSET(x, y)];
1138 w = (d - id) * (d - id);
1139 n += MIN(w, (isiz + 2) / 3);
1149 add_sector(c, newx, newy);
1154 int_cmp(const void *a, const void *b)
1156 return *(int *)b - *(int *)a;
1163 int *isiz = malloc(n * sizeof(*isiz));
1168 for (i = 1; i < n; i++) {
1171 isiz[i] = is + r1 - r0;
1175 qsort(isiz, n, sizeof(*isiz), int_cmp);
1180 * Grow the additional islands.
1181 * Return 1 on success, 0 on error.
1186 int *island_size = size_islands();
1187 int xzone_valid = 0;
1189 int i, j, c, done, secs, isiz, x, y;
1191 init_spheres_of_influence();
1193 for (i = 0; i < ni / nc; i++) {
1199 carry += island_size[i];
1200 isiz = MIN(2 * is, carry);
1202 for (j = 0; j < nc; j++) {
1204 if (!place_island(c + j, isiz)) {
1205 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1212 for (secs = 1; secs < isiz && done; secs++) {
1213 for (j = 0; j < nc; j++) {
1214 if (!grow_one_sector(c + j))
1221 for (j = 0; j < nc; j++) {
1222 if (isecs[c + j] != secs) {
1224 assert(isecs[c + j] == secs);
1225 x = sectx[c + j][secs];
1226 y = secty[c + j][secs];
1228 adj_land_update(x, y);
1234 for (j = 0; j < nc; j++)
1235 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1244 qprint("Only managed to grow %d out of %d island sectors.\n",
1245 is * ni - carry * nc, is * ni);
1250 /****************************************************************************
1252 ****************************************************************************/
1254 create_elevations(void)
1256 init_distance_to_coast();
1261 /* Generic function for finding the distance to the closest sea, land, or
1265 distance_to_what(int x, int y, int flag)
1268 struct hexagon_iter hexit;
1270 for (d = 1; d < 5; ++d) {
1271 hexagon_first(&hexit, x, y, d, &px, &py);
1274 case 0: /* distance to sea */
1275 if (own[px][py] == -1)
1278 case 1: /* distance to land */
1279 if (own[px][py] != -1)
1282 case 2: /* distance to mountain */
1283 if (elev[px][py] == INFINITE_ELEVATION)
1287 } while (hexagon_next(&hexit, &px, &py));
1292 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1294 /* Decide where the mountains go
1299 int max_nm = (pm * MAX(sc, is * 2)) / 100;
1300 int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1301 int highest, where, h, newk, dk;
1302 double elevation, delta;
1304 for (c = 0; c < nc + ni; ++c) {
1307 nm = (pm * ns) / 100;
1309 /* Place the mountains */
1311 for (i = 0; i < ns; ++i) {
1312 off = XYOFFSET(sectx[c][i], secty[c][i]);
1313 dsea[i] = MIN(5, distance[off] + 1);
1314 weight[i] = (total += (dsea[i] * dsea[i]));
1317 for (k = nm, mountain_search = 0;
1318 k && mountain_search < MOUNTAIN_SEARCH_MAX;
1319 ++mountain_search) {
1321 for (i = 0; i < ns; ++i) {
1324 if (r < weight[i] && !elev[x][y] &&
1326 ((!(capx[c] == sectx[c][i] &&
1327 capy[c] == secty[c][i])) &&
1328 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1329 capy[c] == secty[c][i]))))) {
1330 elev[x][y] = INFINITE_ELEVATION;
1337 /* Elevate land that is not mountain and not capital */
1339 for (i = 0; i < ns; ++i)
1340 dmoun[i] = distance_to_mountain();
1341 dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1342 (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1343 100 * INFINITE_ELEVATION;
1344 for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1347 for (i = 0; i < ns; ++i) {
1351 (c >= nc || ((!(capx[c] == sectx[c][i] &&
1352 capy[c] == secty[c][i])) &&
1353 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1354 capy[c] == secty[c][i]))))) {
1355 h = 3 * (5 - dmoun[i]) + dsea[i];
1366 if (newk >= HILLMIN && newk < PLATMIN)
1370 elev[sectx[c][where]][secty[c][where]] = newk;
1373 /* Elevate the mountains and capitals */
1375 elevation = HIGHMIN;
1376 delta = (127.0 - HIGHMIN) / max_nm;
1377 for (i = 0; i < ns; ++i) {
1380 if (elev[x][y] == INFINITE_ELEVATION) {
1382 elev[x][y] = (int)(elevation + 0.5);
1384 * Temporary "useless" die rolls to minimize
1385 * tests/fairland/ churn:
1388 roll0(PLATMIN - HILLMIN);
1390 roll0((256 - HIGHMIN) / 2);
1391 roll0((256 - HIGHMIN) / 2);
1393 } else if (c < nc &&
1394 (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1395 ((new_x(capx[c] + 2) == sectx[c][i] &&
1396 capy[c] == secty[c][i]))))
1397 elev[x][y] = PLATMIN;
1407 for (y = 0; y < WORLD_Y; ++y) {
1408 for (x = y % 2; x < WORLD_X; x += 2) {
1409 off = XYOFFSET(x, y);
1410 if (own[x][y] == -1)
1411 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1417 elev_to_sct_type(int elevation)
1419 if (elevation < LANDMIN)
1421 if (elevation < HILLMIN)
1423 if (elevation < PLATMIN)
1425 if (elevation < HIGHMIN)
1430 /****************************************************************************
1432 ****************************************************************************/
1439 fert = LANDMIN - e + 40;
1440 else if (e < FERT_MAX)
1441 fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1452 oil = (LANDMIN - e) * 2 + roll0(2);
1453 else if (e <= OIL_MAX)
1454 oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1464 if (e >= IRON_MIN && e < HIGHMIN)
1465 iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1475 if (e >= GOLD_MIN) {
1477 gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1479 gold = 100 - 20 * HIGHMIN / e;
1490 if (e >= URAN_MIN && e < HIGHMIN)
1491 uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1498 add_resources(struct sctstr *sct)
1500 sct->sct_fertil = set_fert(sct->sct_elev);
1501 sct->sct_oil = set_oil(sct->sct_elev);
1502 sct->sct_min = set_iron(sct->sct_elev);
1503 sct->sct_gmin = set_gold(sct->sct_elev);
1504 sct->sct_uran = set_uran(sct->sct_elev);
1507 /****************************************************************************
1508 DESIGNATE THE SECTORS
1509 ****************************************************************************/
1517 for (y = 0; y < WORLD_Y; y++) {
1518 for (x = y % 2; x < WORLD_X; x += 2) {
1519 sct = getsectp(x, y);
1520 sct->sct_elev = elev[x][y];
1521 sct->sct_type = elev_to_sct_type(elev[x][y]);
1522 sct->sct_newtype = sct->sct_type;
1523 sct->sct_dterr = own[sct->sct_x][y] + 1;
1524 sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1530 /****************************************************************************
1531 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1532 ****************************************************************************/
1536 int sx, sy, x, y, c, type;
1539 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1544 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1547 type = elev_to_sct_type(elev[x][y]);
1548 if (type == SCT_WATER)
1550 else if (type == SCT_MOUNT)
1555 assert(0 <= c && c < nc);
1556 if ((x == capx[c] || x == new_x(capx[c] + 2))
1558 printf("%c ", numletter[c % 62]);
1568 * Print a map to help visualize own[][].
1569 * This is for debugging.
1576 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1579 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1583 else if (own[x][y] == -1)
1586 putchar(numletter[own[x][y] % 62]);
1593 * Print a map to help visualize elev[][].
1594 * This is for debugging. It expects the terminal to understand
1595 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1598 print_elev_map(void)
1600 int sx, sy, x, y, sat;
1602 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1605 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1609 else if (!elev[x][y])
1611 else if (elev[x][y] < 0) {
1612 sat = 256 + elev[x][y] * 2;
1613 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1614 } else if (elev[x][y] < HIGHMIN / 2) {
1615 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1616 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1617 } else if (elev[x][y] < HIGHMIN) {
1618 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1619 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1621 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1622 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1630 * Print a map to help visualize xzone[].
1631 * This is for debugging.
1634 print_xzone_map(void)
1636 int sx, sy, x, y, off;
1638 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1641 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1643 off = XYOFFSET(x, y);
1646 else if (own[x][y] >= 0)
1648 else if (xzone[off] >= 0)
1649 putchar(numletter[xzone[off] % 62]);
1651 assert(own[x][y] == -1);
1652 putchar(xzone[off] == -1 ? '.' : '!');
1660 * Print a map to help visualize closest[].
1661 * This is for debugging.
1664 print_closest_map(void)
1666 int sx, sy, x, y, off;
1668 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1671 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1673 off = XYOFFSET(x, y);
1676 else if (closest[off] == (natid)-1)
1678 else if (!distance[off]) {
1679 assert(closest[off] == own[x][y]);
1682 putchar(numletter[closest[off] % 62]);
1690 print_distance_map(void)
1692 int sx, sy, x, y, off;
1694 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1697 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1699 off = XYOFFSET(x, y);
1702 else if (closest[off] == (natid)-1)
1704 else if (!distance[off]) {
1705 assert(closest[off] == own[x][y]);
1708 putchar(numletter[distance[off] % 62]);
1716 /***************************************************************************
1717 WRITE A SCRIPT FOR PLACING CAPITALS
1718 ****************************************************************************/
1720 write_newcap_script(void)
1723 FILE *script = fopen(outfile, "w");
1726 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1727 program_name, outfile, strerror(errno));
1731 for (c = 0; c < nc; ++c) {
1732 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1733 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1735 fprintf(script, "add %d visitor visitor v\n", c + 1);
1741 qprint(const char *const fmt, ...)
1747 vfprintf(stdout, fmt, ap);