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