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 with the same sizes.
  69  *
  70  * Pick an island size, and place one island's first sector into each
  71  * sphere, randomly.  Then add one sector to each island in turn,
  72  * until they have the intended size.  Repeat until the specified
  73  * number of islands 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 any of
  80  * the islands being grown lacks the room to grow further.
  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 is_land = own[x][y] != -1;
 948     int dir, nx, ny, noff;
 949
 950     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 951         nx = new_x(x + diroff[dir][0]);
 952         ny = new_y(y + diroff[dir][1]);
 953         noff = XYOFFSET(nx, ny);
 954         if (is_land)
 955             adj_land[noff] |= 1u << DIR_BACK(dir);
 956         else
 957             adj_land[noff] &= ~(1u << DIR_BACK(dir));
 958     }
 959 }
 960
 961 static void
 962 add_sector(int c, int x, int y)
 963 {
 964     assert(own[x][y] == -1);
 965     xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
 966     sectx[c][isecs[c]] = x;
 967     secty[c][isecs[c]] = y;
 968     isecs[c]++;
 969     own[x][y] = c;
 970     adj_land_update(x, y);
 971 }
 972
 973 static int
 974 grow_weight(int c, int x, int y, int spike)
 975 {
 976     int n, b;
 977
 978     /*
 979      * #Land neighbors is #bits set in adj_land[].
 980      * Count them Brian Kernighan's way.
 981      */
 982     n = 0;
 983     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
 984         n++;
 985     assert(n > 0 && n < 7);
 986
 987     if (spike)
 988         return (6 - n) * (6 - n);
 989
 990     return n * n * n;
 991 }
 992
 993 static int
 994 grow_one_sector(int c)
 995 {
 996     int spike = roll0(100) < sp;
 997     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
 998
 999     assert(cur_seen < UINT_MAX);
1000     cur_seen++;
1001     wsum = 0;
1002     newx = newy = -1;
1003
1004     for (i = 0; i < isecs[c]; i++) {
1005         x = sectx[c][i];
1006         y = secty[c][i];
1007         off = XYOFFSET(x, y);
1008
1009         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1010             if (adj_land[off] & (1u << dir))
1011                 continue;
1012             nx = new_x(x + diroff[dir][0]);
1013             ny = new_y(y + diroff[dir][1]);
1014             noff = XYOFFSET(nx, ny);
1015             if (seen[noff] == cur_seen)
1016                 continue;
1017             assert(seen[noff] < cur_seen);
1018             seen[noff] = cur_seen;
1019             if (!can_grow_at(c, nx, ny))
1020                 continue;
1021             w = grow_weight(c, nx, ny, spike);
1022             assert(wsum < INT_MAX - w);
1023             wsum += w;
1024             if (roll0(wsum) < w) {
1025                 newx = nx;
1026                 newy = ny;
1027             }
1028         }
1029     }
1030
1031     if (!wsum)
1032         return 0;
1033
1034     add_sector(c, newx, newy);
1035     return 1;
1036 }
1037
1038 /*
1039  * Grow the continents.
1040  * Return 1 on success, 0 on error.
1041  */
1042 static int
1043 grow_continents(void)
1044 {
1045     int done = 1;
1046     int c, secs;
1047
1048     xzone_init(0);
1049
1050     for (c = 0; c < nc; ++c) {
1051         isecs[c] = 0;
1052         if (!can_grow_at(c, capx[c], capy[c])
1053             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1054             done = 0;
1055             continue;
1056         }
1057         add_sector(c, capx[c], capy[c]);
1058         add_sector(c, new_x(capx[c] + 2), capy[c]);
1059     }
1060
1061     if (!done) {
1062         qprint("No room for continents\n");
1063         return 0;
1064     }
1065
1066     for (secs = 2; secs < sc && done; secs++) {
1067         for (c = 0; c < nc; ++c) {
1068             if (!grow_one_sector(c))
1069                 done = 0;
1070         }
1071     }
1072
1073     for (c = 0; c < nc; ++c)
1074         find_coast(c);
1075
1076     if (!done)
1077         qprint("Only managed to grow %d out of %d sectors.\n",
1078                secs - 1, sc);
1079     return done;
1080 }
1081
1082 /****************************************************************************
1083   GROW THE ISLANDS
1084 ****************************************************************************/
1085
1086 /*
1087  * Place additional island @c's first sector.
1088  * Return 1 on success, 0 on error.
1089  */
1090 static int
1091 place_island(int c)
1092 {
1093     int n, x, y, newx, newy;
1094
1095     n = 0;
1096
1097     for (y = 0; y < WORLD_Y; y++) {
1098         for (x = y % 2; x < WORLD_X; x += 2) {
1099             if (can_grow_at(c, x, y)) {
1100                 n++;
1101                 if (!roll0(n)) {
1102                     newx = x;
1103                     newy = y;
1104                 }
1105             }
1106         }
1107     }
1108
1109     if (n)
1110         add_sector(c, newx, newy);
1111     return n;
1112 }
1113
1114 /*
1115  * Grow the additional islands.
1116  * Return 1 on success, 0 on error.
1117  */
1118 static int
1119 grow_islands(void)
1120 {
1121     int n = ni / nc;
1122     int stunted_islands = 0;
1123     int xzone_valid = 0;
1124     int i, j, c, done, secs, isiz, x, y;
1125
1126     init_spheres_of_influence();
1127
1128     for (i = 0; i < n; i++) {
1129         c = nc + i * nc;
1130
1131         if (!xzone_valid)
1132             xzone_init(c);
1133
1134         isiz = roll(is) + roll0(is);
1135
1136         for (j = 0; j < nc; j++) {
1137             isecs[c + j] = 0;
1138             if (!place_island(c + j)) {
1139                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1140                 return 0;
1141             }
1142         }
1143
1144         done = 1;
1145         for (secs = 1; secs < isiz && done; secs++) {
1146             for (j = 0; j < nc; j++) {
1147                 if (!grow_one_sector(c + j))
1148                     done = 0;
1149             }
1150         }
1151
1152         if (!done) {
1153             secs--;
1154             for (j = 0; j < nc; j++) {
1155                 if (isecs[c + j] != secs) {
1156                     isecs[c + j]--;
1157                     assert(isecs[c + j] == secs);
1158                     x = sectx[c + j][secs];
1159                     y = secty[c + j][secs];
1160                     own[x][y] = -1;
1161                     adj_land_update(x, y);
1162                 }
1163             }
1164             xzone_valid = 0;
1165         }
1166
1167         for (j = 0; j < nc; j++)
1168             stunted_islands += isecs[c + j] != isiz;
1169
1170         for (j = 0; j < nc; j++)
1171             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1172     }
1173
1174     qprint("\n");
1175
1176     if (stunted_islands)
1177         qprint("%d stunted island%s\n",
1178                stunted_islands, splur(stunted_islands));
1179
1180     for (c = nc; c < nc + ni; c++)
1181         find_coast(c);
1182
1183     return 1;
1184 }
1185
1186 /****************************************************************************
1187   CREATE ELEVATIONS
1188 ****************************************************************************/
1189 static void
1190 create_elevations(void)
1191 {
1192     int i, j;
1193
1194     for (i = 0; i < WORLD_X; i++) {
1195         for (j = 0; j < WORLD_Y; j++)
1196             elev[i][j] = -INFINITE_ELEVATION;
1197     }
1198     elevate_land();
1199     elevate_sea();
1200 }
1201
1202 /* Generic function for finding the distance to the closest sea, land, or
1203    mountain
1204 */
1205 static int
1206 distance_to_what(int x, int y, int flag)
1207 {
1208     int d, px, py;
1209     struct hexagon_iter hexit;
1210
1211     for (d = 1; d < 5; ++d) {
1212         hexagon_first(&hexit, x, y, d, &px, &py);
1213         do {
1214             switch (flag) {
1215             case 0:             /* distance to sea */
1216                 if (own[px][py] == -1)
1217                     return d;
1218                 break;
1219             case 1:             /* distance to land */
1220                 if (own[px][py] != -1)
1221                     return d;
1222                 break;
1223             case 2:             /* distance to mountain */
1224                 if (elev[px][py] == INFINITE_ELEVATION)
1225                     return d;
1226                 break;
1227             }
1228         } while (hexagon_next(&hexit, &px, &py));
1229     }
1230     return d;
1231 }
1232
1233 #define ELEV elev[sectx[c][i]][secty[c][i]]
1234 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1235 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1236
1237 /* Decide where the mountains go
1238 */
1239 static void
1240 elevate_land(void)
1241 {
1242     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
1243         r, dk;
1244
1245     for (c = 0; c < nc + ni; ++c) {
1246         total = 0;
1247         ns = isecs[c];
1248         nm = (pm * ns) / 100;
1249
1250 /* Place the mountains */
1251
1252         for (i = 0; i < ns; ++i) {
1253             dsea[i] = distance_to_sea();
1254             weight[i] = (total += (dsea[i] * dsea[i]));
1255         }
1256
1257         for (k = nm, mountain_search = 0;
1258              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1259              ++mountain_search) {
1260             r = roll0(total);
1261             for (i = 0; i < ns; ++i)
1262                 if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
1263                     (c >= nc ||
1264                      ((!(capx[c] == sectx[c][i] &&
1265                          capy[c] == secty[c][i])) &&
1266                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1267                          capy[c] == secty[c][i]))))) {
1268                     ELEV = INFINITE_ELEVATION;
1269                     break;
1270                 }
1271             --k;
1272         }
1273
1274 /* Elevate land that is not mountain and not capital */
1275
1276         for (i = 0; i < ns; ++i)
1277             dmoun[i] = distance_to_mountain();
1278         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1279           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1280           100 * INFINITE_ELEVATION;
1281         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1282             highest = 0;
1283             where = -1;
1284             for (i = 0; i < ns; ++i) {
1285                 if (ELEV == -INFINITE_ELEVATION &&
1286                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1287                                     capy[c] == secty[c][i])) &&
1288                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1289                                     capy[c] == secty[c][i]))))) {
1290                     h = 3 * (5 - dmoun[i]) + dsea[i];
1291                     assert(h > 0);
1292                     if (h > highest) {
1293                         highest = h;
1294                         where = i;
1295                     }
1296                 }
1297             }
1298             if (where == -1)
1299                 break;
1300             newk = k / 100;
1301             if (newk >= HILLMIN && newk < PLATMIN)
1302                 newk = PLATMIN;
1303             if (newk < LANDMIN)
1304                 newk = LANDMIN;
1305             elev[sectx[c][where]][secty[c][where]] = newk;
1306         }
1307
1308 /* Elevate the mountains and capitals */
1309
1310         for (i = 0; i < ns; ++i) {
1311             if (ELEV == INFINITE_ELEVATION) {
1312                 if (dsea[i] == 1)
1313                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1314                 else
1315                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1316                       roll0((256 - HIGHMIN) / 2);
1317             } else if (c < nc &&
1318                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1319                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1320                           capy[c] == secty[c][i]))))
1321                 ELEV = PLATMIN;
1322         }
1323     }
1324 }
1325
1326 #define distance_to_land() distance_to_what(x, y, 1)
1327
1328 static void
1329 elevate_sea(void)
1330 {
1331     int x, y;
1332
1333     for (y = 0; y < WORLD_Y; ++y) {
1334         for (x = y % 2; x < WORLD_X; x += 2) {
1335             if (elev[x][y] == -INFINITE_ELEVATION)
1336                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1337         }
1338     }
1339 }
1340
1341 static int
1342 elev_to_sct_type(int elevation)
1343 {
1344     if (elevation < LANDMIN)
1345         return SCT_WATER;
1346     if (elevation < HILLMIN)
1347         return SCT_RURAL;
1348     if (elevation < PLATMIN)
1349         return SCT_MOUNT;
1350     if (elevation < HIGHMIN)
1351         return SCT_RURAL;
1352     return SCT_MOUNT;
1353 }
1354
1355 /****************************************************************************
1356   ADD THE RESOURCES
1357 ****************************************************************************/
1358
1359 static int
1360 set_fert(int e)
1361 {
1362     int fert = 0;
1363     if (e < LANDMIN)
1364         fert = LANDMIN - e + 40;
1365     else if (e < FERT_MAX)
1366         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1367     if (fert > 100)
1368         fert = 100;
1369     return fert;
1370 }
1371
1372 static int
1373 set_oil(int e)
1374 {
1375     int oil = 0;
1376     if (e < LANDMIN)
1377         oil = (LANDMIN - e) * 2 + roll0(2);
1378     else if (e <= OIL_MAX)
1379         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1380     if (oil > 100)
1381         oil = 100;
1382     return oil;
1383 }
1384
1385 static int
1386 set_iron(int e)
1387 {
1388     int iron = 0;
1389     if (e >= IRON_MIN && e < HIGHMIN)
1390         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1391     if (iron > 100)
1392         iron = 100;
1393     return iron;
1394 }
1395
1396 static int
1397 set_gold(int e)
1398 {
1399     int gold = 0;
1400     if (e >= GOLD_MIN) {
1401         if (e < HIGHMIN)
1402             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1403         else
1404             gold = 100 - 20 * HIGHMIN / e;
1405     }
1406     if (gold > 100)
1407         gold = 100;
1408     return gold;
1409 }
1410
1411 static int
1412 set_uran(int e)
1413 {
1414     int uran = 0;
1415     if (e >= URAN_MIN && e < HIGHMIN)
1416         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1417     if (uran > 100)
1418         uran = 100;
1419     return uran;
1420 }
1421
1422 static void
1423 add_resources(struct sctstr *sct)
1424 {
1425     sct->sct_fertil = set_fert(sct->sct_elev);
1426     sct->sct_oil = set_oil(sct->sct_elev);
1427     sct->sct_min = set_iron(sct->sct_elev);
1428     sct->sct_gmin = set_gold(sct->sct_elev);
1429     sct->sct_uran = set_uran(sct->sct_elev);
1430 }
1431
1432 /****************************************************************************
1433   DESIGNATE THE SECTORS
1434 ****************************************************************************/
1435
1436 static void
1437 write_sects(void)
1438 {
1439     struct sctstr *sct;
1440     int x, y;
1441
1442     for (y = 0; y < WORLD_Y; y++) {
1443         for (x = y % 2; x < WORLD_X; x += 2) {
1444             sct = getsectp(x, y);
1445             sct->sct_elev = elev[x][y];
1446             sct->sct_type = elev_to_sct_type(elev[x][y]);
1447             sct->sct_newtype = sct->sct_type;
1448             sct->sct_dterr = own[sct->sct_x][y] + 1;
1449             add_resources(sct);
1450         }
1451     }
1452     set_coastal_flags();
1453 }
1454
1455 /****************************************************************************
1456   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1457 ****************************************************************************/
1458 static void
1459 output(void)
1460 {
1461     int sx, sy, x, y, c, type;
1462
1463     if (quiet == 0) {
1464         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1465             y = YNORM(sy);
1466             puts("");
1467             if (y % 2)
1468                 printf(" ");
1469             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1470                 x = XNORM(sx);
1471                 c = own[x][y];
1472                 type = elev_to_sct_type(elev[x][y]);
1473                 if (type == SCT_WATER)
1474                     printf(". ");
1475                 else if (type == SCT_MOUNT)
1476                     printf("^ ");
1477                 else if (c >= nc)
1478                     printf("%% ");
1479                 else {
1480                     assert(0 <= c && c < nc);
1481                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1482                         && y == capy[c])
1483                         printf("%c ", numletter[c % 62]);
1484                     else
1485                         printf("# ");
1486                 }
1487             }
1488         }
1489     }
1490 }
1491
1492 /*
1493  * Print a map to help visualize own[][].
1494  * This is for debugging.
1495  */
1496 void
1497 print_own_map(void)
1498 {
1499     int sx, sy, x, y;
1500
1501     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1502         y = YNORM(sy);
1503         printf("%4d ", sy);
1504         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1505             x = XNORM(sx);
1506             if ((x + y) & 1)
1507                 putchar(' ');
1508             else if (own[x][y] == -1)
1509                 putchar('.');
1510             else
1511                 putchar(numletter[own[x][y] % 62]);
1512         }
1513         putchar('\n');
1514     }
1515 }
1516
1517 /*
1518  * Print a map to help visualize elev[][].
1519  * This is for debugging.  It expects the terminal to understand
1520  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1521  */
1522 void
1523 print_elev_map(void)
1524 {
1525     int sx, sy, x, y, sat;
1526
1527     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1528         y = YNORM(sy);
1529         printf("%4d ", sy);
1530         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1531             x = XNORM(sx);
1532             if ((x + y) & 1)
1533                 putchar(' ');
1534             else if (!elev[x][y])
1535                 putchar(' ');
1536             else if (elev[x][y] < 0) {
1537                 sat = 256 + elev[x][y] * 2;
1538                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1539             } else if (elev[x][y] < HIGHMIN / 2) {
1540                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1541                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1542             } else if (elev[x][y] < HIGHMIN) {
1543                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1544                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1545             } else {
1546                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1547                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1548             }
1549         }
1550         putchar('\n');
1551     }
1552 }
1553
1554 /*
1555  * Print a map to help visualize xzone[].
1556  * This is for debugging.
1557  */
1558 void
1559 print_xzone_map(void)
1560 {
1561     int sx, sy, x, y, off;
1562
1563     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1564         y = YNORM(sy);
1565         printf("%4d ", sy);
1566         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1567             x = XNORM(sx);
1568             off = XYOFFSET(x, y);
1569             if ((x + y) & 1)
1570                 putchar(' ');
1571             else if (own[x][y] >= 0)
1572                 putchar('-');
1573             else if (xzone[off] >= 0)
1574                 putchar(numletter[xzone[off] % 62]);
1575             else {
1576                 assert(own[x][y] == -1);
1577                 putchar(xzone[off] == -1 ? '.' : '!');
1578             }
1579         }
1580         putchar('\n');
1581     }
1582 }
1583
1584 /*
1585  * Print a map to help visualize closest[].
1586  * This is for debugging.
1587  */
1588 void
1589 print_closest_map(void)
1590 {
1591     int sx, sy, x, y, off;
1592
1593     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1594         y = YNORM(sy);
1595         printf("%4d ", sy);
1596         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1597             x = XNORM(sx);
1598             off = XYOFFSET(x, y);
1599             if ((x + y) & 1)
1600                 putchar(' ');
1601             else if (closest[off] == (natid)-1)
1602                 putchar('.');
1603             else if (!distance[off]) {
1604                 assert(closest[off] == own[x][y]);
1605                 putchar('-');
1606             } else {
1607                 putchar(numletter[closest[off] % 62]);
1608             }
1609         }
1610         printf("\n");
1611     }
1612 }
1613
1614 void
1615 print_distance_map(void)
1616 {
1617     int sx, sy, x, y, off;
1618
1619     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1620         y = YNORM(sy);
1621         printf("%4d ", sy);
1622         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1623             x = XNORM(sx);
1624             off = XYOFFSET(x, y);
1625             if ((x + y) & 1)
1626                 putchar(' ');
1627             else if (closest[off] == (natid)-1)
1628                 putchar('.');
1629             else if (!distance[off]) {
1630                 assert(closest[off] == own[x][y]);
1631                 putchar('-');
1632             } else {
1633                 putchar(numletter[distance[off] % 62]);
1634             }
1635         }
1636         printf("\n");
1637     }
1638 }
1639
1640
1641 /***************************************************************************
1642   WRITE A SCRIPT FOR PLACING CAPITALS
1643 ****************************************************************************/
1644 static int
1645 write_newcap_script(void)
1646 {
1647     int c;
1648     FILE *script = fopen(outfile, "w");
1649
1650     if (!script) {
1651         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1652                 program_name, outfile, strerror(errno));
1653         return 0;
1654     }
1655
1656     for (c = 0; c < nc; ++c) {
1657         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1658         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1659     }
1660     fprintf(script, "add %d visitor visitor v\n", c + 1);
1661     fclose(script);
1662     return 1;
1663 }
1664
1665 static void
1666 qprint(const char *const fmt, ...)
1667 {
1668     va_list ap;
1669
1670     if (!quiet) {
1671         va_start(ap, fmt);
1672         vfprintf(stdout, fmt, ap);
1673         va_end(ap);
1674     }
1675 }
1676
1677 static void
1678 set_coastal_flags(void)
1679 {
1680     int i, j;
1681     struct sctstr *sp;
1682
1683     for (i = 0; i < nc + ni; ++i) {
1684         for (j = 0; j < isecs[i]; j++) {
1685             sp = getsectp(sectx[i][j], secty[i][j]);
1686             sp->sct_coastal = sectc[i][j];
1687         }
1688     }
1689 }