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