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