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 grow_weight(int c, int x, int y, int spike)
 822 {
 823     int n, b;
 824
 825     /*
 826      * #Land neighbors is #bits set in adj_land[].
 827      * Count them Brian Kernighan's way.
 828      */
 829     n = 0;
 830     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
 831         n++;
 832     assert(n > 0 && n < 7);
 833
 834     if (spike)
 835         return (6 - n) * (6 - n);
 836
 837     return n * n * n;
 838 }
 839
 840 static int
 841 grow_one_sector(int c)
 842 {
 843     int spike = roll0(100) < sp;
 844     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
 845
 846     assert(cur_seen < UINT_MAX);
 847     cur_seen++;
 848     wsum = 0;
 849     newx = newy = -1;
 850
 851     for (i = 0; i < isecs[c]; i++) {
 852         x = sectx[c][i];
 853         y = secty[c][i];
 854         off = XYOFFSET(x, y);
 855
 856         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 857             if (adj_land[off] & (1u << dir))
 858                 continue;
 859             nx = new_x(x + diroff[dir][0]);
 860             ny = new_y(y + diroff[dir][1]);
 861             noff = XYOFFSET(nx, ny);
 862             if (seen[noff] == cur_seen)
 863                 continue;
 864             assert(seen[noff] < cur_seen);
 865             seen[noff] = cur_seen;
 866             if (!can_grow_at(c, nx, ny))
 867                 continue;
 868             w = grow_weight(c, nx, ny, spike);
 869             assert(wsum < INT_MAX - w);
 870             wsum += w;
 871             if (roll0(wsum) < w) {
 872                 newx = nx;
 873                 newy = ny;
 874             }
 875         }
 876     }
 877
 878     if (!wsum)
 879         return 0;
 880
 881     add_sector(c, newx, newy);
 882     return 1;
 883 }
 884
 885 /*
 886  * Grow the continents.
 887  * Return 1 on success, 0 on error.
 888  */
 889 static int
 890 grow_continents(void)
 891 {
 892     int done = 1;
 893     int c, secs;
 894
 895     ctot = 0;
 896     xzone_init(0);
 897
 898     for (c = 0; c < nc; ++c) {
 899         isecs[c] = 0;
 900         if (!can_grow_at(c, capx[c], capy[c])
 901             || !can_grow_at(c, new_x(capx[c] + 2), capy[c])) {
 902             done = 0;
 903             continue;
 904         }
 905         add_sector(c, capx[c], capy[c]);
 906         add_sector(c, new_x(capx[c] + 2), capy[c]);
 907     }
 908
 909     if (!done) {
 910         qprint("No room for continents\n");
 911         return 0;
 912     }
 913
 914     for (secs = 2; secs < sc && done; secs++) {
 915         for (c = 0; c < nc; ++c) {
 916             if (!grow_one_sector(c))
 917                 done = 0;
 918         }
 919     }
 920
 921     for (c = 0; c < nc; ++c)
 922         find_coast(c);
 923
 924     if (!done)
 925         qprint("Only managed to grow %d out of %d sectors.\n",
 926                secs - 1, sc);
 927     ctot = nc;
 928     return done;
 929 }
 930
 931 /****************************************************************************
 932   GROW THE ISLANDS
 933 ****************************************************************************/
 934
 935 /*
 936  * Place additional island @c's first sector.
 937  * Return 1 on success, 0 on error.
 938  */
 939 static int
 940 place_island(int c)
 941 {
 942     int n, x, y, newx, newy;
 943
 944     n = 0;
 945
 946     for (y = 0; y < WORLD_Y; y++) {
 947         for (x = y % 2; x < WORLD_X; x += 2) {
 948             if (can_grow_at(c, x, y)) {
 949                 n++;
 950                 if (!roll0(n)) {
 951                     newx = x;
 952                     newy = y;
 953                 }
 954             }
 955         }
 956     }
 957
 958     if (n)
 959         add_sector(c, newx, newy);
 960     return n;
 961 }
 962
 963 /* Grow all the islands
 964 */
 965
 966 static void
 967 grow_islands(void)
 968 {
 969     int stunted_islands = 0;
 970     int c, secs, isiz;
 971
 972     xzone_init(nc);
 973
 974     for (c = nc; c < nc + ni; ++c) {
 975         if (!place_island(c)) {
 976             qprint("\nNo room for island #%d", c - nc + 1);
 977             break;
 978         }
 979
 980         isiz = roll(is) + roll0(is);
 981         for (secs = 1; secs < isiz; secs++) {
 982             if (!grow_one_sector(c)) {
 983                 stunted_islands++;
 984                 break;
 985             }
 986         }
 987
 988         find_coast(c);
 989         qprint(" %d(%d)", c - nc + 1, secs);
 990         ctot++;
 991     }
 992
 993     if (stunted_islands)
 994         qprint("\n%d stunted island%s",
 995                stunted_islands, splur(stunted_islands));
 996 }
 997
 998 /****************************************************************************
 999   CREATE ELEVATIONS
1000 ****************************************************************************/
1001 static void
1002 create_elevations(void)
1003 {
1004     int i, j;
1005
1006     for (i = 0; i < WORLD_X; i++) {
1007         for (j = 0; j < WORLD_Y; j++)
1008             elev[i][j] = -INFINITE_ELEVATION;
1009     }
1010     elevate_land();
1011     elevate_sea();
1012 }
1013
1014 /* Generic function for finding the distance to the closest sea, land, or
1015    mountain
1016 */
1017 static int
1018 distance_to_what(int x, int y, int flag)
1019 {
1020     int d, px, py;
1021     struct hexagon_iter hexit;
1022
1023     for (d = 1; d < 5; ++d) {
1024         hexagon_first(&hexit, x, y, d, &px, &py);
1025         do {
1026             switch (flag) {
1027             case 0:             /* distance to sea */
1028                 if (own[px][py] == -1)
1029                     return d;
1030                 break;
1031             case 1:             /* distance to land */
1032                 if (own[px][py] != -1)
1033                     return d;
1034                 break;
1035             case 2:             /* distance to mountain */
1036                 if (elev[px][py] == INFINITE_ELEVATION)
1037                     return d;
1038                 break;
1039             }
1040         } while (hexagon_next(&hexit, &px, &py));
1041     }
1042     return d;
1043 }
1044
1045 #define ELEV elev[sectx[c][i]][secty[c][i]]
1046 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
1047 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
1048
1049 /* Decide where the mountains go
1050 */
1051 static void
1052 elevate_land(void)
1053 {
1054     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
1055         r, dk;
1056
1057     for (c = 0; c < ctot; ++c) {
1058         total = 0;
1059         ns = isecs[c];
1060         nm = (pm * ns) / 100;
1061
1062 /* Place the mountains */
1063
1064         for (i = 0; i < ns; ++i) {
1065             dsea[i] = distance_to_sea();
1066             weight[i] = (total += (dsea[i] * dsea[i]));
1067         }
1068
1069         for (k = nm, mountain_search = 0;
1070              k && mountain_search < MOUNTAIN_SEARCH_MAX;
1071              ++mountain_search) {
1072             r = roll0(total);
1073             for (i = 0; i < ns; ++i)
1074                 if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
1075                     (c >= nc ||
1076                      ((!(capx[c] == sectx[c][i] &&
1077                          capy[c] == secty[c][i])) &&
1078                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
1079                          capy[c] == secty[c][i]))))) {
1080                     ELEV = INFINITE_ELEVATION;
1081                     break;
1082                 }
1083             --k;
1084         }
1085
1086 /* Elevate land that is not mountain and not capital */
1087
1088         for (i = 0; i < ns; ++i)
1089             dmoun[i] = distance_to_mountain();
1090         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1091           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1092           100 * INFINITE_ELEVATION;
1093         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1094             highest = 0;
1095             where = -1;
1096             for (i = 0; i < ns; ++i) {
1097                 if (ELEV == -INFINITE_ELEVATION &&
1098                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1099                                     capy[c] == secty[c][i])) &&
1100                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1101                                     capy[c] == secty[c][i]))))) {
1102                     h = 3 * (5 - dmoun[i]) + dsea[i];
1103                     assert(h > 0);
1104                     if (h > highest) {
1105                         highest = h;
1106                         where = i;
1107                     }
1108                 }
1109             }
1110             if (where == -1)
1111                 break;
1112             newk = k / 100;
1113             if (newk >= HILLMIN && newk < PLATMIN)
1114                 newk = PLATMIN;
1115             if (newk < LANDMIN)
1116                 newk = LANDMIN;
1117             elev[sectx[c][where]][secty[c][where]] = newk;
1118         }
1119
1120 /* Elevate the mountains and capitals */
1121
1122         for (i = 0; i < ns; ++i) {
1123             if (ELEV == INFINITE_ELEVATION) {
1124                 if (dsea[i] == 1)
1125                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1126                 else
1127                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1128                       roll0((256 - HIGHMIN) / 2);
1129             } else if (c < nc &&
1130                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1131                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1132                           capy[c] == secty[c][i]))))
1133                 ELEV = PLATMIN;
1134         }
1135     }
1136 }
1137
1138 #define distance_to_land() distance_to_what(x, y, 1)
1139
1140 static void
1141 elevate_sea(void)
1142 {
1143     int x, y;
1144
1145     for (y = 0; y < WORLD_Y; ++y) {
1146         for (x = y % 2; x < WORLD_X; x += 2) {
1147             if (elev[x][y] == -INFINITE_ELEVATION)
1148                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1149         }
1150     }
1151 }
1152
1153 static int
1154 elev_to_sct_type(int elevation)
1155 {
1156     if (elevation < LANDMIN)
1157         return SCT_WATER;
1158     if (elevation < HILLMIN)
1159         return SCT_RURAL;
1160     if (elevation < PLATMIN)
1161         return SCT_MOUNT;
1162     if (elevation < HIGHMIN)
1163         return SCT_RURAL;
1164     return SCT_MOUNT;
1165 }
1166
1167 /****************************************************************************
1168   ADD THE RESOURCES
1169 ****************************************************************************/
1170
1171 static int
1172 set_fert(int e)
1173 {
1174     int fert = 0;
1175     if (e < LANDMIN)
1176         fert = LANDMIN - e + 40;
1177     else if (e < FERT_MAX)
1178         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1179     if (fert > 100)
1180         fert = 100;
1181     return fert;
1182 }
1183
1184 static int
1185 set_oil(int e)
1186 {
1187     int oil = 0;
1188     if (e < LANDMIN)
1189         oil = (LANDMIN - e) * 2 + roll0(2);
1190     else if (e <= OIL_MAX)
1191         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1192     if (oil > 100)
1193         oil = 100;
1194     return oil;
1195 }
1196
1197 static int
1198 set_iron(int e)
1199 {
1200     int iron = 0;
1201     if (e >= IRON_MIN && e < HIGHMIN)
1202         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1203     if (iron > 100)
1204         iron = 100;
1205     return iron;
1206 }
1207
1208 static int
1209 set_gold(int e)
1210 {
1211     int gold = 0;
1212     if (e >= GOLD_MIN) {
1213         if (e < HIGHMIN)
1214             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1215         else
1216             gold = 100 - 20 * HIGHMIN / e;
1217     }
1218     if (gold > 100)
1219         gold = 100;
1220     return gold;
1221 }
1222
1223 static int
1224 set_uran(int e)
1225 {
1226     int uran = 0;
1227     if (e >= URAN_MIN && e < HIGHMIN)
1228         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1229     if (uran > 100)
1230         uran = 100;
1231     return uran;
1232 }
1233
1234 static void
1235 add_resources(struct sctstr *sct)
1236 {
1237     sct->sct_fertil = set_fert(sct->sct_elev);
1238     sct->sct_oil = set_oil(sct->sct_elev);
1239     sct->sct_min = set_iron(sct->sct_elev);
1240     sct->sct_gmin = set_gold(sct->sct_elev);
1241     sct->sct_uran = set_uran(sct->sct_elev);
1242 }
1243
1244 /****************************************************************************
1245   DESIGNATE THE SECTORS
1246 ****************************************************************************/
1247
1248 static void
1249 write_sects(void)
1250 {
1251     struct sctstr *sct;
1252     int x, y;
1253
1254     for (y = 0; y < WORLD_Y; y++) {
1255         for (x = y % 2; x < WORLD_X; x += 2) {
1256             sct = getsectp(x, y);
1257             sct->sct_elev = elev[x][y];
1258             sct->sct_type = elev_to_sct_type(elev[x][y]);
1259             sct->sct_newtype = sct->sct_type;
1260             sct->sct_dterr = own[sct->sct_x][y] + 1;
1261             add_resources(sct);
1262         }
1263     }
1264     set_coastal_flags();
1265 }
1266
1267 /****************************************************************************
1268   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1269 ****************************************************************************/
1270 static void
1271 output(void)
1272 {
1273     int sx, sy, x, y, c, type;
1274
1275     if (quiet == 0) {
1276         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1277             y = YNORM(sy);
1278             puts("");
1279             if (y % 2)
1280                 printf(" ");
1281             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1282                 x = XNORM(sx);
1283                 c = own[x][y];
1284                 type = elev_to_sct_type(elev[x][y]);
1285                 if (type == SCT_WATER)
1286                     printf(". ");
1287                 else if (type == SCT_MOUNT)
1288                     printf("^ ");
1289                 else if (c >= nc)
1290                     printf("%% ");
1291                 else {
1292                     assert(0 <= c && c < nc);
1293                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1294                         && y == capy[c])
1295                         printf("%c ", numletter[c % 62]);
1296                     else
1297                         printf("# ");
1298                 }
1299             }
1300         }
1301     }
1302 }
1303
1304 /*
1305  * Print a map to help visualize own[][].
1306  * This is for debugging.
1307  */
1308 void
1309 print_own_map(void)
1310 {
1311     int sx, sy, x, y;
1312
1313     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1314         y = YNORM(sy);
1315         printf("%4d ", sy);
1316         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1317             x = XNORM(sx);
1318             if ((x + y) & 1)
1319                 putchar(' ');
1320             else if (own[x][y] == -1)
1321                 putchar('.');
1322             else
1323                 putchar(numletter[own[x][y] % 62]);
1324         }
1325         putchar('\n');
1326     }
1327 }
1328
1329 /*
1330  * Print a map to help visualize elev[][].
1331  * This is for debugging.  It expects the terminal to understand
1332  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1333  */
1334 void
1335 print_elev_map(void)
1336 {
1337     int sx, sy, x, y, sat;
1338
1339     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1340         y = YNORM(sy);
1341         printf("%4d ", sy);
1342         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1343             x = XNORM(sx);
1344             if ((x + y) & 1)
1345                 putchar(' ');
1346             else if (!elev[x][y])
1347                 putchar(' ');
1348             else if (elev[x][y] < 0) {
1349                 sat = 256 + elev[x][y] * 2;
1350                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1351             } else if (elev[x][y] < HIGHMIN / 2) {
1352                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1353                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1354             } else if (elev[x][y] < HIGHMIN) {
1355                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1356                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1357             } else {
1358                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1359                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1360             }
1361         }
1362         putchar('\n');
1363     }
1364 }
1365
1366 /*
1367  * Print a map to help visualize xzone[].
1368  * This is for debugging.
1369  */
1370 void
1371 print_xzone_map(void)
1372 {
1373     int sx, sy, x, y, off;
1374
1375     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1376         y = YNORM(sy);
1377         printf("%4d ", sy);
1378         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1379             x = XNORM(sx);
1380             off = XYOFFSET(x, y);
1381             if ((x + y) & 1)
1382                 putchar(' ');
1383             else if (own[x][y] >= 0)
1384                 putchar('-');
1385             else if (xzone[off] >= 0)
1386                 putchar(numletter[xzone[off] % 62]);
1387             else {
1388                 assert(own[x][y] == -1);
1389                 putchar(xzone[off] == -1 ? '.' : '!');
1390             }
1391         }
1392         putchar('\n');
1393     }
1394 }
1395
1396
1397 /***************************************************************************
1398   WRITE A SCRIPT FOR PLACING CAPITALS
1399 ****************************************************************************/
1400 static int
1401 write_newcap_script(void)
1402 {
1403     int c;
1404     FILE *script = fopen(outfile, "w");
1405
1406     if (!script) {
1407         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1408                 program_name, outfile, strerror(errno));
1409         return 0;
1410     }
1411
1412     for (c = 0; c < nc; ++c) {
1413         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1414         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1415     }
1416     fprintf(script, "add %d visitor visitor v\n", c + 1);
1417     fclose(script);
1418     return 1;
1419 }
1420
1421 static void
1422 qprint(const char *const fmt, ...)
1423 {
1424     va_list ap;
1425
1426     if (!quiet) {
1427         va_start(ap, fmt);
1428         vfprintf(stdout, fmt, ap);
1429         va_end(ap);
1430     }
1431 }
1432
1433 static void
1434 set_coastal_flags(void)
1435 {
1436     int i, j;
1437     struct sctstr *sp;
1438
1439     for (i = 0; i < nc + ni; ++i) {
1440         for (j = 0; j < isecs[i]; j++) {
1441             sp = getsectp(sectx[i][j], secty[i][j]);
1442             sp->sct_coastal = sectc[i][j];
1443         }
1444     }
1445 }