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 grow_weight(int c, int x, int y, int spike)
1016 {
1017     int n, b;
1018
1019     /*
1020      * #Land neighbors is #bits set in adj_land[].
1021      * Count them Brian Kernighan's way.
1022      */
1023     n = 0;
1024     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1025         n++;
1026     assert(n > 0 && n < 7);
1027
1028     if (spike)
1029         return (6 - n) * (6 - n);
1030
1031     return n * n * n;
1032 }
1033
1034 static int
1035 grow_one_sector(int c)
1036 {
1037     int spike = roll0(100) < sp;
1038     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1039
1040     assert(cur_seen < UINT_MAX);
1041     cur_seen++;
1042     wsum = 0;
1043     newx = newy = -1;
1044
1045     for (i = 0; i < isecs[c]; i++) {
1046         x = sectx[c][i];
1047         y = secty[c][i];
1048         off = XYOFFSET(x, y);
1049
1050         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1051             if (adj_land[off] & (1u << dir))
1052                 continue;
1053             nx = new_x(x + diroff[dir][0]);
1054             ny = new_y(y + diroff[dir][1]);
1055             noff = XYOFFSET(nx, ny);
1056             if (seen[noff] == cur_seen)
1057                 continue;
1058             assert(seen[noff] < cur_seen);
1059             seen[noff] = cur_seen;
1060             if (!can_grow_at(c, nx, ny))
1061                 continue;
1062             w = grow_weight(c, nx, ny, spike);
1063             assert(wsum < INT_MAX - w);
1064             wsum += w;
1065             if (roll0(wsum) < w) {
1066                 newx = nx;
1067                 newy = ny;
1068             }
1069         }
1070     }
1071
1072     if (!wsum)
1073         return 0;
1074
1075     add_sector(c, newx, newy);
1076     return 1;
1077 }
1078
1079 /*
1080  * Grow the continents.
1081  * Return 1 on success, 0 on error.
1082  */
1083 static int
1084 grow_continents(void)
1085 {
1086     int done = 1;
1087     int c, secs;
1088
1089     xzone_init(0);
1090
1091     for (c = 0; c < nc; ++c) {
1092         isecs[c] = 0;
1093         if (!can_grow_at(c, capx[c], capy[c])
1094             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1095             done = 0;
1096             continue;
1097         }
1098         add_sector(c, capx[c], capy[c]);
1099         add_sector(c, new_x(capx[c] + 2), capy[c]);
1100     }
1101
1102     if (!done) {
1103         qprint("No room for continents\n");
1104         return 0;
1105     }
1106
1107     for (secs = 2; secs < sc && done; secs++) {
1108         for (c = 0; c < nc; ++c) {
1109             if (!grow_one_sector(c))
1110                 done = 0;
1111         }
1112     }
1113
1114     if (!done)
1115         qprint("Only managed to grow %d out of %d sectors.\n",
1116                secs - 1, sc);
1117     return done;
1118 }
1119
1120 /****************************************************************************
1121   GROW THE ISLANDS
1122 ****************************************************************************/
1123
1124 /*
1125  * Place additional island @c's first sector.
1126  * Return 1 on success, 0 on error.
1127  */
1128 static int
1129 place_island(int c, int isiz)
1130 {
1131     int n, x, y, d, w, newx, newy;
1132
1133     n = 0;
1134
1135     for (y = 0; y < WORLD_Y; y++) {
1136         for (x = y % 2; x < WORLD_X; x += 2) {
1137             if (can_grow_at(c, x, y)) {
1138                 d = distance[XYOFFSET(x, y)];
1139                 assert(d > id);
1140                 w = (d - id) * (d - id);
1141                 n += MIN(w, (isiz + 2) / 3);
1142                 if (roll0(n) < w) {
1143                     newx = x;
1144                     newy = y;
1145                 }
1146             }
1147         }
1148     }
1149
1150     if (n)
1151         add_sector(c, newx, newy);
1152     return n;
1153 }
1154
1155 static int
1156 int_cmp(const void *a, const void *b)
1157 {
1158     return *(int *)b - *(int *)a;
1159 }
1160
1161 static int *
1162 size_islands(void)
1163 {
1164     int n = ni / nc;
1165     int *isiz = malloc(n * sizeof(*isiz));
1166     int r0, r1, i;
1167
1168     isiz[0] = n * is;
1169     r1 = roll0(is);
1170     for (i = 1; i < n; i++) {
1171         r0 = r1;
1172         r1 = roll0(is);
1173         isiz[i] = is + r1 - r0;
1174         isiz[0] -= isiz[i];
1175     }
1176
1177     qsort(isiz, n, sizeof(*isiz), int_cmp);
1178     return isiz;
1179 }
1180
1181 /*
1182  * Grow the additional islands.
1183  * Return 1 on success, 0 on error.
1184  */
1185 static int
1186 grow_islands(void)
1187 {
1188     int *island_size = size_islands();
1189     int xzone_valid = 0;
1190     int carry = 0;
1191     int i, j, c, done, secs, isiz, x, y;
1192
1193     init_spheres_of_influence();
1194
1195     for (i = 0; i < ni / nc; i++) {
1196         c = nc + i * nc;
1197
1198         if (!xzone_valid)
1199             xzone_init(c);
1200
1201         carry += island_size[i];
1202         isiz = MIN(2 * is, carry);
1203
1204         for (j = 0; j < nc; j++) {
1205             isecs[c + j] = 0;
1206             if (!place_island(c + j, isiz)) {
1207                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1208                 free(island_size);
1209                 return 0;
1210             }
1211         }
1212
1213         done = 1;
1214         for (secs = 1; secs < isiz && done; secs++) {
1215             for (j = 0; j < nc; j++) {
1216                 if (!grow_one_sector(c + j))
1217                     done = 0;
1218             }
1219         }
1220
1221         if (!done) {
1222             secs--;
1223             for (j = 0; j < nc; j++) {
1224                 if (isecs[c + j] != secs) {
1225                     isecs[c + j]--;
1226                     assert(isecs[c + j] == secs);
1227                     x = sectx[c + j][secs];
1228                     y = secty[c + j][secs];
1229                     own[x][y] = -1;
1230                     adj_land_update(x, y);
1231                 }
1232             }
1233             xzone_valid = 0;
1234         }
1235
1236         for (j = 0; j < nc; j++)
1237             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1238
1239         carry -= secs;
1240     }
1241
1242     free(island_size);
1243     qprint("\n");
1244
1245     if (carry)
1246         qprint("Only managed to grow %d out of %d island sectors.\n",
1247                is * ni - carry * nc, is * ni);
1248
1249     return 1;
1250 }
1251
1252 /****************************************************************************
1253   CREATE ELEVATIONS
1254 ****************************************************************************/
1255 static void
1256 create_elevations(void)
1257 {
1258     init_distance_to_coast();
1259     elevate_land();
1260     elevate_sea();
1261 }
1262
1263 /* Generic function for finding the distance to the closest sea, land, or
1264    mountain
1265 */
1266 static int
1267 distance_to_what(int x, int y, int flag)
1268 {
1269     int d, px, py;
1270     struct hexagon_iter hexit;
1271
1272     for (d = 1; d < 5; ++d) {
1273         hexagon_first(&hexit, x, y, d, &px, &py);
1274         do {
1275             switch (flag) {
1276             case 0:             /* distance to sea */
1277                 if (own[px][py] == -1)
1278                     return d;
1279                 break;
1280             case 1:             /* distance to land */
1281                 if (own[px][py] != -1)
1282                     return d;
1283                 break;
1284             case 2:             /* distance to mountain */
1285                 if (elev[px][py] == INFINITE_ELEVATION)
1286                     return d;
1287                 break;
1288             }
1289         } while (hexagon_next(&hexit, &px, &py));
1290     }
1291     return d;
1292 }
1293
1294 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1295
1296 /* Decide where the mountains go
1297 */
1298 static void
1299 elevate_land(void)
1300 {
1301     int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1302     int highest, where, h, newk, dk;
1303
1304     for (c = 0; c < nc + ni; ++c) {
1305         total = 0;
1306         ns = isecs[c];
1307         nm = (pm * ns) / 100;
1308
1309 /* Place the mountains */
1310
1311         for (i = 0; i < ns; ++i) {
1312             off = XYOFFSET(sectx[c][i], secty[c][i]);
1313             dsea[i] = MIN(5, distance[off] + 1);
1314             weight[i] = (total += (dsea[i] * dsea[i]));
1315         }
1316
1317         for (k = nm, mountain_search = 0;
1318              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1319              ++mountain_search) {
1320             r = roll0(total);
1321             for (i = 0; i < ns; ++i) {
1322                 x = sectx[c][i];
1323                 y = secty[c][i];
1324                 if (r < weight[i] && !elev[x][y] &&
1325                     (c >= nc ||
1326                      ((!(capx[c] == sectx[c][i] &&
1327                          capy[c] == secty[c][i])) &&
1328                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1329                          capy[c] == secty[c][i]))))) {
1330                     elev[x][y] = INFINITE_ELEVATION;
1331                     break;
1332                 }
1333             }
1334             --k;
1335         }
1336
1337 /* Elevate land that is not mountain and not capital */
1338
1339         for (i = 0; i < ns; ++i)
1340             dmoun[i] = distance_to_mountain();
1341         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1342           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1343           100 * INFINITE_ELEVATION;
1344         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1345             highest = 0;
1346             where = -1;
1347             for (i = 0; i < ns; ++i) {
1348                 x = sectx[c][i];
1349                 y = secty[c][i];
1350                 if (!elev[x][y] &&
1351                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1352                                     capy[c] == secty[c][i])) &&
1353                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1354                                     capy[c] == secty[c][i]))))) {
1355                     h = 3 * (5 - dmoun[i]) + dsea[i];
1356                     assert(h > 0);
1357                     if (h > highest) {
1358                         highest = h;
1359                         where = i;
1360                     }
1361                 }
1362             }
1363             if (where == -1)
1364                 break;
1365             newk = k / 100;
1366             if (newk >= HILLMIN && newk < PLATMIN)
1367                 newk = PLATMIN;
1368             if (newk < LANDMIN)
1369                 newk = LANDMIN;
1370             elev[sectx[c][where]][secty[c][where]] = newk;
1371         }
1372
1373 /* Elevate the mountains and capitals */
1374
1375         for (i = 0; i < ns; ++i) {
1376             x = sectx[c][i];
1377             y = secty[c][i];
1378             if (elev[x][y] == INFINITE_ELEVATION) {
1379                 if (dsea[i] == 1)
1380                     elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1381                 else
1382                     elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1383                       roll0((256 - HIGHMIN) / 2);
1384             } else if (c < nc &&
1385                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1386                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1387                           capy[c] == secty[c][i]))))
1388                 elev[x][y] = PLATMIN;
1389         }
1390     }
1391 }
1392
1393 static void
1394 elevate_sea(void)
1395 {
1396     int x, y, off;
1397
1398     for (y = 0; y < WORLD_Y; ++y) {
1399         for (x = y % 2; x < WORLD_X; x += 2) {
1400             off = XYOFFSET(x, y);
1401             if (own[x][y] == -1)
1402                 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1403         }
1404     }
1405 }
1406
1407 static int
1408 elev_to_sct_type(int elevation)
1409 {
1410     if (elevation < LANDMIN)
1411         return SCT_WATER;
1412     if (elevation < HILLMIN)
1413         return SCT_RURAL;
1414     if (elevation < PLATMIN)
1415         return SCT_MOUNT;
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 }