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