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     int i, j;
1260
1261     for (i = 0; i < WORLD_X; i++) {
1262         for (j = 0; j < WORLD_Y; j++)
1263             elev[i][j] = -INFINITE_ELEVATION;
1264     }
1265     init_distance_to_coast();
1266     elevate_land();
1267     elevate_sea();
1268 }
1269
1270 /* Generic function for finding the distance to the closest sea, land, or
1271    mountain
1272 */
1273 static int
1274 distance_to_what(int x, int y, int flag)
1275 {
1276     int d, px, py;
1277     struct hexagon_iter hexit;
1278
1279     for (d = 1; d < 5; ++d) {
1280         hexagon_first(&hexit, x, y, d, &px, &py);
1281         do {
1282             switch (flag) {
1283             case 0:             /* distance to sea */
1284                 if (own[px][py] == -1)
1285                     return d;
1286                 break;
1287             case 1:             /* distance to land */
1288                 if (own[px][py] != -1)
1289                     return d;
1290                 break;
1291             case 2:             /* distance to mountain */
1292                 if (elev[px][py] == INFINITE_ELEVATION)
1293                     return d;
1294                 break;
1295             }
1296         } while (hexagon_next(&hexit, &px, &py));
1297     }
1298     return d;
1299 }
1300
1301 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1302
1303 /* Decide where the mountains go
1304 */
1305 static void
1306 elevate_land(void)
1307 {
1308     int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1309     int highest, where, h, newk, dk;
1310
1311     for (c = 0; c < nc + ni; ++c) {
1312         total = 0;
1313         ns = isecs[c];
1314         nm = (pm * ns) / 100;
1315
1316 /* Place the mountains */
1317
1318         for (i = 0; i < ns; ++i) {
1319             off = XYOFFSET(sectx[c][i], secty[c][i]);
1320             dsea[i] = MIN(5, distance[off] + 1);
1321             weight[i] = (total += (dsea[i] * dsea[i]));
1322         }
1323
1324         for (k = nm, mountain_search = 0;
1325              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1326              ++mountain_search) {
1327             r = roll0(total);
1328             for (i = 0; i < ns; ++i) {
1329                 x = sectx[c][i];
1330                 y = secty[c][i];
1331                 if (r < weight[i] && elev[x][y] == -INFINITE_ELEVATION &&
1332                     (c >= nc ||
1333                      ((!(capx[c] == sectx[c][i] &&
1334                          capy[c] == secty[c][i])) &&
1335                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1336                          capy[c] == secty[c][i]))))) {
1337                     elev[x][y] = INFINITE_ELEVATION;
1338                     break;
1339                 }
1340             }
1341             --k;
1342         }
1343
1344 /* Elevate land that is not mountain and not capital */
1345
1346         for (i = 0; i < ns; ++i)
1347             dmoun[i] = distance_to_mountain();
1348         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1349           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1350           100 * INFINITE_ELEVATION;
1351         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1352             highest = 0;
1353             where = -1;
1354             for (i = 0; i < ns; ++i) {
1355                 x = sectx[c][i];
1356                 y = secty[c][i];
1357                 if (elev[x][y] == -INFINITE_ELEVATION &&
1358                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1359                                     capy[c] == secty[c][i])) &&
1360                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1361                                     capy[c] == secty[c][i]))))) {
1362                     h = 3 * (5 - dmoun[i]) + dsea[i];
1363                     assert(h > 0);
1364                     if (h > highest) {
1365                         highest = h;
1366                         where = i;
1367                     }
1368                 }
1369             }
1370             if (where == -1)
1371                 break;
1372             newk = k / 100;
1373             if (newk >= HILLMIN && newk < PLATMIN)
1374                 newk = PLATMIN;
1375             if (newk < LANDMIN)
1376                 newk = LANDMIN;
1377             elev[sectx[c][where]][secty[c][where]] = newk;
1378         }
1379
1380 /* Elevate the mountains and capitals */
1381
1382         for (i = 0; i < ns; ++i) {
1383             x = sectx[c][i];
1384             y = secty[c][i];
1385             if (elev[x][y] == INFINITE_ELEVATION) {
1386                 if (dsea[i] == 1)
1387                     elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1388                 else
1389                     elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1390                       roll0((256 - HIGHMIN) / 2);
1391             } else if (c < nc &&
1392                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1393                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1394                           capy[c] == secty[c][i]))))
1395                 elev[x][y] = PLATMIN;
1396         }
1397     }
1398 }
1399
1400 static void
1401 elevate_sea(void)
1402 {
1403     int x, y, off;
1404
1405     for (y = 0; y < WORLD_Y; ++y) {
1406         for (x = y % 2; x < WORLD_X; x += 2) {
1407             off = XYOFFSET(x, y);
1408             if (elev[x][y] == -INFINITE_ELEVATION)
1409                 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1410         }
1411     }
1412 }
1413
1414 static int
1415 elev_to_sct_type(int elevation)
1416 {
1417     if (elevation < LANDMIN)
1418         return SCT_WATER;
1419     if (elevation < HILLMIN)
1420         return SCT_RURAL;
1421     if (elevation < PLATMIN)
1422         return SCT_MOUNT;
1423     if (elevation < HIGHMIN)
1424         return SCT_RURAL;
1425     return SCT_MOUNT;
1426 }
1427
1428 /****************************************************************************
1429   ADD THE RESOURCES
1430 ****************************************************************************/
1431
1432 static int
1433 set_fert(int e)
1434 {
1435     int fert = 0;
1436     if (e < LANDMIN)
1437         fert = LANDMIN - e + 40;
1438     else if (e < FERT_MAX)
1439         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1440     if (fert > 100)
1441         fert = 100;
1442     return fert;
1443 }
1444
1445 static int
1446 set_oil(int e)
1447 {
1448     int oil = 0;
1449     if (e < LANDMIN)
1450         oil = (LANDMIN - e) * 2 + roll0(2);
1451     else if (e <= OIL_MAX)
1452         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1453     if (oil > 100)
1454         oil = 100;
1455     return oil;
1456 }
1457
1458 static int
1459 set_iron(int e)
1460 {
1461     int iron = 0;
1462     if (e >= IRON_MIN && e < HIGHMIN)
1463         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1464     if (iron > 100)
1465         iron = 100;
1466     return iron;
1467 }
1468
1469 static int
1470 set_gold(int e)
1471 {
1472     int gold = 0;
1473     if (e >= GOLD_MIN) {
1474         if (e < HIGHMIN)
1475             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1476         else
1477             gold = 100 - 20 * HIGHMIN / e;
1478     }
1479     if (gold > 100)
1480         gold = 100;
1481     return gold;
1482 }
1483
1484 static int
1485 set_uran(int e)
1486 {
1487     int uran = 0;
1488     if (e >= URAN_MIN && e < HIGHMIN)
1489         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1490     if (uran > 100)
1491         uran = 100;
1492     return uran;
1493 }
1494
1495 static void
1496 add_resources(struct sctstr *sct)
1497 {
1498     sct->sct_fertil = set_fert(sct->sct_elev);
1499     sct->sct_oil = set_oil(sct->sct_elev);
1500     sct->sct_min = set_iron(sct->sct_elev);
1501     sct->sct_gmin = set_gold(sct->sct_elev);
1502     sct->sct_uran = set_uran(sct->sct_elev);
1503 }
1504
1505 /****************************************************************************
1506   DESIGNATE THE SECTORS
1507 ****************************************************************************/
1508
1509 static void
1510 write_sects(void)
1511 {
1512     struct sctstr *sct;
1513     int x, y;
1514
1515     for (y = 0; y < WORLD_Y; y++) {
1516         for (x = y % 2; x < WORLD_X; x += 2) {
1517             sct = getsectp(x, y);
1518             sct->sct_elev = elev[x][y];
1519             sct->sct_type = elev_to_sct_type(elev[x][y]);
1520             sct->sct_newtype = sct->sct_type;
1521             sct->sct_dterr = own[sct->sct_x][y] + 1;
1522             sct->sct_coastal = is_coastal(sct->sct_x, sct->sct_y);
1523             add_resources(sct);
1524         }
1525     }
1526 }
1527
1528 /****************************************************************************
1529   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1530 ****************************************************************************/
1531 static void
1532 output(void)
1533 {
1534     int sx, sy, x, y, c, type;
1535
1536     if (quiet == 0) {
1537         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1538             y = YNORM(sy);
1539             puts("");
1540             if (y % 2)
1541                 printf(" ");
1542             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1543                 x = XNORM(sx);
1544                 c = own[x][y];
1545                 type = elev_to_sct_type(elev[x][y]);
1546                 if (type == SCT_WATER)
1547                     printf(". ");
1548                 else if (type == SCT_MOUNT)
1549                     printf("^ ");
1550                 else if (c >= nc)
1551                     printf("%% ");
1552                 else {
1553                     assert(0 <= c && c < nc);
1554                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1555                         && y == capy[c])
1556                         printf("%c ", numletter[c % 62]);
1557                     else
1558                         printf("# ");
1559                 }
1560             }
1561         }
1562     }
1563 }
1564
1565 /*
1566  * Print a map to help visualize own[][].
1567  * This is for debugging.
1568  */
1569 void
1570 print_own_map(void)
1571 {
1572     int sx, sy, x, y;
1573
1574     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1575         y = YNORM(sy);
1576         printf("%4d ", sy);
1577         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1578             x = XNORM(sx);
1579             if ((x + y) & 1)
1580                 putchar(' ');
1581             else if (own[x][y] == -1)
1582                 putchar('.');
1583             else
1584                 putchar(numletter[own[x][y] % 62]);
1585         }
1586         putchar('\n');
1587     }
1588 }
1589
1590 /*
1591  * Print a map to help visualize elev[][].
1592  * This is for debugging.  It expects the terminal to understand
1593  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1594  */
1595 void
1596 print_elev_map(void)
1597 {
1598     int sx, sy, x, y, sat;
1599
1600     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1601         y = YNORM(sy);
1602         printf("%4d ", sy);
1603         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1604             x = XNORM(sx);
1605             if ((x + y) & 1)
1606                 putchar(' ');
1607             else if (!elev[x][y])
1608                 putchar(' ');
1609             else if (elev[x][y] < 0) {
1610                 sat = 256 + elev[x][y] * 2;
1611                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1612             } else if (elev[x][y] < HIGHMIN / 2) {
1613                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1614                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1615             } else if (elev[x][y] < HIGHMIN) {
1616                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1617                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1618             } else {
1619                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1620                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1621             }
1622         }
1623         putchar('\n');
1624     }
1625 }
1626
1627 /*
1628  * Print a map to help visualize xzone[].
1629  * This is for debugging.
1630  */
1631 void
1632 print_xzone_map(void)
1633 {
1634     int sx, sy, x, y, off;
1635
1636     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1637         y = YNORM(sy);
1638         printf("%4d ", sy);
1639         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1640             x = XNORM(sx);
1641             off = XYOFFSET(x, y);
1642             if ((x + y) & 1)
1643                 putchar(' ');
1644             else if (own[x][y] >= 0)
1645                 putchar('-');
1646             else if (xzone[off] >= 0)
1647                 putchar(numletter[xzone[off] % 62]);
1648             else {
1649                 assert(own[x][y] == -1);
1650                 putchar(xzone[off] == -1 ? '.' : '!');
1651             }
1652         }
1653         putchar('\n');
1654     }
1655 }
1656
1657 /*
1658  * Print a map to help visualize closest[].
1659  * This is for debugging.
1660  */
1661 void
1662 print_closest_map(void)
1663 {
1664     int sx, sy, x, y, off;
1665
1666     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1667         y = YNORM(sy);
1668         printf("%4d ", sy);
1669         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1670             x = XNORM(sx);
1671             off = XYOFFSET(x, y);
1672             if ((x + y) & 1)
1673                 putchar(' ');
1674             else if (closest[off] == (natid)-1)
1675                 putchar('.');
1676             else if (!distance[off]) {
1677                 assert(closest[off] == own[x][y]);
1678                 putchar('-');
1679             } else {
1680                 putchar(numletter[closest[off] % 62]);
1681             }
1682         }
1683         printf("\n");
1684     }
1685 }
1686
1687 void
1688 print_distance_map(void)
1689 {
1690     int sx, sy, x, y, off;
1691
1692     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1693         y = YNORM(sy);
1694         printf("%4d ", sy);
1695         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1696             x = XNORM(sx);
1697             off = XYOFFSET(x, y);
1698             if ((x + y) & 1)
1699                 putchar(' ');
1700             else if (closest[off] == (natid)-1)
1701                 putchar('.');
1702             else if (!distance[off]) {
1703                 assert(closest[off] == own[x][y]);
1704                 putchar('-');
1705             } else {
1706                 putchar(numletter[distance[off] % 62]);
1707             }
1708         }
1709         printf("\n");
1710     }
1711 }
1712
1713
1714 /***************************************************************************
1715   WRITE A SCRIPT FOR PLACING CAPITALS
1716 ****************************************************************************/
1717 static int
1718 write_newcap_script(void)
1719 {
1720     int c;
1721     FILE *script = fopen(outfile, "w");
1722
1723     if (!script) {
1724         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1725                 program_name, outfile, strerror(errno));
1726         return 0;
1727     }
1728
1729     for (c = 0; c < nc; ++c) {
1730         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1731         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1732     }
1733     fprintf(script, "add %d visitor visitor v\n", c + 1);
1734     fclose(script);
1735     return 1;
1736 }
1737
1738 static void
1739 qprint(const char *const fmt, ...)
1740 {
1741     va_list ap;
1742
1743     if (!quiet) {
1744         va_start(ap, fmt);
1745         vfprintf(stdout, fmt, ap);
1746         va_end(ap);
1747     }
1748 }