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

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