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 grow_weight(int c, int x, int y, int spike)
1011 {
1012     int n, b;
1013
1014     /*
1015      * #Land neighbors is #bits set in adj_land[].
1016      * Count them Brian Kernighan's way.
1017      */
1018     n = 0;
1019     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1020         n++;
1021     assert(n > 0 && n < 7);
1022
1023     if (spike)
1024         return (6 - n) * (6 - n);
1025
1026     return n * n * n;
1027 }
1028
1029 static int
1030 grow_one_sector(int c)
1031 {
1032     int spike = roll0(100) < sp;
1033     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1034
1035     assert(cur_seen < UINT_MAX);
1036     cur_seen++;
1037     wsum = 0;
1038     newx = newy = -1;
1039
1040     for (i = 0; i < isecs[c]; i++) {
1041         x = sectx[c][i];
1042         y = secty[c][i];
1043         off = XYOFFSET(x, y);
1044
1045         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1046             if (adj_land[off] & (1u << dir))
1047                 continue;
1048             nx = new_x(x + diroff[dir][0]);
1049             ny = new_y(y + diroff[dir][1]);
1050             noff = XYOFFSET(nx, ny);
1051             if (seen[noff] == cur_seen)
1052                 continue;
1053             assert(seen[noff] < cur_seen);
1054             seen[noff] = cur_seen;
1055             if (!can_grow_at(c, nx, ny))
1056                 continue;
1057             w = grow_weight(c, nx, ny, spike);
1058             assert(wsum < INT_MAX - w);
1059             wsum += w;
1060             if (roll0(wsum) < w) {
1061                 newx = nx;
1062                 newy = ny;
1063             }
1064         }
1065     }
1066
1067     if (!wsum)
1068         return 0;
1069
1070     add_sector(c, newx, newy);
1071     return 1;
1072 }
1073
1074 /*
1075  * Grow the continents.
1076  * Return 1 on success, 0 on error.
1077  */
1078 static int
1079 grow_continents(void)
1080 {
1081     int done = 1;
1082     int c, secs;
1083
1084     xzone_init(0);
1085
1086     for (c = 0; c < nc; ++c) {
1087         isecs[c] = 0;
1088         if (!can_grow_at(c, capx[c], capy[c])
1089             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1090             done = 0;
1091             continue;
1092         }
1093         add_sector(c, capx[c], capy[c]);
1094         add_sector(c, new_x(capx[c] + 2), capy[c]);
1095     }
1096
1097     if (!done) {
1098         qprint("No room for continents\n");
1099         return 0;
1100     }
1101
1102     for (secs = 2; secs < sc && done; secs++) {
1103         for (c = 0; c < nc; ++c) {
1104             if (!grow_one_sector(c))
1105                 done = 0;
1106         }
1107     }
1108
1109     if (!done)
1110         qprint("Only managed to grow %d out of %d sectors.\n",
1111                secs - 1, sc);
1112     return done;
1113 }
1114
1115 /****************************************************************************
1116   GROW THE ISLANDS
1117 ****************************************************************************/
1118
1119 /*
1120  * Place additional island @c's first sector.
1121  * Return 1 on success, 0 on error.
1122  */
1123 static int
1124 place_island(int c, int isiz)
1125 {
1126     int n, x, y, d, w, newx, newy;
1127
1128     n = 0;
1129
1130     for (y = 0; y < WORLD_Y; y++) {
1131         for (x = y % 2; x < WORLD_X; x += 2) {
1132             if (can_grow_at(c, x, y)) {
1133                 d = distance[XYOFFSET(x, y)];
1134                 assert(d > id);
1135                 w = (d - id) * (d - id);
1136                 n += MIN(w, (isiz + 2) / 3);
1137                 if (roll0(n) < w) {
1138                     newx = x;
1139                     newy = y;
1140                 }
1141             }
1142         }
1143     }
1144
1145     if (n)
1146         add_sector(c, newx, newy);
1147     return n;
1148 }
1149
1150 static int
1151 int_cmp(const void *a, const void *b)
1152 {
1153     return *(int *)b - *(int *)a;
1154 }
1155
1156 static int *
1157 size_islands(void)
1158 {
1159     int n = ni / nc;
1160     int *isiz = malloc(n * sizeof(*isiz));
1161     int r0, r1, i;
1162
1163     isiz[0] = n * is;
1164     r1 = roll0(is);
1165     for (i = 1; i < n; i++) {
1166         r0 = r1;
1167         r1 = roll0(is);
1168         isiz[i] = is + r1 - r0;
1169         isiz[0] -= isiz[i];
1170     }
1171
1172     qsort(isiz, n, sizeof(*isiz), int_cmp);
1173     return isiz;
1174 }
1175
1176 /*
1177  * Grow the additional islands.
1178  * Return 1 on success, 0 on error.
1179  */
1180 static int
1181 grow_islands(void)
1182 {
1183     int *island_size = size_islands();
1184     int xzone_valid = 0;
1185     int carry = 0;
1186     int i, j, c, done, secs, isiz, x, y;
1187
1188     init_spheres_of_influence();
1189
1190     for (i = 0; i < ni / nc; i++) {
1191         c = nc + i * nc;
1192
1193         if (!xzone_valid)
1194             xzone_init(c);
1195
1196         carry += island_size[i];
1197         isiz = MIN(2 * is, carry);
1198
1199         for (j = 0; j < nc; j++) {
1200             isecs[c + j] = 0;
1201             if (!place_island(c + j, isiz)) {
1202                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1203                 free(island_size);
1204                 return 0;
1205             }
1206         }
1207
1208         done = 1;
1209         for (secs = 1; secs < isiz && done; secs++) {
1210             for (j = 0; j < nc; j++) {
1211                 if (!grow_one_sector(c + j))
1212                     done = 0;
1213             }
1214         }
1215
1216         if (!done) {
1217             secs--;
1218             for (j = 0; j < nc; j++) {
1219                 if (isecs[c + j] != secs) {
1220                     isecs[c + j]--;
1221                     assert(isecs[c + j] == secs);
1222                     x = sectx[c + j][secs];
1223                     y = secty[c + j][secs];
1224                     own[x][y] = -1;
1225                     adj_land_update(x, y);
1226                 }
1227             }
1228             xzone_valid = 0;
1229         }
1230
1231         for (j = 0; j < nc; j++)
1232             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1233
1234         carry -= secs;
1235     }
1236
1237     free(island_size);
1238     qprint("\n");
1239
1240     if (carry)
1241         qprint("Only managed to grow %d out of %d island sectors.\n",
1242                is * ni - carry * nc, is * ni);
1243
1244     return 1;
1245 }
1246
1247 /****************************************************************************
1248   CREATE ELEVATIONS
1249 ****************************************************************************/
1250 static void
1251 create_elevations(void)
1252 {
1253     init_distance_to_coast();
1254     elevate_land();
1255     elevate_sea();
1256 }
1257
1258 /* Generic function for finding the distance to the closest sea, land, or
1259    mountain
1260 */
1261 static int
1262 distance_to_what(int x, int y, int flag)
1263 {
1264     int d, px, py;
1265     struct hexagon_iter hexit;
1266
1267     for (d = 1; d < 5; ++d) {
1268         hexagon_first(&hexit, x, y, d, &px, &py);
1269         do {
1270             switch (flag) {
1271             case 0:             /* distance to sea */
1272                 if (own[px][py] == -1)
1273                     return d;
1274                 break;
1275             case 1:             /* distance to land */
1276                 if (own[px][py] != -1)
1277                     return d;
1278                 break;
1279             case 2:             /* distance to mountain */
1280                 if (elev[px][py] == INFINITE_ELEVATION)
1281                     return d;
1282                 break;
1283             }
1284         } while (hexagon_next(&hexit, &px, &py));
1285     }
1286     return d;
1287 }
1288
1289 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1290
1291 /* Decide where the mountains go
1292 */
1293 static void
1294 elevate_land(void)
1295 {
1296     int max_nm = (pm * MAX(sc, is * 2)) / 100;
1297     int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1298     int highest, where, h, newk, dk;
1299     double elevation, delta;
1300
1301     for (c = 0; c < nc + ni; ++c) {
1302         total = 0;
1303         ns = isecs[c];
1304         nm = (pm * ns) / 100;
1305
1306 /* Place the mountains */
1307
1308         for (i = 0; i < ns; ++i) {
1309             off = XYOFFSET(sectx[c][i], secty[c][i]);
1310             dsea[i] = MIN(5, distance[off] + 1);
1311             weight[i] = (total += (dsea[i] * dsea[i]));
1312         }
1313
1314         for (k = nm, mountain_search = 0;
1315              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1316              ++mountain_search) {
1317             r = roll0(total);
1318             for (i = 0; i < ns; ++i) {
1319                 x = sectx[c][i];
1320                 y = secty[c][i];
1321                 if (r < weight[i] && !elev[x][y] &&
1322                     (c >= nc ||
1323                      ((!(capx[c] == sectx[c][i] &&
1324                          capy[c] == secty[c][i])) &&
1325                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1326                          capy[c] == secty[c][i]))))) {
1327                     elev[x][y] = INFINITE_ELEVATION;
1328                     break;
1329                 }
1330             }
1331             --k;
1332         }
1333
1334 /* Elevate land that is not mountain and not capital */
1335
1336         for (i = 0; i < ns; ++i)
1337             dmoun[i] = distance_to_mountain();
1338         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1339           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1340           100 * INFINITE_ELEVATION;
1341         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1342             highest = 0;
1343             where = -1;
1344             for (i = 0; i < ns; ++i) {
1345                 x = sectx[c][i];
1346                 y = secty[c][i];
1347                 if (!elev[x][y] &&
1348                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1349                                     capy[c] == secty[c][i])) &&
1350                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1351                                     capy[c] == secty[c][i]))))) {
1352                     h = 3 * (5 - dmoun[i]) + dsea[i];
1353                     assert(h > 0);
1354                     if (h > highest) {
1355                         highest = h;
1356                         where = i;
1357                     }
1358                 }
1359             }
1360             if (where == -1)
1361                 break;
1362             newk = k / 100;
1363             if (newk < LANDMIN)
1364                 newk = LANDMIN;
1365             elev[sectx[c][where]][secty[c][where]] = newk;
1366         }
1367
1368 /* Elevate the mountains and capitals */
1369
1370         elevation = HIGHMIN;
1371         delta = (127.0 - HIGHMIN) / max_nm;
1372         for (i = 0; i < ns; ++i) {
1373             x = sectx[c][i];
1374             y = secty[c][i];
1375             if (elev[x][y] == INFINITE_ELEVATION) {
1376                 elevation += delta;
1377                 elev[x][y] = (int)(elevation + 0.5);
1378                 /*
1379                  * Temporary "useless" die rolls to minimize
1380                  * tests/fairland/ churn:
1381                  */
1382                 if (dsea[i] == 1)
1383                     roll0(2);
1384                 else {
1385                     roll0((256 - HIGHMIN) / 2);
1386                     roll0((256 - HIGHMIN) / 2);
1387                 }
1388             } else if (c < nc &&
1389                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1390                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1391                           capy[c] == secty[c][i]))))
1392                 elev[x][y] = PLATMIN;
1393         }
1394     }
1395 }
1396
1397 static void
1398 elevate_sea(void)
1399 {
1400     int x, y, off;
1401
1402     for (y = 0; y < WORLD_Y; ++y) {
1403         for (x = y % 2; x < WORLD_X; x += 2) {
1404             off = XYOFFSET(x, y);
1405             if (own[x][y] == -1)
1406                 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1407         }
1408     }
1409 }
1410
1411 static int
1412 elev_to_sct_type(int elevation)
1413 {
1414     if (elevation < LANDMIN)
1415         return SCT_WATER;
1416     if (elevation < HIGHMIN)
1417         return SCT_RURAL;
1418     return SCT_MOUNT;
1419 }
1420
1421 /****************************************************************************
1422   ADD THE RESOURCES
1423 ****************************************************************************/
1424
1425 static int
1426 set_fert(int e)
1427 {
1428     int fert = 0;
1429     if (e < LANDMIN)
1430         fert = LANDMIN - e + 40;
1431     else if (e < FERT_MAX)
1432         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1433     if (fert > 100)
1434         fert = 100;
1435     return fert;
1436 }
1437
1438 static int
1439 set_oil(int e)
1440 {
1441     int oil = 0;
1442     if (e < LANDMIN)
1443         oil = (LANDMIN - e) * 2 + roll0(2);
1444     else if (e <= OIL_MAX)
1445         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1446     if (oil > 100)
1447         oil = 100;
1448     return oil;
1449 }
1450
1451 static int
1452 set_iron(int e)
1453 {
1454     int iron = 0;
1455     if (e >= IRON_MIN && e < HIGHMIN)
1456         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1457     if (iron > 100)
1458         iron = 100;
1459     return iron;
1460 }
1461
1462 static int
1463 set_gold(int e)
1464 {
1465     int gold = 0;
1466     if (e >= GOLD_MIN) {
1467         if (e < HIGHMIN)
1468             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1469         else
1470             gold = 100 - 20 * HIGHMIN / e;
1471     }
1472     if (gold > 100)
1473         gold = 100;
1474     return gold;
1475 }
1476
1477 static int
1478 set_uran(int e)
1479 {
1480     int uran = 0;
1481     if (e >= URAN_MIN && e < HIGHMIN)
1482         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1483     if (uran > 100)
1484         uran = 100;
1485     return uran;
1486 }
1487
1488 static void
1489 add_resources(struct sctstr *sct)
1490 {
1491     sct->sct_fertil = set_fert(sct->sct_elev);
1492     sct->sct_oil = set_oil(sct->sct_elev);
1493     sct->sct_min = set_iron(sct->sct_elev);
1494     sct->sct_gmin = set_gold(sct->sct_elev);
1495     sct->sct_uran = set_uran(sct->sct_elev);
1496 }
1497
1498 /****************************************************************************
1499   DESIGNATE THE SECTORS
1500 ****************************************************************************/
1501
1502 static void
1503 write_sects(void)
1504 {
1505     struct sctstr *sct;
1506     int x, y;
1507
1508     for (y = 0; y < WORLD_Y; y++) {
1509         for (x = y % 2; x < WORLD_X; x += 2) {
1510             sct = getsectp(x, y);
1511             sct->sct_elev = elev[x][y];
1512             sct->sct_type = elev_to_sct_type(elev[x][y]);
1513             sct->sct_newtype = sct->sct_type;
1514             sct->sct_dterr = own[sct->sct_x][y] + 1;
1515             sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1516             add_resources(sct);
1517         }
1518     }
1519 }
1520
1521 /****************************************************************************
1522   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1523 ****************************************************************************/
1524 static void
1525 output(void)
1526 {
1527     int sx, sy, x, y, c, type;
1528
1529     if (quiet == 0) {
1530         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1531             y = YNORM(sy);
1532             puts("");
1533             if (y % 2)
1534                 printf(" ");
1535             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1536                 x = XNORM(sx);
1537                 c = own[x][y];
1538                 type = elev_to_sct_type(elev[x][y]);
1539                 if (type == SCT_WATER)
1540                     printf(". ");
1541                 else if (type == SCT_MOUNT)
1542                     printf("^ ");
1543                 else if (c >= nc)
1544                     printf("%% ");
1545                 else {
1546                     assert(0 <= c && c < nc);
1547                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1548                         && y == capy[c])
1549                         printf("%c ", numletter[c % 62]);
1550                     else
1551                         printf("# ");
1552                 }
1553             }
1554         }
1555     }
1556 }
1557
1558 /*
1559  * Print a map to help visualize own[][].
1560  * This is for debugging.
1561  */
1562 void
1563 print_own_map(void)
1564 {
1565     int sx, sy, x, y;
1566
1567     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1568         y = YNORM(sy);
1569         printf("%4d ", sy);
1570         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1571             x = XNORM(sx);
1572             if ((x + y) & 1)
1573                 putchar(' ');
1574             else if (own[x][y] == -1)
1575                 putchar('.');
1576             else
1577                 putchar(numletter[own[x][y] % 62]);
1578         }
1579         putchar('\n');
1580     }
1581 }
1582
1583 /*
1584  * Print a map to help visualize elev[][].
1585  * This is for debugging.  It expects the terminal to understand
1586  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1587  */
1588 void
1589 print_elev_map(void)
1590 {
1591     int sx, sy, x, y, sat;
1592
1593     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1594         y = YNORM(sy);
1595         printf("%4d ", sy);
1596         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1597             x = XNORM(sx);
1598             if ((x + y) & 1)
1599                 putchar(' ');
1600             else if (!elev[x][y])
1601                 putchar(' ');
1602             else if (elev[x][y] < 0) {
1603                 sat = 256 + elev[x][y] * 2;
1604                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1605             } else if (elev[x][y] < HIGHMIN / 2) {
1606                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1607                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1608             } else if (elev[x][y] < HIGHMIN) {
1609                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1610                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1611             } else {
1612                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1613                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1614             }
1615         }
1616         putchar('\n');
1617     }
1618 }
1619
1620 /*
1621  * Print a map to help visualize xzone[].
1622  * This is for debugging.
1623  */
1624 void
1625 print_xzone_map(void)
1626 {
1627     int sx, sy, x, y, off;
1628
1629     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1630         y = YNORM(sy);
1631         printf("%4d ", sy);
1632         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1633             x = XNORM(sx);
1634             off = XYOFFSET(x, y);
1635             if ((x + y) & 1)
1636                 putchar(' ');
1637             else if (own[x][y] >= 0)
1638                 putchar('-');
1639             else if (xzone[off] >= 0)
1640                 putchar(numletter[xzone[off] % 62]);
1641             else {
1642                 assert(own[x][y] == -1);
1643                 putchar(xzone[off] == -1 ? '.' : '!');
1644             }
1645         }
1646         putchar('\n');
1647     }
1648 }
1649
1650 /*
1651  * Print a map to help visualize closest[].
1652  * This is for debugging.
1653  */
1654 void
1655 print_closest_map(void)
1656 {
1657     int sx, sy, x, y, off;
1658
1659     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1660         y = YNORM(sy);
1661         printf("%4d ", sy);
1662         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1663             x = XNORM(sx);
1664             off = XYOFFSET(x, y);
1665             if ((x + y) & 1)
1666                 putchar(' ');
1667             else if (closest[off] == (natid)-1)
1668                 putchar('.');
1669             else if (!distance[off]) {
1670                 assert(closest[off] == own[x][y]);
1671                 putchar('-');
1672             } else {
1673                 putchar(numletter[closest[off] % 62]);
1674             }
1675         }
1676         printf("\n");
1677     }
1678 }
1679
1680 void
1681 print_distance_map(void)
1682 {
1683     int sx, sy, x, y, off;
1684
1685     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1686         y = YNORM(sy);
1687         printf("%4d ", sy);
1688         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1689             x = XNORM(sx);
1690             off = XYOFFSET(x, y);
1691             if ((x + y) & 1)
1692                 putchar(' ');
1693             else if (closest[off] == (natid)-1)
1694                 putchar('.');
1695             else if (!distance[off]) {
1696                 assert(closest[off] == own[x][y]);
1697                 putchar('-');
1698             } else {
1699                 putchar(numletter[distance[off] % 62]);
1700             }
1701         }
1702         printf("\n");
1703     }
1704 }
1705
1706
1707 /***************************************************************************
1708   WRITE A SCRIPT FOR PLACING CAPITALS
1709 ****************************************************************************/
1710 static int
1711 write_newcap_script(void)
1712 {
1713     int c;
1714     FILE *script = fopen(outfile, "w");
1715
1716     if (!script) {
1717         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1718                 program_name, outfile, strerror(errno));
1719         return 0;
1720     }
1721
1722     for (c = 0; c < nc; ++c) {
1723         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1724         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1725     }
1726     fprintf(script, "add %d visitor visitor v\n", c + 1);
1727     fclose(script);
1728     return 1;
1729 }
1730
1731 static void
1732 qprint(const char *const fmt, ...)
1733 {
1734     va_list ap;
1735
1736     if (!quiet) {
1737         va_start(ap, fmt);
1738         vfprintf(stdout, fmt, ap);
1739         va_end(ap);
1740     }
1741 }