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().
245 static natid *closest;
246 static unsigned short *distance;
249 * Queue for breadth-first search
251 static int *bfs_queue;
252 static int bfs_queue_head, bfs_queue_tail;
254 static int **elev; /* elevation of the sectors */
255 static int **sectx, **secty; /* the sectors for each continent */
256 static int **sectc; /* which sectors are on the coast? */
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);
279 static void set_coastal_flags(void);
281 static void print_vars(void);
282 static void fl_move(int);
283 static int grow_islands(void);
285 /* Debugging aids: */
286 void print_own_map(void);
287 void print_xzone_map(void);
288 void print_closest_map(void);
289 void print_distance_map(void);
290 void print_elev_map(void);
292 /****************************************************************************
294 ****************************************************************************/
297 main(int argc, char *argv[])
300 char *config_file = NULL;
302 unsigned rnd_seed = 0;
305 program_name = argv[0];
307 while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
310 config_file = optarg;
313 DISTINCT_ISLANDS = 0;
319 rnd_seed = strtoul(optarg, NULL, 10);
329 printf("%s\n\n%s", version, legal);
338 rnd_seed = pick_seed();
341 if (emp_config(config_file) < 0)
345 parse_args(argc - optind, argv + optind);
350 qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
351 qprint("seed is %u\n", rnd_seed);
356 qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
357 qprint("placing capitals...\n");
359 qprint("unstable drift\n");
360 qprint("growing continents...\n");
361 done = grow_continents();
364 qprint("growing islands:");
365 done = grow_islands();
366 } while (!done && ++try < NUMTRIES);
368 fprintf(stderr, "%s: world not large enough for this much land\n",
372 qprint("elevating land...\n");
375 qprint("writing to sectors file...\n");
376 if (!write_newcap_script())
378 if (chdir(gamedir)) {
379 fprintf(stderr, "%s: can't chdir to %s (%s)\n",
380 program_name, gamedir, strerror(errno));
383 if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
386 if (!ef_close(EF_SECTOR))
390 qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
400 puts("Creating a planet with:\n");
401 printf("%d continents\n", nc);
402 printf("continent size: %d\n", sc);
403 printf("number of islands: %d\n", ni);
404 printf("average size of islands: %d\n", is);
405 printf("spike: %d%%\n", sp);
406 printf("%d%% of land is mountain (each continent will have %d mountains)\n",
407 pm, (pm * sc) / 100);
408 printf("minimum distance between continents: %d\n", di);
409 printf("minimum distance from islands to continents: %d\n", id);
410 printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
414 help(char *complaint)
417 fprintf(stderr, "%s: %s\n", program_name, complaint);
418 fprintf(stderr, "Try -h for help.\n");
424 printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
425 " -e CONFIG-FILE configuration file\n"
427 " -i islands may merge\n"
429 " -R SEED seed for random number generator\n"
430 " -s SCRIPT name of script to create (default %s)\n"
431 " -h display this help and exit\n"
432 " -v display version information and exit\n"
433 " NC number of continents\n"
434 " SC continent size\n"
435 " NI number of islands (default NC)\n"
436 " IS average island size (default SC/2)\n"
437 " SP spike percentage: 0 = round, 100 = snake (default %d)\n"
438 " PM percentage of land that is mountain (default %d)\n"
439 " DI minimum distance between continents (default %d)\n"
440 " ID minimum distance from islands to continents (default %d)\n",
441 program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
442 DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
446 parse_args(int argc, char *argv[])
448 int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
451 help("missing arguments");
455 help("too many arguments");
460 fprintf(stderr, "%s: number of continents must be > 0\n",
467 fprintf(stderr, "%s: size of continents must be > 1\n",
478 fprintf(stderr, "%s: number of islands must be >= 0\n",
483 fprintf(stderr, "%s: number of islands must be a multiple of"
484 " the number of continents\n",
492 fprintf(stderr, "%s: size of islands must be > 0\n",
499 if (sp < 0 || sp > 100) {
501 "%s: spike percentage must be between 0 and 100\n",
508 if (pm < 0 || pm > 100) {
510 "%s: mountain percentage must be between 0 and 100\n",
518 fprintf(stderr, "%s: distance between continents must be >= 0\n",
523 fprintf(stderr, "%s: distance between continents too large\n",
532 "%s: distance from islands to continents must be >= 0\n",
538 "%s: distance from islands to continents too large\n",
544 /****************************************************************************
545 VARIABLE INITIALIZATION
546 ****************************************************************************/
549 allocate_memory(void)
553 capx = calloc(nc, sizeof(int));
554 capy = calloc(nc, sizeof(int));
555 own = calloc(WORLD_X, sizeof(int *));
556 adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
557 xzone = malloc(WORLD_SZ() * sizeof(*xzone));
558 seen = calloc(WORLD_SZ(), sizeof(*seen));
559 closest = malloc(WORLD_SZ() * sizeof(*closest));
560 distance = malloc(WORLD_SZ() * sizeof(*distance));
561 bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
562 elev = calloc(WORLD_X, sizeof(int *));
563 for (i = 0; i < WORLD_X; ++i) {
564 own[i] = calloc(WORLD_Y, sizeof(int));
565 elev[i] = calloc(WORLD_Y, sizeof(int));
567 sectx = calloc(nc + ni, sizeof(int *));
568 secty = calloc(nc + ni, sizeof(int *));
569 sectc = calloc(nc + ni, sizeof(int *));
570 isecs = calloc(nc + ni, sizeof(int));
571 weight = calloc(MAX(sc, is * 2), sizeof(int));
572 dsea = calloc(MAX(sc, is * 2), sizeof(int));
573 dmoun = calloc(MAX(sc, is * 2), sizeof(int));
574 for (i = 0; i < nc; ++i) {
575 sectx[i] = calloc(sc, sizeof(int));
576 secty[i] = calloc(sc, sizeof(int));
577 sectc[i] = calloc(sc, sizeof(int));
579 for (i = nc; i < nc + ni; ++i) {
580 sectx[i] = calloc(is * 2, sizeof(int));
581 secty[i] = calloc(is * 2, sizeof(int));
582 sectc[i] = calloc(is * 2, sizeof(int));
592 for (i = 0; i < WORLD_X; ++i) {
593 for (j = 0; j < WORLD_Y; ++j) {
597 memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
600 /****************************************************************************
601 DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
602 ****************************************************************************/
605 * How isolated is capital @j at @newx,@newy?
606 * Return the distance to the closest other capital.
609 iso(int j, int newx, int newy)
614 for (i = 0; i < nc; ++i) {
617 md = mapdist(capx[i], capy[i], newx, newy);
627 * Return 1 for a stable drift, 0 for an unstable one.
634 for (i = 0; i < nc; i++) {
635 capy[i] = (2 * i) / WORLD_X;
636 capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
637 if (capy[i] >= WORLD_Y) {
639 "%s: world not big enough for all the continents\n",
645 for (turns = 0; turns < DRIFT_MAX; ++turns) {
648 for (i = 0; i < nc; ++i)
655 * Has the drift stabilized?
656 * @turns is the number of turns so far.
661 static int mc[STABLE_CYCLE];
662 int i, isod, d = 0, stab = 1;
665 for (i = 0; i < STABLE_CYCLE; i++)
669 if (turns <= DRIFT_BEFORE_CHECK)
672 for (i = 0; i < nc; ++i) {
673 isod = iso(i, capx[i], capy[i]);
678 for (i = 0; i < STABLE_CYCLE; ++i)
682 mc[turns % STABLE_CYCLE] = d;
686 /* This routine does the actual drifting
692 int dir, i, newx, newy;
694 dir = DIR_L + roll0(6);
695 for (i = 0; i < 6; i++) {
698 newx = new_x(capx[j] + diroff[dir][0]);
699 newy = new_y(capy[j] + diroff[dir][1]);
701 if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
709 /****************************************************************************
711 ****************************************************************************/
713 /* Look for a coastal sector of continent c
721 for (i = 0; i < isecs[c]; ++i) {
723 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
724 nx = new_x(sectx[c][i] + diroff[dir][0]);
725 ny = new_y(secty[c][i] + diroff[dir][1]);
726 if (own[nx][ny] == -1)
732 struct hexagon_iter {
737 * Start iterating around @x0,@y0 at distance @d.
738 * Set *x,*y to coordinates of the first sector.
741 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
744 *x = new_x(x0 - 2 * n);
746 iter->dir = DIR_FIRST;
752 * Continue iteration started with hexagon_first().
753 * Set *x,*y to coordinates of the next sector.
754 * Return whether we're back at the first sector, i.e. iteration is
758 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
760 *x = new_x(*x + diroff[iter->dir][0]);
761 *y = new_y(*y + diroff[iter->dir][1]);
763 if (iter->i == iter->n) {
767 return iter->dir <= DIR_LAST;
771 * Is @x,@y in no exclusive zone other than perhaps @c's?
774 xzone_ok(int c, int x, int y)
776 int off = XYOFFSET(x, y);
778 return xzone[off] == c || xzone[off] == -1;
782 * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
785 xzone_around_sector(int c, int x, int y, int dist)
788 struct hexagon_iter hexit;
790 assert(xzone_ok(c, x, y));
792 xzone[XYOFFSET(x, y)] = c;
793 for (d = 1; d <= dist; d++) {
794 hexagon_first(&hexit, x, y, d, &x1, &y1);
796 off = XYOFFSET(x1, y1);
797 if (xzone[off] == -1)
799 else if (xzone[off] != c)
801 } while (hexagon_next(&hexit, &x1, &y1));
806 * Add sectors within distance @dist to island @c's exclusive zone.
809 xzone_around_island(int c, int dist)
813 for (i = 0; i < isecs[c]; i++)
814 xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
818 * Initialize exclusive zones around @n islands.
825 for (i = 0; i < WORLD_SZ(); i++)
828 for (c = 0; c < n; c++)
829 xzone_around_island(c, id);
833 * Initialize breadth-first search.
840 for (i = 0; i < WORLD_SZ(); i++) {
842 distance[i] = USHRT_MAX;
845 bfs_queue_head = bfs_queue_tail = 0;
849 * Add sector @x,@y to the BFS queue.
850 * It's closest to @c, with distance @dist.
853 bfs_enqueue(int c, int x, int y, int dist)
855 int off = XYOFFSET(x, y);
857 assert(dist < distance[off]);
859 distance[off] = dist;
860 bfs_queue[bfs_queue_tail] = off;
862 if (bfs_queue_tail >= WORLD_SZ())
864 assert(bfs_queue_tail != bfs_queue_head);
868 * Search breadth-first until the queue is empty.
873 int off, dist, i, noff, nx, ny;
876 while (bfs_queue_head != bfs_queue_tail) {
877 off = bfs_queue[bfs_queue_head];
879 if (bfs_queue_head >= WORLD_SZ())
881 dist = distance[off] + 1;
882 sctoff2xy(&x, &y, off);
883 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
884 nx = new_x(x + diroff[i][0]);
885 ny = new_y(y + diroff[i][1]);
886 noff = XYOFFSET(nx, ny);
887 if (dist < distance[noff]) {
888 bfs_enqueue(closest[off], nx, ny, dist);
889 } else if (distance[noff] == dist) {
890 if (closest[off] != closest[noff])
891 closest[noff] = (natid)-1;
893 assert(distance[noff] < dist);
899 * Add island @c's coastal sectors to the BFS queue, with distance 0.
902 bfs_enqueue_island(int c)
906 for (i = 0; i < isecs[c]; i++) {
908 bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
913 * Enqueue spheres of influence borders for breadth-first search.
916 bfs_enqueue_border(void)
918 int x, y, off, dir, nx, ny, noff;
920 for (y = 0; y < WORLD_Y; y++) {
921 for (x = y % 2; x < WORLD_X; x += 2) {
922 off = XYOFFSET(x, y);
923 if (distance[off] <= id + 1)
925 if (closest[off] == (natid)-1)
927 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
928 nx = new_x(x + diroff[dir][0]);
929 ny = new_y(y + diroff[dir][1]);
930 noff = XYOFFSET(nx, ny);
931 if (closest[noff] != closest[off]) {
932 bfs_enqueue(closest[off], x, y, id + 1);
941 * Compute spheres of influence
942 * A continent's sphere of influence is the set of sectors closer to
943 * it than to any other continent.
944 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
945 * -1 if no single continent is closest.
946 * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
947 * closest coastal land sector and the distance to just outside the
948 * sphere of influence plus @id. For sea sectors within a continent's
949 * sphere of influence, distance[off] - id is the distance to the
950 * border of the area where additional islands can be placed.
953 init_spheres_of_influence(void)
958 for (c = 0; c < nc; c++)
959 bfs_enqueue_island(c);
961 bfs_enqueue_border();
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))
1112 for (c = 0; c < nc; ++c)
1116 qprint("Only managed to grow %d out of %d sectors.\n",
1121 /****************************************************************************
1123 ****************************************************************************/
1126 * Place additional island @c's first sector.
1127 * Return 1 on success, 0 on error.
1130 place_island(int c, int isiz)
1132 int n, x, y, d, w, newx, newy;
1136 for (y = 0; y < WORLD_Y; y++) {
1137 for (x = y % 2; x < WORLD_X; x += 2) {
1138 if (can_grow_at(c, x, y)) {
1139 d = distance[XYOFFSET(x, y)];
1141 w = (d - id) * (d - id);
1142 n += MIN(w, (isiz + 2) / 3);
1152 add_sector(c, newx, newy);
1157 int_cmp(const void *a, const void *b)
1159 return *(int *)b - *(int *)a;
1166 int *isiz = malloc(n * sizeof(*isiz));
1171 for (i = 1; i < n; i++) {
1174 isiz[i] = is + r1 - r0;
1178 qsort(isiz, n, sizeof(*isiz), int_cmp);
1183 * Grow the additional islands.
1184 * Return 1 on success, 0 on error.
1189 int *island_size = size_islands();
1190 int xzone_valid = 0;
1192 int i, j, c, done, secs, isiz, x, y;
1194 init_spheres_of_influence();
1196 for (i = 0; i < ni / nc; i++) {
1202 carry += island_size[i];
1203 isiz = MIN(2 * is, carry);
1205 for (j = 0; j < nc; j++) {
1207 if (!place_island(c + j, isiz)) {
1208 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1215 for (secs = 1; secs < isiz && done; secs++) {
1216 for (j = 0; j < nc; j++) {
1217 if (!grow_one_sector(c + j))
1224 for (j = 0; j < nc; j++) {
1225 if (isecs[c + j] != secs) {
1227 assert(isecs[c + j] == secs);
1228 x = sectx[c + j][secs];
1229 y = secty[c + j][secs];
1231 adj_land_update(x, y);
1237 for (j = 0; j < nc; j++)
1238 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1247 qprint("Only managed to grow %d out of %d island sectors.\n",
1248 is * ni - carry * nc, is * ni);
1250 for (c = nc; c < nc + ni; c++)
1256 /****************************************************************************
1258 ****************************************************************************/
1260 create_elevations(void)
1264 for (i = 0; i < WORLD_X; i++) {
1265 for (j = 0; j < WORLD_Y; j++)
1266 elev[i][j] = -INFINITE_ELEVATION;
1272 /* Generic function for finding the distance to the closest sea, land, or
1276 distance_to_what(int x, int y, int flag)
1279 struct hexagon_iter hexit;
1281 for (d = 1; d < 5; ++d) {
1282 hexagon_first(&hexit, x, y, d, &px, &py);
1285 case 0: /* distance to sea */
1286 if (own[px][py] == -1)
1289 case 1: /* distance to land */
1290 if (own[px][py] != -1)
1293 case 2: /* distance to mountain */
1294 if (elev[px][py] == INFINITE_ELEVATION)
1298 } while (hexagon_next(&hexit, &px, &py));
1303 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1304 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1306 /* Decide where the mountains go
1311 int i, mountain_search, k, c, total, ns, nm, r, x, y;
1312 int highest, where, h, newk, dk;
1314 for (c = 0; c < nc + ni; ++c) {
1317 nm = (pm * ns) / 100;
1319 /* Place the mountains */
1321 for (i = 0; i < ns; ++i) {
1322 dsea[i] = distance_to_sea();
1323 weight[i] = (total += (dsea[i] * dsea[i]));
1326 for (k = nm, mountain_search = 0;
1327 k && mountain_search < MOUNTAIN_SEARCH_MAX;
1328 ++mountain_search) {
1330 for (i = 0; i < ns; ++i) {
1333 if (r < weight[i] && elev[x][y] == -INFINITE_ELEVATION &&
1335 ((!(capx[c] == sectx[c][i] &&
1336 capy[c] == secty[c][i])) &&
1337 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1338 capy[c] == secty[c][i]))))) {
1339 elev[x][y] = INFINITE_ELEVATION;
1346 /* Elevate land that is not mountain and not capital */
1348 for (i = 0; i < ns; ++i)
1349 dmoun[i] = distance_to_mountain();
1350 dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1351 (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1352 100 * INFINITE_ELEVATION;
1353 for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1356 for (i = 0; i < ns; ++i) {
1359 if (elev[x][y] == -INFINITE_ELEVATION &&
1360 (c >= nc || ((!(capx[c] == sectx[c][i] &&
1361 capy[c] == secty[c][i])) &&
1362 (!(new_x(capx[c] + 2) == sectx[c][i] &&
1363 capy[c] == secty[c][i]))))) {
1364 h = 3 * (5 - dmoun[i]) + dsea[i];
1375 if (newk >= HILLMIN && newk < PLATMIN)
1379 elev[sectx[c][where]][secty[c][where]] = newk;
1382 /* Elevate the mountains and capitals */
1384 for (i = 0; i < ns; ++i) {
1387 if (elev[x][y] == INFINITE_ELEVATION) {
1389 elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1391 elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1392 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;
1402 #define distance_to_land() distance_to_what(x, y, 1)
1409 for (y = 0; y < WORLD_Y; ++y) {
1410 for (x = y % 2; x < WORLD_X; x += 2) {
1411 if (elev[x][y] == -INFINITE_ELEVATION)
1412 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1418 elev_to_sct_type(int elevation)
1420 if (elevation < LANDMIN)
1422 if (elevation < HILLMIN)
1424 if (elevation < PLATMIN)
1426 if (elevation < HIGHMIN)
1431 /****************************************************************************
1433 ****************************************************************************/
1440 fert = LANDMIN - e + 40;
1441 else if (e < FERT_MAX)
1442 fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1453 oil = (LANDMIN - e) * 2 + roll0(2);
1454 else if (e <= OIL_MAX)
1455 oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1465 if (e >= IRON_MIN && e < HIGHMIN)
1466 iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1476 if (e >= GOLD_MIN) {
1478 gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1480 gold = 100 - 20 * HIGHMIN / e;
1491 if (e >= URAN_MIN && e < HIGHMIN)
1492 uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1499 add_resources(struct sctstr *sct)
1501 sct->sct_fertil = set_fert(sct->sct_elev);
1502 sct->sct_oil = set_oil(sct->sct_elev);
1503 sct->sct_min = set_iron(sct->sct_elev);
1504 sct->sct_gmin = set_gold(sct->sct_elev);
1505 sct->sct_uran = set_uran(sct->sct_elev);
1508 /****************************************************************************
1509 DESIGNATE THE SECTORS
1510 ****************************************************************************/
1518 for (y = 0; y < WORLD_Y; y++) {
1519 for (x = y % 2; x < WORLD_X; x += 2) {
1520 sct = getsectp(x, y);
1521 sct->sct_elev = elev[x][y];
1522 sct->sct_type = elev_to_sct_type(elev[x][y]);
1523 sct->sct_newtype = sct->sct_type;
1524 sct->sct_dterr = own[sct->sct_x][y] + 1;
1528 set_coastal_flags();
1531 /****************************************************************************
1532 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1533 ****************************************************************************/
1537 int sx, sy, x, y, c, type;
1540 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1545 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1548 type = elev_to_sct_type(elev[x][y]);
1549 if (type == SCT_WATER)
1551 else if (type == SCT_MOUNT)
1556 assert(0 <= c && c < nc);
1557 if ((x == capx[c] || x == new_x(capx[c] + 2))
1559 printf("%c ", numletter[c % 62]);
1569 * Print a map to help visualize own[][].
1570 * This is for debugging.
1577 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1580 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1584 else if (own[x][y] == -1)
1587 putchar(numletter[own[x][y] % 62]);
1594 * Print a map to help visualize elev[][].
1595 * This is for debugging. It expects the terminal to understand
1596 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1599 print_elev_map(void)
1601 int sx, sy, x, y, sat;
1603 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1606 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1610 else if (!elev[x][y])
1612 else if (elev[x][y] < 0) {
1613 sat = 256 + elev[x][y] * 2;
1614 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1615 } else if (elev[x][y] < HIGHMIN / 2) {
1616 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1617 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1618 } else if (elev[x][y] < HIGHMIN) {
1619 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1620 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1622 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1623 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1631 * Print a map to help visualize xzone[].
1632 * This is for debugging.
1635 print_xzone_map(void)
1637 int sx, sy, x, y, off;
1639 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1642 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1644 off = XYOFFSET(x, y);
1647 else if (own[x][y] >= 0)
1649 else if (xzone[off] >= 0)
1650 putchar(numletter[xzone[off] % 62]);
1652 assert(own[x][y] == -1);
1653 putchar(xzone[off] == -1 ? '.' : '!');
1661 * Print a map to help visualize closest[].
1662 * This is for debugging.
1665 print_closest_map(void)
1667 int sx, sy, x, y, off;
1669 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1672 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1674 off = XYOFFSET(x, y);
1677 else if (closest[off] == (natid)-1)
1679 else if (!distance[off]) {
1680 assert(closest[off] == own[x][y]);
1683 putchar(numletter[closest[off] % 62]);
1691 print_distance_map(void)
1693 int sx, sy, x, y, off;
1695 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1698 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1700 off = XYOFFSET(x, y);
1703 else if (closest[off] == (natid)-1)
1705 else if (!distance[off]) {
1706 assert(closest[off] == own[x][y]);
1709 putchar(numletter[distance[off] % 62]);
1717 /***************************************************************************
1718 WRITE A SCRIPT FOR PLACING CAPITALS
1719 ****************************************************************************/
1721 write_newcap_script(void)
1724 FILE *script = fopen(outfile, "w");
1727 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1728 program_name, outfile, strerror(errno));
1732 for (c = 0; c < nc; ++c) {
1733 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1734 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1736 fprintf(script, "add %d visitor visitor v\n", c + 1);
1742 qprint(const char *const fmt, ...)
1748 vfprintf(stdout, fmt, ap);
1754 set_coastal_flags(void)
1759 for (i = 0; i < nc + ni; ++i) {
1760 for (j = 0; j < isecs[i]; j++) {
1761 sp = getsectp(sectx[i][j], secty[i][j]);
1762 sp->sct_coastal = sectc[i][j];