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