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

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