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