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