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