git.pond.sub.org Git - empserver/blob - src/util/fairland.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2020, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                Ken Stevens, Steve McClure, Markus Armbruster
   5  *
   6  *  Empire is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  *
  19  *  ---
  20  *
  21  *  See files README, COPYING and CREDITS in the root of the source
  22  *  tree for related information and legal notices.  It is expected
  23  *  that future projects/authors will amend these files as needed.
  24  *
  25  *  ---
  26  *
  27  *  fairland.c: Create a nice, new world
  28  *
  29  *  Known contributors to this file:
  30  *     Ken Stevens, 1995
  31  *     Steve McClure, 1998
  32  *     Markus Armbruster, 2004-2020
  33  */
  34
  35 /*
  36  * How fairland works
  37  *
  38  * 1. Place capitals
  39  *
  40  * Place the capitals on the torus in such a way so as to maximize
  41  * their distances from one another.  This uses the perturbation
  42  * technique of calculus of variations.
  43  *
  44  * 2. Grow start islands ("continents")
  45  *
  46  * For all continents, add the first sector at the capital's location,
  47  * and the second right to it.  These are the capital sectors.  Then
  48  * add one sector to each continent in turn, until they have the
  49  * specified size.
  50  *
  51  * Growth uses weighted random sampling to pick one sector from the
  52  * set of adjacent sea sectors that aren't too close to another
  53  * continent.  Growth operates in spiking mode with a chance given by
  54  * the spike percentage.  When "spiking", a sector's weight increases
  55  * with number of adjacent sea sectors.  This directs the growth away
  56  * from land, resulting in spikes.  When not spiking, the weight
  57  * increases with the number of adjacent land sectors.  This makes the
  58  * island more rounded.
  59  *
  60  * If growing fails due to lack of room, start over.  If it fails too
  61  * many times, give up and terminate unsuccessfully.
  62  *
  63  * 3. Place and grow additional islands
  64  *
  65  * Each continent has a "sphere of influence": the set of sectors
  66  * closer to it than to any other continent.  Each island is entirely
  67  * in one such sphere, and each sphere contains the same number of
  68  * islands with the same sizes.
  69  *
  70  * First, split the specified number of island sectors per continent
  71  * randomly into the island sizes.  Sort by size so that larger
  72  * islands are grown before smaller ones, to give the large ones the
  73  * best chance to grow to their planned size.
  74  *
  75  * Then place one island's first sector into each sphere, using
  76  * weighted random sampling with weights favoring sectors away from
  77  * land and other spheres.  Add one sector to each island in turn,
  78  * until they have the intended size.  Repeat until the specified
  79  * number of islands has been grown.
  80  *
  81  * If placement fails due to lack of room, start over, just like for
  82  * continents.
  83  *
  84  * Growing works as for continents, except the minimum distance for
  85  * additional islands applies, and growing simply stops when any of
  86  * the islands being grown lacks the room to grow further.  The number
  87  * of sectors not grown carries over to the next island size.
  88  *
  89  * 4. Compute elevation
  90  *
  91  * Elevate islands one after the other.
  92  *
  93  * First, place the specified number of mountains randomly.
  94  * Probability increases with distance to sea.
  95  *
  96  * Last, elevate mountains and the capitals.  Pick coastal mountain
  97  * elevation randomly from an interval of medium elevations reserved
  98  * for them.  Pick non-coastal mountain elevation randomly from an
  99  * interval of high elevation reserved for them.  Set capital
 100  * elevation to a fixed, medium value.
 101  *
 102  * In between, elevate the remaining land one by one, working from
 103  * mountains towards the sea, and from the elevation just below the
 104  * non-coastal mountains' interval linearly down to 1, avoiding the
 105  * coastal mountains' interval.
 106  *
 107  * This gives islands of the same size the same set of elevations,
 108  * except for mountains.
 109  *
 110  * Elevate sea: pick a random depth from an interval that deepens with
 111  * the distance to land.
 112  *
 113  * 5. Set resources
 114  *
 115  * Sector resources are simple functions of elevation.  You can alter
 116  * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
 117  * customize them.
 118  */
 119
 120 #include <config.h>
 121
 122 #include <assert.h>
 123 #include <errno.h>
 124 #include <limits.h>
 125 #include <stdarg.h>
 126 #include <stdio.h>
 127 #include <unistd.h>
 128 #include "chance.h"
 129 #include "optlist.h"
 130 #include "path.h"
 131 #include "prototypes.h"
 132 #include "sect.h"
 133 #include "version.h"
 134 #include "xy.h"
 135
 136 /* The following five numbers refer to elevation under which (in the case of
 137    fertility or oil) or over which (in the case of iron, gold, and uranium)
 138    sectors with that elevation will contain that resource.  Elevation ranges
 139    from 0 to 100 */
 140
 141 /* raise FERT_MAX for more fertility */
 142 #define FERT_MAX   56
 143
 144 /* raise OIL_MAX for more oil */
 145 #define OIL_MAX    33
 146
 147 /* lower IRON_MIN for more iron */
 148 #define IRON_MIN   22
 149
 150 /* lower GOLD_MIN for more gold */
 151 #define GOLD_MIN   36
 152
 153 /* lower URAN_MIN for more uranium */
 154 #define URAN_MIN   56
 155
 156 /* do not change these 4 defines */
 157 #define LANDMIN         1       /* plate altitude for normal land */
 158 #define HILLMIN         34      /* plate altitude for hills */
 159 #define PLATMIN         36      /* plate altitude for plateau */
 160 #define HIGHMIN         98      /* plate altitude for mountains */
 161
 162 static void qprint(const char * const fmt, ...)
 163     ATTRIBUTE((format (printf, 1, 2)));
 164
 165 /*
 166  * Program arguments and options
 167  */
 168 static char *program_name;
 169 static int nc, sc;              /* number and size of continents */
 170 static int ni, is;              /* number and size of islands */
 171 #define DEFAULT_SPIKE 10
 172 static int sp = DEFAULT_SPIKE;  /* spike percentage */
 173 #define DEFAULT_MOUNTAIN 0
 174 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
 175 #define DEFAULT_CONTDIST 2
 176 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
 177 #define DEFAULT_ISLDIST 1
 178 static int id = DEFAULT_ISLDIST;  /* ... continents and islands */
 179 /* don't let the islands crash into each other.
 180    1 = don't merge, 0 = merge. */
 181 static int DISTINCT_ISLANDS = 1;
 182 static int quiet;
 183 #define DEFAULT_OUTFILE_NAME "newcap_script"
 184 static const char *outfile = DEFAULT_OUTFILE_NAME;
 185
 186 #define STABLE_CYCLE 4          /* stability required for perterbed capitals */
 187 #define INFINITE_ELEVATION 999
 188
 189 /* these defines prevent infinite loops:
 190 */
 191 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
 192 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
 193 #define MOUNTAIN_SEARCH_MAX 1000        /* how long do we try to place mountains */
 194
 195 /* handy macros:
 196 */
 197
 198 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
 199 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
 200
 201 /*
 202  * Island sizes
 203  * isecs[i] is the size of the i-th island.
 204  */
 205 static int *isecs;
 206
 207 static int *capx, *capy;        /* location of the nc capitals */
 208
 209 static int **own;               /* owner of the sector.  -1 means water */
 210
 211 /*
 212  * Adjacent land sectors
 213  * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
 214  * to x, y in direction d is land.
 215  */
 216 static unsigned char *adj_land;
 217
 218 /*
 219  * Exclusive zones
 220  * Each island is surrounded by an exclusive zone where only it may
 221  * grow.  The width of the zone depends on minimum distances.
 222  * While growing continents, it is @di sectors wide.
 223  * While growing additional islands, it is @id sectors wide.
 224  * DISTINCT_ISLANDS nullifies the exclusive zone then.
 225  * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
 226  * zone, a (non-negative) island number when it is in that island's
 227  * exclusive zone and no other, and -2 when it is in multiple
 228  * exclusive zones.
 229  */
 230 static short *xzone;
 231
 232 /*
 233  * Set of sectors seen already
 234  * Increment @cur_seen to empty the set of sectors seen, set
 235  * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
 236  */
 237 static unsigned *seen;
 238 static unsigned cur_seen;
 239
 240 /*
 241  * Closest continent and "distance"
 242  * closest[XYOFFSET(x, y)] is the closest continent's number.
 243  * distance[] is complicated; see init_spheres_of_influence() and
 244  * init_distance_to_coast().
 245  */
 246 static natid *closest;
 247 static unsigned short *distance;
 248
 249 /*
 250  * Queue for breadth-first search
 251  */
 252 static int *bfs_queue;
 253 static int bfs_queue_head, bfs_queue_tail;
 254
 255 static int **elev;              /* elevation of the sectors */
 256 static int **sectx, **secty;    /* the sectors for each continent */
 257 static int **sectc;             /* which sectors are on the coast? */
 258 static int *weight;             /* used for placing mountains */
 259 static int *dsea, *dmoun;       /* the dist to the ocean and mountain */
 260
 261 #define NUMTRIES 10             /* keep trying to grow this many times */
 262
 263 static const char *numletter =
 264     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 265
 266 static void help(char *);
 267 static void usage(void);
 268 static void parse_args(int argc, char *argv[]);
 269 static void allocate_memory(void);
 270 static void init(void);
 271 static int drift(void);
 272 static int grow_continents(void);
 273 static void create_elevations(void);
 274 static void write_sects(void);
 275 static void output(void);
 276 static int write_newcap_script(void);
 277 static int stable(int);
 278 static void elevate_land(void);
 279 static void elevate_sea(void);
 280 static void set_coastal_flags(void);
 281
 282 static void print_vars(void);
 283 static void fl_move(int);
 284 static int grow_islands(void);
 285
 286 /* Debugging aids: */
 287 void print_own_map(void);
 288 void print_xzone_map(void);
 289 void print_closest_map(void);
 290 void print_distance_map(void);
 291 void print_elev_map(void);
 292
 293 /****************************************************************************
 294   MAIN
 295 ****************************************************************************/
 296
 297 int
 298 main(int argc, char *argv[])
 299 {
 300     int opt;
 301     char *config_file = NULL;
 302     int try, done;
 303     unsigned rnd_seed = 0;
 304     int seed_set = 0;
 305
 306     program_name = argv[0];
 307
 308     while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
 309         switch (opt) {
 310         case 'e':
 311             config_file = optarg;
 312             break;
 313         case 'i':
 314             DISTINCT_ISLANDS = 0;
 315             break;
 316         case 'q':
 317             quiet = 1;
 318             break;
 319         case 'R':
 320             rnd_seed = strtoul(optarg, NULL, 10);
 321             seed_set = 1;
 322             break;
 323         case 's':
 324             outfile = optarg;
 325             break;
 326         case 'h':
 327             usage();
 328             exit(0);
 329         case 'v':
 330             printf("%s\n\n%s", version, legal);
 331             exit(0);
 332         default:
 333             help(NULL);
 334             exit(1);
 335         }
 336     }
 337
 338     if (!seed_set)
 339         rnd_seed = pick_seed();
 340     seed_prng(rnd_seed);
 341     empfile_init();
 342     if (emp_config(config_file) < 0)
 343         exit(1);
 344     empfile_fixup();
 345
 346     parse_args(argc - optind, argv + optind);
 347
 348     allocate_memory();
 349     print_vars();
 350
 351     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
 352     qprint("seed is %u\n", rnd_seed);
 353     try = 0;
 354     do {
 355         init();
 356         if (try)
 357             qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
 358         qprint("placing capitals...\n");
 359         if (!drift())
 360             qprint("unstable drift\n");
 361         qprint("growing continents...\n");
 362         done = grow_continents();
 363         if (!done)
 364             continue;
 365         qprint("growing islands:");
 366         done = grow_islands();
 367     } while (!done && ++try < NUMTRIES);
 368     if (!done) {
 369         fprintf(stderr, "%s: world not large enough for this much land\n",
 370                 program_name);
 371         exit(1);
 372     }
 373     qprint("elevating land...\n");
 374     create_elevations();
 375
 376     qprint("writing to sectors file...\n");
 377     if (!write_newcap_script())
 378         exit(1);
 379     if (chdir(gamedir)) {
 380         fprintf(stderr, "%s: can't chdir to %s (%s)\n",
 381                 program_name, gamedir, strerror(errno));
 382         exit(1);
 383     }
 384     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
 385         exit(1);
 386     write_sects();
 387     if (!ef_close(EF_SECTOR))
 388         exit(1);
 389
 390     output();
 391     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
 392            outfile);
 393     exit(0);
 394 }
 395
 396 static void
 397 print_vars(void)
 398 {
 399     if (quiet)
 400         return;
 401     puts("Creating a planet with:\n");
 402     printf("%d continents\n", nc);
 403     printf("continent size: %d\n", sc);
 404     printf("number of islands: %d\n", ni);
 405     printf("average size of islands: %d\n", is);
 406     printf("spike: %d%%\n", sp);
 407     printf("%d%% of land is mountain (each continent will have %d mountains)\n",
 408            pm, (pm * sc) / 100);
 409     printf("minimum distance between continents: %d\n", di);
 410     printf("minimum distance from islands to continents: %d\n", id);
 411     printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
 412 }
 413
 414 static void
 415 help(char *complaint)
 416 {
 417     if (complaint)
 418         fprintf(stderr, "%s: %s\n", program_name, complaint);
 419     fprintf(stderr, "Try -h for help.\n");
 420 }
 421
 422 static void
 423 usage(void)
 424 {
 425     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
 426            "  -e CONFIG-FILE  configuration file\n"
 427            "                  (default %s)\n"
 428            "  -i              islands may merge\n"
 429            "  -q              quiet\n"
 430            "  -R SEED         seed for random number generator\n"
 431            "  -s SCRIPT       name of script to create (default %s)\n"
 432            "  -h              display this help and exit\n"
 433            "  -v              display version information and exit\n"
 434            "  NC              number of continents\n"
 435            "  SC              continent size\n"
 436            "  NI              number of islands (default NC)\n"
 437            "  IS              average island size (default SC/2)\n"
 438            "  SP              spike percentage: 0 = round, 100 = snake (default %d)\n"
 439            "  PM              percentage of land that is mountain (default %d)\n"
 440            "  DI              minimum distance between continents (default %d)\n"
 441            "  ID              minimum distance from islands to continents (default %d)\n",
 442            program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
 443            DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
 444 }
 445
 446 static void
 447 parse_args(int argc, char *argv[])
 448 {
 449     int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
 450
 451     if (argc < 2) {
 452         help("missing arguments");
 453         exit(1);
 454     }
 455     if (argc > 8) {
 456         help("too many arguments");
 457         exit(1);
 458     }
 459     nc = atoi(argv[0]);
 460     if (nc < 1) {
 461         fprintf(stderr, "%s: number of continents must be > 0\n",
 462                 program_name);
 463         exit(1);
 464     }
 465
 466     sc = atoi(argv[1]);
 467     if (sc < 2) {
 468         fprintf(stderr, "%s: size of continents must be > 1\n",
 469                 program_name);
 470         exit(1);
 471     }
 472
 473     ni = nc;
 474     is = sc / 2;
 475
 476     if (argc > 2)
 477         ni = atoi(argv[2]);
 478     if (ni < 0) {
 479         fprintf(stderr, "%s: number of islands must be >= 0\n",
 480                 program_name);
 481         exit(1);
 482     }
 483     if (ni % nc) {
 484         fprintf(stderr, "%s: number of islands must be a multiple of"
 485                 " the number of continents\n",
 486                 program_name);
 487         exit(1);
 488     }
 489
 490     if (argc > 3)
 491         is = atoi(argv[3]);
 492     if (is < 1) {
 493         fprintf(stderr, "%s: size of islands must be > 0\n",
 494                 program_name);
 495         exit(1);
 496     }
 497
 498     if (argc > 4)
 499         sp = atoi(argv[4]);
 500     if (sp < 0 || sp > 100) {
 501         fprintf(stderr,
 502                 "%s: spike percentage must be between 0 and 100\n",
 503                 program_name);
 504         exit(1);
 505     }
 506
 507     if (argc > 5)
 508         pm = atoi(argv[5]);
 509     if (pm < 0 || pm > 100) {
 510         fprintf(stderr,
 511                 "%s: mountain percentage must be between 0 and 100\n",
 512                 program_name);
 513         exit(1);
 514     }
 515
 516     if (argc > 6)
 517         di = atoi(argv[6]);
 518     if (di < 0) {
 519         fprintf(stderr, "%s: distance between continents must be >= 0\n",
 520                 program_name);
 521         exit(1);
 522     }
 523     if (di > dist_max) {
 524         fprintf(stderr, "%s: distance between continents too large\n",
 525                 program_name);
 526         exit(1);
 527     }
 528
 529     if (argc > 7)
 530         id = atoi(argv[7]);
 531     if (id < 0) {
 532         fprintf(stderr,
 533                 "%s: distance from islands to continents must be >= 0\n",
 534                 program_name);
 535         exit(1);
 536     }
 537     if (id > dist_max) {
 538         fprintf(stderr,
 539                 "%s: distance from islands to continents too large\n",
 540                 program_name);
 541         exit(1);
 542     }
 543 }
 544
 545 /****************************************************************************
 546   VARIABLE INITIALIZATION
 547 ****************************************************************************/
 548
 549 static void
 550 allocate_memory(void)
 551 {
 552     int i;
 553
 554     capx = calloc(nc, sizeof(int));
 555     capy = calloc(nc, sizeof(int));
 556     own = calloc(WORLD_X, sizeof(int *));
 557     adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
 558     xzone = malloc(WORLD_SZ() * sizeof(*xzone));
 559     seen = calloc(WORLD_SZ(), sizeof(*seen));
 560     closest = malloc(WORLD_SZ() * sizeof(*closest));
 561     distance = malloc(WORLD_SZ() * sizeof(*distance));
 562     bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
 563     elev = calloc(WORLD_X, sizeof(int *));
 564     for (i = 0; i < WORLD_X; ++i) {
 565         own[i] = calloc(WORLD_Y, sizeof(int));
 566         elev[i] = calloc(WORLD_Y, sizeof(int));
 567     }
 568     sectx = calloc(nc + ni, sizeof(int *));
 569     secty = calloc(nc + ni, sizeof(int *));
 570     sectc = calloc(nc + ni, sizeof(int *));
 571     isecs = calloc(nc + ni, sizeof(int));
 572     weight = calloc(MAX(sc, is * 2), sizeof(int));
 573     dsea = calloc(MAX(sc, is * 2), sizeof(int));
 574     dmoun = calloc(MAX(sc, is * 2), sizeof(int));
 575     for (i = 0; i < nc; ++i) {
 576         sectx[i] = calloc(sc, sizeof(int));
 577         secty[i] = calloc(sc, sizeof(int));
 578         sectc[i] = calloc(sc, sizeof(int));
 579     }
 580     for (i = nc; i < nc + ni; ++i) {
 581         sectx[i] = calloc(is * 2, sizeof(int));
 582         secty[i] = calloc(is * 2, sizeof(int));
 583         sectc[i] = calloc(is * 2, sizeof(int));
 584     }
 585
 586 }
 587
 588 static void
 589 init(void)
 590 {
 591     int i, j;
 592
 593     for (i = 0; i < WORLD_X; ++i) {
 594         for (j = 0; j < WORLD_Y; ++j) {
 595             own[i][j] = -1;
 596         }
 597     }
 598     memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
 599 }
 600
 601 /****************************************************************************
 602   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
 603 ****************************************************************************/
 604
 605 /*
 606  * How isolated is capital @j at @newx,@newy?
 607  * Return the distance to the closest other capital.
 608  */
 609 static int
 610 iso(int j, int newx, int newy)
 611 {
 612     int d = INT_MAX;
 613     int i, md;
 614
 615     for (i = 0; i < nc; ++i) {
 616         if (i == j)
 617             continue;
 618         md = mapdist(capx[i], capy[i], newx, newy);
 619         if (md < d)
 620             d = md;
 621     }
 622
 623     return d;
 624 }
 625
 626 /*
 627  * Drift the capitals
 628  * Return 1 for a stable drift, 0 for an unstable one.
 629  */
 630 static int
 631 drift(void)
 632 {
 633     int turns, i;
 634
 635     for (i = 0; i < nc; i++) {
 636         capy[i] = (2 * i) / WORLD_X;
 637         capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
 638         if (capy[i] >= WORLD_Y) {
 639             fprintf(stderr,
 640                     "%s: world not big enough for all the continents\n",
 641                     program_name);
 642             exit(1);
 643         }
 644     }
 645
 646     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 647         if (stable(turns))
 648             return 1;
 649         for (i = 0; i < nc; ++i)
 650             fl_move(i);
 651     }
 652     return 0;
 653 }
 654
 655 /*
 656  * Has the drift stabilized?
 657  * @turns is the number of turns so far.
 658  */
 659 static int
 660 stable(int turns)
 661 {
 662     static int mc[STABLE_CYCLE];
 663     int i, isod, d = 0, stab = 1;
 664
 665     if (!turns) {
 666         for (i = 0; i < STABLE_CYCLE; i++)
 667             mc[i] = i;
 668     }
 669
 670     if (turns <= DRIFT_BEFORE_CHECK)
 671         return 0;
 672
 673     for (i = 0; i < nc; ++i) {
 674         isod = iso(i, capx[i], capy[i]);
 675         if (isod > d)
 676             d = isod;
 677     }
 678
 679     for (i = 0; i < STABLE_CYCLE; ++i)
 680         if (d != mc[i])
 681             stab = 0;
 682
 683     mc[turns % STABLE_CYCLE] = d;
 684     return stab;
 685 }
 686
 687 /* This routine does the actual drifting
 688 */
 689
 690 static void
 691 fl_move(int j)
 692 {
 693     int dir, i, newx, newy;
 694
 695     dir = DIR_L + roll0(6);
 696     for (i = 0; i < 6; i++) {
 697         if (dir > DIR_LAST)
 698             dir -= 6;
 699         newx = new_x(capx[j] + diroff[dir][0]);
 700         newy = new_y(capy[j] + diroff[dir][1]);
 701         dir++;
 702         if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
 703             capx[j] = newx;
 704             capy[j] = newy;
 705             return;
 706         }
 707     }
 708 }
 709
 710 /****************************************************************************
 711   GROW THE CONTINENTS
 712 ****************************************************************************/
 713
 714 /* Look for a coastal sector of continent c
 715 */
 716
 717 static void
 718 find_coast(int c)
 719 {
 720     int i, dir, nx, ny;
 721
 722     for (i = 0; i < isecs[c]; ++i) {
 723         sectc[c][i] = 0;
 724         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 725             nx = new_x(sectx[c][i] + diroff[dir][0]);
 726             ny = new_y(secty[c][i] + diroff[dir][1]);
 727             if (own[nx][ny] == -1)
 728                 sectc[c][i] = 1;
 729         }
 730     }
 731 }
 732
 733 struct hexagon_iter {
 734     int dir, i, n;
 735 };
 736
 737 /*
 738  * Start iterating around @x0,@y0 at distance @d.
 739  * Set *x,*y to coordinates of the first sector.
 740  */
 741 static inline void
 742 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
 743               int *x, int *y)
 744 {
 745     *x = new_x(x0 - 2 * n);
 746     *y = y0;
 747     iter->dir = DIR_FIRST;
 748     iter->i = 0;
 749     iter->n = n;
 750 }
 751
 752 /*
 753  * Continue iteration started with hexagon_first().
 754  * Set *x,*y to coordinates of the next sector.
 755  * Return whether we're back at the first sector, i.e. iteration is
 756  * complete.
 757  */
 758 static inline int
 759 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
 760 {
 761     *x = new_x(*x + diroff[iter->dir][0]);
 762     *y = new_y(*y + diroff[iter->dir][1]);
 763     iter->i++;
 764     if (iter->i == iter->n) {
 765         iter->i = 0;
 766         iter->dir++;
 767     }
 768     return iter->dir <= DIR_LAST;
 769 }
 770
 771 /*
 772  * Is @x,@y in no exclusive zone other than perhaps @c's?
 773  */
 774 static int
 775 xzone_ok(int c, int x, int y)
 776 {
 777     int off = XYOFFSET(x, y);
 778
 779     return xzone[off] == c || xzone[off] == -1;
 780 }
 781
 782 /*
 783  * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
 784  */
 785 static void
 786 xzone_around_sector(int c, int x, int y, int dist)
 787 {
 788     int d, x1, y1, off;
 789     struct hexagon_iter hexit;
 790
 791     assert(xzone_ok(c, x, y));
 792
 793     xzone[XYOFFSET(x, y)] = c;
 794     for (d = 1; d <= dist; d++) {
 795         hexagon_first(&hexit, x, y, d, &x1, &y1);
 796         do {
 797             off = XYOFFSET(x1, y1);
 798             if (xzone[off] == -1)
 799                 xzone[off] = c;
 800             else if (xzone[off] != c)
 801                 xzone[off] = -2;
 802         } while (hexagon_next(&hexit, &x1, &y1));
 803     }
 804 }
 805
 806 /*
 807  * Add sectors within distance @dist to island @c's exclusive zone.
 808  */
 809 static void
 810 xzone_around_island(int c, int dist)
 811 {
 812     int i;
 813
 814     for (i = 0; i < isecs[c]; i++)
 815         xzone_around_sector(c, sectx[c][i], secty[c][i], dist);
 816 }
 817
 818 /*
 819  * Initialize exclusive zones around @n islands.
 820  */
 821 static void
 822 xzone_init(int n)
 823 {
 824     int i, c;
 825
 826     for (i = 0; i < WORLD_SZ(); i++)
 827         xzone[i] = -1;
 828
 829     for (c = 0; c < n; c++)
 830         xzone_around_island(c, id);
 831 }
 832
 833 /*
 834  * Initialize breadth-first search.
 835  */
 836 static void
 837 bfs_init(void)
 838 {
 839     int i;
 840
 841     for (i = 0; i < WORLD_SZ(); i++) {
 842         closest[i] = -1;
 843         distance[i] = USHRT_MAX;
 844     }
 845
 846     bfs_queue_head = bfs_queue_tail = 0;
 847 }
 848
 849 /*
 850  * Add sector @x,@y to the BFS queue.
 851  * It's closest to @c, with distance @dist.
 852  */
 853 static void
 854 bfs_enqueue(int c, int x, int y, int dist)
 855 {
 856     int off = XYOFFSET(x, y);
 857
 858     assert(dist < distance[off]);
 859     closest[off] = c;
 860     distance[off] = dist;
 861     bfs_queue[bfs_queue_tail] = off;
 862     bfs_queue_tail++;
 863     if (bfs_queue_tail >= WORLD_SZ())
 864         bfs_queue_tail = 0;
 865     assert(bfs_queue_tail != bfs_queue_head);
 866 }
 867
 868 /*
 869  * Search breadth-first until the queue is empty.
 870  */
 871 static void
 872 bfs_run_queue(void)
 873 {
 874     int off, dist, i, noff, nx, ny;
 875     coord x, y;
 876
 877     while (bfs_queue_head != bfs_queue_tail) {
 878         off = bfs_queue[bfs_queue_head];
 879         bfs_queue_head++;
 880         if (bfs_queue_head >= WORLD_SZ())
 881             bfs_queue_head = 0;
 882         dist = distance[off] + 1;
 883         sctoff2xy(&x, &y, off);
 884         for (i = DIR_FIRST; i <= DIR_LAST; i++) {
 885             nx = new_x(x + diroff[i][0]);
 886             ny = new_y(y + diroff[i][1]);
 887             noff = XYOFFSET(nx, ny);
 888             if (dist < distance[noff]) {
 889                 bfs_enqueue(closest[off], nx, ny, dist);
 890             } else if (distance[noff] == dist) {
 891                 if (closest[off] != closest[noff])
 892                     closest[noff] = (natid)-1;
 893             } else
 894                 assert(distance[noff] < dist);
 895         }
 896     }
 897 }
 898
 899 /*
 900  * Add island @c's coastal sectors to the BFS queue, with distance 0.
 901  */
 902 static void
 903 bfs_enqueue_island(int c)
 904 {
 905     int i;
 906
 907     for (i = 0; i < isecs[c]; i++) {
 908         if (sectc[c][i])
 909             bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
 910     }
 911 }
 912
 913 /*
 914  * Enqueue spheres of influence borders for breadth-first search.
 915  */
 916 static void
 917 bfs_enqueue_border(void)
 918 {
 919     int x, y, off, dir, nx, ny, noff;
 920
 921     for (y = 0; y < WORLD_Y; y++) {
 922         for (x = y % 2; x < WORLD_X; x += 2) {
 923             off = XYOFFSET(x, y);
 924             if (distance[off] <= id + 1)
 925                 continue;
 926             if (closest[off] == (natid)-1)
 927                 continue;
 928             for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 929                 nx = new_x(x + diroff[dir][0]);
 930                 ny = new_y(y + diroff[dir][1]);
 931                 noff = XYOFFSET(nx, ny);
 932                 if (closest[noff] != closest[off]) {
 933                     bfs_enqueue(closest[off], x, y, id + 1);
 934                     break;
 935                 }
 936             }
 937         }
 938     }
 939 }
 940
 941 /*
 942  * Compute spheres of influence
 943  * A continent's sphere of influence is the set of sectors closer to
 944  * it than to any other continent.
 945  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 946  * -1 if no single continent is closest.
 947  * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
 948  * closest coastal land sector and the distance to just outside the
 949  * sphere of influence plus @id.  For sea sectors within a continent's
 950  * sphere of influence, distance[off] - id is the distance to the
 951  * border of the area where additional islands can be placed.
 952  */
 953 static void
 954 init_spheres_of_influence(void)
 955 {
 956     int c;
 957
 958     bfs_init();
 959     for (c = 0; c < nc; c++)
 960         bfs_enqueue_island(c);
 961     bfs_run_queue();
 962     bfs_enqueue_border();
 963     bfs_run_queue();
 964 }
 965
 966 /*
 967  * Precompute distance to coast
 968  * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
 969  * land sector.
 970  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 971  * -1 if no single continent is closest.
 972  */
 973 static void
 974 init_distance_to_coast(void)
 975 {
 976     int c;
 977
 978     bfs_init();
 979     for (c = 0; c < nc + ni; c++)
 980         bfs_enqueue_island(c);
 981     bfs_run_queue();
 982 }
 983
 984 /*
 985  * Is @x,@y in the same sphere of influence as island @c?
 986  * Always true when @c is a continent.
 987  */
 988 static int
 989 is_in_sphere(int c, int x, int y)
 990 {
 991     return c < nc || closest[XYOFFSET(x, y)] == c % nc;
 992 }
 993
 994 /*
 995  * Can island @c grow at @x,@y?
 996  */
 997 static int
 998 can_grow_at(int c, int x, int y)
 999 {
1000     return own[x][y] == -1 && xzone_ok(c, x, y) && is_in_sphere(c, x, y);
1001 }
1002
1003 static void
1004 adj_land_update(int x, int y)
1005 {
1006     int is_land = own[x][y] != -1;
1007     int dir, nx, ny, noff;
1008
1009     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1010         nx = new_x(x + diroff[dir][0]);
1011         ny = new_y(y + diroff[dir][1]);
1012         noff = XYOFFSET(nx, ny);
1013         if (is_land)
1014             adj_land[noff] |= 1u << DIR_BACK(dir);
1015         else
1016             adj_land[noff] &= ~(1u << DIR_BACK(dir));
1017     }
1018 }
1019
1020 static void
1021 add_sector(int c, int x, int y)
1022 {
1023     assert(own[x][y] == -1);
1024     xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1025     sectx[c][isecs[c]] = x;
1026     secty[c][isecs[c]] = y;
1027     isecs[c]++;
1028     own[x][y] = c;
1029     adj_land_update(x, y);
1030 }
1031
1032 static int grow_weight(int c, int x, int y, int spike)
1033 {
1034     int n, b;
1035
1036     /*
1037      * #Land neighbors is #bits set in adj_land[].
1038      * Count them Brian Kernighan's way.
1039      */
1040     n = 0;
1041     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1042         n++;
1043     assert(n > 0 && n < 7);
1044
1045     if (spike)
1046         return (6 - n) * (6 - n);
1047
1048     return n * n * n;
1049 }
1050
1051 static int
1052 grow_one_sector(int c)
1053 {
1054     int spike = roll0(100) < sp;
1055     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1056
1057     assert(cur_seen < UINT_MAX);
1058     cur_seen++;
1059     wsum = 0;
1060     newx = newy = -1;
1061
1062     for (i = 0; i < isecs[c]; i++) {
1063         x = sectx[c][i];
1064         y = secty[c][i];
1065         off = XYOFFSET(x, y);
1066
1067         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1068             if (adj_land[off] & (1u << dir))
1069                 continue;
1070             nx = new_x(x + diroff[dir][0]);
1071             ny = new_y(y + diroff[dir][1]);
1072             noff = XYOFFSET(nx, ny);
1073             if (seen[noff] == cur_seen)
1074                 continue;
1075             assert(seen[noff] < cur_seen);
1076             seen[noff] = cur_seen;
1077             if (!can_grow_at(c, nx, ny))
1078                 continue;
1079             w = grow_weight(c, nx, ny, spike);
1080             assert(wsum < INT_MAX - w);
1081             wsum += w;
1082             if (roll0(wsum) < w) {
1083                 newx = nx;
1084                 newy = ny;
1085             }
1086         }
1087     }
1088
1089     if (!wsum)
1090         return 0;
1091
1092     add_sector(c, newx, newy);
1093     return 1;
1094 }
1095
1096 /*
1097  * Grow the continents.
1098  * Return 1 on success, 0 on error.
1099  */
1100 static int
1101 grow_continents(void)
1102 {
1103     int done = 1;
1104     int c, secs;
1105
1106     xzone_init(0);
1107
1108     for (c = 0; c < nc; ++c) {
1109         isecs[c] = 0;
1110         if (!can_grow_at(c, capx[c], capy[c])
1111             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1112             done = 0;
1113             continue;
1114         }
1115         add_sector(c, capx[c], capy[c]);
1116         add_sector(c, new_x(capx[c] + 2), capy[c]);
1117     }
1118
1119     if (!done) {
1120         qprint("No room for continents\n");
1121         return 0;
1122     }
1123
1124     for (secs = 2; secs < sc && done; secs++) {
1125         for (c = 0; c < nc; ++c) {
1126             if (!grow_one_sector(c))
1127                 done = 0;
1128         }
1129     }
1130
1131     for (c = 0; c < nc; ++c)
1132         find_coast(c);
1133
1134     if (!done)
1135         qprint("Only managed to grow %d out of %d sectors.\n",
1136                secs - 1, sc);
1137     return done;
1138 }
1139
1140 /****************************************************************************
1141   GROW THE ISLANDS
1142 ****************************************************************************/
1143
1144 /*
1145  * Place additional island @c's first sector.
1146  * Return 1 on success, 0 on error.
1147  */
1148 static int
1149 place_island(int c, int isiz)
1150 {
1151     int n, x, y, d, w, newx, newy;
1152
1153     n = 0;
1154
1155     for (y = 0; y < WORLD_Y; y++) {
1156         for (x = y % 2; x < WORLD_X; x += 2) {
1157             if (can_grow_at(c, x, y)) {
1158                 d = distance[XYOFFSET(x, y)];
1159                 assert(d > id);
1160                 w = (d - id) * (d - id);
1161                 n += MIN(w, (isiz + 2) / 3);
1162                 if (roll0(n) < w) {
1163                     newx = x;
1164                     newy = y;
1165                 }
1166             }
1167         }
1168     }
1169
1170     if (n)
1171         add_sector(c, newx, newy);
1172     return n;
1173 }
1174
1175 static int
1176 int_cmp(const void *a, const void *b)
1177 {
1178     return *(int *)b - *(int *)a;
1179 }
1180
1181 static int *
1182 size_islands(void)
1183 {
1184     int n = ni / nc;
1185     int *isiz = malloc(n * sizeof(*isiz));
1186     int r0, r1, i;
1187
1188     isiz[0] = n * is;
1189     r1 = roll0(is);
1190     for (i = 1; i < n; i++) {
1191         r0 = r1;
1192         r1 = roll0(is);
1193         isiz[i] = is + r1 - r0;
1194         isiz[0] -= isiz[i];
1195     }
1196
1197     qsort(isiz, n, sizeof(*isiz), int_cmp);
1198     return isiz;
1199 }
1200
1201 /*
1202  * Grow the additional islands.
1203  * Return 1 on success, 0 on error.
1204  */
1205 static int
1206 grow_islands(void)
1207 {
1208     int *island_size = size_islands();
1209     int xzone_valid = 0;
1210     int carry = 0;
1211     int i, j, c, done, secs, isiz, x, y;
1212
1213     init_spheres_of_influence();
1214
1215     for (i = 0; i < ni / nc; i++) {
1216         c = nc + i * nc;
1217
1218         if (!xzone_valid)
1219             xzone_init(c);
1220
1221         carry += island_size[i];
1222         isiz = MIN(2 * is, carry);
1223
1224         for (j = 0; j < nc; j++) {
1225             isecs[c + j] = 0;
1226             if (!place_island(c + j, isiz)) {
1227                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1228                 free(island_size);
1229                 return 0;
1230             }
1231         }
1232
1233         done = 1;
1234         for (secs = 1; secs < isiz && done; secs++) {
1235             for (j = 0; j < nc; j++) {
1236                 if (!grow_one_sector(c + j))
1237                     done = 0;
1238             }
1239         }
1240
1241         if (!done) {
1242             secs--;
1243             for (j = 0; j < nc; j++) {
1244                 if (isecs[c + j] != secs) {
1245                     isecs[c + j]--;
1246                     assert(isecs[c + j] == secs);
1247                     x = sectx[c + j][secs];
1248                     y = secty[c + j][secs];
1249                     own[x][y] = -1;
1250                     adj_land_update(x, y);
1251                 }
1252             }
1253             xzone_valid = 0;
1254         }
1255
1256         for (j = 0; j < nc; j++)
1257             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1258
1259         carry -= secs;
1260     }
1261
1262     free(island_size);
1263     qprint("\n");
1264
1265     if (carry)
1266         qprint("Only managed to grow %d out of %d island sectors.\n",
1267                is * ni - carry * nc, is * ni);
1268
1269     for (c = nc; c < nc + ni; c++)
1270         find_coast(c);
1271
1272     return 1;
1273 }
1274
1275 /****************************************************************************
1276   CREATE ELEVATIONS
1277 ****************************************************************************/
1278 static void
1279 create_elevations(void)
1280 {
1281     int i, j;
1282
1283     for (i = 0; i < WORLD_X; i++) {
1284         for (j = 0; j < WORLD_Y; j++)
1285             elev[i][j] = -INFINITE_ELEVATION;
1286     }
1287     init_distance_to_coast();
1288     elevate_land();
1289     elevate_sea();
1290 }
1291
1292 /* Generic function for finding the distance to the closest sea, land, or
1293    mountain
1294 */
1295 static int
1296 distance_to_what(int x, int y, int flag)
1297 {
1298     int d, px, py;
1299     struct hexagon_iter hexit;
1300
1301     for (d = 1; d < 5; ++d) {
1302         hexagon_first(&hexit, x, y, d, &px, &py);
1303         do {
1304             switch (flag) {
1305             case 0:             /* distance to sea */
1306                 if (own[px][py] == -1)
1307                     return d;
1308                 break;
1309             case 1:             /* distance to land */
1310                 if (own[px][py] != -1)
1311                     return d;
1312                 break;
1313             case 2:             /* distance to mountain */
1314                 if (elev[px][py] == INFINITE_ELEVATION)
1315                     return d;
1316                 break;
1317             }
1318         } while (hexagon_next(&hexit, &px, &py));
1319     }
1320     return d;
1321 }
1322
1323 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1324
1325 /* Decide where the mountains go
1326 */
1327 static void
1328 elevate_land(void)
1329 {
1330     int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1331     int highest, where, h, newk, dk;
1332
1333     for (c = 0; c < nc + ni; ++c) {
1334         total = 0;
1335         ns = isecs[c];
1336         nm = (pm * ns) / 100;
1337
1338 /* Place the mountains */
1339
1340         for (i = 0; i < ns; ++i) {
1341             off = XYOFFSET(sectx[c][i], secty[c][i]);
1342             dsea[i] = MIN(5, distance[off] + 1);
1343             weight[i] = (total += (dsea[i] * dsea[i]));
1344         }
1345
1346         for (k = nm, mountain_search = 0;
1347              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1348              ++mountain_search) {
1349             r = roll0(total);
1350             for (i = 0; i < ns; ++i) {
1351                 x = sectx[c][i];
1352                 y = secty[c][i];
1353                 if (r < weight[i] && elev[x][y] == -INFINITE_ELEVATION &&
1354                     (c >= nc ||
1355                      ((!(capx[c] == sectx[c][i] &&
1356                          capy[c] == secty[c][i])) &&
1357                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1358                          capy[c] == secty[c][i]))))) {
1359                     elev[x][y] = INFINITE_ELEVATION;
1360                     break;
1361                 }
1362             }
1363             --k;
1364         }
1365
1366 /* Elevate land that is not mountain and not capital */
1367
1368         for (i = 0; i < ns; ++i)
1369             dmoun[i] = distance_to_mountain();
1370         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1371           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1372           100 * INFINITE_ELEVATION;
1373         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1374             highest = 0;
1375             where = -1;
1376             for (i = 0; i < ns; ++i) {
1377                 x = sectx[c][i];
1378                 y = secty[c][i];
1379                 if (elev[x][y] == -INFINITE_ELEVATION &&
1380                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1381                                     capy[c] == secty[c][i])) &&
1382                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1383                                     capy[c] == secty[c][i]))))) {
1384                     h = 3 * (5 - dmoun[i]) + dsea[i];
1385                     assert(h > 0);
1386                     if (h > highest) {
1387                         highest = h;
1388                         where = i;
1389                     }
1390                 }
1391             }
1392             if (where == -1)
1393                 break;
1394             newk = k / 100;
1395             if (newk >= HILLMIN && newk < PLATMIN)
1396                 newk = PLATMIN;
1397             if (newk < LANDMIN)
1398                 newk = LANDMIN;
1399             elev[sectx[c][where]][secty[c][where]] = newk;
1400         }
1401
1402 /* Elevate the mountains and capitals */
1403
1404         for (i = 0; i < ns; ++i) {
1405             x = sectx[c][i];
1406             y = secty[c][i];
1407             if (elev[x][y] == INFINITE_ELEVATION) {
1408                 if (dsea[i] == 1)
1409                     elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1410                 else
1411                     elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1412                       roll0((256 - HIGHMIN) / 2);
1413             } else if (c < nc &&
1414                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1415                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1416                           capy[c] == secty[c][i]))))
1417                 elev[x][y] = PLATMIN;
1418         }
1419     }
1420 }
1421
1422 static void
1423 elevate_sea(void)
1424 {
1425     int x, y, off;
1426
1427     for (y = 0; y < WORLD_Y; ++y) {
1428         for (x = y % 2; x < WORLD_X; x += 2) {
1429             off = XYOFFSET(x, y);
1430             if (elev[x][y] == -INFINITE_ELEVATION)
1431                 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1432         }
1433     }
1434 }
1435
1436 static int
1437 elev_to_sct_type(int elevation)
1438 {
1439     if (elevation < LANDMIN)
1440         return SCT_WATER;
1441     if (elevation < HILLMIN)
1442         return SCT_RURAL;
1443     if (elevation < PLATMIN)
1444         return SCT_MOUNT;
1445     if (elevation < HIGHMIN)
1446         return SCT_RURAL;
1447     return SCT_MOUNT;
1448 }
1449
1450 /****************************************************************************
1451   ADD THE RESOURCES
1452 ****************************************************************************/
1453
1454 static int
1455 set_fert(int e)
1456 {
1457     int fert = 0;
1458     if (e < LANDMIN)
1459         fert = LANDMIN - e + 40;
1460     else if (e < FERT_MAX)
1461         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1462     if (fert > 100)
1463         fert = 100;
1464     return fert;
1465 }
1466
1467 static int
1468 set_oil(int e)
1469 {
1470     int oil = 0;
1471     if (e < LANDMIN)
1472         oil = (LANDMIN - e) * 2 + roll0(2);
1473     else if (e <= OIL_MAX)
1474         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1475     if (oil > 100)
1476         oil = 100;
1477     return oil;
1478 }
1479
1480 static int
1481 set_iron(int e)
1482 {
1483     int iron = 0;
1484     if (e >= IRON_MIN && e < HIGHMIN)
1485         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1486     if (iron > 100)
1487         iron = 100;
1488     return iron;
1489 }
1490
1491 static int
1492 set_gold(int e)
1493 {
1494     int gold = 0;
1495     if (e >= GOLD_MIN) {
1496         if (e < HIGHMIN)
1497             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1498         else
1499             gold = 100 - 20 * HIGHMIN / e;
1500     }
1501     if (gold > 100)
1502         gold = 100;
1503     return gold;
1504 }
1505
1506 static int
1507 set_uran(int e)
1508 {
1509     int uran = 0;
1510     if (e >= URAN_MIN && e < HIGHMIN)
1511         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1512     if (uran > 100)
1513         uran = 100;
1514     return uran;
1515 }
1516
1517 static void
1518 add_resources(struct sctstr *sct)
1519 {
1520     sct->sct_fertil = set_fert(sct->sct_elev);
1521     sct->sct_oil = set_oil(sct->sct_elev);
1522     sct->sct_min = set_iron(sct->sct_elev);
1523     sct->sct_gmin = set_gold(sct->sct_elev);
1524     sct->sct_uran = set_uran(sct->sct_elev);
1525 }
1526
1527 /****************************************************************************
1528   DESIGNATE THE SECTORS
1529 ****************************************************************************/
1530
1531 static void
1532 write_sects(void)
1533 {
1534     struct sctstr *sct;
1535     int x, y;
1536
1537     for (y = 0; y < WORLD_Y; y++) {
1538         for (x = y % 2; x < WORLD_X; x += 2) {
1539             sct = getsectp(x, y);
1540             sct->sct_elev = elev[x][y];
1541             sct->sct_type = elev_to_sct_type(elev[x][y]);
1542             sct->sct_newtype = sct->sct_type;
1543             sct->sct_dterr = own[sct->sct_x][y] + 1;
1544             add_resources(sct);
1545         }
1546     }
1547     set_coastal_flags();
1548 }
1549
1550 /****************************************************************************
1551   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1552 ****************************************************************************/
1553 static void
1554 output(void)
1555 {
1556     int sx, sy, x, y, c, type;
1557
1558     if (quiet == 0) {
1559         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1560             y = YNORM(sy);
1561             puts("");
1562             if (y % 2)
1563                 printf(" ");
1564             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1565                 x = XNORM(sx);
1566                 c = own[x][y];
1567                 type = elev_to_sct_type(elev[x][y]);
1568                 if (type == SCT_WATER)
1569                     printf(". ");
1570                 else if (type == SCT_MOUNT)
1571                     printf("^ ");
1572                 else if (c >= nc)
1573                     printf("%% ");
1574                 else {
1575                     assert(0 <= c && c < nc);
1576                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1577                         && y == capy[c])
1578                         printf("%c ", numletter[c % 62]);
1579                     else
1580                         printf("# ");
1581                 }
1582             }
1583         }
1584     }
1585 }
1586
1587 /*
1588  * Print a map to help visualize own[][].
1589  * This is for debugging.
1590  */
1591 void
1592 print_own_map(void)
1593 {
1594     int sx, sy, x, y;
1595
1596     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1597         y = YNORM(sy);
1598         printf("%4d ", sy);
1599         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1600             x = XNORM(sx);
1601             if ((x + y) & 1)
1602                 putchar(' ');
1603             else if (own[x][y] == -1)
1604                 putchar('.');
1605             else
1606                 putchar(numletter[own[x][y] % 62]);
1607         }
1608         putchar('\n');
1609     }
1610 }
1611
1612 /*
1613  * Print a map to help visualize elev[][].
1614  * This is for debugging.  It expects the terminal to understand
1615  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1616  */
1617 void
1618 print_elev_map(void)
1619 {
1620     int sx, sy, x, y, sat;
1621
1622     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1623         y = YNORM(sy);
1624         printf("%4d ", sy);
1625         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1626             x = XNORM(sx);
1627             if ((x + y) & 1)
1628                 putchar(' ');
1629             else if (!elev[x][y])
1630                 putchar(' ');
1631             else if (elev[x][y] < 0) {
1632                 sat = 256 + elev[x][y] * 2;
1633                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1634             } else if (elev[x][y] < HIGHMIN / 2) {
1635                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1636                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1637             } else if (elev[x][y] < HIGHMIN) {
1638                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1639                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1640             } else {
1641                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1642                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1643             }
1644         }
1645         putchar('\n');
1646     }
1647 }
1648
1649 /*
1650  * Print a map to help visualize xzone[].
1651  * This is for debugging.
1652  */
1653 void
1654 print_xzone_map(void)
1655 {
1656     int sx, sy, x, y, off;
1657
1658     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1659         y = YNORM(sy);
1660         printf("%4d ", sy);
1661         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1662             x = XNORM(sx);
1663             off = XYOFFSET(x, y);
1664             if ((x + y) & 1)
1665                 putchar(' ');
1666             else if (own[x][y] >= 0)
1667                 putchar('-');
1668             else if (xzone[off] >= 0)
1669                 putchar(numletter[xzone[off] % 62]);
1670             else {
1671                 assert(own[x][y] == -1);
1672                 putchar(xzone[off] == -1 ? '.' : '!');
1673             }
1674         }
1675         putchar('\n');
1676     }
1677 }
1678
1679 /*
1680  * Print a map to help visualize closest[].
1681  * This is for debugging.
1682  */
1683 void
1684 print_closest_map(void)
1685 {
1686     int sx, sy, x, y, off;
1687
1688     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1689         y = YNORM(sy);
1690         printf("%4d ", sy);
1691         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1692             x = XNORM(sx);
1693             off = XYOFFSET(x, y);
1694             if ((x + y) & 1)
1695                 putchar(' ');
1696             else if (closest[off] == (natid)-1)
1697                 putchar('.');
1698             else if (!distance[off]) {
1699                 assert(closest[off] == own[x][y]);
1700                 putchar('-');
1701             } else {
1702                 putchar(numletter[closest[off] % 62]);
1703             }
1704         }
1705         printf("\n");
1706     }
1707 }
1708
1709 void
1710 print_distance_map(void)
1711 {
1712     int sx, sy, x, y, off;
1713
1714     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1715         y = YNORM(sy);
1716         printf("%4d ", sy);
1717         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1718             x = XNORM(sx);
1719             off = XYOFFSET(x, y);
1720             if ((x + y) & 1)
1721                 putchar(' ');
1722             else if (closest[off] == (natid)-1)
1723                 putchar('.');
1724             else if (!distance[off]) {
1725                 assert(closest[off] == own[x][y]);
1726                 putchar('-');
1727             } else {
1728                 putchar(numletter[distance[off] % 62]);
1729             }
1730         }
1731         printf("\n");
1732     }
1733 }
1734
1735
1736 /***************************************************************************
1737   WRITE A SCRIPT FOR PLACING CAPITALS
1738 ****************************************************************************/
1739 static int
1740 write_newcap_script(void)
1741 {
1742     int c;
1743     FILE *script = fopen(outfile, "w");
1744
1745     if (!script) {
1746         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1747                 program_name, outfile, strerror(errno));
1748         return 0;
1749     }
1750
1751     for (c = 0; c < nc; ++c) {
1752         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1753         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1754     }
1755     fprintf(script, "add %d visitor visitor v\n", c + 1);
1756     fclose(script);
1757     return 1;
1758 }
1759
1760 static void
1761 qprint(const char *const fmt, ...)
1762 {
1763     va_list ap;
1764
1765     if (!quiet) {
1766         va_start(ap, fmt);
1767         vfprintf(stdout, fmt, ap);
1768         va_end(ap);
1769     }
1770 }
1771
1772 static void
1773 set_coastal_flags(void)
1774 {
1775     int i, j;
1776     struct sctstr *sp;
1777
1778     for (i = 0; i < nc + ni; ++i) {
1779         for (j = 0; j < isecs[i]; j++) {
1780             sp = getsectp(sectx[i][j], secty[i][j]);
1781             sp->sct_coastal = sectc[i][j];
1782         }
1783     }
1784 }