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