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