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().
 244  */
 245 static natid *closest;
 246 static unsigned short *distance;
 247
 248 /*
 249  * Queue for breadth-first search
 250  */
 251 static int *bfs_queue;
 252 static int bfs_queue_head, bfs_queue_tail;
 253
 254 static int **elev;              /* elevation of the sectors */
 255 static int **sectx, **secty;    /* the sectors for each continent */
 256 static int **sectc;             /* which sectors are on the coast? */
 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 static void set_coastal_flags(void);
 280
 281 static void print_vars(void);
 282 static void fl_move(int);
 283 static int grow_islands(void);
 284
 285 /* Debugging aids: */
 286 void print_own_map(void);
 287 void print_xzone_map(void);
 288 void print_closest_map(void);
 289 void print_distance_map(void);
 290 void print_elev_map(void);
 291
 292 /****************************************************************************
 293   MAIN
 294 ****************************************************************************/
 295
 296 int
 297 main(int argc, char *argv[])
 298 {
 299     int opt;
 300     char *config_file = NULL;
 301     int try, done;
 302     unsigned rnd_seed = 0;
 303     int seed_set = 0;
 304
 305     program_name = argv[0];
 306
 307     while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
 308         switch (opt) {
 309         case 'e':
 310             config_file = optarg;
 311             break;
 312         case 'i':
 313             DISTINCT_ISLANDS = 0;
 314             break;
 315         case 'q':
 316             quiet = 1;
 317             break;
 318         case 'R':
 319             rnd_seed = strtoul(optarg, NULL, 10);
 320             seed_set = 1;
 321             break;
 322         case 's':
 323             outfile = optarg;
 324             break;
 325         case 'h':
 326             usage();
 327             exit(0);
 328         case 'v':
 329             printf("%s\n\n%s", version, legal);
 330             exit(0);
 331         default:
 332             help(NULL);
 333             exit(1);
 334         }
 335     }
 336
 337     if (!seed_set)
 338         rnd_seed = pick_seed();
 339     seed_prng(rnd_seed);
 340     empfile_init();
 341     if (emp_config(config_file) < 0)
 342         exit(1);
 343     empfile_fixup();
 344
 345     parse_args(argc - optind, argv + optind);
 346
 347     allocate_memory();
 348     print_vars();
 349
 350     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
 351     qprint("seed is %u\n", rnd_seed);
 352     try = 0;
 353     do {
 354         init();
 355         if (try)
 356             qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
 357         qprint("placing capitals...\n");
 358         if (!drift())
 359             qprint("unstable drift\n");
 360         qprint("growing continents...\n");
 361         done = grow_continents();
 362         if (!done)
 363             continue;
 364         qprint("growing islands:");
 365         done = grow_islands();
 366     } while (!done && ++try < NUMTRIES);
 367     if (!done) {
 368         fprintf(stderr, "%s: world not large enough for this much land\n",
 369                 program_name);
 370         exit(1);
 371     }
 372     qprint("elevating land...\n");
 373     create_elevations();
 374
 375     qprint("writing to sectors file...\n");
 376     if (!write_newcap_script())
 377         exit(1);
 378     if (chdir(gamedir)) {
 379         fprintf(stderr, "%s: can't chdir to %s (%s)\n",
 380                 program_name, gamedir, strerror(errno));
 381         exit(1);
 382     }
 383     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
 384         exit(1);
 385     write_sects();
 386     if (!ef_close(EF_SECTOR))
 387         exit(1);
 388
 389     output();
 390     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
 391            outfile);
 392     exit(0);
 393 }
 394
 395 static void
 396 print_vars(void)
 397 {
 398     if (quiet)
 399         return;
 400     puts("Creating a planet with:\n");
 401     printf("%d continents\n", nc);
 402     printf("continent size: %d\n", sc);
 403     printf("number of islands: %d\n", ni);
 404     printf("average size of islands: %d\n", is);
 405     printf("spike: %d%%\n", sp);
 406     printf("%d%% of land is mountain (each continent will have %d mountains)\n",
 407            pm, (pm * sc) / 100);
 408     printf("minimum distance between continents: %d\n", di);
 409     printf("minimum distance from islands to continents: %d\n", id);
 410     printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
 411 }
 412
 413 static void
 414 help(char *complaint)
 415 {
 416     if (complaint)
 417         fprintf(stderr, "%s: %s\n", program_name, complaint);
 418     fprintf(stderr, "Try -h for help.\n");
 419 }
 420
 421 static void
 422 usage(void)
 423 {
 424     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
 425            "  -e CONFIG-FILE  configuration file\n"
 426            "                  (default %s)\n"
 427            "  -i              islands may merge\n"
 428            "  -q              quiet\n"
 429            "  -R SEED         seed for random number generator\n"
 430            "  -s SCRIPT       name of script to create (default %s)\n"
 431            "  -h              display this help and exit\n"
 432            "  -v              display version information and exit\n"
 433            "  NC              number of continents\n"
 434            "  SC              continent size\n"
 435            "  NI              number of islands (default NC)\n"
 436            "  IS              average island size (default SC/2)\n"
 437            "  SP              spike percentage: 0 = round, 100 = snake (default %d)\n"
 438            "  PM              percentage of land that is mountain (default %d)\n"
 439            "  DI              minimum distance between continents (default %d)\n"
 440            "  ID              minimum distance from islands to continents (default %d)\n",
 441            program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
 442            DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
 443 }
 444
 445 static void
 446 parse_args(int argc, char *argv[])
 447 {
 448     int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
 449
 450     if (argc < 2) {
 451         help("missing arguments");
 452         exit(1);
 453     }
 454     if (argc > 8) {
 455         help("too many arguments");
 456         exit(1);
 457     }
 458     nc = atoi(argv[0]);
 459     if (nc < 1) {
 460         fprintf(stderr, "%s: number of continents must be > 0\n",
 461                 program_name);
 462         exit(1);
 463     }
 464
 465     sc = atoi(argv[1]);
 466     if (sc < 2) {
 467         fprintf(stderr, "%s: size of continents must be > 1\n",
 468                 program_name);
 469         exit(1);
 470     }
 471
 472     ni = nc;
 473     is = sc / 2;
 474
 475     if (argc > 2)
 476         ni = atoi(argv[2]);
 477     if (ni < 0) {
 478         fprintf(stderr, "%s: number of islands must be >= 0\n",
 479                 program_name);
 480         exit(1);
 481     }
 482     if (ni % nc) {
 483         fprintf(stderr, "%s: number of islands must be a multiple of"
 484                 " the number of continents\n",
 485                 program_name);
 486         exit(1);
 487     }
 488
 489     if (argc > 3)
 490         is = atoi(argv[3]);
 491     if (is < 1) {
 492         fprintf(stderr, "%s: size of islands must be > 0\n",
 493                 program_name);
 494         exit(1);
 495     }
 496
 497     if (argc > 4)
 498         sp = atoi(argv[4]);
 499     if (sp < 0 || sp > 100) {
 500         fprintf(stderr,
 501                 "%s: spike percentage must be between 0 and 100\n",
 502                 program_name);
 503         exit(1);
 504     }
 505
 506     if (argc > 5)
 507         pm = atoi(argv[5]);
 508     if (pm < 0 || pm > 100) {
 509         fprintf(stderr,
 510                 "%s: mountain percentage must be between 0 and 100\n",
 511                 program_name);
 512         exit(1);
 513     }
 514
 515     if (argc > 6)
 516         di = atoi(argv[6]);
 517     if (di < 0) {
 518         fprintf(stderr, "%s: distance between continents must be >= 0\n",
 519                 program_name);
 520         exit(1);
 521     }
 522     if (di > dist_max) {
 523         fprintf(stderr, "%s: distance between continents too large\n",
 524                 program_name);
 525         exit(1);
 526     }
 527
 528     if (argc > 7)
 529         id = atoi(argv[7]);
 530     if (id < 0) {
 531         fprintf(stderr,
 532                 "%s: distance from islands to continents must be >= 0\n",
 533                 program_name);
 534         exit(1);
 535     }
 536     if (id > dist_max) {
 537         fprintf(stderr,
 538                 "%s: distance from islands to continents too large\n",
 539                 program_name);
 540         exit(1);
 541     }
 542 }
 543
 544 /****************************************************************************
 545   VARIABLE INITIALIZATION
 546 ****************************************************************************/
 547
 548 static void
 549 allocate_memory(void)
 550 {
 551     int i;
 552
 553     capx = calloc(nc, sizeof(int));
 554     capy = calloc(nc, sizeof(int));
 555     own = calloc(WORLD_X, sizeof(int *));
 556     adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
 557     xzone = malloc(WORLD_SZ() * sizeof(*xzone));
 558     seen = calloc(WORLD_SZ(), sizeof(*seen));
 559     closest = malloc(WORLD_SZ() * sizeof(*closest));
 560     distance = malloc(WORLD_SZ() * sizeof(*distance));
 561     bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
 562     elev = calloc(WORLD_X, sizeof(int *));
 563     for (i = 0; i < WORLD_X; ++i) {
 564         own[i] = calloc(WORLD_Y, sizeof(int));
 565         elev[i] = calloc(WORLD_Y, sizeof(int));
 566     }
 567     sectx = calloc(nc + ni, sizeof(int *));
 568     secty = calloc(nc + ni, sizeof(int *));
 569     sectc = calloc(nc + ni, sizeof(int *));
 570     isecs = calloc(nc + ni, sizeof(int));
 571     weight = calloc(MAX(sc, is * 2), sizeof(int));
 572     dsea = calloc(MAX(sc, is * 2), sizeof(int));
 573     dmoun = calloc(MAX(sc, is * 2), sizeof(int));
 574     for (i = 0; i < nc; ++i) {
 575         sectx[i] = calloc(sc, sizeof(int));
 576         secty[i] = calloc(sc, sizeof(int));
 577         sectc[i] = calloc(sc, sizeof(int));
 578     }
 579     for (i = nc; i < nc + ni; ++i) {
 580         sectx[i] = calloc(is * 2, sizeof(int));
 581         secty[i] = calloc(is * 2, sizeof(int));
 582         sectc[i] = calloc(is * 2, sizeof(int));
 583     }
 584
 585 }
 586
 587 static void
 588 init(void)
 589 {
 590     int i, j;
 591
 592     for (i = 0; i < WORLD_X; ++i) {
 593         for (j = 0; j < WORLD_Y; ++j) {
 594             own[i][j] = -1;
 595         }
 596     }
 597     memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
 598 }
 599
 600 /****************************************************************************
 601   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
 602 ****************************************************************************/
 603
 604 /*
 605  * How isolated is capital @j at @newx,@newy?
 606  * Return the distance to the closest other capital.
 607  */
 608 static int
 609 iso(int j, int newx, int newy)
 610 {
 611     int d = INT_MAX;
 612     int i, md;
 613
 614     for (i = 0; i < nc; ++i) {
 615         if (i == j)
 616             continue;
 617         md = mapdist(capx[i], capy[i], newx, newy);
 618         if (md < d)
 619             d = md;
 620     }
 621
 622     return d;
 623 }
 624
 625 /*
 626  * Drift the capitals
 627  * Return 1 for a stable drift, 0 for an unstable one.
 628  */
 629 static int
 630 drift(void)
 631 {
 632     int turns, i;
 633
 634     for (i = 0; i < nc; i++) {
 635         capy[i] = (2 * i) / WORLD_X;
 636         capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
 637         if (capy[i] >= WORLD_Y) {
 638             fprintf(stderr,
 639                     "%s: world not big enough for all the continents\n",
 640                     program_name);
 641             exit(1);
 642         }
 643     }
 644
 645     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 646         if (stable(turns))
 647             return 1;
 648         for (i = 0; i < nc; ++i)
 649             fl_move(i);
 650     }
 651     return 0;
 652 }
 653
 654 /*
 655  * Has the drift stabilized?
 656  * @turns is the number of turns so far.
 657  */
 658 static int
 659 stable(int turns)
 660 {
 661     static int mc[STABLE_CYCLE];
 662     int i, isod, d = 0, stab = 1;
 663
 664     if (!turns) {
 665         for (i = 0; i < STABLE_CYCLE; i++)
 666             mc[i] = i;
 667     }
 668
 669     if (turns <= DRIFT_BEFORE_CHECK)
 670         return 0;
 671
 672     for (i = 0; i < nc; ++i) {
 673         isod = iso(i, capx[i], capy[i]);
 674         if (isod > d)
 675             d = isod;
 676     }
 677
 678     for (i = 0; i < STABLE_CYCLE; ++i)
 679         if (d != mc[i])
 680             stab = 0;
 681
 682     mc[turns % STABLE_CYCLE] = d;
 683     return stab;
 684 }
 685
 686 /* This routine does the actual drifting
 687 */
 688
 689 static void
 690 fl_move(int j)
 691 {
 692     int dir, i, newx, newy;
 693
 694     dir = DIR_L + roll0(6);
 695     for (i = 0; i < 6; i++) {
 696         if (dir > DIR_LAST)
 697             dir -= 6;
 698         newx = new_x(capx[j] + diroff[dir][0]);
 699         newy = new_y(capy[j] + diroff[dir][1]);
 700         dir++;
 701         if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
 702             capx[j] = newx;
 703             capy[j] = newy;
 704             return;
 705         }
 706     }
 707 }
 708
 709 /****************************************************************************
 710   GROW THE CONTINENTS
 711 ****************************************************************************/
 712
 713 /* Look for a coastal sector of continent c
 714 */
 715
 716 static void
 717 find_coast(int c)
 718 {
 719     int i, dir, nx, ny;
 720
 721     for (i = 0; i < isecs[c]; ++i) {
 722         sectc[c][i] = 0;
 723         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 724             nx = new_x(sectx[c][i] + diroff[dir][0]);
 725             ny = new_y(secty[c][i] + diroff[dir][1]);
 726             if (own[nx][ny] == -1)
 727                 sectc[c][i] = 1;
 728         }
 729     }
 730 }
 731
 732 struct hexagon_iter {
 733     int dir, i, n;
 734 };
 735
 736 /*
 737  * Start iterating around @x0,@y0 at distance @d.
 738  * Set *x,*y to coordinates of the first sector.
 739  */
 740 static inline void
 741 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
 742               int *x, int *y)
 743 {
 744     *x = new_x(x0 - 2 * n);
 745     *y = y0;
 746     iter->dir = DIR_FIRST;
 747     iter->i = 0;
 748     iter->n = n;
 749 }
 750
 751 /*
 752  * Continue iteration started with hexagon_first().
 753  * Set *x,*y to coordinates of the next sector.
 754  * Return whether we're back at the first sector, i.e. iteration is
 755  * complete.
 756  */
 757 static inline int
 758 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
 759 {
 760     *x = new_x(*x + diroff[iter->dir][0]);
 761     *y = new_y(*y + diroff[iter->dir][1]);
 762     iter->i++;
 763     if (iter->i == iter->n) {
 764         iter->i = 0;
 765         iter->dir++;
 766     }
 767     return iter->dir <= DIR_LAST;
 768 }
 769
 770 /*
 771  * Is @x,@y in no exclusive zone other than perhaps @c's?
 772  */
 773 static int
 774 xzone_ok(int c, int x, int y)
 775 {
 776     int off = XYOFFSET(x, y);
 777
 778     return xzone[off] == c || xzone[off] == -1;
 779 }
 780
 781 /*
 782  * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
 783  */
 784 static void
 785 xzone_around_sector(int c, int x, int y, int dist)
 786 {
 787     int d, x1, y1, off;
 788     struct hexagon_iter hexit;
 789
 790     assert(xzone_ok(c, x, y));
 791
 792     xzone[XYOFFSET(x, y)] = c;
 793     for (d = 1; d <= dist; d++) {
 794         hexagon_first(&hexit, x, y, d, &x1, &y1);
 795         do {
 796             off = XYOFFSET(x1, y1);
 797             if (xzone[off] == -1)
 798                 xzone[off] = c;
 799             else if (xzone[off] != c)
 800                 xzone[off] = -2;
 801         } while (hexagon_next(&hexit, &x1, &y1));
 802     }
 803 }
 804
 805 /*
 806  * Add sectors within distance @dist to island @c's exclusive zone.
 807  */
 808 static void
 809 xzone_around_island(int c, int dist)
 810 {
 811     int i;
 812
 813     for (i = 0; i < isecs[c]; i++)
 814         xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
 815 }
 816
 817 /*
 818  * Initialize exclusive zones around @n islands.
 819  */
 820 static void
 821 xzone_init(int n)
 822 {
 823     int i, c;
 824
 825     for (i = 0; i < WORLD_SZ(); i++)
 826         xzone[i] = -1;
 827
 828     for (c = 0; c < n; c++)
 829         xzone_around_island(c, id);
 830 }
 831
 832 /*
 833  * Initialize breadth-first search.
 834  */
 835 static void
 836 bfs_init(void)
 837 {
 838     int i;
 839
 840     for (i = 0; i < WORLD_SZ(); i++) {
 841         closest[i] = -1;
 842         distance[i] = USHRT_MAX;
 843     }
 844
 845     bfs_queue_head = bfs_queue_tail = 0;
 846 }
 847
 848 /*
 849  * Add sector @x,@y to the BFS queue.
 850  * It's closest to @c, with distance @dist.
 851  */
 852 static void
 853 bfs_enqueue(int c, int x, int y, int dist)
 854 {
 855     int off = XYOFFSET(x, y);
 856
 857     assert(dist < distance[off]);
 858     closest[off] = c;
 859     distance[off] = dist;
 860     bfs_queue[bfs_queue_tail] = off;
 861     bfs_queue_tail++;
 862     if (bfs_queue_tail >= WORLD_SZ())
 863         bfs_queue_tail = 0;
 864     assert(bfs_queue_tail != bfs_queue_head);
 865 }
 866
 867 /*
 868  * Search breadth-first until the queue is empty.
 869  */
 870 static void
 871 bfs_run_queue(void)
 872 {
 873     int off, dist, i, noff, nx, ny;
 874     coord x, y;
 875
 876     while (bfs_queue_head != bfs_queue_tail) {
 877         off = bfs_queue[bfs_queue_head];
 878         bfs_queue_head++;
 879         if (bfs_queue_head >= WORLD_SZ())
 880             bfs_queue_head = 0;
 881         dist = distance[off] + 1;
 882         sctoff2xy(&x, &y, off);
 883         for (i = DIR_FIRST; i <= DIR_LAST; i++) {
 884             nx = new_x(x + diroff[i][0]);
 885             ny = new_y(y + diroff[i][1]);
 886             noff = XYOFFSET(nx, ny);
 887             if (dist < distance[noff]) {
 888                 bfs_enqueue(closest[off], nx, ny, dist);
 889             } else if (distance[noff] == dist) {
 890                 if (closest[off] != closest[noff])
 891                     closest[noff] = (natid)-1;
 892             } else
 893                 assert(distance[noff] < dist);
 894         }
 895     }
 896 }
 897
 898 /*
 899  * Add island @c's coastal sectors to the BFS queue, with distance 0.
 900  */
 901 static void
 902 bfs_enqueue_island(int c)
 903 {
 904     int i;
 905
 906     for (i = 0; i < isecs[c]; i++) {
 907         if (sectc[c][i])
 908             bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
 909     }
 910 }
 911
 912 /*
 913  * Enqueue spheres of influence borders for breadth-first search.
 914  */
 915 static void
 916 bfs_enqueue_border(void)
 917 {
 918     int x, y, off, dir, nx, ny, noff;
 919
 920     for (y = 0; y < WORLD_Y; y++) {
 921         for (x = y % 2; x < WORLD_X; x += 2) {
 922             off = XYOFFSET(x, y);
 923             if (distance[off] <= id + 1)
 924                 continue;
 925             if (closest[off] == (natid)-1)
 926                 continue;
 927             for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 928                 nx = new_x(x + diroff[dir][0]);
 929                 ny = new_y(y + diroff[dir][1]);
 930                 noff = XYOFFSET(nx, ny);
 931                 if (closest[noff] != closest[off]) {
 932                     bfs_enqueue(closest[off], x, y, id + 1);
 933                     break;
 934                 }
 935             }
 936         }
 937     }
 938 }
 939
 940 /*
 941  * Compute spheres of influence
 942  * A continent's sphere of influence is the set of sectors closer to
 943  * it than to any other continent.
 944  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 945  * -1 if no single continent is closest.
 946  * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
 947  * closest coastal land sector and the distance to just outside the
 948  * sphere of influence plus @id.  For sea sectors within a continent's
 949  * sphere of influence, distance[off] - id is the distance to the
 950  * border of the area where additional islands can be placed.
 951  */
 952 static void
 953 init_spheres_of_influence(void)
 954 {
 955     int c;
 956
 957     bfs_init();
 958     for (c = 0; c < nc; c++)
 959         bfs_enqueue_island(c);
 960     bfs_run_queue();
 961     bfs_enqueue_border();
 962     bfs_run_queue();
 963 }
 964
 965 /*
 966  * Is @x,@y in the same sphere of influence as island @c?
 967  * Always true when @c is a continent.
 968  */
 969 static int
 970 is_in_sphere(int c, int x, int y)
 971 {
 972     return c < nc || closest[XYOFFSET(x, y)] == c % nc;
 973 }
 974
 975 /*
 976  * Can island @c grow at @x,@y?
 977  */
 978 static int
 979 can_grow_at(int c, int x, int y)
 980 {
 981     return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
 982 }
 983
 984 static void
 985 adj_land_update(int x, int y)
 986 {
 987     int is_land = own[x][y] != -1;
 988     int dir, nx, ny, noff;
 989
 990     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 991         nx = new_x(x + diroff[dir][0]);
 992         ny = new_y(y + diroff[dir][1]);
 993         noff = XYOFFSET(nx, ny);
 994         if (is_land)
 995             adj_land[noff] |= 1u << DIR_BACK(dir);
 996         else
 997             adj_land[noff] &= ~(1u << DIR_BACK(dir));
 998     }
 999 }
