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
1033 grow_weight(int c, int x, int y, int spike)
1034 {
1035     int n, b;
1036
1037     /*
1038      * #Land neighbors is #bits set in adj_land[].
1039      * Count them Brian Kernighan's way.
1040      */
1041     n = 0;
1042     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1043         n++;
1044     assert(n > 0 && n < 7);
1045
1046     if (spike)
1047         return (6 - n) * (6 - n);
1048
1049     return n * n * n;
1050 }
1051
1052 static int
1053 grow_one_sector(int c)
1054 {
1055     int spike = roll0(100) < sp;
1056     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1057
1058     assert(cur_seen < UINT_MAX);
1059     cur_seen++;
1060     wsum = 0;
1061     newx = newy = -1;
1062
1063     for (i = 0; i < isecs[c]; i++) {
1064         x = sectx[c][i];
1065         y = secty[c][i];
1066         off = XYOFFSET(x, y);
1067
1068         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1069             if (adj_land[off] & (1u << dir))
1070                 continue;
1071             nx = new_x(x + diroff[dir][0]);
1072             ny = new_y(y + diroff[dir][1]);
1073             noff = XYOFFSET(nx, ny);
1074             if (seen[noff] == cur_seen)
1075                 continue;
1076             assert(seen[noff] < cur_seen);
1077             seen[noff] = cur_seen;
1078             if (!can_grow_at(c, nx, ny))
1079                 continue;
1080             w = grow_weight(c, nx, ny, spike);
1081             assert(wsum < INT_MAX - w);
1082             wsum += w;
1083             if (roll0(wsum) < w) {
1084                 newx = nx;
1085                 newy = ny;
1086             }
1087         }
1088     }
1089
1090     if (!wsum)
1091         return 0;
1092
1093     add_sector(c, newx, newy);
1094     return 1;
1095 }
1096
1097 /*
1098  * Grow the continents.
1099  * Return 1 on success, 0 on error.
1100  */
1101 static int
1102 grow_continents(void)
1103 {
1104     int done = 1;
1105     int c, secs;
1106
1107     xzone_init(0);
1108
1109     for (c = 0; c < nc; ++c) {
1110         isecs[c] = 0;
1111         if (!can_grow_at(c, capx[c], capy[c])
1112             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
1113             done = 0;
1114             continue;
1115         }
1116         add_sector(c, capx[c], capy[c]);
1117         add_sector(c, new_x(capx[c] + 2), capy[c]);
1118     }
1119
1120     if (!done) {
1121         qprint("No room for continents\n");
1122         return 0;
1123     }
1124
1125     for (secs = 2; secs < sc && done; secs++) {
1126         for (c = 0; c < nc; ++c) {
1127             if (!grow_one_sector(c))
1128                 done = 0;
1129         }
1130     }
1131
1132     for (c = 0; c < nc; ++c)
1133         find_coast(c);
1134
1135     if (!done)
1136         qprint("Only managed to grow %d out of %d sectors.\n",
1137                secs - 1, sc);
1138     return done;
1139 }
1140
1141 /****************************************************************************
1142   GROW THE ISLANDS
1143 ****************************************************************************/
1144
1145 /*
1146  * Place additional island @c's first sector.
1147  * Return 1 on success, 0 on error.
1148  */
1149 static int
1150 place_island(int c, int isiz)
1151 {
1152     int n, x, y, d, w, newx, newy;
1153
1154     n = 0;
1155
1156     for (y = 0; y < WORLD_Y; y++) {
1157         for (x = y % 2; x < WORLD_X; x += 2) {
1158             if (can_grow_at(c, x, y)) {
1159                 d = distance[XYOFFSET(x, y)];
1160                 assert(d > id);
1161                 w = (d - id) * (d - id);
1162                 n += MIN(w, (isiz + 2) / 3);
1163                 if (roll0(n) < w) {
1164                     newx = x;
1165                     newy = y;
1166                 }
1167             }
1168         }
1169     }
1170
1171     if (n)
1172         add_sector(c, newx, newy);
1173     return n;
1174 }
1175
1176 static int
1177 int_cmp(const void *a, const void *b)
1178 {
1179     return *(int *)b - *(int *)a;
1180 }
1181
1182 static int *
1183 size_islands(void)
1184 {
1185     int n = ni / nc;
1186     int *isiz = malloc(n * sizeof(*isiz));
1187     int r0, r1, i;
1188
1189     isiz[0] = n * is;
1190     r1 = roll0(is);
1191     for (i = 1; i < n; i++) {
1192         r0 = r1;
1193         r1 = roll0(is);
1194         isiz[i] = is + r1 - r0;
1195         isiz[0] -= isiz[i];
1196     }
1197
1198     qsort(isiz, n, sizeof(*isiz), int_cmp);
1199     return isiz;
1200 }
1201
1202 /*
1203  * Grow the additional islands.
1204  * Return 1 on success, 0 on error.
1205  */
1206 static int
1207 grow_islands(void)
1208 {
1209     int *island_size = size_islands();
1210     int xzone_valid = 0;
1211     int carry = 0;
1212     int i, j, c, done, secs, isiz, x, y;
1213
1214     init_spheres_of_influence();
1215
1216     for (i = 0; i < ni / nc; i++) {
1217         c = nc + i * nc;
1218
1219         if (!xzone_valid)
1220             xzone_init(c);
1221
1222         carry += island_size[i];
1223         isiz = MIN(2 * is, carry);
1224
1225         for (j = 0; j < nc; j++) {
1226             isecs[c + j] = 0;
1227             if (!place_island(c + j, isiz)) {
1228                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1229                 free(island_size);
1230                 return 0;
1231             }
1232         }
1233
1234         done = 1;
1235         for (secs = 1; secs < isiz && done; secs++) {
1236             for (j = 0; j < nc; j++) {
1237                 if (!grow_one_sector(c + j))
1238                     done = 0;
1239             }
1240         }
1241
1242         if (!done) {
1243             secs--;
1244             for (j = 0; j < nc; j++) {
1245                 if (isecs[c + j] != secs) {
1246                     isecs[c + j]--;
1247                     assert(isecs[c + j] == secs);
1248                     x = sectx[c + j][secs];
1249                     y = secty[c + j][secs];
1250                     own[x][y] = -1;
1251                     adj_land_update(x, y);
1252                 }
1253             }
1254             xzone_valid = 0;
1255         }
1256
1257         for (j = 0; j < nc; j++)
1258             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1259
1260         carry -= secs;
1261     }
1262
1263     free(island_size);
1264     qprint("\n");
1265
1266     if (carry)
1267         qprint("Only managed to grow %d out of %d island sectors.\n",
1268                is * ni - carry * nc, is * ni);
1269
1270     for (c = nc; c < nc + ni; c++)
1271         find_coast(c);
1272
1273     return 1;
1274 }
1275
1276 /****************************************************************************
1277   CREATE ELEVATIONS
1278 ****************************************************************************/
1279 static void
1280 create_elevations(void)
1281 {
1282     int i, j;
1283
1284     for (i = 0; i < WORLD_X; i++) {
1285         for (j = 0; j < WORLD_Y; j++)
1286             elev[i][j] = -INFINITE_ELEVATION;
1287     }
1288     init_distance_to_coast();
1289     elevate_land();
1290     elevate_sea();
1291 }
1292
1293 /* Generic function for finding the distance to the closest sea, land, or
1294    mountain
1295 */
1296 static int
1297 distance_to_what(int x, int y, int flag)
1298 {
1299     int d, px, py;
1300     struct hexagon_iter hexit;
1301
1302     for (d = 1; d < 5; ++d) {
1303         hexagon_first(&hexit, x, y, d, &px, &py);
1304         do {
1305             switch (flag) {
1306             case 0:             /* distance to sea */
1307                 if (own[px][py] == -1)
1308                     return d;
1309                 break;
1310             case 1:             /* distance to land */
1311                 if (own[px][py] != -1)
1312                     return d;
1313                 break;
1314             case 2:             /* distance to mountain */
1315                 if (elev[px][py] == INFINITE_ELEVATION)
1316                     return d;
1317                 break;
1318             }
1319         } while (hexagon_next(&hexit, &px, &py));
1320     }
1321     return d;
1322 }
1323
1324 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1325
1326 /* Decide where the mountains go
1327 */
1328 static void
1329 elevate_land(void)
1330 {
1331     int i, off, mountain_search, k, c, total, ns, nm, r, x, y;
1332     int highest, where, h, newk, dk;
1333
1334     for (c = 0; c < nc + ni; ++c) {
1335         total = 0;
1336         ns = isecs[c];
1337         nm = (pm * ns) / 100;
1338
1339 /* Place the mountains */
1340
1341         for (i = 0; i < ns; ++i) {
1342             off = XYOFFSET(sectx[c][i], secty[c][i]);
1343             dsea[i] = MIN(5, distance[off] + 1);
1344             weight[i] = (total += (dsea[i] * dsea[i]));
1345         }
1346
1347         for (k = nm, mountain_search = 0;
1348              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1349              ++mountain_search) {
1350             r = roll0(total);
1351             for (i = 0; i < ns; ++i) {
1352                 x = sectx[c][i];
1353                 y = secty[c][i];
1354                 if (r < weight[i] && elev[x][y] == -INFINITE_ELEVATION &&
1355                     (c >= nc ||
1356                      ((!(capx[c] == sectx[c][i] &&
1357                          capy[c] == secty[c][i])) &&
1358                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1359                          capy[c] == secty[c][i]))))) {
1360                     elev[x][y] = INFINITE_ELEVATION;
1361                     break;
1362                 }
1363             }
1364             --k;
1365         }
1366
1367 /* Elevate land that is not mountain and not capital */
1368
1369         for (i = 0; i < ns; ++i)
1370             dmoun[i] = distance_to_mountain();
1371         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1372           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1373           100 * INFINITE_ELEVATION;
1374         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1375             highest = 0;
1376             where = -1;
1377             for (i = 0; i < ns; ++i) {
1378                 x = sectx[c][i];
1379                 y = secty[c][i];
1380                 if (elev[x][y] == -INFINITE_ELEVATION &&
1381                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1382                                     capy[c] == secty[c][i])) &&
1383                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1384                                     capy[c] == secty[c][i]))))) {
1385                     h = 3 * (5 - dmoun[i]) + dsea[i];
1386                     assert(h > 0);
1387                     if (h > highest) {
1388                         highest = h;
1389                         where = i;
1390                     }
1391                 }
1392             }
1393             if (where == -1)
1394                 break;
1395             newk = k / 100;
1396             if (newk >= HILLMIN && newk < PLATMIN)
1397                 newk = PLATMIN;
1398             if (newk < LANDMIN)
1399                 newk = LANDMIN;
1400             elev[sectx[c][where]][secty[c][where]] = newk;
1401         }
1402
1403 /* Elevate the mountains and capitals */
1404
1405         for (i = 0; i < ns; ++i) {
1406             x = sectx[c][i];
1407             y = secty[c][i];
1408             if (elev[x][y] == INFINITE_ELEVATION) {
1409                 if (dsea[i] == 1)
1410                     elev[x][y] = HILLMIN + roll0(PLATMIN - HILLMIN);
1411                 else
1412                     elev[x][y] = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1413                       roll0((256 - HIGHMIN) / 2);
1414             } else if (c < nc &&
1415                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1416                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1417                           capy[c] == secty[c][i]))))
1418                 elev[x][y] = PLATMIN;
1419         }
1420     }
1421 }
1422
1423 static void
1424 elevate_sea(void)
1425 {
1426     int x, y, off;
1427
1428     for (y = 0; y < WORLD_Y; ++y) {
1429         for (x = y % 2; x < WORLD_X; x += 2) {
1430             off = XYOFFSET(x, y);
1431             if (elev[x][y] == -INFINITE_ELEVATION)
1432                 elev[x][y] = -roll(MIN(5, distance[off]) * 20 + 27);
1433         }
1434     }
1435 }
1436
1437 static int
1438 elev_to_sct_type(int elevation)
1439 {
1440     if (elevation < LANDMIN)
1441         return SCT_WATER;
1442     if (elevation < HILLMIN)
1443         return SCT_RURAL;
1444     if (elevation < PLATMIN)
1445         return SCT_MOUNT;
1446     if (elevation < HIGHMIN)
1447         return SCT_RURAL;
1448     return SCT_MOUNT;
1449 }
1450
1451 /****************************************************************************
1452   ADD THE RESOURCES
1453 ****************************************************************************/
1454
1455 static int
1456 set_fert(int e)
1457 {
1458     int fert = 0;
1459     if (e < LANDMIN)
1460         fert = LANDMIN - e + 40;
1461     else if (e < FERT_MAX)
1462         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1463     if (fert > 100)
1464         fert = 100;
1465     return fert;
1466 }
1467
1468 static int
1469 set_oil(int e)
1470 {
1471     int oil = 0;
1472     if (e < LANDMIN)
1473         oil = (LANDMIN - e) * 2 + roll0(2);
1474     else if (e <= OIL_MAX)
1475         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1476     if (oil > 100)
1477         oil = 100;
1478     return oil;
1479 }
1480
1481 static int
1482 set_iron(int e)
1483 {
1484     int iron = 0;
1485     if (e >= IRON_MIN && e < HIGHMIN)
1486         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1487     if (iron > 100)
1488         iron = 100;
1489     return iron;
1490 }
1491
1492 static int
1493 set_gold(int e)
1494 {
1495     int gold = 0;
1496     if (e >= GOLD_MIN) {
1497         if (e < HIGHMIN)
1498             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1499         else
1500             gold = 100 - 20 * HIGHMIN / e;
1501     }
1502     if (gold > 100)
1503         gold = 100;
1504     return gold;
1505 }
1506
1507 static int
1508 set_uran(int e)
1509 {
1510     int uran = 0;
1511     if (e >= URAN_MIN && e < HIGHMIN)
1512         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1513     if (uran > 100)
1514         uran = 100;
1515     return uran;
1516 }
1517
1518 static void
1519 add_resources(struct sctstr *sct)
1520 {
1521     sct->sct_fertil = set_fert(sct->sct_elev);
1522     sct->sct_oil = set_oil(sct->sct_elev);
1523     sct->sct_min = set_iron(sct->sct_elev);
1524     sct->sct_gmin = set_gold(sct->sct_elev);
1525     sct->sct_uran = set_uran(sct->sct_elev);
1526 }
1527
1528 /****************************************************************************
1529   DESIGNATE THE SECTORS
1530 ****************************************************************************/
1531
1532 static void
1533 write_sects(void)
1534 {
1535     struct sctstr *sct;
1536     int x, y;
1537
1538     for (y = 0; y < WORLD_Y; y++) {
1539         for (x = y % 2; x < WORLD_X; x += 2) {
1540             sct = getsectp(x, y);
1541             sct->sct_elev = elev[x][y];
1542             sct->sct_type = elev_to_sct_type(elev[x][y]);
1543             sct->sct_newtype = sct->sct_type;
1544             sct->sct_dterr = own[sct->sct_x][y] + 1;
1545             add_resources(sct);
1546         }
1547     }
1548     set_coastal_flags();
1549 }
1550
1551 /****************************************************************************
1552   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1553 ****************************************************************************/
1554 static void
1555 output(void)
1556 {
1557     int sx, sy, x, y, c, type;
1558
1559     if (quiet == 0) {
1560         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1561             y = YNORM(sy);
1562             puts("");
1563             if (y % 2)
1564                 printf(" ");
1565             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1566                 x = XNORM(sx);
1567                 c = own[x][y];
1568                 type = elev_to_sct_type(elev[x][y]);
1569                 if (type == SCT_WATER)
1570                     printf(". ");
1571                 else if (type == SCT_MOUNT)
1572                     printf("^ ");
1573                 else if (c >= nc)
1574                     printf("%% ");
1575                 else {
1576                     assert(0 <= c && c < nc);
1577                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1578                         && y == capy[c])
1579                         printf("%c ", numletter[c % 62]);
1580                     else
1581                         printf("# ");
1582                 }
1583             }
1584         }
1585     }
1586 }
1587
1588 /*
1589  * Print a map to help visualize own[][].
1590  * This is for debugging.
1591  */
1592 void
1593 print_own_map(void)
1594 {
1595     int sx, sy, x, y;
1596
1597     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1598         y = YNORM(sy);
1599         printf("%4d ", sy);
1600         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1601             x = XNORM(sx);
1602             if ((x + y) & 1)
1603                 putchar(' ');
1604             else if (own[x][y] == -1)
1605                 putchar('.');
1606             else
1607                 putchar(numletter[own[x][y] % 62]);
1608         }
1609         putchar('\n');
1610     }
1611 }
1612
1613 /*
1614  * Print a map to help visualize elev[][].
1615  * This is for debugging.  It expects the terminal to understand
1616  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1617  */
1618 void
1619 print_elev_map(void)
1620 {
1621     int sx, sy, x, y, sat;
1622
1623     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1624         y = YNORM(sy);
1625         printf("%4d ", sy);
1626         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1627             x = XNORM(sx);
1628             if ((x + y) & 1)
1629                 putchar(' ');
1630             else if (!elev[x][y])
1631                 putchar(' ');
1632             else if (elev[x][y] < 0) {
1633                 sat = 256 + elev[x][y] * 2;
1634                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1635             } else if (elev[x][y] < HIGHMIN / 2) {
1636                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1637                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1638             } else if (elev[x][y] < HIGHMIN) {
1639                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1640                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1641             } else {
1642                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1643                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1644             }
1645         }
1646         putchar('\n');
1647     }
1648 }
1649
1650 /*
1651  * Print a map to help visualize xzone[].
1652  * This is for debugging.
1653  */
1654 void
1655 print_xzone_map(void)
1656 {
1657     int sx, sy, x, y, off;
1658
1659     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1660         y = YNORM(sy);
1661         printf("%4d ", sy);
1662         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1663             x = XNORM(sx);
1664             off = XYOFFSET(x, y);
1665             if ((x + y) & 1)
1666                 putchar(' ');
1667             else if (own[x][y] >= 0)
1668                 putchar('-');
1669             else if (xzone[off] >= 0)
1670                 putchar(numletter[xzone[off] % 62]);
1671             else {
1672                 assert(own[x][y] == -1);
1673                 putchar(xzone[off] == -1 ? '.' : '!');
1674             }
1675         }
1676         putchar('\n');
1677     }
1678 }
1679
1680 /*
1681  * Print a map to help visualize closest[].
1682  * This is for debugging.
1683  */
1684 void
1685 print_closest_map(void)
1686 {
1687     int sx, sy, x, y, off;
1688
1689     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1690         y = YNORM(sy);
1691         printf("%4d ", sy);
1692         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1693             x = XNORM(sx);
1694             off = XYOFFSET(x, y);
1695             if ((x + y) & 1)
1696                 putchar(' ');
1697             else if (closest[off] == (natid)-1)
1698                 putchar('.');
1699             else if (!distance[off]) {
1700                 assert(closest[off] == own[x][y]);
1701                 putchar('-');
1702             } else {
1703                 putchar(numletter[closest[off] % 62]);
1704             }
1705         }
1706         printf("\n");
1707     }
1708 }
1709
1710 void
1711 print_distance_map(void)
1712 {
1713     int sx, sy, x, y, off;
1714
1715     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1716         y = YNORM(sy);
1717         printf("%4d ", sy);
1718         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1719             x = XNORM(sx);
1720             off = XYOFFSET(x, y);
1721             if ((x + y) & 1)
1722                 putchar(' ');
1723             else if (closest[off] == (natid)-1)
1724                 putchar('.');
1725             else if (!distance[off]) {
1726                 assert(closest[off] == own[x][y]);
1727                 putchar('-');
1728             } else {
1729                 putchar(numletter[distance[off] % 62]);
1730             }
1731         }
1732         printf("\n");
1733     }
1734 }
1735
1736
1737 /***************************************************************************
1738   WRITE A SCRIPT FOR PLACING CAPITALS
1739 ****************************************************************************/
1740 static int
1741 write_newcap_script(void)
1742 {
1743     int c;
1744     FILE *script = fopen(outfile, "w");
1745
1746     if (!script) {
1747         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1748                 program_name, outfile, strerror(errno));
1749         return 0;
1750     }
1751
1752     for (c = 0; c < nc; ++c) {
1753         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1754         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1755     }
1756     fprintf(script, "add %d visitor visitor v\n", c + 1);
1757     fclose(script);
1758     return 1;
1759 }
1760
1761 static void
1762 qprint(const char *const fmt, ...)
1763 {
1764     va_list ap;
1765
1766     if (!quiet) {
1767         va_start(ap, fmt);
1768         vfprintf(stdout, fmt, ap);
1769         va_end(ap);
1770     }
1771 }
1772
1773 static void
1774 set_coastal_flags(void)
1775 {
1776     int i, j;
1777     struct sctstr *sp;
1778
1779     for (i = 0; i < nc + ni; ++i) {
1780         for (j = 0; j < isecs[i]; j++) {
1781             sp = getsectp(sectx[i][j], secty[i][j]);
1782             sp->sct_coastal = sectc[i][j];
1783         }
1784     }
1785 }