405021e964146498543c0e6fff89807c3fec2095
[empserver] / src / util / fairland.c
1 /*
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
5  *
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.
10  *
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.
15  *
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/>.
18  *
19  *  ---
20  *
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.
24  *
25  *  ---
26  *
27  *  fairland.c: Create a nice, new world
28  *
29  *  Known contributors to this file:
30  *     Ken Stevens, 1995
31  *     Steve McClure, 1998
32  *     Markus Armbruster, 2004-2020
33  */
34
35 /*
36  * How fairland works
37  *
38  * 1. Place capitals
39  *
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.
43  *
44  * 2. Grow start islands ("continents")
45  *
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
49  * specified size.
50  *
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.
59  *
60  * If growing fails due to lack of room, start over.  If it fails too
61  * many times, give up and terminate unsuccessfully.
62  *
63  * 3. Place and grow additional islands
64  *
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.
69  *
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.
74  *
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.
80  *
81  * If placement fails due to lack of room, start over, just like for
82  * continents.
83  *
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.
88  *
89  * 4. Compute elevation
90  *
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.
95  *
96  * Then, elevate islands one after the other.
97  *
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.
103  *
104  * This gives islands of the same size the same set of elevations.
105  * Larger islands get more and taller mountains.
106  *
107  * Finally, elevate sea: normalize the raw elevations to [-127:-1].
108  *
109  * 5. Set resources
110  *
111  * Sector resources are simple functions of elevation.  You can alter
112  * iron_conf[], gold_conf[], fert_conf[], oil_conf[], and uran_conf[]
113  * to customize them.
114  */
115
116 #include <config.h>
117
118 #include <assert.h>
119 #include <errno.h>
120 #include <limits.h>
121 #include <stdarg.h>
122 #include <stdio.h>
123 #include <unistd.h>
124 #include "chance.h"
125 #include "optlist.h"
126 #include "path.h"
127 #include "prototypes.h"
128 #include "sect.h"
129 #include "version.h"
130 #include "xy.h"
131
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 */
136
137 /*
138  * Resource configuration
139
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.
144  */
145
146 struct resource_point {
147     int elev;
148     double res;
149 };
150
151 struct resource_point iron_conf[] = {
152     { -127, 0 },
153     { 21, 0 },
154     { 84, 120.0 * 63 / 76 },
155     { 85, 100 },
156     { HIGHMIN - 1, 100 },
157     { HIGHMIN , 0 },
158     { 127, 0 } };
159
160 struct resource_point gold_conf[] = {
161     { -127, 0 },
162     { 35, 0 },
163     { HIGHMIN - 1, 80 },
164     { HIGHMIN, 80 },
165     { 127, 85 } };
166
167 struct resource_point fert_conf[] = {
168     { -127, 100 },
169     { -59, 100 },
170     { LANDMIN - 1, 41 },
171     { LANDMIN, 100 },
172     { 10, 100 },
173     { 11, 120.0 * 45 / 55 },
174     { 56, 0 },
175     { 127, 0 } };
176
177 struct resource_point oil_conf[] = {
178     { -127, 100 },
179     { -49, 100 },
180     { LANDMIN - 1, 2 },
181     { LANDMIN, 100 },
182     { 6, 100 },
183     { 7, 120.0 * 27 / 33 },
184     { 34, 0 },
185     { 127, 0 } };
186
187 struct resource_point uran_conf[] = {
188     { -127, 0 },
189     { 55, 0 },
190     { 90, 100 },
191     { 97, 100 },
192     { 98, 0 },
193     { 127, 0 } };
194
195 static void qprint(const char * const fmt, ...)
196     ATTRIBUTE((format (printf, 1, 2)));
197
198 /*
199  * Program arguments and options
200  */
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;
215 static int quiet;
216 #define DEFAULT_OUTFILE_NAME "newcap_script"
217 static const char *outfile = DEFAULT_OUTFILE_NAME;
218
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)
222
223 /* handy macros:
224 */
225
226 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
227 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
228
229 /*
230  * Island sizes
231  * isecs[i] is the size of the i-th island.
232  */
233 static int *isecs;
234
235 static int *capx, *capy;        /* location of the nc capitals */
236
237 static int **own;               /* owner of the sector.  -1 means water */
238
239 /*
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.
243  */
244 static unsigned char *adj_land;
245
246 /*
247  * Elevation at x,y
248  * elev[XYOFFSET(x, y)] is x,y's elevation.
249  */
250 static short *elev;
251
252 /*
253  * Exclusive zones
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
262  * exclusive zones.
263  */
264 static short *xzone;
265
266 /*
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.
270  */
271 static unsigned *seen;
272 static unsigned cur_seen;
273
274 /*
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().
279  */
280 static natid *closest;
281 static unsigned short *distance;
282
283 /*
284  * Queue for breadth-first search
285  */
286 static int *bfs_queue;
287 static int bfs_queue_head, bfs_queue_tail;
288
289 static int **sectx, **secty;    /* the sectors for each continent */
290
291 #define NUMTRIES 10             /* keep trying to grow this many times */
292
293 static const char *numletter =
294     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
295
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);
311
312 static void print_vars(void);
313 static void fl_move(int);
314 static int grow_islands(void);
315
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);
322
323 /****************************************************************************
324   MAIN
325 ****************************************************************************/
326
327 int
328 main(int argc, char *argv[])
329 {
330     int opt;
331     char *config_file = NULL;
332     int try, done;
333     unsigned rnd_seed = 0;
334     int seed_set = 0;
335
336     program_name = argv[0];
337
338     while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
339         switch (opt) {
340         case 'e':
341             config_file = optarg;
342             break;
343         case 'i':
344             DISTINCT_ISLANDS = 0;
345             break;
346         case 'q':
347             quiet = 1;
348             break;
349         case 'R':
350             rnd_seed = strtoul(optarg, NULL, 10);
351             seed_set = 1;
352             break;
353         case 's':
354             outfile = optarg;
355             break;
356         case 'h':
357             usage();
358             exit(0);
359         case 'v':
360             printf("%s\n\n%s", version, legal);
361             exit(0);
362         default:
363             help(NULL);
364             exit(1);
365         }
366     }
367
368     if (!seed_set)
369         rnd_seed = pick_seed();
370     seed_prng(rnd_seed);
371     empfile_init();
372     if (emp_config(config_file) < 0)
373         exit(1);
374     empfile_fixup();
375
376     parse_args(argc - optind, argv + optind);
377
378     allocate_memory();
379     print_vars();
380
381     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
382     qprint("seed is %u\n", rnd_seed);
383     try = 0;
384     do {
385         init();
386         if (try)
387             qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
388         qprint("placing capitals...\n");
389         if (!drift())
390             qprint("unstable drift\n");
391         qprint("growing continents...\n");
392         done = grow_continents();
393         if (!done)
394             continue;
395         qprint("growing islands:");
396         done = grow_islands();
397     } while (!done && ++try < NUMTRIES);
398     if (!done) {
399         fprintf(stderr, "%s: world not large enough for this much land\n",
400                 program_name);
401         exit(1);
402     }
403     qprint("elevating land...\n");
404     create_elevations();
405
406     qprint("writing to sectors file...\n");
407     if (!write_newcap_script())
408         exit(1);
409     if (chdir(gamedir)) {
410         fprintf(stderr, "%s: can't chdir to %s (%s)\n",
411                 program_name, gamedir, strerror(errno));
412         exit(1);
413     }
414     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
415         exit(1);
416     write_sects();
417     if (!ef_close(EF_SECTOR))
418         exit(1);
419
420     output();
421     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
422            outfile);
423     exit(0);
424 }
425
426 static void
427 print_vars(void)
428 {
429     if (quiet)
430         return;
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);
442 }
443
444 static void
445 help(char *complaint)
446 {
447     if (complaint)
448         fprintf(stderr, "%s: %s\n", program_name, complaint);
449     fprintf(stderr, "Try -h for help.\n");
450 }
451
452 static void
453 usage(void)
454 {
455     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
456            "  -e CONFIG-FILE  configuration file\n"
457            "                  (default %s)\n"
458            "  -i              islands may merge\n"
459            "  -q              quiet\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);
474 }
475
476 static void
477 parse_args(int argc, char *argv[])
478 {
479     int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
480
481     if (argc < 2) {
482         help("missing arguments");
483         exit(1);
484     }
485     if (argc > 8) {
486         help("too many arguments");
487         exit(1);
488     }
489     nc = atoi(argv[0]);
490     if (nc < 1) {
491         fprintf(stderr, "%s: number of continents must be > 0\n",
492                 program_name);
493         exit(1);
494     }
495
496     sc = atoi(argv[1]);
497     if (sc < 2) {
498         fprintf(stderr, "%s: size of continents must be > 1\n",
499                 program_name);
500         exit(1);
501     }
502
503     ni = nc;
504     is = sc / 2;
505
506     if (argc > 2)
507         ni = atoi(argv[2]);
508     if (ni < 0) {
509         fprintf(stderr, "%s: number of islands must be >= 0\n",
510                 program_name);
511         exit(1);
512     }
513     if (ni % nc) {
514         fprintf(stderr, "%s: number of islands must be a multiple of"
515                 " the number of continents\n",
516                 program_name);
517         exit(1);
518     }
519
520     if (argc > 3)
521         is = atoi(argv[3]);
522     if (is < 1) {
523         fprintf(stderr, "%s: size of islands must be > 0\n",
524                 program_name);
525         exit(1);
526     }
527
528     if (argc > 4)
529         sp = atoi(argv[4]);
530     if (sp < 0 || sp > 100) {
531         fprintf(stderr,
532                 "%s: spike percentage must be between 0 and 100\n",
533                 program_name);
534         exit(1);
535     }
536
537     if (argc > 5)
538         pm = atoi(argv[5]);
539     if (pm < 0 || pm > 100) {
540         fprintf(stderr,
541                 "%s: mountain percentage must be between 0 and 100\n",
542                 program_name);
543         exit(1);
544     }
545
546     if (argc > 6)
547         di = atoi(argv[6]);
548     if (di < 0) {
549         fprintf(stderr, "%s: distance between continents must be >= 0\n",
550                 program_name);
551         exit(1);
552     }
553     if (di > dist_max) {
554         fprintf(stderr, "%s: distance between continents too large\n",
555                 program_name);
556         exit(1);
557     }
558
559     if (argc > 7)
560         id = atoi(argv[7]);
561     if (id < 0) {
562         fprintf(stderr,
563                 "%s: distance from islands to continents must be >= 0\n",
564                 program_name);
565         exit(1);
566     }
567     if (id > dist_max) {
568         fprintf(stderr,
569                 "%s: distance from islands to continents too large\n",
570                 program_name);
571         exit(1);
572     }
573 }
574
575 /****************************************************************************
576   VARIABLE INITIALIZATION
577 ****************************************************************************/
578
579 static void
580 allocate_memory(void)
581 {
582     int i;
583
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));
596     }
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));
603     }
604     for (i = nc; i < nc + ni; ++i) {
605         sectx[i] = calloc(is * 2, sizeof(int));
606         secty[i] = calloc(is * 2, sizeof(int));
607     }
608
609 }
610
611 static void
612 init(void)
613 {
614     int i, j;
615
616     for (i = 0; i < WORLD_X; ++i) {
617         for (j = 0; j < WORLD_Y; ++j) {
618             own[i][j] = -1;
619         }
620     }
621     memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
622 }
623
624 /****************************************************************************
625   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
626 ****************************************************************************/
627
628 /*
629  * How isolated is capital @j at @newx,@newy?
630  * Return the distance to the closest other capital.
631  */
632 static int
633 iso(int j, int newx, int newy)
634 {
635     int d = INT_MAX;
636     int i, md;
637
638     for (i = 0; i < nc; ++i) {
639         if (i == j)
640             continue;
641         md = mapdist(capx[i], capy[i], newx, newy);
642         if (md < d)
643             d = md;
644     }
645
646     return d;
647 }
648
649 /*
650  * Drift the capitals
651  * Return 1 for a stable drift, 0 for an unstable one.
652  */
653 static int
654 drift(void)
655 {
656     int turns, i;
657
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) {
662             fprintf(stderr,
663                     "%s: world not big enough for all the continents\n",
664                     program_name);
665             exit(1);
666         }
667     }
668
669     for (turns = 0; turns < DRIFT_MAX; ++turns) {
670         if (stable(turns))
671             return 1;
672         for (i = 0; i < nc; ++i)
673             fl_move(i);
674     }
675     return 0;
676 }
677
678 /*
679  * Has the drift stabilized?
680  * @turns is the number of turns so far.
681  */
682 static int
683 stable(int turns)
684 {
685     static int mc[STABLE_CYCLE];
686     int i, isod, d = 0, stab = 1;
687
688     if (!turns) {
689         for (i = 0; i < STABLE_CYCLE; i++)
690             mc[i] = i;
691     }
692
693     if (turns <= DRIFT_BEFORE_CHECK)
694         return 0;
695
696     for (i = 0; i < nc; ++i) {
697         isod = iso(i, capx[i], capy[i]);
698         if (isod > d)
699             d = isod;
700     }
701
702     for (i = 0; i < STABLE_CYCLE; ++i)
703         if (d != mc[i])
704             stab = 0;
705
706     mc[turns % STABLE_CYCLE] = d;
707     return stab;
708 }
709
710 /* This routine does the actual drifting
711 */
712
713 static void
714 fl_move(int j)
715 {
716     int dir, i, newx, newy;
717
718     dir = DIR_L + roll0(6);
719     for (i = 0; i < 6; i++) {
720         if (dir > DIR_LAST)
721             dir -= 6;
722         newx = new_x(capx[j] + diroff[dir][0]);
723         newy = new_y(capy[j] + diroff[dir][1]);
724         dir++;
725         if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
726             capx[j] = newx;
727             capy[j] = newy;
728             return;
729         }
730     }
731 }
732
733 /****************************************************************************
734   GROW THE CONTINENTS
735 ****************************************************************************/
736
737 static int
738 is_coastal(int x, int y)
739 {
740     return adj_land[XYOFFSET(x, y)]
741         != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
742 }
743
744 struct hexagon_iter {
745     int dir, i, n;
746 };
747
748 /*
749  * Start iterating around @x0,@y0 at distance @d.
750  * Set *x,*y to coordinates of the first sector.
751  */
752 static inline void
753 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
754               int *x, int *y)
755 {
756     *x = new_x(x0 - 2 * n);
757     *y = y0;
758     iter->dir = DIR_FIRST;
759     iter->i = 0;
760     iter->n = n;
761 }
762
763 /*
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
767  * complete.
768  */
769 static inline int
770 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
771 {
772     *x = new_x(*x + diroff[iter->dir][0]);
773     *y = new_y(*y + diroff[iter->dir][1]);
774     iter->i++;
775     if (iter->i == iter->n) {
776         iter->i = 0;
777         iter->dir++;
778     }
779     return iter->dir <= DIR_LAST;
780 }
781
782 /*
783  * Is @x,@y in no exclusive zone other than perhaps @c's?
784  */
785 static int
786 xzone_ok(int c, int x, int y)
787 {
788     int off = XYOFFSET(x, y);
789
790     return xzone[off] == c || xzone[off] == -1;
791 }
792
793 /*
794  * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
795  */
796 static void
797 xzone_around_sector(int c, int x, int y, int dist)
798 {
799     int d, x1, y1, off;
800     struct hexagon_iter hexit;
801
802     assert(xzone_ok(c, x, y));
803
804     xzone[XYOFFSET(x, y)] = c;
805     for (d = 1; d <= dist; d++) {
806         hexagon_first(&hexit, x, y, d, &x1, &y1);
807         do {
808             off = XYOFFSET(x1, y1);
809             if (xzone[off] == -1)
810                 xzone[off] = c;
811             else if (xzone[off] != c)
812                 xzone[off] = -2;
813         } while (hexagon_next(&hexit, &x1, &y1));
814     }
815 }
816
817 /*
818  * Add sectors within distance @dist to island @c's exclusive zone.
819  */
820 static void
821 xzone_around_island(int c, int dist)
822 {
823     int i;
824
825     for (i = 0; i < isecs[c]; i++)
826         xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
827 }
828
829 /*
830  * Initialize exclusive zones around @n islands.
831  */
832 static void
833 xzone_init(int n)
834 {
835     int i, c;
836
837     for (i = 0; i < WORLD_SZ(); i++)
838         xzone[i] = -1;
839
840     for (c = 0; c < n; c++)
841         xzone_around_island(c, id);
842 }
843
844 /*
845  * Initialize breadth-first search.
846  */
847 static void
848 bfs_init(void)
849 {
850     int i;
851
852     for (i = 0; i < WORLD_SZ(); i++) {
853         closest[i] = -1;
854         distance[i] = USHRT_MAX;
855     }
856
857     bfs_queue_head = bfs_queue_tail = 0;
858 }
859
860 /*
861  * Add sector @x,@y to the BFS queue.
862  * It's closest to @c, with distance @dist.
863  */
864 static void
865 bfs_enqueue(int c, int x, int y, int dist)
866 {
867     int off = XYOFFSET(x, y);
868
869     assert(dist < distance[off]);
870     closest[off] = c;
871     distance[off] = dist;
872     bfs_queue[bfs_queue_tail] = off;
873     bfs_queue_tail++;
874     if (bfs_queue_tail >= WORLD_SZ())
875         bfs_queue_tail = 0;
876     assert(bfs_queue_tail != bfs_queue_head);
877 }
878
879 /*
880  * Search breadth-first until the queue is empty.
881  */
882 static void
883 bfs_run_queue(void)
884 {
885     int off, dist, i, noff, nx, ny;
886     coord x, y;
887
888     while (bfs_queue_head != bfs_queue_tail) {
889         off = bfs_queue[bfs_queue_head];
890         bfs_queue_head++;
891         if (bfs_queue_head >= WORLD_SZ())
892             bfs_queue_head = 0;
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;
904             } else
905                 assert(distance[noff] < dist);
906         }
907     }
908 }
909
910 /*
911  * Add island @c's coastal sectors to the BFS queue, with distance 0.
912  */
913 static void
914 bfs_enqueue_island(int c)
915 {
916     int i;
917
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);
921     }
922 }
923
924 /*
925  * Enqueue spheres of influence borders for breadth-first search.
926  */
927 static void
928 bfs_enqueue_border(void)
929 {
930     int x, y, off, dir, nx, ny, noff;
931
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)
936                 continue;
937             if (closest[off] == (natid)-1)
938                 continue;
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);
945                     break;
946                 }
947             }
948         }
949     }
950 }
951
952 /*
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.
963  */
964 static void
965 init_spheres_of_influence(void)
966 {
967     int c;
968
969     bfs_init();
970     for (c = 0; c < nc; c++)
971         bfs_enqueue_island(c);
972     bfs_run_queue();
973     bfs_enqueue_border();
974     bfs_run_queue();
975 }
976
977 /*
978  * Precompute distance to coast
979  * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
980  * land sector.
981  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
982  * -1 if no single continent is closest.
983  */
984 static void
985 init_distance_to_coast(void)
986 {
987     int c;
988
989     bfs_init();
990     for (c = 0; c < nc + ni; c++)
991         bfs_enqueue_island(c);
992     bfs_run_queue();
993 }
994
995 /*
996  * Is @x,@y in the same sphere of influence as island @c?
997  * Always true when @c is a continent.
998  */
999 static int
1000 is_in_sphere(int c, int x, int y)
1001 {
1002     return c < nc || closest[XYOFFSET(x, y)] == c % nc;
1003 }
1004
1005 /*
1006  * Can island @c grow at @x,@y?
1007  */
1008 static int
1009 can_grow_at(int c, int x, int y)
1010 {
1011     return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
1012 }
1013
1014 static void
1015 adj_land_update(int x, int y)
1016 {
1017     int is_land = own[x][y] != -1;
1018     int dir, nx, ny, noff;
1019
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);
1024         if (is_land)
1025             adj_land[noff] |= 1u << DIR_BACK(dir);
1026         else
1027             adj_land[noff] &= ~(1u << DIR_BACK(dir));
1028     }
1029 }
1030
1031 static void
1032 add_sector(int c, int x, int y)
1033 {
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;
1038     isecs[c]++;
1039     own[x][y] = c;
1040     adj_land_update(x, y);
1041 }
1042
1043 static int
1044 grow_weight(int c, int x, int y, int spike)
1045 {
1046     int n, b;
1047
1048     /*
1049      * #Land neighbors is #bits set in adj_land[].
1050      * Count them Brian Kernighan's way.
1051      */
1052     n = 0;
1053     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1054         n++;
1055     assert(n > 0 && n < 7);
1056
1057     if (spike)
1058         return (6 - n) * (6 - n);
1059
1060     return n * n * n;
1061 }
1062
1063 static int
1064 grow_one_sector(int c)
1065 {
1066     int spike = roll0(100) < sp;
1067     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1068
1069     assert(cur_seen < UINT_MAX);
1070     cur_seen++;
1071     wsum = 0;
1072     newx = newy = -1;
1073
1074     for (i = 0; i < isecs[c]; i++) {
1075         x = sectx[c][i];
1076         y = secty[c][i];
1077         off = XYOFFSET(x, y);
1078
1079         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1080             if (adj_land[off] & (1u << dir))
1081                 continue;
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)
1086                 continue;
1087             assert(seen[noff] < cur_seen);
1088             seen[noff] = cur_seen;
1089             if (!can_grow_at(c, nx, ny))
1090                 continue;
1091             w = grow_weight(c, nx, ny, spike);
1092             assert(wsum < INT_MAX - w);
1093             wsum += w;
1094             if (roll0(wsum) < w) {
1095                 newx = nx;
1096                 newy = ny;
1097             }
1098         }
1099     }
1100
1101     if (!wsum)
1102         return 0;
1103
1104     add_sector(c, newx, newy);
1105     return 1;
1106 }
1107
1108 /*
1109  * Grow the continents.
1110  * Return 1 on success, 0 on error.
1111  */
1112 static int
1113 grow_continents(void)
1114 {
1115     int done = 1;
1116     int c, secs;
1117
1118     xzone_init(0);
1119
1120     for (c = 0; c < nc; ++c) {
1121         isecs[c] = 0;
1122         if (!can_grow_at(c, capx[c], capy[c])
1123             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1124             done = 0;
1125             continue;
1126         }
1127         add_sector(c, capx[c], capy[c]);
1128         add_sector(c, new_x(capx[c] + 2), capy[c]);
1129     }
1130
1131     if (!done) {
1132         qprint("No room for continents\n");
1133         return 0;
1134     }
1135
1136     for (secs = 2; secs < sc && done; secs++) {
1137         for (c = 0; c < nc; ++c) {
1138             if (!grow_one_sector(c))
1139                 done = 0;
1140         }
1141     }
1142
1143     if (!done)
1144         qprint("Only managed to grow %d out of %d sectors.\n",
1145                secs - 1, sc);
1146     return done;
1147 }
1148
1149 /****************************************************************************
1150   GROW THE ISLANDS
1151 ****************************************************************************/
1152
1153 /*
1154  * Place additional island @c's first sector.
1155  * Return 1 on success, 0 on error.
1156  */
1157 static int
1158 place_island(int c, int isiz)
1159 {
1160     int n, x, y, d, w, newx, newy;
1161
1162     n = 0;
1163
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)];
1168                 assert(d > id);
1169                 w = (d - id) * (d - id);
1170                 n += MIN(w, (isiz + 2) / 3);
1171                 if (roll0(n) < w) {
1172                     newx = x;
1173                     newy = y;
1174                 }
1175             }
1176         }
1177     }
1178
1179     if (n)
1180         add_sector(c, newx, newy);
1181     return n;
1182 }
1183
1184 static int
1185 int_cmp(const void *a, const void *b)
1186 {
1187     return *(int *)b - *(int *)a;
1188 }
1189
1190 static int *
1191 size_islands(void)
1192 {
1193     int n = ni / nc;
1194     int *isiz = malloc(n * sizeof(*isiz));
1195     int r0, r1, i;
1196
1197     isiz[0] = n * is;
1198     r1 = roll0(is);
1199     for (i = 1; i < n; i++) {
1200         r0 = r1;
1201         r1 = roll0(is);
1202         isiz[i] = is + r1 - r0;
1203         isiz[0] -= isiz[i];
1204     }
1205
1206     qsort(isiz, n, sizeof(*isiz), int_cmp);
1207     return isiz;
1208 }
1209
1210 /*
1211  * Grow the additional islands.
1212  * Return 1 on success, 0 on error.
1213  */
1214 static int
1215 grow_islands(void)
1216 {
1217     int *island_size = size_islands();
1218     int xzone_valid = 0;
1219     int carry = 0;
1220     int i, j, c, done, secs, isiz, x, y;
1221
1222     init_spheres_of_influence();
1223
1224     for (i = 0; i < ni / nc; i++) {
1225         c = nc + i * nc;
1226
1227         if (!xzone_valid)
1228             xzone_init(c);
1229
1230         carry += island_size[i];
1231         isiz = MIN(2 * is, carry);
1232
1233         for (j = 0; j < nc; j++) {
1234             isecs[c + j] = 0;
1235             if (!place_island(c + j, isiz)) {
1236                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1237                 free(island_size);
1238                 return 0;
1239             }
1240         }
1241
1242         done = 1;
1243         for (secs = 1; secs < isiz && done; secs++) {
1244             for (j = 0; j < nc; j++) {
1245                 if (!grow_one_sector(c + j))
1246                     done = 0;
1247             }
1248         }
1249
1250         if (!done) {
1251             secs--;
1252             for (j = 0; j < nc; j++) {
1253                 if (isecs[c + j] != secs) {
1254                     isecs[c + j]--;
1255                     assert(isecs[c + j] == secs);
1256                     x = sectx[c + j][secs];
1257                     y = secty[c + j][secs];
1258                     own[x][y] = -1;
1259                     adj_land_update(x, y);
1260                 }
1261             }
1262             xzone_valid = 0;
1263         }
1264
1265         for (j = 0; j < nc; j++)
1266             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1267
1268         carry -= secs;
1269     }
1270
1271     free(island_size);
1272     qprint("\n");
1273
1274     if (carry)
1275         qprint("Only managed to grow %d out of %d island sectors.\n",
1276                is * ni - carry * nc, is * ni);
1277
1278     return 1;
1279 }
1280
1281 /****************************************************************************
1282   CREATE ELEVATIONS
1283 ****************************************************************************/
1284 static void
1285 create_elevations(void)
1286 {
1287     elevate_prep();
1288     elevate_land();
1289     elevate_sea();
1290 }
1291
1292 static int
1293 elev_cmp(const void *p, const void *q)
1294 {
1295     int a = *(int *)p;
1296     int b = *(int *)q;
1297     int delev = elev[a] - elev[b];
1298
1299     return delev ? delev : a - b;
1300 }
1301
1302 static void
1303 elevate_prep(void)
1304 {
1305     int n = WORLD_SZ() * 8;
1306     int off0, r, sign, elevation, d, x1, y1, off1;
1307     coord x0, y0;
1308     struct hexagon_iter hexit;
1309
1310     init_distance_to_coast();
1311
1312     while (n > 0) {
1313         off0 = roll0(WORLD_SZ());
1314         sctoff2xy(&x0, &y0, off0);
1315         if (own[x0][y0] == -1) {
1316             r = roll(MIN(3, distance[off0]));
1317             sign = -1;
1318         } else {
1319             r = roll(MIN(3, distance[off0]) + 1);
1320             sign = 1;
1321         }
1322         elevation = elev[off0] + sign * r * r;
1323         elev[off0] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1324         n--;
1325         for (d = 1; d < r; d++) {
1326             hexagon_first(&hexit, x0, y0, d, &x1, &y1);
1327             do {
1328                 off1 = XYOFFSET(x1, y1);
1329                 elevation = elev[off1] + sign * (r * r - d * d);
1330                 elev[off1] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1331                 n--;
1332             } while (hexagon_next(&hexit, &x1, &y1));
1333         }
1334     }
1335 }
1336
1337 static void
1338 elevate_land(void)
1339 {
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;
1344
1345     for (c = 0; c < nc + ni; c++) {
1346         nm = (pm * isecs[c]) / 100;
1347         i0 = c < nc ? 2 : 0;
1348         n = isecs[c] - i0;
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);
1358             elevation += delta;
1359         }
1360         elevation = HIGHMIN;
1361         delta = (127.0 - HIGHMIN) / max_nm;
1362         for (; i < n; i++) {
1363             elevation += delta;
1364             elev[off[i]] = (int)(elevation + 0.5);
1365         }
1366     }
1367
1368     free(off);
1369 }
1370
1371 static void
1372 elevate_sea(void)
1373 {
1374     int i, min;
1375
1376     min = 0;
1377     for (i = 0; i < WORLD_SZ(); i++) {
1378         if (elev[i] < min)
1379             min = elev[i];
1380     }
1381
1382     for (i = 0; i < WORLD_SZ(); i++) {
1383         if (elev[i] < 0)
1384             elev[i] = -1 - 126 * elev[i] / min;
1385     }
1386 }
1387
1388 static int
1389 elev_to_sct_type(int elevation)
1390 {
1391     if (elevation < LANDMIN)
1392         return SCT_WATER;
1393     if (elevation < HIGHMIN)
1394         return SCT_RURAL;
1395     return SCT_MOUNT;
1396 }
1397
1398 /****************************************************************************
1399   ADD THE RESOURCES
1400 ****************************************************************************/
1401
1402 /*
1403  * Map elevation @elev to a resource value according to @conf.
1404  * This is a linear interpolation on the data points in @conf.
1405  */
1406 static int
1407 elev_to_resource(int elev, struct resource_point conf[])
1408 {
1409     int i, elev1, elev2, delev;
1410     double res1, res2, dres;
1411
1412     for (i = 1; elev > conf[i].elev; i++) ;
1413     assert(conf[i - 1].elev <= elev);
1414
1415     elev1 = conf[i - 1].elev;
1416     elev2 = conf[i].elev;
1417     delev = elev2 - elev1;
1418     res1 = conf[i - 1].res;
1419     res2 = conf[i].res;
1420     dres = res2 - res1;
1421     return (int)(res1 + ((elev - elev1) * dres) / delev);
1422 }
1423
1424 static void
1425 add_resources(struct sctstr *sct)
1426 {
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);
1432 }
1433
1434 /****************************************************************************
1435   DESIGNATE THE SECTORS
1436 ****************************************************************************/
1437
1438 static void
1439 write_sects(void)
1440 {
1441     struct sctstr *sct;
1442     int x, y;
1443
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);
1452             add_resources(sct);
1453         }
1454     }
1455 }
1456
1457 /****************************************************************************
1458   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1459 ****************************************************************************/
1460 static void
1461 output(void)
1462 {
1463     int sx, sy, x, y, off, c, type;
1464
1465     if (quiet == 0) {
1466         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1467             y = YNORM(sy);
1468             puts("");
1469             if (y % 2)
1470                 printf(" ");
1471             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1472                 x = XNORM(sx);
1473                 off = XYOFFSET(x, y);
1474                 c = own[x][y];
1475                 type = elev_to_sct_type(elev[off]);
1476                 if (type == SCT_WATER)
1477                     printf(". ");
1478                 else if (type == SCT_MOUNT)
1479                     printf("^ ");
1480                 else if (c >= nc)
1481                     printf("%% ");
1482                 else {
1483                     assert(0 <= c && c < nc);
1484                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1485                         && y == capy[c])
1486                         printf("%c ", numletter[c % 62]);
1487                     else
1488                         printf("# ");
1489                 }
1490             }
1491         }
1492     }
1493 }
1494
1495 /*
1496  * Print a map to help visualize own[][].
1497  * This is for debugging.
1498  */
1499 void
1500 print_own_map(void)
1501 {
1502     int sx, sy, x, y;
1503
1504     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1505         y = YNORM(sy);
1506         printf("%4d ", sy);
1507         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1508             x = XNORM(sx);
1509             if ((x + y) & 1)
1510                 putchar(' ');
1511             else if (own[x][y] == -1)
1512                 putchar('.');
1513             else
1514                 putchar(numletter[own[x][y] % 62]);
1515         }
1516         putchar('\n');
1517     }
1518 }
1519
1520 /*
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.
1524  */
1525 void
1526 print_elev_map(void)
1527 {
1528     int sx, sy, x, y, off, sat;
1529
1530     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1531         y = YNORM(sy);
1532         printf("%4d ", sy);
1533         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1534             x = XNORM(sx);
1535             off = XYOFFSET(x, y);
1536             if ((x + y) & 1)
1537                 putchar(' ');
1538             else if (!elev[off])
1539                 putchar(' ');
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);
1549             } else {
1550                 sat = 128 + (elev[off] - HIGHMIN) * 2;
1551                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1552             }
1553         }
1554         putchar('\n');
1555     }
1556 }
1557
1558 /*
1559  * Print a map to help visualize xzone[].
1560  * This is for debugging.
1561  */
1562 void
1563 print_xzone_map(void)
1564 {
1565     int sx, sy, x, y, off;
1566
1567     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1568         y = YNORM(sy);
1569         printf("%4d ", sy);
1570         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1571             x = XNORM(sx);
1572             off = XYOFFSET(x, y);
1573             if ((x + y) & 1)
1574                 putchar(' ');
1575             else if (own[x][y] >= 0)
1576                 putchar('-');
1577             else if (xzone[off] >= 0)
1578                 putchar(numletter[xzone[off] % 62]);
1579             else {
1580                 assert(own[x][y] == -1);
1581                 putchar(xzone[off] == -1 ? '.' : '!');
1582             }
1583         }
1584         putchar('\n');
1585     }
1586 }
1587
1588 /*
1589  * Print a map to help visualize closest[].
1590  * This is for debugging.
1591  */
1592 void
1593 print_closest_map(void)
1594 {
1595     int sx, sy, x, y, off;
1596
1597     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1598         y = YNORM(sy);
1599         printf("%4d ", sy);
1600         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1601             x = XNORM(sx);
1602             off = XYOFFSET(x, y);
1603             if ((x + y) & 1)
1604                 putchar(' ');
1605             else if (closest[off] == (natid)-1)
1606                 putchar('.');
1607             else if (!distance[off]) {
1608                 assert(closest[off] == own[x][y]);
1609                 putchar('-');
1610             } else {
1611                 putchar(numletter[closest[off] % 62]);
1612             }
1613         }
1614         printf("\n");
1615     }
1616 }
1617
1618 void
1619 print_distance_map(void)
1620 {
1621     int sx, sy, x, y, off;
1622
1623     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1624         y = YNORM(sy);
1625         printf("%4d ", sy);
1626         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1627             x = XNORM(sx);
1628             off = XYOFFSET(x, y);
1629             if ((x + y) & 1)
1630                 putchar(' ');
1631             else if (closest[off] == (natid)-1)
1632                 putchar('.');
1633             else if (!distance[off]) {
1634                 assert(closest[off] == own[x][y]);
1635                 putchar('-');
1636             } else {
1637                 putchar(numletter[distance[off] % 62]);
1638             }
1639         }
1640         printf("\n");
1641     }
1642 }
1643
1644
1645 /***************************************************************************
1646   WRITE A SCRIPT FOR PLACING CAPITALS
1647 ****************************************************************************/
1648 static int
1649 write_newcap_script(void)
1650 {
1651     int c;
1652     FILE *script = fopen(outfile, "w");
1653
1654     if (!script) {
1655         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1656                 program_name, outfile, strerror(errno));
1657         return 0;
1658     }
1659
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]);
1663     }
1664     fprintf(script, "add %d visitor visitor v\n", c + 1);
1665     fclose(script);
1666     return 1;
1667 }
1668
1669 static void
1670 qprint(const char *const fmt, ...)
1671 {
1672     va_list ap;
1673
1674     if (!quiet) {
1675         va_start(ap, fmt);
1676         vfprintf(stdout, fmt, ap);
1677         va_end(ap);
1678     }
1679 }