1000
1001 static void
1002 add_sector(int c, int x, int y)
1003 {
1004     assert(own[x][y] == -1);
1005     xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1006     sectx[c][isecs[c]] = x;
1007     secty[c][isecs[c]] = y;
1008     isecs[c]++;
1009     own[x][y] = c;
1010     adj_land_update(x, y);
1011 }
1012
1013 static int
1014 grow_weight(int c, int x, int y, int spike)
1015 {
1016     int n, b;
1017
1018     /*
1019      * #Land neighbors is #bits set in adj_land[].
1020      * Count them Brian Kernighan's way.
1021      */
1022     n = 0;
1023     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1024         n++;
1025     assert(n > 0 && n < 7);
1026
1027     if (spike)
1028         return (6 - n) * (6 - n);
1029
1030     return n * n * n;
1031 }
1032
1033 static int
1034 grow_one_sector(int c)
1035 {
1036     int spike = roll0(100) < sp;
1037     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1038
1039     assert(cur_seen < UINT_MAX);
1040     cur_seen++;
1041     wsum = 0;
1042     newx = newy = -1;
1043
1044     for (i = 0; i < isecs[c]; i++) {
1045         x = sectx[c][i];
1046         y = secty[c][i];
1047         off = XYOFFSET(x, y);
1048
1049         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1050             if (adj_land[off] & (1u << dir))
1051                 continue;
1052             nx = new_x(x + diroff[dir][0]);
1053             ny = new_y(y + diroff[dir][1]);
1054             noff = XYOFFSET(nx, ny);
1055             if (seen[noff] == cur_seen)
1056                 continue;
1057             assert(seen[noff] < cur_seen);
1058             seen[noff] = cur_seen;
1059             if (!can_grow_at(c, nx, ny))
1060                 continue;
1061             w = grow_weight(c, nx, ny, spike);
1062             assert(wsum < INT_MAX - w);
1063             wsum += w;
1064             if (roll0(wsum) < w) {
1065                 newx = nx;
1066                 newy = ny;
1067             }
1068         }
1069     }
1070
1071     if (!wsum)
1072         return 0;
1073
1074     add_sector(c, newx, newy);
1075     return 1;
1076 }
1077
1078 /*
1079  * Grow the continents.
1080  * Return 1 on success, 0 on error.
1081  */
1082 static int
1083 grow_continents(void)
1084 {
1085     int done = 1;
1086     int c, secs;
1087
1088     xzone_init(0);
1089
1090     for (c = 0; c < nc; ++c) {
1091         isecs[c] = 0;
1092         if (!can_grow_at(c, capx[c], capy[c])
1093             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1094             done = 0;
1095             continue;
1096         }
1097         add_sector(c, capx[c], capy[c]);
1098         add_sector(c, new_x(capx[c] + 2), capy[c]);
1099     }
1100
1101     if (!done) {
1102         qprint("No room for continents\n");
1103         return 0;
1104     }
1105
1106     for (secs = 2; secs < sc && done; secs++) {
1107         for (c = 0; c < nc; ++c) {
1108             if (!grow_one_sector(c))
1109                 done = 0;
1110         }
1111     }
1112
1113     for (c = 0; c < nc; ++c)
1114         find_coast(c);
1115
1116     if (!done)
1117         qprint("Only managed to grow %d out of %d sectors.\n",
1118                secs - 1, sc);
1119     return done;
1120 }
1121
1122 /****************************************************************************
1123   GROW THE ISLANDS
1124 ****************************************************************************/
1125
1126 /*
1127  * Place additional island @c's first sector.
1128  * Return 1 on success, 0 on error.
1129  */
1130 static int
1131 place_island(int c, int isiz)
1132 {
1133     int n, x, y, d, w, newx, newy;
1134
1135     n = 0;
1136
1137     for (y = 0; y < WORLD_Y; y++) {
1138         for (x = y % 2; x < WORLD_X; x += 2) {
1139             if (can_grow_at(c, x, y)) {
1140                 d = distance[XYOFFSET(x, y)];
1141                 assert(d > id);
1142                 w = (d - id) * (d - id);
1143                 n += MIN(w, (isiz + 2) / 3);
1144                 if (roll0(n) < w) {
1145                     newx = x;
1146                     newy = y;
1147                 }
1148             }
1149         }
1150     }
1151
1152     if (n)
1153         add_sector(c, newx, newy);
1154     return n;
1155 }
1156
1157 static int
1158 int_cmp(const void *a, const void *b)
1159 {
1160     return *(int *)b - *(int *)a;
1161 }
1162
1163 static int *
1164 size_islands(void)
1165 {
1166     int n = ni / nc;
1167     int *isiz = malloc(n * sizeof(*isiz));
1168     int r0, r1, i;
1169
1170     isiz[0] = n * is;
1171     r1 = roll0(is);
1172     for (i = 1; i < n; i++) {
1173         r0 = r1;
1174         r1 = roll0(is);
1175         isiz[i] = is + r1 - r0;
1176         isiz[0] -= isiz[i];
1177     }
1178
1179     qsort(isiz, n, sizeof(*isiz), int_cmp);
1180     return isiz;
1181 }
1182
1183 /*
1184  * Grow the additional islands.
1185  * Return 1 on success, 0 on error.
1186  */
1187 static int
1188 grow_islands(void)
1189 {
1190     int *island_size = size_islands();
1191     int xzone_valid = 0;
1192     int carry = 0;
1193     int i, j, c, done, secs, isiz, x, y;
1194
1195     init_spheres_of_influence();
1196
1197     for (i = 0; i < ni / nc; i++) {
1198         c = nc + i * nc;
1199
1200         if (!xzone_valid)
1201             xzone_init(c);
1202
1203         carry += island_size[i];
1204         isiz = MIN(2 * is, carry);
1205
1206         for (j = 0; j < nc; j++) {
1207             isecs[c + j] = 0;
1208             if (!place_island(c + j, isiz)) {
1209                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1210                 free(island_size);
1211                 return 0;
1212             }
1213         }
1214
1215         done = 1;
1216         for (secs = 1; secs < isiz && done; secs++) {
1217             for (j = 0; j < nc; j++) {
1218                 if (!grow_one_sector(c + j))
1219                     done = 0;
1220             }
1221         }
1222
1223         if (!done) {
1224             secs--;
1225             for (j = 0; j < nc; j++) {
1226                 if (isecs[c + j] != secs) {
1227                     isecs[c + j]--;
1228                     assert(isecs[c + j] == secs);
1229                     x = sectx[c + j][secs];
1230                     y = secty[c + j][secs];
1231                     own[x][y] = -1;
1232                     adj_land_update(x, y);
1233                 }
1234             }
1235             xzone_valid = 0;
1236         }
1237
1238         for (j = 0; j < nc; j++)
1239             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1240
1241         carry -= secs;
1242     }
1243
1244     free(island_size);
1245     qprint("\n");
1246
1247     if (carry)
1248         qprint("Only managed to grow %d out of %d island sectors.\n",
1249                is * ni - carry * nc, is * ni);
1250
1251     for (c = nc; c < nc + ni; c++)
1252         find_coast(c);
1253
1254     return 1;
1255 }
1256
1257 /****************************************************************************
1258   CREATE ELEVATIONS
1259 ****************************************************************************/
1260 static void
1261 create_elevations(void)
1262 {
1263     int i, j;
1264
1265     for (i = 0; i < WORLD_X; i++) {
1266         for (j = 0; j < WORLD_Y; j++)
1267             elev[i][j] = -INFINITE_ELEVATION;
1268     }
1269     elevate_land();
1270     elevate_sea();
1271 }
1272
1273 /* Generic function for finding the distance to the closest sea, land, or
1274    mountain
1275 */
1276 static int
1277 distance_to_what(int x, int y, int flag)
1278 {
1279     int d, px, py;
1280     struct hexagon_iter hexit;
1281
1282     for (d = 1; d < 5; ++d) {
1283         hexagon_first(&hexit, x, y, d, &px, &py);
1284         do {
1285             switch (flag) {
1286             case 0:             /* distance to sea */
1287                 if (own[px][py] == -1)
1288                     return d;
1289                 break;
1290             case 1:             /* distance to land */
1291                 if (own[px][py] != -1)
1292                     return d;
1293                 break;
1294             case 2:             /* distance to mountain */
1295                 if (elev[px][py] == INFINITE_ELEVATION)
1296                     return d;
1297                 break;
1298             }
1299         } while (hexagon_next(&hexit, &px, &py));
1300     }
1301     return d;
1302 }
1303
1304 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1305 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1306
1307 /* Decide where the mountains go
1308 */
1309 static void
1310 elevate_land(void)
1311 {
1312     int i, mountain_search, k, c, total, ns, nm, r, x, y;
1313     int highest, where, h, newk, dk;
1314
1315     for (c = 0; c < nc + ni; ++c) {
1316         total = 0;
1317         ns = isecs[c];
1318         nm = (pm * ns) / 100;
1319
1320 /* Place the mountains */
1321
1322         for (i = 0; i < ns; ++i) {
1323             dsea[i] = distance_to_sea();
1324             weight[i] = (total += (dsea[i] * dsea[i]));
1325         }
1326
1327         for (k = nm, mountain_search = 0;
1328              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1329              ++mountain_search) {
1330             r = roll0(total);
1331             for (i = 0; i < ns; ++i) {
1332                 x = sectx[c][i];
1333                 y = secty[c][i];
1334                 if (r < weight[i] && elev[x][y] == -INFINITE_ELEVATION &&
1335                     (c >= nc ||
1336                      ((!(capx[c] == sectx[c][i] &&
1337                          capy[c] == secty[c][i])) &&
1338                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1339                          capy[c] == secty[c][i]))))) {
1340                     elev[x][y] = INFINITE_ELEVATION;
1341                     break;
1342                 }
1343             }
1344             --k;
1345         }
1346
1347 /* Elevate land that is not mountain and not capital */
1348
1349         for (i = 0; i < ns; ++i)
1350             dmoun[i] = distance_to_mountain();
1351         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1352           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1353           100 * INFINITE_ELEVATION;
1354         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1355             highest = 0;
1356             where = -1;
1357             for (i = 0; i < ns; ++i) {
1358                 x = sectx[c][i];
1359                 y = secty[c][i];
1360                 if (elev[x][y] == -INFINITE_ELEVATION &&
1361                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1362                                     capy[c] == secty[c][i])) &&
1363                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1364                                     capy[c] == secty[c][i]))))) {
1365                     h = 3 * (5 - dmoun[i]) + dsea[i];
1366                     assert(h > 0);
1367                     if (h > highest) {
1368                         highest = h;
1369                         where = i;
1370                     }
1371                 }
1372             }
1373             if (where == -1)
1374                 break;
1375             newk = k / 100;
1376             if (newk >= HILLMIN && newk < PLATMIN)
1377                 newk = PLATMIN;
1378             if (newk < LANDMIN)
1379                 newk = LANDMIN;
1380             elev[sectx[c][where]][secty[c][where]] = newk;
1381         }
1382
1383 /* Elevate the mountains and capitals */
1384
1385         for (i = 0; i < ns; ++i) {
1386             x = sectx[c][i];
1387             y = secty[c][i];
1388             if (elev[x][y] == INFINITE_ELEVATION) {
1389                 if (dsea[i] == 1)
1390                     elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1391                 else
1392                     elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1393                       roll0((256 - HIGHMIN) / 2);
1394             } else if (c < nc &&
1395                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1396                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1397                           capy[c] == secty[c][i]))))
1398                 elev[x][y] = PLATMIN;
1399         }
1400     }
1401 }
1402
1403 #define distance_to_land() distance_to_what(x, y, 1)
1404
1405 static void
1406 elevate_sea(void)
1407 {
1408     int x, y;
1409
1410     for (y = 0; y < WORLD_Y; ++y) {
1411         for (x = y % 2; x < WORLD_X; x += 2) {
1412             if (elev[x][y] == -INFINITE_ELEVATION)
1413                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1414         }
1415     }
1416 }
1417
1418 static int
1419 elev_to_sct_type(int elevation)
1420 {
1421     if (elevation < LANDMIN)
1422         return SCT_WATER;
1423     if (elevation < HILLMIN)
1424         return SCT_RURAL;
1425     if (elevation < PLATMIN)
1426         return SCT_MOUNT;
1427     if (elevation < HIGHMIN)
1428         return SCT_RURAL;
1429     return SCT_MOUNT;
1430 }
1431
1432 /****************************************************************************
1433   ADD THE RESOURCES
1434 ****************************************************************************/
1435
1436 static int
1437 set_fert(int e)
1438 {
1439     int fert = 0;
1440     if (e < LANDMIN)
1441         fert = LANDMIN - e + 40;
1442     else if (e < FERT_MAX)
1443         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1444     if (fert > 100)
1445         fert = 100;
1446     return fert;
1447 }
1448
1449 static int
1450 set_oil(int e)
1451 {
1452     int oil = 0;
1453     if (e < LANDMIN)
1454         oil = (LANDMIN - e) * 2 + roll0(2);
1455     else if (e <= OIL_MAX)
1456         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1457     if (oil > 100)
1458         oil = 100;
1459     return oil;
1460 }
1461
1462 static int
1463 set_iron(int e)
1464 {
1465     int iron = 0;
1466     if (e >= IRON_MIN && e < HIGHMIN)
1467         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1468     if (iron > 100)
1469         iron = 100;
1470     return iron;
1471 }
1472
1473 static int
1474 set_gold(int e)
1475 {
1476     int gold = 0;
1477     if (e >= GOLD_MIN) {
1478         if (e < HIGHMIN)
1479             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1480         else
1481             gold = 100 - 20 * HIGHMIN / e;
1482     }
1483     if (gold > 100)
1484         gold = 100;
1485     return gold;
1486 }
1487
1488 static int
1489 set_uran(int e)
1490 {
1491     int uran = 0;
1492     if (e >= URAN_MIN && e < HIGHMIN)
1493         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1494     if (uran > 100)
1495         uran = 100;
1496     return uran;
1497 }
1498
1499 static void
1500 add_resources(struct sctstr *sct)
1501 {
1502     sct->sct_fertil = set_fert(sct->sct_elev);
1503     sct->sct_oil = set_oil(sct->sct_elev);
1504     sct->sct_min = set_iron(sct->sct_elev);
1505     sct->sct_gmin = set_gold(sct->sct_elev);
1506     sct->sct_uran = set_uran(sct->sct_elev);
1507 }
1508
1509 /****************************************************************************
1510   DESIGNATE THE SECTORS
1511 ****************************************************************************/
1512
1513 static void
1514 write_sects(void)
1515 {
1516     struct sctstr *sct;
1517     int x, y;
1518
1519     for (y = 0; y < WORLD_Y; y++) {
1520         for (x = y % 2; x < WORLD_X; x += 2) {
1521             sct = getsectp(x, y);
1522             sct->sct_elev = elev[x][y];
1523             sct->sct_type = elev_to_sct_type(elev[x][y]);
1524             sct->sct_newtype = sct->sct_type;
1525             sct->sct_dterr = own[sct->sct_x][y] + 1;
1526             add_resources(sct);
1527         }
1528     }
1529     set_coastal_flags();
1530 }
1531
1532 /****************************************************************************
1533   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1534 ****************************************************************************/
1535 static void
1536 output(void)
1537 {
1538     int sx, sy, x, y, c, type;
1539
1540     if (quiet == 0) {
1541         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1542             y = YNORM(sy);
1543             puts("");
1544             if (y % 2)
1545                 printf(" ");
1546             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1547                 x = XNORM(sx);
1548                 c = own[x][y];
1549                 type = elev_to_sct_type(elev[x][y]);
1550                 if (type == SCT_WATER)
1551                     printf(". ");
1552                 else if (type == SCT_MOUNT)
1553                     printf("^ ");
1554                 else if (c >= nc)
1555                     printf("%% ");
1556                 else {
1557                     assert(0 <= c && c < nc);
1558                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1559                         && y == capy[c])
1560                         printf("%c ", numletter[c % 62]);
1561                     else
1562                         printf("# ");
1563                 }
1564             }
1565         }
1566     }
1567 }
1568
1569 /*
1570  * Print a map to help visualize own[][].
1571  * This is for debugging.
1572  */
1573 void
1574 print_own_map(void)
1575 {
1576     int sx, sy, x, y;
1577
1578     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1579         y = YNORM(sy);
1580         printf("%4d ", sy);
1581         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1582             x = XNORM(sx);
1583             if ((x + y) & 1)
1584                 putchar(' ');
1585             else if (own[x][y] == -1)
1586                 putchar('.');
1587             else
1588                 putchar(numletter[own[x][y] % 62]);
1589         }
1590         putchar('\n');
1591     }
1592 }
1593
1594 /*
1595  * Print a map to help visualize elev[][].
1596  * This is for debugging.  It expects the terminal to understand
1597  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1598  */
1599 void
1600 print_elev_map(void)
1601 {
1602     int sx, sy, x, y, sat;
1603
1604     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1605         y = YNORM(sy);
1606         printf("%4d ", sy);
1607         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1608             x = XNORM(sx);
1609             if ((x + y) & 1)
1610                 putchar(' ');
1611             else if (!elev[x][y])
1612                 putchar(' ');
1613             else if (elev[x][y] < 0) {
1614                 sat = 256 + elev[x][y] * 2;
1615                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1616             } else if (elev[x][y] < HIGHMIN / 2) {
1617                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1618                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1619             } else if (elev[x][y] < HIGHMIN) {
1620                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1621                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1622             } else {
1623                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1624                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1625             }
1626         }
1627         putchar('\n');
1628     }
1629 }
1630
1631 /*
1632  * Print a map to help visualize xzone[].
1633  * This is for debugging.
1634  */
1635 void
1636 print_xzone_map(void)
1637 {
1638     int sx, sy, x, y, off;
1639
1640     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1641         y = YNORM(sy);
1642         printf("%4d ", sy);
1643         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1644             x = XNORM(sx);
1645             off = XYOFFSET(x, y);
1646             if ((x + y) & 1)
1647                 putchar(' ');
1648             else if (own[x][y] >= 0)
1649                 putchar('-');
1650             else if (xzone[off] >= 0)
1651                 putchar(numletter[xzone[off] % 62]);
1652             else {
1653                 assert(own[x][y] == -1);
1654                 putchar(xzone[off] == -1 ? '.' : '!');
1655             }
1656         }
1657         putchar('\n');
1658     }
1659 }
1660
1661 /*
1662  * Print a map to help visualize closest[].
1663  * This is for debugging.
1664  */
1665 void
1666 print_closest_map(void)
1667 {
1668     int sx, sy, x, y, off;
1669
1670     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1671         y = YNORM(sy);
1672         printf("%4d ", sy);
1673         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1674             x = XNORM(sx);
1675             off = XYOFFSET(x, y);
1676             if ((x + y) & 1)
1677                 putchar(' ');
1678             else if (closest[off] == (natid)-1)
1679                 putchar('.');
1680             else if (!distance[off]) {
1681                 assert(closest[off] == own[x][y]);
1682                 putchar('-');
1683             } else {
1684                 putchar(numletter[closest[off] % 62]);
1685             }
1686         }
1687         printf("\n");
1688     }
1689 }
1690
1691 void
1692 print_distance_map(void)
1693 {
1694     int sx, sy, x, y, off;
1695
1696     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1697         y = YNORM(sy);
1698         printf("%4d ", sy);
1699         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1700             x = XNORM(sx);
1701             off = XYOFFSET(x, y);
1702             if ((x + y) & 1)
1703                 putchar(' ');
1704             else if (closest[off] == (natid)-1)
1705                 putchar('.');
1706             else if (!distance[off]) {
1707                 assert(closest[off] == own[x][y]);
1708                 putchar('-');
1709             } else {
1710                 putchar(numletter[distance[off] % 62]);
1711             }
1712         }
1713         printf("\n");
1714     }
1715 }
1716
1717
1718 /***************************************************************************
1719   WRITE A SCRIPT FOR PLACING CAPITALS
1720 ****************************************************************************/
1721 static int
1722 write_newcap_script(void)
1723 {
1724     int c;
1725     FILE *script = fopen(outfile, "w");
1726
1727     if (!script) {
1728         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1729                 program_name, outfile, strerror(errno));
1730         return 0;
1731     }
1732
1733     for (c = 0; c < nc; ++c) {
1734         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1735         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1736     }
1737     fprintf(script, "add %d visitor visitor v\n", c + 1);
1738     fclose(script);
1739     return 1;
1740 }
1741
1742 static void
1743 qprint(const char *const fmt, ...)
1744 {
1745     va_list ap;
1746
1747     if (!quiet) {
1748         va_start(ap, fmt);
1749         vfprintf(stdout, fmt, ap);
1750         va_end(ap);
1751     }
1752 }
1753
1754 static void
1755 set_coastal_flags(void)
1756 {
1757     int i, j;
1758     struct sctstr *sp;
1759
1760     for (i = 0; i < nc + ni; ++i) {
1761         for (j = 0; j < isecs[i]; j++) {
1762             sp = getsectp(sectx[i][j], secty[i][j]);
1763             sp->sct_coastal = sectc[i][j];
1764         }
1765     }
1766 }