git.pond.sub.org Git - empserver/blob - 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.
  69  *
  70  * Pick an island size, then place and grow one island of that size in
  71  * each sphere.  Place the first sector randomly, then grow the island
  72  * to the intended size.  Repeat until the specified number of islands
  73  * has been grown.
  74  *
  75  * If placement fails due to lack of room, start over, just like for
  76  * continents.
  77  *
  78  * Growing works as for continents, except the minimum distance for
  79  * additional islands applies, and growing simply stops when there is
  80  * no room.
  81  *
  82  * 4. Compute elevation
  83  *
  84  * Elevate islands one after the other.
  85  *
  86  * First, place the specified number of mountains randomly.
  87  * Probability increases with distance to sea.
  88  *
  89  * Last, elevate mountains and the capitals.  Pick coastal mountain
  90  * elevation randomly from an interval of medium elevations reserved
  91  * for them.  Pick non-coastal mountain elevation randomly from an
  92  * interval of high elevation reserved for them.  Set capital
  93  * elevation to a fixed, medium value.
  94  *
  95  * In between, elevate the remaining land one by one, working from
  96  * mountains towards the sea, and from the elevation just below the
  97  * non-coastal mountains' interval linearly down to 1, avoiding the
  98  * coastal mountains' interval.
  99  *
 100  * This gives islands of the same size the same set of elevations,
 101  * except for mountains.
 102  *
 103  * Elevate sea: pick a random depth from an interval that deepens with
 104  * the distance to land.
 105  *
 106  * 5. Set resources
 107  *
 108  * Sector resources are simple functions of elevation.  You can alter
 109  * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
 110  * customize them.
 111  */
 112
 113 #include <config.h>
 114
 115 #include <assert.h>
 116 #include <errno.h>
 117 #include <limits.h>
 118 #include <stdarg.h>
 119 #include <stdio.h>
 120 #include <unistd.h>
 121 #include "chance.h"
 122 #include "optlist.h"
 123 #include "path.h"
 124 #include "prototypes.h"
 125 #include "sect.h"
 126 #include "version.h"
 127 #include "xy.h"
 128
 129 /* The following five numbers refer to elevation under which (in the case of
 130    fertility or oil) or over which (in the case of iron, gold, and uranium)
 131    sectors with that elevation will contain that resource.  Elevation ranges
 132    from 0 to 100 */
 133
 134 /* raise FERT_MAX for more fertility */
 135 #define FERT_MAX   56
 136
 137 /* raise OIL_MAX for more oil */
 138 #define OIL_MAX    33
 139
 140 /* lower IRON_MIN for more iron */
 141 #define IRON_MIN   22
 142
 143 /* lower GOLD_MIN for more gold */
 144 #define GOLD_MIN   36
 145
 146 /* lower URAN_MIN for more uranium */
 147 #define URAN_MIN   56
 148
 149 /* do not change these 4 defines */
 150 #define LANDMIN         1       /* plate altitude for normal land */
 151 #define HILLMIN         34      /* plate altitude for hills */
 152 #define PLATMIN         36      /* plate altitude for plateau */
 153 #define HIGHMIN         98      /* plate altitude for mountains */
 154
 155 static void qprint(const char * const fmt, ...)
 156     ATTRIBUTE((format (printf, 1, 2)));
 157
 158 /*
 159  * Program arguments and options
 160  */
 161 static char *program_name;
 162 static int nc, sc;              /* number and size of continents */
 163 static int ni, is;              /* number and size of islands */
 164 #define DEFAULT_SPIKE 10
 165 static int sp = DEFAULT_SPIKE;  /* spike percentage */
 166 #define DEFAULT_MOUNTAIN 0
 167 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
 168 #define DEFAULT_CONTDIST 2
 169 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
 170 #define DEFAULT_ISLDIST 1
 171 static int id = DEFAULT_ISLDIST;  /* ... continents and islands */
 172 /* don't let the islands crash into each other.
 173    1 = don't merge, 0 = merge. */
 174 static int DISTINCT_ISLANDS = 1;
 175 static int quiet;
 176 #define DEFAULT_OUTFILE_NAME "newcap_script"
 177 static const char *outfile = DEFAULT_OUTFILE_NAME;
 178
 179 #define STABLE_CYCLE 4          /* stability required for perterbed capitals */
 180 #define INFINITE_ELEVATION 999
 181
 182 /* these defines prevent infinite loops:
 183 */
 184 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
 185 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
 186 #define MOUNTAIN_SEARCH_MAX 1000        /* how long do we try to place mountains */
 187
 188 /* handy macros:
 189 */
 190
 191 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
 192 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
 193
 194 /*
 195  * Island sizes
 196  * isecs[i] is the size of the i-th island.
 197  */
 198 static int *isecs;
 199
 200 static int *capx, *capy;        /* location of the nc capitals */
 201
 202 static int **own;               /* owner of the sector.  -1 means water */
 203
 204 /*
 205  * Adjacent land sectors
 206  * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
 207  * to x, y in direction d is land.
 208  */
 209 static unsigned char *adj_land;
 210
 211 /*
 212  * Exclusive zones
 213  * Each island is surrounded by an exclusive zone where only it may
 214  * grow.  The width of the zone depends on minimum distances.
 215  * While growing continents, it is @di sectors wide.
 216  * While growing additional islands, it is @id sectors wide.
 217  * DISTINCT_ISLANDS nullifies the exclusive zone then.
 218  * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
 219  * zone, a (non-negative) island number when it is in that island's
 220  * exclusive zone and no other, and -2 when it is in multiple
 221  * exclusive zones.
 222  */
 223 static short *xzone;
 224
 225 /*
 226  * Set of sectors seen already
 227  * Increment @cur_seen to empty the set of sectors seen, set
 228  * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
 229  */
 230 static unsigned *seen;
 231 static unsigned cur_seen;
 232
 233 /*
 234  * Closest continent and "distance"
 235  * closest[XYOFFSET(x, y)] is the closest continent's number.
 236  * distance[] is complicated; see init_spheres_of_influence().
 237  */
 238 static natid *closest;
 239 static unsigned short *distance;
 240
 241 /*
 242  * Queue for breadth-first search
 243  */
 244 static int *bfs_queue;
 245 static int bfs_queue_head, bfs_queue_tail;
 246
 247 static int **elev;              /* elevation of the sectors */
 248 static int **sectx, **secty;    /* the sectors for each continent */
 249 static int **sectc;             /* which sectors are on the coast? */
 250 static int *weight;             /* used for placing mountains */
 251 static int *dsea, *dmoun;       /* the dist to the ocean and mountain */
 252
 253 #define NUMTRIES 10             /* keep trying to grow this many times */
 254
 255 static const char *numletter =
 256     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 257
 258 static void help(char *);
 259 static void usage(void);
 260 static void parse_args(int argc, char *argv[]);
 261 static void allocate_memory(void);
 262 static void init(void);
 263 static int drift(void);
 264 static int grow_continents(void);
 265 static void create_elevations(void);
 266 static void write_sects(void);
 267 static void output(void);
 268 static int write_newcap_script(void);
 269 static int stable(int);
 270 static void elevate_land(void);
 271 static void elevate_sea(void);
 272 static void set_coastal_flags(void);
 273
 274 static void print_vars(void);
 275 static void fl_move(int);
 276 static int grow_islands(void);
 277
 278 /* Debugging aids: */
 279 void print_own_map(void);
 280 void print_xzone_map(void);
 281 void print_closest_map(void);
 282 void print_distance_map(void);
 283 void print_elev_map(void);
 284
 285 /****************************************************************************
 286   MAIN
 287 ****************************************************************************/
 288
 289 int
 290 main(int argc, char *argv[])
 291 {
 292     int opt;
 293     char *config_file = NULL;
 294     int try, done;
 295     unsigned rnd_seed = 0;
 296     int seed_set = 0;
 297
 298     program_name = argv[0];
 299
 300     while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
 301         switch (opt) {
 302         case 'e':
 303             config_file = optarg;
 304             break;
 305         case 'i':
 306             DISTINCT_ISLANDS = 0;
 307             break;
 308         case 'q':
 309             quiet = 1;
 310             break;
 311         case 'R':
 312             rnd_seed = strtoul(optarg, NULL, 10);
 313             seed_set = 1;
 314             break;
 315         case 's':
 316             outfile = optarg;
 317             break;
 318         case 'h':
 319             usage();
 320             exit(0);
 321         case 'v':
 322             printf("%s\n\n%s", version, legal);
 323             exit(0);
 324         default:
 325             help(NULL);
 326             exit(1);
 327         }
 328     }
 329
 330     if (!seed_set)
 331         rnd_seed = pick_seed();
 332     seed_prng(rnd_seed);
 333     empfile_init();
 334     if (emp_config(config_file) < 0)
 335         exit(1);
 336     empfile_fixup();
 337
 338     parse_args(argc - optind, argv + optind);
 339
 340     allocate_memory();
 341     print_vars();
 342
 343     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
 344     qprint("seed is %u\n", rnd_seed);
 345     try = 0;
 346     do {
 347         init();
 348         if (try)
 349             qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
 350         qprint("placing capitals...\n");
 351         if (!drift())
 352             qprint("unstable drift\n");
 353         qprint("growing continents...\n");
 354         done = grow_continents();
 355         if (!done)
 356             continue;
 357         qprint("growing islands:");
 358         done = grow_islands();
 359     } while (!done && ++try < NUMTRIES);
 360     if (!done) {
 361         fprintf(stderr, "%s: world not large enough for this much land\n",
 362                 program_name);
 363         exit(1);
 364     }
 365     qprint("elevating land...\n");
 366     create_elevations();
 367
 368     qprint("writing to sectors file...\n");
 369     if (!write_newcap_script())
 370         exit(1);
 371     if (chdir(gamedir)) {
 372         fprintf(stderr, "%s: can't chdir to %s (%s)\n",
 373                 program_name, gamedir, strerror(errno));
 374         exit(1);
 375     }
 376     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
 377         exit(1);
 378     write_sects();
 379     if (!ef_close(EF_SECTOR))
 380         exit(1);
 381
 382     output();
 383     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
 384            outfile);
 385     exit(0);
 386 }
 387
 388 static void
 389 print_vars(void)
 390 {
 391     if (quiet)
 392         return;
 393     puts("Creating a planet with:\n");
 394     printf("%d continents\n", nc);
 395     printf("continent size: %d\n", sc);
 396     printf("number of islands: %d\n", ni);
 397     printf("average size of islands: %d\n", is);
 398     printf("spike: %d%%\n", sp);
 399     printf("%d%% of land is mountain (each continent will have %d mountains)\n",
 400            pm, (pm * sc) / 100);
 401     printf("minimum distance between continents: %d\n", di);
 402     printf("minimum distance from islands to continents: %d\n", id);
 403     printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
 404 }
 405
 406 static void
 407 help(char *complaint)
 408 {
 409     if (complaint)
 410         fprintf(stderr, "%s: %s\n", program_name, complaint);
 411     fprintf(stderr, "Try -h for help.\n");
 412 }
 413
 414 static void
 415 usage(void)
 416 {
 417     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
 418            "  -e CONFIG-FILE  configuration file\n"
 419            "                  (default %s)\n"
 420            "  -i              islands may merge\n"
 421            "  -q              quiet\n"
 422            "  -R SEED         seed for random number generator\n"
 423            "  -s SCRIPT       name of script to create (default %s)\n"
 424            "  -h              display this help and exit\n"
 425            "  -v              display version information and exit\n"
 426            "  NC              number of continents\n"
 427            "  SC              continent size\n"
 428            "  NI              number of islands (default NC)\n"
 429            "  IS              average island size (default SC/2)\n"
 430            "  SP              spike percentage: 0 = round, 100 = snake (default %d)\n"
 431            "  PM              percentage of land that is mountain (default %d)\n"
 432            "  DI              minimum distance between continents (default %d)\n"
 433            "  ID              minimum distance from islands to continents (default %d)\n",
 434            program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
 435            DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
 436 }
 437
 438 static void
 439 parse_args(int argc, char *argv[])
 440 {
 441     int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
 442
 443     if (argc < 2) {
 444         help("missing arguments");
 445         exit(1);
 446     }
 447     if (argc > 8) {
 448         help("too many arguments");
 449         exit(1);
 450     }
 451     nc = atoi(argv[0]);
 452     if (nc < 1) {
 453         fprintf(stderr, "%s: number of continents must be > 0\n",
 454                 program_name);
 455         exit(1);
 456     }
 457
 458     sc = atoi(argv[1]);
 459     if (sc < 2) {
 460         fprintf(stderr, "%s: size of continents must be > 1\n",
 461                 program_name);
 462         exit(1);
 463     }
 464
 465     ni = nc;
 466     is = sc / 2;
 467
 468     if (argc > 2)
 469         ni = atoi(argv[2]);
 470     if (ni < 0) {
 471         fprintf(stderr, "%s: number of islands must be >= 0\n",
 472                 program_name);
 473         exit(1);
 474     }
 475     if (ni % nc) {
 476         fprintf(stderr, "%s: number of islands must be a multiple of"
 477                 " the number of continents\n",
 478                 program_name);
 479         exit(1);
 480     }
 481
 482     if (argc > 3)
 483         is = atoi(argv[3]);
 484     if (is < 1) {
 485         fprintf(stderr, "%s: size of islands must be > 0\n",
 486                 program_name);
 487         exit(1);
 488     }
 489
 490     if (argc > 4)
 491         sp = atoi(argv[4]);
 492     if (sp < 0 || sp > 100) {
 493         fprintf(stderr,
 494                 "%s: spike percentage must be between 0 and 100\n",
 495                 program_name);
 496         exit(1);
 497     }
 498
 499     if (argc > 5)
 500         pm = atoi(argv[5]);
 501     if (pm < 0 || pm > 100) {
 502         fprintf(stderr,
 503                 "%s: mountain percentage must be between 0 and 100\n",
 504                 program_name);
 505         exit(1);
 506     }
 507
 508     if (argc > 6)
 509         di = atoi(argv[6]);
 510     if (di < 0) {
 511         fprintf(stderr, "%s: distance between continents must be >= 0\n",
 512                 program_name);
 513         exit(1);
 514     }
 515     if (di > dist_max) {
 516         fprintf(stderr, "%s: distance between continents too large\n",
 517                 program_name);
 518         exit(1);
 519     }
 520
 521     if (argc > 7)
 522         id = atoi(argv[7]);
 523     if (id < 0) {
 524         fprintf(stderr,
 525                 "%s: distance from islands to continents must be >= 0\n",
 526                 program_name);
 527         exit(1);
 528     }
 529     if (id > dist_max) {
 530         fprintf(stderr,
 531                 "%s: distance from islands to continents too large\n",
 532                 program_name);
 533         exit(1);
 534     }
 535 }
 536
 537 /****************************************************************************
 538   VARIABLE INITIALIZATION
 539 ****************************************************************************/
 540
 541 static void
 542 allocate_memory(void)
 543 {
 544     int i;
 545
 546     capx = calloc(nc, sizeof(int));
 547     capy = calloc(nc, sizeof(int));
 548     own = calloc(WORLD_X, sizeof(int *));
 549     adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
 550     xzone = malloc(WORLD_SZ() * sizeof(*xzone));
 551     seen = calloc(WORLD_SZ(), sizeof(*seen));
 552     closest = malloc(WORLD_SZ() * sizeof(*closest));
 553     distance = malloc(WORLD_SZ() * sizeof(*distance));
 554     bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
 555     elev = calloc(WORLD_X, sizeof(int *));
 556     for (i = 0; i < WORLD_X; ++i) {
 557         own[i] = calloc(WORLD_Y, sizeof(int));
 558         elev[i] = calloc(WORLD_Y, sizeof(int));
 559     }
 560     sectx = calloc(nc + ni, sizeof(int *));
 561     secty = calloc(nc + ni, sizeof(int *));
 562     sectc = calloc(nc + ni, sizeof(int *));
 563     isecs = calloc(nc + ni, sizeof(int));
 564     weight = calloc(MAX(sc, is * 2), sizeof(int));
 565     dsea = calloc(MAX(sc, is * 2), sizeof(int));
 566     dmoun = calloc(MAX(sc, is * 2), sizeof(int));
 567     for (i = 0; i < nc; ++i) {
 568         sectx[i] = calloc(sc, sizeof(int));
 569         secty[i] = calloc(sc, sizeof(int));
 570         sectc[i] = calloc(sc, sizeof(int));
 571     }
 572     for (i = nc; i < nc + ni; ++i) {
 573         sectx[i] = calloc(is * 2, sizeof(int));
 574         secty[i] = calloc(is * 2, sizeof(int));
 575         sectc[i] = calloc(is * 2, sizeof(int));
 576     }
 577
 578 }
 579
 580 static void
 581 init(void)
 582 {
 583     int i, j;
 584
 585     for (i = 0; i < WORLD_X; ++i) {
 586         for (j = 0; j < WORLD_Y; ++j) {
 587             own[i][j] = -1;
 588         }
 589     }
 590     memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
 591 }
 592
 593 /****************************************************************************
 594   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
 595 ****************************************************************************/
 596
 597 /*
 598  * How isolated is capital @j at @newx,@newy?
 599  * Return the distance to the closest other capital.
 600  */
 601 static int
 602 iso(int j, int newx, int newy)
 603 {
 604     int d = INT_MAX;
 605     int i, md;
 606
 607     for (i = 0; i < nc; ++i) {
 608         if (i == j)
 609             continue;
 610         md = mapdist(capx[i], capy[i], newx, newy);
 611         if (md < d)
 612             d = md;
 613     }
 614
 615     return d;
 616 }
 617
 618 /*
 619  * Drift the capitals
 620  * Return 1 for a stable drift, 0 for an unstable one.
 621  */
 622 static int
 623 drift(void)
 624 {
 625     int turns, i;
 626
 627     for (i = 0; i < nc; i++) {
 628         capy[i] = (2 * i) / WORLD_X;
 629         capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
 630         if (capy[i] >= WORLD_Y) {
 631             fprintf(stderr,
 632                     "%s: world not big enough for all the continents\n",
 633                     program_name);
 634             exit(1);
 635         }
 636     }
 637
 638     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 639         if (stable(turns))
 640             return 1;
 641         for (i = 0; i < nc; ++i)
 642             fl_move(i);
 643     }
 644     return 0;
 645 }
 646
 647 /*
 648  * Has the drift stabilized?
 649  * @turns is the number of turns so far.
 650  */
 651 static int
 652 stable(int turns)
 653 {
 654     static int mc[STABLE_CYCLE];
 655     int i, isod, d = 0, stab = 1;
 656
 657     if (!turns) {
 658         for (i = 0; i < STABLE_CYCLE; i++)
 659             mc[i] = i;
 660     }
 661
 662     if (turns <= DRIFT_BEFORE_CHECK)
 663         return 0;
 664
 665     for (i = 0; i < nc; ++i) {
 666         isod = iso(i, capx[i], capy[i]);
 667         if (isod > d)
 668             d = isod;
 669     }
 670
 671     for (i = 0; i < STABLE_CYCLE; ++i)
 672         if (d != mc[i])
 673             stab = 0;
 674
 675     mc[turns % STABLE_CYCLE] = d;
 676     return stab;
 677 }
 678
 679 /* This routine does the actual drifting
 680 */
 681
 682 static void
 683 fl_move(int j)
 684 {
 685     int dir, i, newx, newy;
 686
 687     dir = DIR_L + roll0(6);
 688     for (i = 0; i < 6; i++) {
 689         if (dir > DIR_LAST)
 690             dir -= 6;
 691         newx = new_x(capx[j] + diroff[dir][0]);
 692         newy = new_y(capy[j] + diroff[dir][1]);
 693         dir++;
 694         if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
 695             capx[j] = newx;
 696             capy[j] = newy;
 697             return;
 698         }
 699     }
 700 }
 701
 702 /****************************************************************************
 703   GROW THE CONTINENTS
 704 ****************************************************************************/
 705
 706 /* Look for a coastal sector of continent c
 707 */
 708
 709 static void
 710 find_coast(int c)
 711 {
 712     int i, dir, nx, ny;
 713
 714     for (i = 0; i < isecs[c]; ++i) {
 715         sectc[c][i] = 0;
 716         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 717             nx = new_x(sectx[c][i] + diroff[dir][0]);
 718             ny = new_y(secty[c][i] + diroff[dir][1]);
 719             if (own[nx][ny] == -1)
 720                 sectc[c][i] = 1;
 721         }
 722     }
 723 }
 724
 725 struct hexagon_iter {
 726     int dir, i, n;
 727 };
 728
 729 /*
 730  * Start iterating around @x0,@y0 at distance @d.
 731  * Set *x,*y to coordinates of the first sector.
 732  */
 733 static inline void
 734 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
 735               int *x, int *y)
 736 {
 737     *x = new_x(x0 - 2 * n);
 738     *y = y0;
 739     iter->dir = DIR_FIRST;
 740     iter->i = 0;
 741     iter->n = n;
 742 }
 743
 744 /*
 745  * Continue iteration started with hexagon_first().
 746  * Set *x,*y to coordinates of the next sector.
 747  * Return whether we're back at the first sector, i.e. iteration is
 748  * complete.
 749  */
 750 static inline int
 751 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
 752 {
 753     *x = new_x(*x + diroff[iter->dir][0]);
 754     *y = new_y(*y + diroff[iter->dir][1]);
 755     iter->i++;
 756     if (iter->i == iter->n) {
 757         iter->i = 0;
 758         iter->dir++;
 759     }
 760     return iter->dir <= DIR_LAST;
 761 }
 762
 763 /*
 764  * Is @x,@y in no exclusive zone other than perhaps @c's?
 765  */
 766 static int
 767 xzone_ok(int c, int x, int y)
 768 {
 769     int off = XYOFFSET(x, y);
 770
 771     return xzone[off] == c || xzone[off] == -1;
 772 }
 773
 774 /*
 775  * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
 776  */
 777 static void
 778 xzone_around_sector(int c, int x, int y, int dist)
 779 {
 780     int d, x1, y1, off;
 781     struct hexagon_iter hexit;
 782
 783     assert(xzone_ok(c, x, y));
 784
 785     xzone[XYOFFSET(x, y)] = c;
 786     for (d = 1; d <= dist; d++) {
 787         hexagon_first(&hexit, x, y, d, &x1, &y1);
 788         do {
 789             off = XYOFFSET(x1, y1);
 790             if (xzone[off] == -1)
 791                 xzone[off] = c;
 792             else if (xzone[off] != c)
 793                 xzone[off] = -2;
 794         } while (hexagon_next(&hexit, &x1, &y1));
 795     }
 796 }
 797
 798 /*
 799  * Add sectors within distance @dist to island @c's exclusive zone.
 800  */
 801 static void
 802 xzone_around_island(int c, int dist)
 803 {
 804     int i;
 805
 806     for (i = 0; i < isecs[c]; i++)
 807         xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
 808 }
 809
 810 /*
 811  * Initialize exclusive zones around @n islands.
 812  */
 813 static void
 814 xzone_init(int n)
 815 {
 816     int i, c;
 817
 818     for (i = 0; i < WORLD_SZ(); i++)
 819         xzone[i] = -1;
 820
 821     for (c = 0; c < n; c++)
 822         xzone_around_island(c, id);
 823 }
 824
 825 /*
 826  * Initialize breadth-first search.
 827  */
 828 static void
 829 bfs_init(void)
 830 {
 831     int i;
 832
 833     for (i = 0; i < WORLD_SZ(); i++) {
 834         closest[i] = -1;
 835         distance[i] = USHRT_MAX;
 836     }
 837
 838     bfs_queue_head = bfs_queue_tail = 0;
 839 }
 840
 841 /*
 842  * Add sector @x,@y to the BFS queue.
 843  * It's closest to @c, with distance @dist.
 844  */
 845 static void
 846 bfs_enqueue(int c, int x, int y, int dist)
 847 {
 848     int off = XYOFFSET(x, y);
 849
 850     assert(dist < distance[off]);
 851     closest[off] = c;
 852     distance[off] = dist;
 853     bfs_queue[bfs_queue_tail] = off;
 854     bfs_queue_tail++;
 855     if (bfs_queue_tail >= WORLD_SZ())
 856         bfs_queue_tail = 0;
 857     assert(bfs_queue_tail != bfs_queue_head);
 858 }
 859
 860 /*
 861  * Search breadth-first until the queue is empty.
 862  */
 863 static void
 864 bfs_run_queue(void)
 865 {
 866     int off, dist, i, noff, nx, ny;
 867     coord x, y;
 868
 869     while (bfs_queue_head != bfs_queue_tail) {
 870         off = bfs_queue[bfs_queue_head];
 871         bfs_queue_head++;
 872         if (bfs_queue_head >= WORLD_SZ())
 873             bfs_queue_head = 0;
 874         dist = distance[off] + 1;
 875         sctoff2xy(&x, &y, off);
 876         for (i = DIR_FIRST; i <= DIR_LAST; i++) {
 877             nx = new_x(x + diroff[i][0]);
 878             ny = new_y(y + diroff[i][1]);
 879             noff = XYOFFSET(nx, ny);
 880             if (dist < distance[noff]) {
 881                 bfs_enqueue(closest[off], nx, ny, dist);
 882             } else if (distance[noff] == dist) {
 883                 if (closest[off] != closest[noff])
 884                     closest[noff] = (natid)-1;
 885             } else
 886                 assert(distance[noff] < dist);
 887         }
 888     }
 889 }
 890
 891 /*
 892  * Add island @c's coastal sectors to the BFS queue, with distance 0.
 893  */
 894 static void
 895 bfs_enqueue_island(int c)
 896 {
 897     int i;
 898
 899     for (i = 0; i < isecs[c]; i++) {
 900         if (sectc[c][i])
 901             bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
 902     }
 903 }
 904
 905 /*
 906  * Compute spheres of influence
 907  * A continent's sphere of influence is the set of sectors closer to
 908  * it than to any other continent.
 909  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 910  * -1 if no single continent is closest.
 911  * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
 912  * land sector.
 913  */
 914 static void
 915 init_spheres_of_influence(void)
 916 {
 917     int c;
 918
 919     bfs_init();
 920     for (c = 0; c < nc; c++)
 921         bfs_enqueue_island(c);
 922     bfs_run_queue();
 923 }
 924
 925 /*
 926  * Is @x,@y in the same sphere of influence as island @c?
 927  * Always true when @c is a continent.
 928  */
 929 static int
 930 is_in_sphere(int c, int x, int y)
 931 {
 932     return c < nc || closest[XYOFFSET(x, y)] == c % nc;
 933 }
 934
 935 /*
 936  * Can island @c grow at @x,@y?
 937  */
 938 static int
 939 can_grow_at(int c, int x, int y)
 940 {
 941     return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
 942 }
 943
 944 static void
 945 adj_land_update(int x, int y)
 946 {
 947     int dir, nx, ny, noff;
 948
 949     assert(own[x][y] != -1);
 950
 951     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 952         nx = new_x(x + diroff[dir][0]);
 953         ny = new_y(y + diroff[dir][1]);
 954         noff = XYOFFSET(nx, ny);
 955         adj_land[noff] |= 1u << DIR_BACK(dir);
 956     }
 957 }
 958
 959 static void
 960 add_sector(int c, int x, int y)
 961 {
 962     assert(own[x][y] == -1);
 963     xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
 964     sectx[c][isecs[c]] = x;
 965     secty[c][isecs[c]] = y;
 966     isecs[c]++;
 967     own[x][y] = c;
 968     adj_land_update(x, y);
 969 }
 970
 971 static int
 972 grow_weight(int c, int x, int y, int spike)
 973 {
 974     int n, b;
 975
 976     /*
 977      * #Land neighbors is #bits set in adj_land[].
 978      * Count them Brian Kernighan's way.
 979      */
 980     n = 0;
 981     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
 982         n++;
 983     assert(n > 0 && n < 7);
 984
 985     if (spike)
 986         return (6 - n) * (6 - n);
 987
 988     return n * n * n;
 989 }
 990
 991 static int
 992 grow_one_sector(int c)
 993 {
 994     int spike = roll0(100) < sp;
 995     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
 996
 997     assert(cur_seen < UINT_MAX);
 998     cur_seen++;
 999     wsum = 0;
1000     newx = newy = -1;
1001
1002     for (i = 0; i < isecs[c]; i++) {
1003         x = sectx[c][i];
1004         y = secty[c][i];
1005         off = XYOFFSET(x, y);
1006
1007         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1008             if (adj_land[off] & (1u << dir))
1009                 continue;
1010             nx = new_x(x + diroff[dir][0]);
1011             ny = new_y(y + diroff[dir][1]);
1012             noff = XYOFFSET(nx, ny);
1013             if (seen[noff] == cur_seen)
1014                 continue;
1015             assert(seen[noff] < cur_seen);
1016             seen[noff] = cur_seen;
1017             if (!can_grow_at(c, nx, ny))
1018                 continue;
1019             w = grow_weight(c, nx, ny, spike);
1020             assert(wsum < INT_MAX - w);
1021             wsum += w;
1022             if (roll0(wsum) < w) {
1023                 newx = nx;
1024                 newy = ny;
1025             }
1026         }
1027     }
1028
1029     if (!wsum)
1030         return 0;
1031
1032     add_sector(c, newx, newy);
1033     return 1;
1034 }
1035
1036 /*
1037  * Grow the continents.
1038  * Return 1 on success, 0 on error.
1039  */
1040 static int
1041 grow_continents(void)
1042 {
1043     int done = 1;
1044     int c, secs;
1045
1046     xzone_init(0);
1047
1048     for (c = 0; c < nc; ++c) {
1049         isecs[c] = 0;
1050         if (!can_grow_at(c, capx[c], capy[c])
1051             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1052             done = 0;
1053             continue;
1054         }
1055         add_sector(c, capx[c], capy[c]);
1056         add_sector(c, new_x(capx[c] + 2), capy[c]);
1057     }
1058
1059     if (!done) {
1060         qprint("No room for continents\n");
1061         return 0;
1062     }
1063
1064     for (secs = 2; secs < sc && done; secs++) {
1065         for (c = 0; c < nc; ++c) {
1066             if (!grow_one_sector(c))
1067                 done = 0;
1068         }
1069     }
1070
1071     for (c = 0; c < nc; ++c)
1072         find_coast(c);
1073
1074     if (!done)
1075         qprint("Only managed to grow %d out of %d sectors.\n",
1076                secs - 1, sc);
1077     return done;
1078 }
1079
1080 /****************************************************************************
1081   GROW THE ISLANDS
1082 ****************************************************************************/
1083
1084 /*
1085  * Place additional island @c's first sector.
1086  * Return 1 on success, 0 on error.
1087  */
1088 static int
1089 place_island(int c)
1090 {
1091     int n, x, y, newx, newy;
1092
1093     n = 0;
1094
1095     for (y = 0; y < WORLD_Y; y++) {
1096         for (x = y % 2; x < WORLD_X; x += 2) {
1097             if (can_grow_at(c, x, y)) {
1098                 n++;
1099                 if (!roll0(n)) {
1100                     newx = x;
1101                     newy = y;
1102                 }
1103             }
1104         }
1105     }
1106
1107     if (n)
1108         add_sector(c, newx, newy);
1109     return n;
1110 }
1111
1112 /*
1113  * Grow the additional islands.
1114  * Return 1 on success, 0 on error.
1115  */
1116 static int
1117 grow_islands(void)
1118 {
1119     int stunted_islands = 0;
1120     int c, secs, isiz;
1121
1122     xzone_init(nc);
1123     init_spheres_of_influence();
1124
1125     for (c = nc; c < nc + ni; ++c) {
1126         isecs[c] = 0;
1127         if (c % nc == 0)
1128             isiz = roll(is) + roll0(is);
1129         assert(isiz > 0);
1130
1131         if (!place_island(c)) {
1132             qprint("\nNo room for island #%d", c - nc + 1);
1133             break;
1134         }
1135
1136         for (secs = 1; secs < isiz; secs++) {
1137             if (!grow_one_sector(c)) {
1138                 stunted_islands++;
1139                 break;
1140             }
1141         }
1142
1143         find_coast(c);
1144         qprint(" %d(%d)", c - nc + 1, secs);
1145     }
1146
1147     qprint("\n");
1148
1149     if (c < nc + ni)
1150         return 0;
1151
1152     if (stunted_islands)
1153         qprint("%d stunted island%s\n",
1154                stunted_islands, splur(stunted_islands));
1155     return 1;
1156 }
1157
1158 /****************************************************************************
1159   CREATE ELEVATIONS
1160 ****************************************************************************/
1161 static void
1162 create_elevations(void)
1163 {
1164     int i, j;
1165
1166     for (i = 0; i < WORLD_X; i++) {
1167         for (j = 0; j < WORLD_Y; j++)
1168             elev[i][j] = -INFINITE_ELEVATION;
1169     }
1170     elevate_land();
1171     elevate_sea();
1172 }
1173
1174 /* Generic function for finding the distance to the closest sea, land, or
1175    mountain
1176 */
1177 static int
1178 distance_to_what(int x, int y, int flag)
1179 {
1180     int d, px, py;
1181     struct hexagon_iter hexit;
1182
1183     for (d = 1; d < 5; ++d) {
1184         hexagon_first(&hexit, x, y, d, &px, &py);
1185         do {
1186             switch (flag) {
1187             case 0:             /* distance to sea */
1188                 if (own[px][py] == -1)
1189                     return d;
1190                 break;
1191             case 1:             /* distance to land */
1192                 if (own[px][py] != -1)
1193                     return d;
1194                 break;
1195             case 2:             /* distance to mountain */
1196                 if (elev[px][py] == INFINITE_ELEVATION)
1197                     return d;
1198                 break;
1199             }
1200         } while (hexagon_next(&hexit, &px, &py));
1201     }
1202     return d;
1203 }
1204
1205 #define ELEV elev[sectx[c][i]][secty[c][i]]
1206 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1207 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1208
1209 /* Decide where the mountains go
1210 */
1211 static void
1212 elevate_land(void)
1213 {
1214     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
1215         r, dk;
1216
1217     for (c = 0; c < nc + ni; ++c) {
1218         total = 0;
1219         ns = isecs[c];
1220         nm = (pm * ns) / 100;
1221
1222 /* Place the mountains */
1223
1224         for (i = 0; i < ns; ++i) {
1225             dsea[i] = distance_to_sea();
1226             weight[i] = (total += (dsea[i] * dsea[i]));
1227         }
1228
1229         for (k = nm, mountain_search = 0;
1230              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1231              ++mountain_search) {
1232             r = roll0(total);
1233             for (i = 0; i < ns; ++i)
1234                 if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
1235                     (c >= nc ||
1236                      ((!(capx[c] == sectx[c][i] &&
1237                          capy[c] == secty[c][i])) &&
1238                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1239                          capy[c] == secty[c][i]))))) {
1240                     ELEV = INFINITE_ELEVATION;
1241                     break;
1242                 }
1243             --k;
1244         }
1245
1246 /* Elevate land that is not mountain and not capital */
1247
1248         for (i = 0; i < ns; ++i)
1249             dmoun[i] = distance_to_mountain();
1250         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1251           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1252           100 * INFINITE_ELEVATION;
1253         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1254             highest = 0;
1255             where = -1;
1256             for (i = 0; i < ns; ++i) {
1257                 if (ELEV == -INFINITE_ELEVATION &&
1258                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1259                                     capy[c] == secty[c][i])) &&
1260                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1261                                     capy[c] == secty[c][i]))))) {
1262                     h = 3 * (5 - dmoun[i]) + dsea[i];
1263                     assert(h > 0);
1264                     if (h > highest) {
1265                         highest = h;
1266                         where = i;
1267                     }
1268                 }
1269             }
1270             if (where == -1)
1271                 break;
1272             newk = k / 100;
1273             if (newk >= HILLMIN && newk < PLATMIN)
1274                 newk = PLATMIN;
1275             if (newk < LANDMIN)
1276                 newk = LANDMIN;
1277             elev[sectx[c][where]][secty[c][where]] = newk;
1278         }
1279
1280 /* Elevate the mountains and capitals */
1281
1282         for (i = 0; i < ns; ++i) {
1283             if (ELEV == INFINITE_ELEVATION) {
1284                 if (dsea[i] == 1)
1285                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1286                 else
1287                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1288                       roll0((256 - HIGHMIN) / 2);
1289             } else if (c < nc &&
1290                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1291                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1292                           capy[c] == secty[c][i]))))
1293                 ELEV = PLATMIN;
1294         }
1295     }
1296 }
1297
1298 #define distance_to_land() distance_to_what(x, y, 1)
1299
1300 static void
1301 elevate_sea(void)
1302 {
1303     int x, y;
1304
1305     for (y = 0; y < WORLD_Y; ++y) {
1306         for (x = y % 2; x < WORLD_X; x += 2) {
1307             if (elev[x][y] == -INFINITE_ELEVATION)
1308                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1309         }
1310     }
1311 }
1312
1313 static int
1314 elev_to_sct_type(int elevation)
1315 {
1316     if (elevation < LANDMIN)
1317         return SCT_WATER;
1318     if (elevation < HILLMIN)
1319         return SCT_RURAL;
1320     if (elevation < PLATMIN)
1321         return SCT_MOUNT;
1322     if (elevation < HIGHMIN)
1323         return SCT_RURAL;
1324     return SCT_MOUNT;
1325 }
1326
1327 /****************************************************************************
1328   ADD THE RESOURCES
1329 ****************************************************************************/
1330
1331 static int
1332 set_fert(int e)
1333 {
1334     int fert = 0;
1335     if (e < LANDMIN)
1336         fert = LANDMIN - e + 40;
1337     else if (e < FERT_MAX)
1338         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1339     if (fert > 100)
1340         fert = 100;
1341     return fert;
1342 }
1343
1344 static int
1345 set_oil(int e)
1346 {
1347     int oil = 0;
1348     if (e < LANDMIN)
1349         oil = (LANDMIN - e) * 2 + roll0(2);
1350     else if (e <= OIL_MAX)
1351         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1352     if (oil > 100)
1353         oil = 100;
1354     return oil;
1355 }
1356
1357 static int
1358 set_iron(int e)
1359 {
1360     int iron = 0;
1361     if (e >= IRON_MIN && e < HIGHMIN)
1362         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1363     if (iron > 100)
1364         iron = 100;
1365     return iron;
1366 }
1367
1368 static int
1369 set_gold(int e)
1370 {
1371     int gold = 0;
1372     if (e >= GOLD_MIN) {
1373         if (e < HIGHMIN)
1374             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1375         else
1376             gold = 100 - 20 * HIGHMIN / e;
1377     }
1378     if (gold > 100)
1379         gold = 100;
1380     return gold;
1381 }
1382
1383 static int
1384 set_uran(int e)
1385 {
1386     int uran = 0;
1387     if (e >= URAN_MIN && e < HIGHMIN)
1388         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1389     if (uran > 100)
1390         uran = 100;
1391     return uran;
1392 }
1393
1394 static void
1395 add_resources(struct sctstr *sct)
1396 {
1397     sct->sct_fertil = set_fert(sct->sct_elev);
1398     sct->sct_oil = set_oil(sct->sct_elev);
1399     sct->sct_min = set_iron(sct->sct_elev);
1400     sct->sct_gmin = set_gold(sct->sct_elev);
1401     sct->sct_uran = set_uran(sct->sct_elev);
1402 }
1403
1404 /****************************************************************************
1405   DESIGNATE THE SECTORS
1406 ****************************************************************************/
1407
1408 static void
1409 write_sects(void)
1410 {
1411     struct sctstr *sct;
1412     int x, y;
1413
1414     for (y = 0; y < WORLD_Y; y++) {
1415         for (x = y % 2; x < WORLD_X; x += 2) {
1416             sct = getsectp(x, y);
1417             sct->sct_elev = elev[x][y];
1418             sct->sct_type = elev_to_sct_type(elev[x][y]);
1419             sct->sct_newtype = sct->sct_type;
1420             sct->sct_dterr = own[sct->sct_x][y] + 1;
1421             add_resources(sct);
1422         }
1423     }
1424     set_coastal_flags();
1425 }
1426
1427 /****************************************************************************
1428   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1429 ****************************************************************************/
1430 static void
1431 output(void)
1432 {
1433     int sx, sy, x, y, c, type;
1434
1435     if (quiet == 0) {
1436         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1437             y = YNORM(sy);
1438             puts("");
1439             if (y % 2)
1440                 printf(" ");
1441             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1442                 x = XNORM(sx);
1443                 c = own[x][y];
1444                 type = elev_to_sct_type(elev[x][y]);
1445                 if (type == SCT_WATER)
1446                     printf(". ");
1447                 else if (type == SCT_MOUNT)
1448                     printf("^ ");
1449                 else if (c >= nc)
1450                     printf("%% ");
1451                 else {
1452                     assert(0 <= c && c < nc);
1453                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1454                         && y == capy[c])
1455                         printf("%c ", numletter[c % 62]);
1456                     else
1457                         printf("# ");
1458                 }
1459             }
1460         }
1461     }
1462 }
1463
1464 /*
1465  * Print a map to help visualize own[][].
1466  * This is for debugging.
1467  */
1468 void
1469 print_own_map(void)
1470 {
1471     int sx, sy, x, y;
1472
1473     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1474         y = YNORM(sy);
1475         printf("%4d ", sy);
1476         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1477             x = XNORM(sx);
1478             if ((x + y) & 1)
1479                 putchar(' ');
1480             else if (own[x][y] == -1)
1481                 putchar('.');
1482             else
1483                 putchar(numletter[own[x][y] % 62]);
1484         }
1485         putchar('\n');
1486     }
1487 }
1488
1489 /*
1490  * Print a map to help visualize elev[][].
1491  * This is for debugging.  It expects the terminal to understand
1492  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1493  */
1494 void
1495 print_elev_map(void)
1496 {
1497     int sx, sy, x, y, sat;
1498
1499     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1500         y = YNORM(sy);
1501         printf("%4d ", sy);
1502         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1503             x = XNORM(sx);
1504             if ((x + y) & 1)
1505                 putchar(' ');
1506             else if (!elev[x][y])
1507                 putchar(' ');
1508             else if (elev[x][y] < 0) {
1509                 sat = 256 + elev[x][y] * 2;
1510                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1511             } else if (elev[x][y] < HIGHMIN / 2) {
1512                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1513                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1514             } else if (elev[x][y] < HIGHMIN) {
1515                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1516                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1517             } else {
1518                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1519                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1520             }
1521         }
1522         putchar('\n');
1523     }
1524 }
1525
1526 /*
1527  * Print a map to help visualize xzone[].
1528  * This is for debugging.
1529  */
1530 void
1531 print_xzone_map(void)
1532 {
1533     int sx, sy, x, y, off;
1534
1535     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1536         y = YNORM(sy);
1537         printf("%4d ", sy);
1538         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1539             x = XNORM(sx);
1540             off = XYOFFSET(x, y);
1541             if ((x + y) & 1)
1542                 putchar(' ');
1543             else if (own[x][y] >= 0)
1544                 putchar('-');
1545             else if (xzone[off] >= 0)
1546                 putchar(numletter[xzone[off] % 62]);
1547             else {
1548                 assert(own[x][y] == -1);
1549                 putchar(xzone[off] == -1 ? '.' : '!');
1550             }
1551         }
1552         putchar('\n');
1553     }
1554 }
1555
1556 /*
1557  * Print a map to help visualize closest[].
1558  * This is for debugging.
1559  */
1560 void
1561 print_closest_map(void)
1562 {
1563     int sx, sy, x, y, off;
1564
1565     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1566         y = YNORM(sy);
1567         printf("%4d ", sy);
1568         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1569             x = XNORM(sx);
1570             off = XYOFFSET(x, y);
1571             if ((x + y) & 1)
1572                 putchar(' ');
1573             else if (closest[off] == (natid)-1)
1574                 putchar('.');
1575             else if (!distance[off]) {
1576                 assert(closest[off] == own[x][y]);
1577                 putchar('-');
1578             } else {
1579                 putchar(numletter[closest[off] % 62]);
1580             }
1581         }
1582         printf("\n");
1583     }
1584 }
1585
1586 void
1587 print_distance_map(void)
1588 {
1589     int sx, sy, x, y, off;
1590
1591     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1592         y = YNORM(sy);
1593         printf("%4d ", sy);
1594         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1595             x = XNORM(sx);
1596             off = XYOFFSET(x, y);
1597             if ((x + y) & 1)
1598                 putchar(' ');
1599             else if (closest[off] == (natid)-1)
1600                 putchar('.');
1601             else if (!distance[off]) {
1602                 assert(closest[off] == own[x][y]);
1603                 putchar('-');
1604             } else {
1605                 putchar(numletter[distance[off] % 62]);
1606             }
1607         }
1608         printf("\n");
1609     }
1610 }
1611
1612
1613 /***************************************************************************
1614   WRITE A SCRIPT FOR PLACING CAPITALS
1615 ****************************************************************************/
1616 static int
1617 write_newcap_script(void)
1618 {
1619     int c;
1620     FILE *script = fopen(outfile, "w");
1621
1622     if (!script) {
1623         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1624                 program_name, outfile, strerror(errno));
1625         return 0;
1626     }
1627
1628     for (c = 0; c < nc; ++c) {
1629         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1630         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1631     }
1632     fprintf(script, "add %d visitor visitor v\n", c + 1);
1633     fclose(script);
1634     return 1;
1635 }
1636
1637 static void
1638 qprint(const char *const fmt, ...)
1639 {
1640     va_list ap;
1641
1642     if (!quiet) {
1643         va_start(ap, fmt);
1644         vfprintf(stdout, fmt, ap);
1645         va_end(ap);
1646     }
1647 }
1648
1649 static void
1650 set_coastal_flags(void)
1651 {
1652     int i, j;
1653     struct sctstr *sp;
1654
1655     for (i = 0; i < nc + ni; ++i) {
1656         for (j = 0; j < isecs[i]; j++) {
1657             sp = getsectp(sectx[i][j], secty[i][j]);
1658             sp->sct_coastal = sectc[i][j];
1659         }
1660     }
1661 }