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