git.pond.sub.org Git - empserver/blob - src/util/fairland.c

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