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  * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
 113  * 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 /* The following five numbers refer to elevation under which (in the case of
 133    fertility or oil) or over which (in the case of iron, gold, and uranium)
 134    sectors with that elevation will contain that resource.  Elevation ranges
 135    from 0 to 100 */
 136
 137 /* raise FERT_MAX for more fertility */
 138 #define FERT_MAX   56
 139
 140 /* raise OIL_MAX for more oil */
 141 #define OIL_MAX    33
 142
 143 /* lower IRON_MIN for more iron */
 144 #define IRON_MIN   22
 145
 146 /* lower GOLD_MIN for more gold */
 147 #define GOLD_MIN   36
 148
 149 /* lower URAN_MIN for more uranium */
 150 #define URAN_MIN   56
 151
 152 /* do not change these defines */
 153 #define LANDMIN         1       /* plate altitude for normal land */
 154 #define PLATMIN         36      /* plate altitude for plateau */
 155 #define HIGHMIN         98      /* plate altitude for mountains */
 156
 157 static void qprint(const char * const fmt, ...)
 158     ATTRIBUTE((format (printf, 1, 2)));
 159
 160 /*
 161  * Program arguments and options
 162  */
 163 static char *program_name;
 164 static int nc, sc;              /* number and size of continents */
 165 static int ni, is;              /* number and size of islands */
 166 #define DEFAULT_SPIKE 10
 167 static int sp = DEFAULT_SPIKE;  /* spike percentage */
 168 #define DEFAULT_MOUNTAIN 0
 169 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
 170 #define DEFAULT_CONTDIST 2
 171 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
 172 #define DEFAULT_ISLDIST 1
 173 static int id = DEFAULT_ISLDIST;  /* ... continents and islands */
 174 /* don't let the islands crash into each other.
 175    1 = don't merge, 0 = merge. */
 176 static int DISTINCT_ISLANDS = 1;
 177 static int quiet;
 178 #define DEFAULT_OUTFILE_NAME "newcap_script"
 179 static const char *outfile = DEFAULT_OUTFILE_NAME;
 180
 181 #define STABLE_CYCLE 4          /* stability required for perterbed capitals */
 182 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
 183 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
 184
 185 /* handy macros:
 186 */
 187
 188 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
 189 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
 190
 191 /*
 192  * Island sizes
 193  * isecs[i] is the size of the i-th island.
 194  */
 195 static int *isecs;
 196
 197 static int *capx, *capy;        /* location of the nc capitals */
 198
 199 static int **own;               /* owner of the sector.  -1 means water */
 200
 201 /*
 202  * Adjacent land sectors
 203  * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
 204  * to x, y in direction d is land.
 205  */
 206 static unsigned char *adj_land;
 207
 208 /*
 209  * Elevation at x,y
 210  * elev[XYOFFSET(x, y)] is x,y's elevation.
 211  */
 212 static short *elev;
 213
 214 /*
 215  * Exclusive zones
 216  * Each island is surrounded by an exclusive zone where only it may
 217  * grow.  The width of the zone depends on minimum distances.
 218  * While growing continents, it is @di sectors wide.
 219  * While growing additional islands, it is @id sectors wide.
 220  * DISTINCT_ISLANDS nullifies the exclusive zone then.
 221  * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
 222  * zone, a (non-negative) island number when it is in that island's
 223  * exclusive zone and no other, and -2 when it is in multiple
 224  * exclusive zones.
 225  */
 226 static short *xzone;
 227
 228 /*
 229  * Set of sectors seen already
 230  * Increment @cur_seen to empty the set of sectors seen, set
 231  * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
 232  */
 233 static unsigned *seen;
 234 static unsigned cur_seen;
 235
 236 /*
 237  * Closest continent and "distance"
 238  * closest[XYOFFSET(x, y)] is the closest continent's number.
 239  * distance[] is complicated; see init_spheres_of_influence() and
 240  * init_distance_to_coast().
 241  */
 242 static natid *closest;
 243 static unsigned short *distance;
 244
 245 /*
 246  * Queue for breadth-first search
 247  */
 248 static int *bfs_queue;
 249 static int bfs_queue_head, bfs_queue_tail;
 250
 251 static int **sectx, **secty;    /* the sectors for each continent */
 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_prep(void);
 271 static void elevate_land(void);
 272 static void elevate_sea(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     elev = calloc(WORLD_SZ(), sizeof(*elev));
 551     xzone = malloc(WORLD_SZ() * sizeof(*xzone));
 552     seen = calloc(WORLD_SZ(), sizeof(*seen));
 553     closest = malloc(WORLD_SZ() * sizeof(*closest));
 554     distance = malloc(WORLD_SZ() * sizeof(*distance));
 555     bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
 556     for (i = 0; i < WORLD_X; ++i) {
 557         own[i] = calloc(WORLD_Y, sizeof(int));
 558     }
 559     sectx = calloc(nc + ni, sizeof(int *));
 560     secty = calloc(nc + ni, sizeof(int *));
 561     isecs = calloc(nc + ni, sizeof(int));
 562     for (i = 0; i < nc; ++i) {
 563         sectx[i] = calloc(sc, sizeof(int));
 564         secty[i] = calloc(sc, sizeof(int));
 565     }
 566     for (i = nc; i < nc + ni; ++i) {
 567         sectx[i] = calloc(is * 2, sizeof(int));
 568         secty[i] = calloc(is * 2, sizeof(int));
 569     }
 570
 571 }
 572
 573 static void
 574 init(void)
 575 {
 576     int i, j;
 577
 578     for (i = 0; i < WORLD_X; ++i) {
 579         for (j = 0; j < WORLD_Y; ++j) {
 580             own[i][j] = -1;
 581         }
 582     }
 583     memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
 584 }
 585
 586 /****************************************************************************
 587   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
 588 ****************************************************************************/
 589
 590 /*
 591  * How isolated is capital @j at @newx,@newy?
 592  * Return the distance to the closest other capital.
 593  */
 594 static int
 595 iso(int j, int newx, int newy)
 596 {
 597     int d = INT_MAX;
 598     int i, md;
 599
 600     for (i = 0; i < nc; ++i) {
 601         if (i == j)
 602             continue;
 603         md = mapdist(capx[i], capy[i], newx, newy);
 604         if (md < d)
 605             d = md;
 606     }
 607
 608     return d;
 609 }
 610
 611 /*
 612  * Drift the capitals
 613  * Return 1 for a stable drift, 0 for an unstable one.
 614  */
 615 static int
 616 drift(void)
 617 {
 618     int turns, i;
 619
 620     for (i = 0; i < nc; i++) {
 621         capy[i] = (2 * i) / WORLD_X;
 622         capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
 623         if (capy[i] >= WORLD_Y) {
 624             fprintf(stderr,
 625                     "%s: world not big enough for all the continents\n",
 626                     program_name);
 627             exit(1);
 628         }
 629     }
 630
 631     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 632         if (stable(turns))
 633             return 1;
 634         for (i = 0; i < nc; ++i)
 635             fl_move(i);
 636     }
 637     return 0;
 638 }
 639
 640 /*
 641  * Has the drift stabilized?
 642  * @turns is the number of turns so far.
 643  */
 644 static int
 645 stable(int turns)
 646 {
 647     static int mc[STABLE_CYCLE];
 648     int i, isod, d = 0, stab = 1;
 649
 650     if (!turns) {
 651         for (i = 0; i < STABLE_CYCLE; i++)
 652             mc[i] = i;
 653     }
 654
 655     if (turns <= DRIFT_BEFORE_CHECK)
 656         return 0;
 657
 658     for (i = 0; i < nc; ++i) {
 659         isod = iso(i, capx[i], capy[i]);
 660         if (isod > d)
 661             d = isod;
 662     }
 663
 664     for (i = 0; i < STABLE_CYCLE; ++i)
 665         if (d != mc[i])
 666             stab = 0;
 667
 668     mc[turns % STABLE_CYCLE] = d;
 669     return stab;
 670 }
 671
 672 /* This routine does the actual drifting
 673 */
 674
 675 static void
 676 fl_move(int j)
 677 {
 678     int dir, i, newx, newy;
 679
 680     dir = DIR_L + roll0(6);
 681     for (i = 0; i < 6; i++) {
 682         if (dir > DIR_LAST)
 683             dir -= 6;
 684         newx = new_x(capx[j] + diroff[dir][0]);
 685         newy = new_y(capy[j] + diroff[dir][1]);
 686         dir++;
 687         if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
 688             capx[j] = newx;
 689             capy[j] = newy;
 690             return;
 691         }
 692     }
 693 }
 694
 695 /****************************************************************************
 696   GROW THE CONTINENTS
 697 ****************************************************************************/
 698
 699 static int
 700 is_coastal(int x, int y)
 701 {
 702     return adj_land[XYOFFSET(x, y)]
 703         != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
 704 }
 705
 706 struct hexagon_iter {
 707     int dir, i, n;
 708 };
 709
 710 /*
 711  * Start iterating around @x0,@y0 at distance @d.
 712  * Set *x,*y to coordinates of the first sector.
 713  */
 714 static inline void
 715 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
 716               int *x, int *y)
 717 {
 718     *x = new_x(x0 - 2 * n);
 719     *y = y0;
 720     iter->dir = DIR_FIRST;
 721     iter->i = 0;
 722     iter->n = n;
 723 }
 724
 725 /*
 726  * Continue iteration started with hexagon_first().
 727  * Set *x,*y to coordinates of the next sector.
 728  * Return whether we're back at the first sector, i.e. iteration is
 729  * complete.
 730  */
 731 static inline int
 732 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
 733 {
 734     *x = new_x(*x + diroff[iter->dir][0]);
 735     *y = new_y(*y + diroff[iter->dir][1]);
 736     iter->i++;
 737     if (iter->i == iter->n) {
 738         iter->i = 0;
 739         iter->dir++;
 740     }
 741     return iter->dir <= DIR_LAST;
 742 }
 743
 744 /*
 745  * Is @x,@y in no exclusive zone other than perhaps @c's?
 746  */
 747 static int
 748 xzone_ok(int c, int x, int y)
 749 {
 750     int off = XYOFFSET(x, y);
 751
 752     return xzone[off] == c || xzone[off] == -1;
 753 }
 754
 755 /*
 756  * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
 757  */
 758 static void
 759 xzone_around_sector(int c, int x, int y, int dist)
 760 {
 761     int d, x1, y1, off;
 762     struct hexagon_iter hexit;
 763
 764     assert(xzone_ok(c, x, y));
 765
 766     xzone[XYOFFSET(x, y)] = c;
 767     for (d = 1; d <= dist; d++) {
 768         hexagon_first(&hexit, x, y, d, &x1, &y1);
 769         do {
 770             off = XYOFFSET(x1, y1);
 771             if (xzone[off] == -1)
 772                 xzone[off] = c;
 773             else if (xzone[off] != c)
 774                 xzone[off] = -2;
 775         } while (hexagon_next(&hexit, &x1, &y1));
 776     }
 777 }
 778
 779 /*
 780  * Add sectors within distance @dist to island @c's exclusive zone.
 781  */
 782 static void
 783 xzone_around_island(int c, int dist)
 784 {
 785     int i;
 786
 787     for (i = 0; i < isecs[c]; i++)
 788         xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
 789 }
 790
 791 /*
 792  * Initialize exclusive zones around @n islands.
 793  */
 794 static void
 795 xzone_init(int n)
 796 {
 797     int i, c;
 798
 799     for (i = 0; i < WORLD_SZ(); i++)
 800         xzone[i] = -1;
 801
 802     for (c = 0; c < n; c++)
 803         xzone_around_island(c, id);
 804 }
 805
 806 /*
 807  * Initialize breadth-first search.
 808  */
 809 static void
 810 bfs_init(void)
 811 {
 812     int i;
 813
 814     for (i = 0; i < WORLD_SZ(); i++) {
 815         closest[i] = -1;
 816         distance[i] = USHRT_MAX;
 817     }
 818
 819     bfs_queue_head = bfs_queue_tail = 0;
 820 }
 821
 822 /*
 823  * Add sector @x,@y to the BFS queue.
 824  * It's closest to @c, with distance @dist.
 825  */
 826 static void
 827 bfs_enqueue(int c, int x, int y, int dist)
 828 {
 829     int off = XYOFFSET(x, y);
 830
 831     assert(dist < distance[off]);
 832     closest[off] = c;
 833     distance[off] = dist;
 834     bfs_queue[bfs_queue_tail] = off;
 835     bfs_queue_tail++;
 836     if (bfs_queue_tail >= WORLD_SZ())
 837         bfs_queue_tail = 0;
 838     assert(bfs_queue_tail != bfs_queue_head);
 839 }
 840
 841 /*
 842  * Search breadth-first until the queue is empty.
 843  */
 844 static void
 845 bfs_run_queue(void)
 846 {
 847     int off, dist, i, noff, nx, ny;
 848     coord x, y;
 849
 850     while (bfs_queue_head != bfs_queue_tail) {
 851         off = bfs_queue[bfs_queue_head];
 852         bfs_queue_head++;
 853         if (bfs_queue_head >= WORLD_SZ())
 854             bfs_queue_head = 0;
 855         dist = distance[off] + 1;
 856         sctoff2xy(&x, &y, off);
 857         for (i = DIR_FIRST; i <= DIR_LAST; i++) {
 858             nx = new_x(x + diroff[i][0]);
 859             ny = new_y(y + diroff[i][1]);
 860             noff = XYOFFSET(nx, ny);
 861             if (dist < distance[noff]) {
 862                 bfs_enqueue(closest[off], nx, ny, dist);
 863             } else if (distance[noff] == dist) {
 864                 if (closest[off] != closest[noff])
 865                     closest[noff] = (natid)-1;
 866             } else
 867                 assert(distance[noff] < dist);
 868         }
 869     }
 870 }
 871
 872 /*
 873  * Add island @c's coastal sectors to the BFS queue, with distance 0.
 874  */
 875 static void
 876 bfs_enqueue_island(int c)
 877 {
 878     int i;
 879
 880     for (i = 0; i < isecs[c]; i++) {
 881         if (is_coastal(sectx[c][i], secty[c][i]))
 882             bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
 883     }
 884 }
 885
 886 /*
 887  * Enqueue spheres of influence borders for breadth-first search.
 888  */
 889 static void
 890 bfs_enqueue_border(void)
 891 {
 892     int x, y, off, dir, nx, ny, noff;
 893
 894     for (y = 0; y < WORLD_Y; y++) {
 895         for (x = y % 2; x < WORLD_X; x += 2) {
 896             off = XYOFFSET(x, y);
 897             if (distance[off] <= id + 1)
 898                 continue;
 899             if (closest[off] == (natid)-1)
 900                 continue;
 901             for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 902                 nx = new_x(x + diroff[dir][0]);
 903                 ny = new_y(y + diroff[dir][1]);
 904                 noff = XYOFFSET(nx, ny);
 905                 if (closest[noff] != closest[off]) {
 906                     bfs_enqueue(closest[off], x, y, id + 1);
 907                     break;
 908                 }
 909             }
 910         }
 911     }
 912 }
 913
 914 /*
 915  * Compute spheres of influence
 916  * A continent's sphere of influence is the set of sectors closer to
 917  * it than to any other continent.
 918  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 919  * -1 if no single continent is closest.
 920  * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
 921  * closest coastal land sector and the distance to just outside the
 922  * sphere of influence plus @id.  For sea sectors within a continent's
 923  * sphere of influence, distance[off] - id is the distance to the
 924  * border of the area where additional islands can be placed.
 925  */
 926 static void
 927 init_spheres_of_influence(void)
 928 {
 929     int c;
 930
 931     bfs_init();
 932     for (c = 0; c < nc; c++)
 933         bfs_enqueue_island(c);
 934     bfs_run_queue();
 935     bfs_enqueue_border();
 936     bfs_run_queue();
 937 }
 938
 939 /*
 940  * Precompute distance to coast
 941  * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
 942  * land sector.
 943  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 944  * -1 if no single continent is closest.
 945  */
 946 static void
 947 init_distance_to_coast(void)
 948 {
 949     int c;
 950
 951     bfs_init();
 952     for (c = 0; c < nc + ni; c++)
 953         bfs_enqueue_island(c);
 954     bfs_run_queue();
 955 }
 956
 957 /*
 958  * Is @x,@y in the same sphere of influence as island @c?
 959  * Always true when @c is a continent.
 960  */
 961 static int
 962 is_in_sphere(int c, int x, int y)
 963 {
 964     return c < nc || closest[XYOFFSET(x, y)] == c % nc;
 965 }
 966
 967 /*
 968  * Can island @c grow at @x,@y?
 969  */
 970 static int
 971 can_grow_at(int c, int x, int y)
 972 {
 973     return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
 974 }
 975
 976 static void
 977 adj_land_update(int x, int y)
 978 {
 979     int is_land = own[x][y] != -1;
 980     int dir, nx, ny, noff;
 981
 982     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 983         nx = new_x(x + diroff[dir][0]);
 984         ny = new_y(y + diroff[dir][1]);
 985         noff = XYOFFSET(nx, ny);
 986         if (is_land)
 987             adj_land[noff] |= 1u << DIR_BACK(dir);
 988         else
 989             adj_land[noff] &= ~(1u << DIR_BACK(dir));
 990     }
 991 }
 992
 993 static void
 994 add_sector(int c, int x, int y)
 995 {
 996     assert(own[x][y] == -1);
 997     xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
 998     sectx[c][isecs[c]] = x;
 999     secty[c][isecs[c]] = y;
1000     isecs[c]++;
1001     own[x][y] = c;
1002     adj_land_update(x, y);
1003 }
1004
1005 static int grow_weight(int c, int x, int y, int spike)
1006 {
1007     int n, b;
1008
1009     /*
1010      * #Land neighbors is #bits set in adj_land[].
1011      * Count them Brian Kernighan's way.
1012      */
1013     n = 0;
1014     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1015         n++;
1016     assert(n > 0 && n < 7);
1017
1018     if (spike)
1019         return (6 - n) * (6 - n);
1020
1021     return n * n * n;
1022 }
1023
1024 static int
1025 grow_one_sector(int c)
1026 {
1027     int spike = roll0(100) < sp;
1028     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1029
1030     assert(cur_seen < UINT_MAX);
1031     cur_seen++;
1032     wsum = 0;
1033     newx = newy = -1;
1034
1035     for (i = 0; i < isecs[c]; i++) {
1036         x = sectx[c][i];
1037         y = secty[c][i];
1038         off = XYOFFSET(x, y);
1039
1040         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1041             if (adj_land[off] & (1u << dir))
1042                 continue;
1043             nx = new_x(x + diroff[dir][0]);
1044             ny = new_y(y + diroff[dir][1]);
1045             noff = XYOFFSET(nx, ny);
1046             if (seen[noff] == cur_seen)
1047                 continue;
1048             assert(seen[noff] < cur_seen);
1049             seen[noff] = cur_seen;
1050             if (!can_grow_at(c, nx, ny))
1051                 continue;
1052             w = grow_weight(c, nx, ny, spike);
1053             assert(wsum < INT_MAX - w);
1054             wsum += w;
1055             if (roll0(wsum) < w) {
1056                 newx = nx;
1057                 newy = ny;
1058             }
1059         }
1060     }
1061
1062     if (!wsum)
1063         return 0;
1064
1065     add_sector(c, newx, newy);
1066     return 1;
1067 }
1068
1069 /*
1070  * Grow the continents.
1071  * Return 1 on success, 0 on error.
1072  */
1073 static int
1074 grow_continents(void)
1075 {
1076     int done = 1;
1077     int c, secs;
1078
1079     xzone_init(0);
1080
1081     for (c = 0; c < nc; ++c) {
1082         isecs[c] = 0;
1083         if (!can_grow_at(c, capx[c], capy[c])
1084             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1085             done = 0;
1086             continue;
1087         }
1088         add_sector(c, capx[c], capy[c]);
1089         add_sector(c, new_x(capx[c] + 2), capy[c]);
1090     }
1091
1092     if (!done) {
1093         qprint("No room for continents\n");
1094         return 0;
1095     }
1096
1097     for (secs = 2; secs < sc && done; secs++) {
1098         for (c = 0; c < nc; ++c) {
1099             if (!grow_one_sector(c))
1100                 done = 0;
1101         }
1102     }
1103
1104     if (!done)
1105         qprint("Only managed to grow %d out of %d sectors.\n",
1106                secs - 1, sc);
1107     return done;
1108 }
1109
1110 /****************************************************************************
1111   GROW THE ISLANDS
1112 ****************************************************************************/
1113
1114 /*
1115  * Place additional island @c's first sector.
1116  * Return 1 on success, 0 on error.
1117  */
1118 static int
1119 place_island(int c, int isiz)
1120 {
1121     int n, x, y, d, w, newx, newy;
1122
1123     n = 0;
1124
1125     for (y = 0; y < WORLD_Y; y++) {
1126         for (x = y % 2; x < WORLD_X; x += 2) {
1127             if (can_grow_at(c, x, y)) {
1128                 d = distance[XYOFFSET(x, y)];
1129                 assert(d > id);
1130                 w = (d - id) * (d - id);
1131                 n += MIN(w, (isiz + 2) / 3);
1132                 if (roll0(n) < w) {
1133                     newx = x;
1134                     newy = y;
1135                 }
1136             }
1137         }
1138     }
1139
1140     if (n)
1141         add_sector(c, newx, newy);
1142     return n;
1143 }
1144
1145 static int
1146 int_cmp(const void *a, const void *b)
1147 {
1148     return *(int *)b - *(int *)a;
1149 }
1150
1151 static int *
1152 size_islands(void)
1153 {
1154     int n = ni / nc;
1155     int *isiz = malloc(n * sizeof(*isiz));
1156     int r0, r1, i;
1157
1158     isiz[0] = n * is;
1159     r1 = roll0(is);
1160     for (i = 1; i < n; i++) {
1161         r0 = r1;
1162         r1 = roll0(is);
1163         isiz[i] = is + r1 - r0;
1164         isiz[0] -= isiz[i];
1165     }
1166
1167     qsort(isiz, n, sizeof(*isiz), int_cmp);
1168     return isiz;
1169 }
1170
1171 /*
1172  * Grow the additional islands.
1173  * Return 1 on success, 0 on error.
1174  */
1175 static int
1176 grow_islands(void)
1177 {
1178     int *island_size = size_islands();
1179     int xzone_valid = 0;
1180     int carry = 0;
1181     int i, j, c, done, secs, isiz, x, y;
1182
1183     init_spheres_of_influence();
1184
1185     for (i = 0; i < ni / nc; i++) {
1186         c = nc + i * nc;
1187
1188         if (!xzone_valid)
1189             xzone_init(c);
1190
1191         carry += island_size[i];
1192         isiz = MIN(2 * is, carry);
1193
1194         for (j = 0; j < nc; j++) {
1195             isecs[c + j] = 0;
1196             if (!place_island(c + j, isiz)) {
1197                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1198                 free(island_size);
1199                 return 0;
1200             }
1201         }
1202
1203         done = 1;
1204         for (secs = 1; secs < isiz && done; secs++) {
1205             for (j = 0; j < nc; j++) {
1206                 if (!grow_one_sector(c + j))
1207                     done = 0;
1208             }
1209         }
1210
1211         if (!done) {
1212             secs--;
1213             for (j = 0; j < nc; j++) {
1214                 if (isecs[c + j] != secs) {
1215                     isecs[c + j]--;
1216                     assert(isecs[c + j] == secs);
1217                     x = sectx[c + j][secs];
1218                     y = secty[c + j][secs];
1219                     own[x][y] = -1;
1220                     adj_land_update(x, y);
1221                 }
1222             }
1223             xzone_valid = 0;
1224         }
1225
1226         for (j = 0; j < nc; j++)
1227             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1228
1229         carry -= secs;
1230     }
1231
1232     free(island_size);
1233     qprint("\n");
1234
1235     if (carry)
1236         qprint("Only managed to grow %d out of %d island sectors.\n",
1237                is * ni - carry * nc, is * ni);
1238
1239     return 1;
1240 }
1241
1242 /****************************************************************************
1243   CREATE ELEVATIONS
1244 ****************************************************************************/
1245 static void
1246 create_elevations(void)
1247 {
1248     elevate_prep();
1249     elevate_land();
1250     elevate_sea();
1251 }
1252
1253 static int
1254 elev_cmp(const void *p, const void *q)
1255 {
1256     int a = *(int *)p;
1257     int b = *(int *)q;
1258     int delev = elev[a] - elev[b];
1259
1260     return delev ? delev : a - b;
1261 }
1262
1263 static void
1264 elevate_prep(void)
1265 {
1266     int n = WORLD_SZ() * 8;
1267     int off0, r, sign, elevation, d, x1, y1, off1;
1268     coord x0, y0;
1269     struct hexagon_iter hexit;
1270
1271     init_distance_to_coast();
1272
1273     while (n > 0) {
1274         off0 = roll0(WORLD_SZ());
1275         sctoff2xy(&x0, &y0, off0);
1276         if (own[x0][y0] == -1) {
1277             r = roll(MIN(3, distance[off0]));
1278             sign = -1;
1279         } else {
1280             r = roll(MIN(3, distance[off0]) + 1);
1281             sign = 1;
1282         }
1283         elevation = elev[off0] + sign * r * r;
1284         elev[off0] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1285         n--;
1286         for (d = 1; d < r; d++) {
1287             hexagon_first(&hexit, x0, y0, d, &x1, &y1);
1288             do {
1289                 off1 = XYOFFSET(x1, y1);
1290                 elevation = elev[off1] + sign * (r * r - d * d);
1291                 elev[off1] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1292                 n--;
1293             } while (hexagon_next(&hexit, &x1, &y1));
1294         }
1295     }
1296 }
1297
1298 static void
1299 elevate_land(void)
1300 {
1301     int *off = malloc(MAX(sc, is * 2) * sizeof(*off));
1302     int max_nm = (pm * MAX(sc, is * 2)) / 100;
1303     int c, nm, i0, n, i;
1304     double elevation, delta;
1305
1306     for (c = 0; c < nc + ni; c++) {
1307         nm = (pm * isecs[c]) / 100;
1308         i0 = c < nc ? 2 : 0;
1309         n = isecs[c] - i0;
1310         for (i = 0; i < i0; i++)
1311             elev[XYOFFSET(sectx[c][i], secty[c][i])] = PLATMIN;
1312         for (i = 0; i < n; i++)
1313             off[i] = XYOFFSET(sectx[c][i0 + i], secty[c][i0 + i]);
1314         qsort(off, n, sizeof(*off), elev_cmp);
1315         delta = (double)(HIGHMIN - LANDMIN - 1) / (n - nm - 1);
1316         elevation = LANDMIN;
1317         for (i = 0; i < n - nm; i++) {
1318             elev[off[i]] = (int)(elevation + 0.5);
1319             elevation += delta;
1320         }
1321         elevation = HIGHMIN;
1322         delta = (127.0 - HIGHMIN) / max_nm;
1323         for (; i < n; i++) {
1324             elevation += delta;
1325             elev[off[i]] = (int)(elevation + 0.5);
1326         }
1327     }
1328
1329     free(off);
1330 }
1331
1332 static void
1333 elevate_sea(void)
1334 {
1335     int i, min;
1336
1337     min = 0;
1338     for (i = 0; i < WORLD_SZ(); i++) {
1339         if (elev[i] < min)
1340             min = elev[i];
1341     }
1342
1343     for (i = 0; i < WORLD_SZ(); i++) {
1344         if (elev[i] < 0)
1345             elev[i] = -1 - 126 * elev[i] / min;
1346     }
1347 }
1348
1349 static int
1350 elev_to_sct_type(int elevation)
1351 {
1352     if (elevation < LANDMIN)
1353         return SCT_WATER;
1354     if (elevation < HIGHMIN)
1355         return SCT_RURAL;
1356     return SCT_MOUNT;
1357 }
1358
1359 /****************************************************************************
1360   ADD THE RESOURCES
1361 ****************************************************************************/
1362
1363 static int
1364 set_fert(int e)
1365 {
1366     int fert = 0;
1367     if (e < LANDMIN)
1368         fert = LANDMIN - e + 40;
1369     else if (e < FERT_MAX)
1370         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1371     if (fert > 100)
1372         fert = 100;
1373     return fert;
1374 }
1375
1376 static int
1377 set_oil(int e)
1378 {
1379     int oil = 0;
1380     if (e < LANDMIN)
1381         oil = (LANDMIN - e) * 2;
1382     else if (e <= OIL_MAX)
1383         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1384     if (oil > 100)
1385         oil = 100;
1386     return oil;
1387 }
1388
1389 static int
1390 set_iron(int e)
1391 {
1392     int iron = 0;
1393     if (e >= IRON_MIN && e < HIGHMIN)
1394         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1395     if (iron > 100)
1396         iron = 100;
1397     return iron;
1398 }
1399
1400 static int
1401 set_gold(int e)
1402 {
1403     int gold = 0;
1404     if (e >= GOLD_MIN) {
1405         if (e < HIGHMIN)
1406             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1407         else
1408             gold = 80 + 5 * (e - HIGHMIN) / (127 - HIGHMIN);
1409     }
1410     if (gold > 100)
1411         gold = 100;
1412     return gold;
1413 }
1414
1415 static int
1416 set_uran(int e)
1417 {
1418     int uran = 0;
1419     if (e >= URAN_MIN && e < HIGHMIN)
1420         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1421     if (uran > 100)
1422         uran = 100;
1423     return uran;
1424 }
1425
1426 static void
1427 add_resources(struct sctstr *sct)
1428 {
1429     sct->sct_fertil = set_fert(sct->sct_elev);
1430     sct->sct_oil = set_oil(sct->sct_elev);
1431     sct->sct_min = set_iron(sct->sct_elev);
1432     sct->sct_gmin = set_gold(sct->sct_elev);
1433     sct->sct_uran = set_uran(sct->sct_elev);
1434 }
1435
1436 /****************************************************************************
1437   DESIGNATE THE SECTORS
1438 ****************************************************************************/
1439
1440 static void
1441 write_sects(void)
1442 {
1443     struct sctstr *sct;
1444     int x, y;
1445
1446     for (y = 0; y < WORLD_Y; y++) {
1447         for (x = y % 2; x < WORLD_X; x += 2) {
1448             sct = getsectp(x, y);
1449             sct->sct_elev = elev[sct->sct_uid];
1450             sct->sct_type = elev_to_sct_type(sct->sct_elev);
1451             sct->sct_newtype = sct->sct_type;
1452             sct->sct_dterr = own[sct->sct_x][y] + 1;
1453             sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1454             add_resources(sct);
1455         }
1456     }
1457 }
1458
1459 /****************************************************************************
1460   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1461 ****************************************************************************/
1462 static void
1463 output(void)
1464 {
1465     int sx, sy, x, y, off, c, type;
1466
1467     if (quiet == 0) {
1468         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1469             y = YNORM(sy);
1470             puts("");
1471             if (y % 2)
1472                 printf(" ");
1473             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1474                 x = XNORM(sx);
1475                 off = XYOFFSET(x, y);
1476                 c = own[x][y];
1477                 type = elev_to_sct_type(elev[off]);
1478                 if (type == SCT_WATER)
1479                     printf(". ");
1480                 else if (type == SCT_MOUNT)
1481                     printf("^ ");
1482                 else if (c >= nc)
1483                     printf("%% ");
1484                 else {
1485                     assert(0 <= c && c < nc);
1486                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1487                         && y == capy[c])
1488                         printf("%c ", numletter[c % 62]);
1489                     else
1490                         printf("# ");
1491                 }
1492             }
1493         }
1494     }
1495 }
1496
1497 /*
1498  * Print a map to help visualize own[][].
1499  * This is for debugging.
1500  */
1501 void
1502 print_own_map(void)
1503 {
1504     int sx, sy, x, y;
1505
1506     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1507         y = YNORM(sy);
1508         printf("%4d ", sy);
1509         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1510             x = XNORM(sx);
1511             if ((x + y) & 1)
1512                 putchar(' ');
1513             else if (own[x][y] == -1)
1514                 putchar('.');
1515             else
1516                 putchar(numletter[own[x][y] % 62]);
1517         }
1518         putchar('\n');
1519     }
1520 }
1521
1522 /*
1523  * Print a map to help visualize elev[].
1524  * This is for debugging.  It expects the terminal to understand
1525  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1526  */
1527 void
1528 print_elev_map(void)
1529 {
1530     int sx, sy, x, y, off, sat;
1531
1532     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1533         y = YNORM(sy);
1534         printf("%4d ", sy);
1535         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1536             x = XNORM(sx);
1537             off = XYOFFSET(x, y);
1538             if ((x + y) & 1)
1539                 putchar(' ');
1540             else if (!elev[off])
1541                 putchar(' ');
1542             else if (elev[off] < 0) {
1543                 sat = 256 + elev[off] * 2;
1544                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1545             } else if (elev[off] < HIGHMIN / 2) {
1546                 sat = (HIGHMIN / 2 - elev[off]) * 4;
1547                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1548             } else if (elev[off] < HIGHMIN) {
1549                 sat = 128 + (HIGHMIN - elev[off]) * 2;
1550                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1551             } else {
1552                 sat = 128 + (elev[off] - HIGHMIN) * 2;
1553                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1554             }
1555         }
1556         putchar('\n');
1557     }
1558 }
1559
1560 /*
1561  * Print a map to help visualize xzone[].
1562  * This is for debugging.
1563  */
1564 void
1565 print_xzone_map(void)
1566 {
1567     int sx, sy, x, y, off;
1568
1569     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1570         y = YNORM(sy);
1571         printf("%4d ", sy);
1572         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1573             x = XNORM(sx);
1574             off = XYOFFSET(x, y);
1575             if ((x + y) & 1)
1576                 putchar(' ');
1577             else if (own[x][y] >= 0)
1578                 putchar('-');
1579             else if (xzone[off] >= 0)
1580                 putchar(numletter[xzone[off] % 62]);
1581             else {
1582                 assert(own[x][y] == -1);
1583                 putchar(xzone[off] == -1 ? '.' : '!');
1584             }
1585         }
1586         putchar('\n');
1587     }
1588 }
1589
1590 /*
1591  * Print a map to help visualize closest[].
1592  * This is for debugging.
1593  */
1594 void
1595 print_closest_map(void)
1596 {
1597     int sx, sy, x, y, off;
1598
1599     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1600         y = YNORM(sy);
1601         printf("%4d ", sy);
1602         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1603             x = XNORM(sx);
1604             off = XYOFFSET(x, y);
1605             if ((x + y) & 1)
1606                 putchar(' ');
1607             else if (closest[off] == (natid)-1)
1608                 putchar('.');
1609             else if (!distance[off]) {
1610                 assert(closest[off] == own[x][y]);
1611                 putchar('-');
1612             } else {
1613                 putchar(numletter[closest[off] % 62]);
1614             }
1615         }
1616         printf("\n");
1617     }
1618 }
1619
1620 void
1621 print_distance_map(void)
1622 {
1623     int sx, sy, x, y, off;
1624
1625     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1626         y = YNORM(sy);
1627         printf("%4d ", sy);
1628         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1629             x = XNORM(sx);
1630             off = XYOFFSET(x, y);
1631             if ((x + y) & 1)
1632                 putchar(' ');
1633             else if (closest[off] == (natid)-1)
1634                 putchar('.');
1635             else if (!distance[off]) {
1636                 assert(closest[off] == own[x][y]);
1637                 putchar('-');
1638             } else {
1639                 putchar(numletter[distance[off] % 62]);
1640             }
1641         }
1642         printf("\n");
1643     }
1644 }
1645
1646
1647 /***************************************************************************
1648   WRITE A SCRIPT FOR PLACING CAPITALS
1649 ****************************************************************************/
1650 static int
1651 write_newcap_script(void)
1652 {
1653     int c;
1654     FILE *script = fopen(outfile, "w");
1655
1656     if (!script) {
1657         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1658                 program_name, outfile, strerror(errno));
1659         return 0;
1660     }
1661
1662     for (c = 0; c < nc; ++c) {
1663         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1664         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1665     }
1666     fprintf(script, "add %d visitor visitor v\n", c + 1);
1667     fclose(script);
1668     return 1;
1669 }
1670
1671 static void
1672 qprint(const char *const fmt, ...)
1673 {
1674     va_list ap;
1675
1676     if (!quiet) {
1677         va_start(ap, fmt);
1678         vfprintf(stdout, fmt, ap);
1679         va_end(ap);
1680     }
1681 }