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