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