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