git.pond.sub.org Git - empserver/blob - src/util/fairland.c

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