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

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