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