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 * First, use a simple random hill algorithm to assign raw elevations:
92 * initialize elevation to zero, then randomly raise circular hills on
93 * land / lower circular depressions at sea. Their size and height
94 * depends on the distance to the coast.
96 * Then, elevate islands one after the other.
98 * Set the capitals' elevation to a fixed value. Process the
99 * remaining sectors in order of increasing raw elevation, first
100 * non-mountains, then mountains. Non-mountain elevation starts at 1,
101 * and increases linearly to just below "high" elevation. Mountain
102 * elevation starts at "high" elevation, and increases linearly.
104 * This gives islands of the same size the same set of elevations.
105 * Larger islands get more and taller mountains.
107 * Finally, elevate sea: normalize the raw elevations to [-127:-1].
111 * Sector resources are simple functions of elevation. You can alter
112 * iron_conf[], gold_conf[], fert_conf[], oil_conf[], and uran_conf[]
127 #include "prototypes.h"
132 /* do not change these defines */
133 #define LANDMIN 1 /* plate altitude for normal land */
134 #define PLATMIN 36 /* plate altitude for plateau */
135 #define HIGHMIN 98 /* plate altitude for mountains */
138 * Resource configuration
140 * Resources are determined by elevation. The map from elevation to
141 * resource is defined as a linear interpolation of resource data
142 * points (elev, res) defined in the tables below. Elevations range
143 * from -127 to 127, and resource values from 0 to 100.
146 struct resource_point {
151 struct resource_point iron_conf[] = {
154 { 84, 120.0 * 63 / 76 },
156 { HIGHMIN - 1, 100 },
160 struct resource_point gold_conf[] = {
167 struct resource_point fert_conf[] = {
173 { 11, 120.0 * 45 / 55 },
177 struct resource_point oil_conf[] = {
183 { 7, 120.0 * 27 / 33 },
187 struct resource_point uran_conf[] = {
195 static void qprint(const char * const fmt, ...)
196 ATTRIBUTE((format (printf, 1, 2)));
199 * Program arguments and options
201 static char *program_name;
202 static int nc, sc; /* number and size of continents */
203 static int ni, is; /* number and size of islands */
204 #define DEFAULT_SPIKE 10
205 static int sp = DEFAULT_SPIKE; /* spike percentage */
206 #define DEFAULT_MOUNTAIN 0
207 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
208 #define DEFAULT_CONTDIST 2
209 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
210 #define DEFAULT_ISLDIST 1
211 static int id = DEFAULT_ISLDIST; /* ... continents and islands */
212 /* don't let the islands crash into each other.
213 1 = don't merge, 0 = merge. */
214 static int DISTINCT_ISLANDS = 1;
216 #define DEFAULT_OUTFILE_NAME "newcap_script"
217 static const char *outfile = DEFAULT_OUTFILE_NAME;
219 #define STABLE_CYCLE 4 /* stability required for perterbed capitals */
220 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
221 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
226 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
227 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
231 * isecs[i] is the size of the i-th island.
235 static int *capx, *capy; /* location of the nc capitals */
237 static int **own; /* owner of the sector. -1 means water */
240 * Adjacent land sectors
241 * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
242 * to x, y in direction d is land.
244 static unsigned char *adj_land;
248 * elev[XYOFFSET(x, y)] is x,y's elevation.
254 * Each island is surrounded by an exclusive zone where only it may
255 * grow. The width of the zone depends on minimum distances.
256 * While growing continents, it is @di sectors wide.
257 * While growing additional islands, it is @id sectors wide.
258 * DISTINCT_ISLANDS nullifies the exclusive zone then.
259 * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
260 * zone, a (non-negative) island number when it is in that island's
261 * exclusive zone and no other, and -2 when it is in multiple
267 * Set of sectors seen already
268 * Increment @cur_seen to empty the set of sectors seen, set
269 * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
271 static unsigned *seen;
272 static unsigned cur_seen;
275 * Closest continent and "distance"
276 * closest[XYOFFSET(x, y)] is the closest continent's number.
277 * distance[] is complicated; see init_spheres_of_influence() and
278 * init_distance_to_coast().
280 static natid *closest;
281 static unsigned short *distance;
284 * Queue for breadth-first search
286 static int *bfs_queue;
287 static int bfs_queue_head, bfs_queue_tail;
289 static int **sectx, **secty; /* the sectors for each continent */
291 #define NUMTRIES 10 /* keep trying to grow this many times */
293 static const char *numletter =
294 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
296 static void help(char *);
297 static void usage(void);
298 static void parse_args(int argc, char *argv[]);
299 static void allocate_memory(void);
300 static void init(void);
301 static int drift(void);
302 static int grow_continents(void);
303 static void create_elevations(void);
304 static void write_sects(void);
305 static void output(void);
306 static int write_newcap_script(void);
307 static int stable(int);
308 static void elevate_prep(void);
309 static void elevate_land(void);
310 static void elevate_sea(void);
312 static void print_vars(void);
313 static void fl_move(int);
314 static int grow_islands(void);
316 /* Debugging aids: */
317 void print_own_map(void);
318 void print_xzone_map(void);
319 void print_closest_map(void);
320 void print_distance_map(void);
321 void print_elev_map(void);
323 /****************************************************************************
325 ****************************************************************************/
328 main(int argc, char *argv[])
331 char *config_file = NULL;
333 unsigned rnd_seed = 0;
336 program_name = argv[0];
338 while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
341 config_file = optarg;
344 DISTINCT_ISLANDS = 0;
350 rnd_seed = strtoul(optarg, NULL, 10);
360 printf("%s\n\n%s", version, legal);
369 rnd_seed = pick_seed();
372 if (emp_config(config_file) < 0)
376 parse_args(argc - optind, argv + optind);
381 qprint("\n #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
382 qprint("seed is %u\n", rnd_seed);
387 qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
388 qprint("placing capitals...\n");
390 qprint("unstable drift\n");
391 qprint("growing continents...\n");
392 done = grow_continents();
395 qprint("growing islands:");
396 done = grow_islands();
397 } while (!done && ++try < NUMTRIES);
399 fprintf(stderr, "%s: world not large enough for this much land\n",
403 qprint("elevating land...\n");
406 qprint("writing to sectors file...\n");
407 if (!write_newcap_script())
409 if (chdir(gamedir)) {
410 fprintf(stderr, "%s: can't chdir to %s (%s)\n",
411 program_name, gamedir, strerror(errno));
414 if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
417 if (!ef_close(EF_SECTOR))
421 qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
431 puts("Creating a planet with:\n");
432 printf("%d continents\n", nc);
433 printf("continent size: %d\n", sc);
434 printf("number of islands: %d\n", ni);
435 printf("average size of islands: %d\n", is);
436 printf("spike: %d%%\n", sp);
437 printf("%d%% of land is mountain (each continent will have %d mountains)\n",
438 pm, (pm * sc) / 100);
439 printf("minimum distance between continents: %d\n", di);
440 printf("minimum distance from islands to continents: %d\n", id);
441 printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
445 help(char *complaint)
448 fprintf(stderr, "%s: %s\n", program_name, complaint);
449 fprintf(stderr, "Try -h for help.\n");
455 printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
456 " -e CONFIG-FILE configuration file\n"
458 " -i islands may merge\n"
460 " -R SEED seed for random number generator\n"
461 " -s SCRIPT name of script to create (default %s)\n"
462 " -h display this help and exit\n"
463 " -v display version information and exit\n"
464 " NC number of continents\n"
465 " SC continent size\n"
466 " NI number of islands (default NC)\n"
467 " IS average island size (default SC/2)\n"
468 " SP spike percentage: 0 = round, 100 = snake (default %d)\n"
469 " PM percentage of land that is mountain (default %d)\n"
470 " DI minimum distance between continents (default %d)\n"
471 " ID minimum distance from islands to continents (default %d)\n",
472 program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
473 DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
477 parse_args(int argc, char *argv[])
479 int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
482 help("missing arguments");
486 help("too many arguments");
491 fprintf(stderr, "%s: number of continents must be > 0\n",
498 fprintf(stderr, "%s: size of continents must be > 1\n",
509 fprintf(stderr, "%s: number of islands must be >= 0\n",
514 fprintf(stderr, "%s: number of islands must be a multiple of"
515 " the number of continents\n",
523 fprintf(stderr, "%s: size of islands must be > 0\n",
530 if (sp < 0 || sp > 100) {
532 "%s: spike percentage must be between 0 and 100\n",
539 if (pm < 0 || pm > 100) {
541 "%s: mountain percentage must be between 0 and 100\n",
549 fprintf(stderr, "%s: distance between continents must be >= 0\n",
554 fprintf(stderr, "%s: distance between continents too large\n",
563 "%s: distance from islands to continents must be >= 0\n",
569 "%s: distance from islands to continents too large\n",
575 /****************************************************************************
576 VARIABLE INITIALIZATION
577 ****************************************************************************/
580 allocate_memory(void)
584 capx = calloc(nc, sizeof(int));
585 capy = calloc(nc, sizeof(int));
586 own = calloc(WORLD_X, sizeof(int *));
587 adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
588 elev = calloc(WORLD_SZ(), sizeof(*elev));
589 xzone = malloc(WORLD_SZ() * sizeof(*xzone));
590 seen = calloc(WORLD_SZ(), sizeof(*seen));
591 closest = malloc(WORLD_SZ() * sizeof(*closest));
592 distance = malloc(WORLD_SZ() * sizeof(*distance));
593 bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
594 for (i = 0; i < WORLD_X; ++i) {
595 own[i] = calloc(WORLD_Y, sizeof(int));
597 sectx = calloc(nc + ni, sizeof(int *));
598 secty = calloc(nc + ni, sizeof(int *));
599 isecs = calloc(nc + ni, sizeof(int));
600 for (i = 0; i < nc; ++i) {
601 sectx[i] = calloc(sc, sizeof(int));
602 secty[i] = calloc(sc, sizeof(int));
604 for (i = nc; i < nc + ni; ++i) {
605 sectx[i] = calloc(is * 2, sizeof(int));
606 secty[i] = calloc(is * 2, sizeof(int));
616 for (i = 0; i < WORLD_X; ++i) {
617 for (j = 0; j < WORLD_Y; ++j) {
621 memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
624 /****************************************************************************
625 DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
626 ****************************************************************************/
629 * How isolated is capital @j at @newx,@newy?
630 * Return the distance to the closest other capital.
633 iso(int j, int newx, int newy)
638 for (i = 0; i < nc; ++i) {
641 md = mapdist(capx[i], capy[i], newx, newy);
651 * Return 1 for a stable drift, 0 for an unstable one.
658 for (i = 0; i < nc; i++) {
659 capy[i] = (2 * i) / WORLD_X;
660 capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
661 if (capy[i] >= WORLD_Y) {
663 "%s: world not big enough for all the continents\n",
669 for (turns = 0; turns < DRIFT_MAX; ++turns) {
672 for (i = 0; i < nc; ++i)
679 * Has the drift stabilized?
680 * @turns is the number of turns so far.
685 static int mc[STABLE_CYCLE];
686 int i, isod, d = 0, stab = 1;
689 for (i = 0; i < STABLE_CYCLE; i++)
693 if (turns <= DRIFT_BEFORE_CHECK)
696 for (i = 0; i < nc; ++i) {
697 isod = iso(i, capx[i], capy[i]);
702 for (i = 0; i < STABLE_CYCLE; ++i)
706 mc[turns % STABLE_CYCLE] = d;
710 /* This routine does the actual drifting
716 int dir, i, newx, newy;
718 dir = DIR_L + roll0(6);
719 for (i = 0; i < 6; i++) {
722 newx = new_x(capx[j] + diroff[dir][0]);
723 newy = new_y(capy[j] + diroff[dir][1]);
725 if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
733 /****************************************************************************
735 ****************************************************************************/
738 is_coastal(int x, int y)
740 return adj_land[XYOFFSET(x, y)]
741 != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
744 struct hexagon_iter {
749 * Start iterating around @x0,@y0 at distance @d.
750 * Set *x,*y to coordinates of the first sector.
753 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
756 *x = new_x(x0 - 2 * n);
758 iter->dir = DIR_FIRST;
764 * Continue iteration started with hexagon_first().
765 * Set *x,*y to coordinates of the next sector.
766 * Return whether we're back at the first sector, i.e. iteration is
770 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
772 *x = new_x(*x + diroff[iter->dir][0]);
773 *y = new_y(*y + diroff[iter->dir][1]);
775 if (iter->i == iter->n) {
779 return iter->dir <= DIR_LAST;
783 * Is @x,@y in no exclusive zone other than perhaps @c's?
786 xzone_ok(int c, int x, int y)
788 int off = XYOFFSET(x, y);
790 return xzone[off] == c || xzone[off] == -1;
794 * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
797 xzone_around_sector(int c, int x, int y, int dist)
800 struct hexagon_iter hexit;
802 assert(xzone_ok(c, x, y));
804 xzone[XYOFFSET(x, y)] = c;
805 for (d = 1; d <= dist; d++) {
806 hexagon_first(&hexit, x, y, d, &x1, &y1);
808 off = XYOFFSET(x1, y1);
809 if (xzone[off] == -1)
811 else if (xzone[off] != c)
813 } while (hexagon_next(&hexit, &x1, &y1));
818 * Add sectors within distance @dist to island @c's exclusive zone.
821 xzone_around_island(int c, int dist)
825 for (i = 0; i < isecs[c]; i++)
826 xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
830 * Initialize exclusive zones around @n islands.
837 for (i = 0; i < WORLD_SZ(); i++)
840 for (c = 0; c < n; c++)
841 xzone_around_island(c, id);
845 * Initialize breadth-first search.
852 for (i = 0; i < WORLD_SZ(); i++) {
854 distance[i] = USHRT_MAX;
857 bfs_queue_head = bfs_queue_tail = 0;
861 * Add sector @x,@y to the BFS queue.
862 * It's closest to @c, with distance @dist.
865 bfs_enqueue(int c, int x, int y, int dist)
867 int off = XYOFFSET(x, y);
869 assert(dist < distance[off]);
871 distance[off] = dist;
872 bfs_queue[bfs_queue_tail] = off;
874 if (bfs_queue_tail >= WORLD_SZ())
876 assert(bfs_queue_tail != bfs_queue_head);
880 * Search breadth-first until the queue is empty.
885 int off, dist, i, noff, nx, ny;
888 while (bfs_queue_head != bfs_queue_tail) {
889 off = bfs_queue[bfs_queue_head];
891 if (bfs_queue_head >= WORLD_SZ())
893 dist = distance[off] + 1;
894 sctoff2xy(&x, &y, off);
895 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
896 nx = new_x(x + diroff[i][0]);
897 ny = new_y(y + diroff[i][1]);
898 noff = XYOFFSET(nx, ny);
899 if (dist < distance[noff]) {
900 bfs_enqueue(closest[off], nx, ny, dist);
901 } else if (distance[noff] == dist) {
902 if (closest[off] != closest[noff])
903 closest[noff] = (natid)-1;
905 assert(distance[noff] < dist);
911 * Add island @c's coastal sectors to the BFS queue, with distance 0.
914 bfs_enqueue_island(int c)
918 for (i = 0; i < isecs[c]; i++) {
919 if (is_coastal(sectx[c][i], secty[c][i]))
920 bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
925 * Enqueue spheres of influence borders for breadth-first search.
928 bfs_enqueue_border(void)
930 int x, y, off, dir, nx, ny, noff;
932 for (y = 0; y < WORLD_Y; y++) {
933 for (x = y % 2; x < WORLD_X; x += 2) {
934 off = XYOFFSET(x, y);
935 if (distance[off] <= id + 1)
937 if (closest[off] == (natid)-1)
939 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
940 nx = new_x(x + diroff[dir][0]);
941 ny = new_y(y + diroff[dir][1]);
942 noff = XYOFFSET(nx, ny);
943 if (closest[noff] != closest[off]) {
944 bfs_enqueue(closest[off], x, y, id + 1);
953 * Compute spheres of influence
954 * A continent's sphere of influence is the set of sectors closer to
955 * it than to any other continent.
956 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
957 * -1 if no single continent is closest.
958 * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
959 * closest coastal land sector and the distance to just outside the
960 * sphere of influence plus @id. For sea sectors within a continent's
961 * sphere of influence, distance[off] - id is the distance to the
962 * border of the area where additional islands can be placed.
965 init_spheres_of_influence(void)
970 for (c = 0; c < nc; c++)
971 bfs_enqueue_island(c);
973 bfs_enqueue_border();
978 * Precompute distance to coast
979 * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
981 * Set closest[XYOFFSET(x, y)] to the closest continent's number,
982 * -1 if no single continent is closest.
985 init_distance_to_coast(void)
990 for (c = 0; c < nc + ni; c++)
991 bfs_enqueue_island(c);
996 * Is @x,@y in the same sphere of influence as island @c?
997 * Always true when @c is a continent.
1000 is_in_sphere(int c, int x, int y)
1002 return c < nc || closest[XYOFFSET(x, y)] == c % nc;
1006 * Can island @c grow at @x,@y?
1009 can_grow_at(int c, int x, int y)
1011 return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
1015 adj_land_update(int x, int y)
1017 int is_land = own[x][y] != -1;
1018 int dir, nx, ny, noff;
1020 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1021 nx = new_x(x + diroff[dir][0]);
1022 ny = new_y(y + diroff[dir][1]);
1023 noff = XYOFFSET(nx, ny);
1025 adj_land[noff] |= 1u << DIR_BACK(dir);
1027 adj_land[noff] &= ~(1u << DIR_BACK(dir));
1032 add_sector(int c, int x, int y)
1034 assert(own[x][y] == -1);
1035 xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1036 sectx[c][isecs[c]] = x;
1037 secty[c][isecs[c]] = y;
1040 adj_land_update(x, y);
1044 grow_weight(int c, int x, int y, int spike)
1049 * #Land neighbors is #bits set in adj_land[].
1050 * Count them Brian Kernighan's way.
1053 for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1055 assert(n > 0 && n < 7);
1058 return (6 - n) * (6 - n);
1064 grow_one_sector(int c)
1066 int spike = roll0(100) < sp;
1067 int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1069 assert(cur_seen < UINT_MAX);
1074 for (i = 0; i < isecs[c]; i++) {
1077 off = XYOFFSET(x, y);
1079 for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1080 if (adj_land[off] & (1u << dir))
1082 nx = new_x(x + diroff[dir][0]);
1083 ny = new_y(y + diroff[dir][1]);
1084 noff = XYOFFSET(nx, ny);
1085 if (seen[noff] == cur_seen)
1087 assert(seen[noff] < cur_seen);
1088 seen[noff] = cur_seen;
1089 if (!can_grow_at(c, nx, ny))
1091 w = grow_weight(c, nx, ny, spike);
1092 assert(wsum < INT_MAX - w);
1094 if (roll0(wsum) < w) {
1104 add_sector(c, newx, newy);
1109 * Grow the continents.
1110 * Return 1 on success, 0 on error.
1113 grow_continents(void)
1120 for (c = 0; c < nc; ++c) {
1122 if (!can_grow_at(c, capx[c], capy[c])
1123 || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1127 add_sector(c, capx[c], capy[c]);
1128 add_sector(c, new_x(capx[c] + 2), capy[c]);
1132 qprint("No room for continents\n");
1136 for (secs = 2; secs < sc && done; secs++) {
1137 for (c = 0; c < nc; ++c) {
1138 if (!grow_one_sector(c))
1144 qprint("Only managed to grow %d out of %d sectors.\n",
1149 /****************************************************************************
1151 ****************************************************************************/
1154 * Place additional island @c's first sector.
1155 * Return 1 on success, 0 on error.
1158 place_island(int c, int isiz)
1160 int n, x, y, d, w, newx, newy;
1164 for (y = 0; y < WORLD_Y; y++) {
1165 for (x = y % 2; x < WORLD_X; x += 2) {
1166 if (can_grow_at(c, x, y)) {
1167 d = distance[XYOFFSET(x, y)];
1169 w = (d - id) * (d - id);
1170 n += MIN(w, (isiz + 2) / 3);
1180 add_sector(c, newx, newy);
1185 int_cmp(const void *a, const void *b)
1187 return *(int *)b - *(int *)a;
1194 int *isiz = malloc(n * sizeof(*isiz));
1199 for (i = 1; i < n; i++) {
1202 isiz[i] = is + r1 - r0;
1206 qsort(isiz, n, sizeof(*isiz), int_cmp);
1211 * Grow the additional islands.
1212 * Return 1 on success, 0 on error.
1217 int *island_size = size_islands();
1218 int xzone_valid = 0;
1220 int i, j, c, done, secs, isiz, x, y;
1222 init_spheres_of_influence();
1224 for (i = 0; i < ni / nc; i++) {
1230 carry += island_size[i];
1231 isiz = MIN(2 * is, carry);
1233 for (j = 0; j < nc; j++) {
1235 if (!place_island(c + j, isiz)) {
1236 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1243 for (secs = 1; secs < isiz && done; secs++) {
1244 for (j = 0; j < nc; j++) {
1245 if (!grow_one_sector(c + j))
1252 for (j = 0; j < nc; j++) {
1253 if (isecs[c + j] != secs) {
1255 assert(isecs[c + j] == secs);
1256 x = sectx[c + j][secs];
1257 y = secty[c + j][secs];
1259 adj_land_update(x, y);
1265 for (j = 0; j < nc; j++)
1266 qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1275 qprint("Only managed to grow %d out of %d island sectors.\n",
1276 is * ni - carry * nc, is * ni);
1281 /****************************************************************************
1283 ****************************************************************************/
1285 create_elevations(void)
1293 elev_cmp(const void *p, const void *q)
1297 int delev = elev[a] - elev[b];
1299 return delev ? delev : a - b;
1305 int n = WORLD_SZ() * 8;
1306 int off0, r, sign, elevation, d, x1, y1, off1;
1308 struct hexagon_iter hexit;
1310 init_distance_to_coast();
1313 off0 = roll0(WORLD_SZ());
1314 sctoff2xy(&x0, &y0, off0);
1315 if (own[x0][y0] == -1) {
1316 r = roll(MIN(3, distance[off0]));
1319 r = roll(MIN(3, distance[off0]) + 1);
1322 elevation = elev[off0] + sign * r * r;
1323 elev[off0] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1325 for (d = 1; d < r; d++) {
1326 hexagon_first(&hexit, x0, y0, d, &x1, &y1);
1328 off1 = XYOFFSET(x1, y1);
1329 elevation = elev[off1] + sign * (r * r - d * d);
1330 elev[off1] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1332 } while (hexagon_next(&hexit, &x1, &y1));
1340 int *off = malloc(MAX(sc, is * 2) * sizeof(*off));
1341 int max_nm = (pm * MAX(sc, is * 2)) / 100;
1342 int c, nm, i0, n, i;
1343 double elevation, delta;
1345 for (c = 0; c < nc + ni; c++) {
1346 nm = (pm * isecs[c]) / 100;
1347 i0 = c < nc ? 2 : 0;
1349 for (i = 0; i < i0; i++)
1350 elev[XYOFFSET(sectx[c][i], secty[c][i])] = PLATMIN;
1351 for (i = 0; i < n; i++)
1352 off[i] = XYOFFSET(sectx[c][i0 + i], secty[c][i0 + i]);
1353 qsort(off, n, sizeof(*off), elev_cmp);
1354 delta = (double)(HIGHMIN - LANDMIN - 1) / (n - nm - 1);
1355 elevation = LANDMIN;
1356 for (i = 0; i < n - nm; i++) {
1357 elev[off[i]] = (int)(elevation + 0.5);
1360 elevation = HIGHMIN;
1361 delta = (127.0 - HIGHMIN) / max_nm;
1362 for (; i < n; i++) {
1364 elev[off[i]] = (int)(elevation + 0.5);
1377 for (i = 0; i < WORLD_SZ(); i++) {
1382 for (i = 0; i < WORLD_SZ(); i++) {
1384 elev[i] = -1 - 126 * elev[i] / min;
1389 elev_to_sct_type(int elevation)
1391 if (elevation < LANDMIN)
1393 if (elevation < HIGHMIN)
1398 /****************************************************************************
1400 ****************************************************************************/
1403 * Map elevation @elev to a resource value according to @conf.
1404 * This is a linear interpolation on the data points in @conf.
1407 elev_to_resource(int elev, struct resource_point conf[])
1409 int i, elev1, elev2, delev;
1410 double res1, res2, dres;
1412 for (i = 1; elev > conf[i].elev; i++) ;
1413 assert(conf[i - 1].elev <= elev);
1415 elev1 = conf[i - 1].elev;
1416 elev2 = conf[i].elev;
1417 delev = elev2 - elev1;
1418 res1 = conf[i - 1].res;
1421 return (int)(res1 + ((elev - elev1) * dres) / delev);
1425 add_resources(struct sctstr *sct)
1427 sct->sct_min = elev_to_resource(sct->sct_elev, iron_conf);
1428 sct->sct_gmin = elev_to_resource(sct->sct_elev, gold_conf);
1429 sct->sct_fertil = elev_to_resource(sct->sct_elev, fert_conf);
1430 sct->sct_oil = elev_to_resource(sct->sct_elev, oil_conf);
1431 sct->sct_uran = elev_to_resource(sct->sct_elev, uran_conf);
1434 /****************************************************************************
1435 DESIGNATE THE SECTORS
1436 ****************************************************************************/
1444 for (y = 0; y < WORLD_Y; y++) {
1445 for (x = y % 2; x < WORLD_X; x += 2) {
1446 sct = getsectp(x, y);
1447 sct->sct_elev = elev[sct->sct_uid];
1448 sct->sct_type = elev_to_sct_type(sct->sct_elev);
1449 sct->sct_newtype = sct->sct_type;
1450 sct->sct_dterr = own[sct->sct_x][y] + 1;
1451 sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1457 /****************************************************************************
1458 PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1459 ****************************************************************************/
1463 int sx, sy, x, y, off, c, type;
1466 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1471 for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1473 off = XYOFFSET(x, y);
1475 type = elev_to_sct_type(elev[off]);
1476 if (type == SCT_WATER)
1478 else if (type == SCT_MOUNT)
1483 assert(0 <= c && c < nc);
1484 if ((x == capx[c] || x == new_x(capx[c] + 2))
1486 printf("%c ", numletter[c % 62]);
1496 * Print a map to help visualize own[][].
1497 * This is for debugging.
1504 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1507 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1511 else if (own[x][y] == -1)
1514 putchar(numletter[own[x][y] % 62]);
1521 * Print a map to help visualize elev[].
1522 * This is for debugging. It expects the terminal to understand
1523 * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1526 print_elev_map(void)
1528 int sx, sy, x, y, off, sat;
1530 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1533 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1535 off = XYOFFSET(x, y);
1538 else if (!elev[off])
1540 else if (elev[off] < 0) {
1541 sat = 256 + elev[off] * 2;
1542 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1543 } else if (elev[off] < HIGHMIN / 2) {
1544 sat = (HIGHMIN / 2 - elev[off]) * 4;
1545 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1546 } else if (elev[off] < HIGHMIN) {
1547 sat = 128 + (HIGHMIN - elev[off]) * 2;
1548 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1550 sat = 128 + (elev[off] - HIGHMIN) * 2;
1551 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1559 * Print a map to help visualize xzone[].
1560 * This is for debugging.
1563 print_xzone_map(void)
1565 int sx, sy, x, y, off;
1567 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1570 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1572 off = XYOFFSET(x, y);
1575 else if (own[x][y] >= 0)
1577 else if (xzone[off] >= 0)
1578 putchar(numletter[xzone[off] % 62]);
1580 assert(own[x][y] == -1);
1581 putchar(xzone[off] == -1 ? '.' : '!');
1589 * Print a map to help visualize closest[].
1590 * This is for debugging.
1593 print_closest_map(void)
1595 int sx, sy, x, y, off;
1597 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1600 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1602 off = XYOFFSET(x, y);
1605 else if (closest[off] == (natid)-1)
1607 else if (!distance[off]) {
1608 assert(closest[off] == own[x][y]);
1611 putchar(numletter[closest[off] % 62]);
1619 print_distance_map(void)
1621 int sx, sy, x, y, off;
1623 for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1626 for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1628 off = XYOFFSET(x, y);
1631 else if (closest[off] == (natid)-1)
1633 else if (!distance[off]) {
1634 assert(closest[off] == own[x][y]);
1637 putchar(numletter[distance[off] % 62]);
1645 /***************************************************************************
1646 WRITE A SCRIPT FOR PLACING CAPITALS
1647 ****************************************************************************/
1649 write_newcap_script(void)
1652 FILE *script = fopen(outfile, "w");
1655 fprintf(stderr, "%s: unable to write to %s (%s)\n",
1656 program_name, outfile, strerror(errno));
1660 for (c = 0; c < nc; ++c) {
1661 fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1662 fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1664 fprintf(script, "add %d visitor visitor v\n", c + 1);
1670 qprint(const char *const fmt, ...)
1676 vfprintf(stdout, fmt, ap);