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 static int
 682 try_to_grow(int c, int newx, int newy, int extra_dist)
 683 {
 684     int d = (c < nc ? di : id) + extra_dist;
 685     int i, px, py;
 686     struct hexagon_iter hexit;
 687
 688     if (own[newx][newy] != -1)
 689         return 0;
 690
 691     for (i = 1; i <= d; ++i) {
 692         hexagon_first(&hexit, newx, newy, i, &px, &py);
 693         do {
 694             if (own[px][py] != -1 &&
 695                 own[px][py] != c &&
 696                 (DISTINCT_ISLANDS || own[px][py] < nc))
 697                 return 0;
 698         } while (hexagon_next(&hexit, &px, &py));
 699     }
 700     sectx[c][isecs[c]] = newx;
 701     secty[c][isecs[c]] = newy;
 702     isecs[c]++;
 703     own[newx][newy] = c;
 704     return 1;
 705 }
 706
 707 /* Move along the coast in a clockwise direction.
 708 */
 709
 710 static void
 711 next_coast(int c, int x, int y, int *xp, int *yp)
 712 {
 713     int i, nx, ny, wat = 0;
 714
 715     if (isecs[c] == 1) {
 716         *xp = x;
 717         *yp = y;
 718         return;
 719     }
 720
 721     for (i = 0; i < 12; ++i) {
 722         nx = new_x(x + dirx[i % 6]);
 723         ny = new_y(y + diry[i % 6]);
 724         if (own[nx][ny] == -1)
 725             wat = 1;
 726         if (wat && own[nx][ny] == c) {
 727             *xp = nx;
 728             *yp = ny;
 729             return;
 730         }
 731     }
 732 }
 733
 734 /* Choose a sector to grow from
 735 */
 736
 737 static int
 738 new_try(int c, int spike)
 739 {
 740     int secs = isecs[c];
 741     int i, starti;
 742
 743     if (secs == 1) {
 744         if (sectc[c][0])
 745             return 0;
 746     } else {
 747         i = starti = (spike && sectc[c][secs - 1]) ? secs - 1 : roll0(secs);
 748         do {
 749             if (sectc[c][i])
 750                 return i;
 751             i = (i + 1) % secs;
 752         } while (i != starti);
 753         assert(c >= nc);
 754         return -1;
 755     }
 756     return -1;
 757 }
 758
 759 /* Grow continent c by 1 sector
 760 */
 761
 762 static int
 763 grow_one_sector(int c)
 764 {
 765     int spike = roll0(100) < sp;
 766     int done, coast_search, try1, x, y, newx, newy, i, n, sx, sy;
 767
 768     if ((try1 = new_try(c, spike)) == -1)
 769         return 0;
 770     x = sx = sectx[c][try1];
 771     y = sy = secty[c][try1];
 772     coast_search = 0;
 773     done = 0;
 774     do {
 775         if (spike) {
 776             for (i = roll0(6), n = 0; n < 12 && !done; i = (i + 1) % 6, ++n) {
 777                 newx = new_x(x + dirx[i]);
 778                 newy = new_y(y + diry[i]);
 779                 if (n > 5 ||
 780                     (own[new_x(x+dirx[(i+5)%6])][new_y(y+diry[(i+5)%6])] == -1 &&
 781                      own[new_x(x+dirx[(i+1)%6])][new_y(y+diry[(i+1)%6])] == -1))
 782                     if (try_to_grow(c, newx, newy, 0))
 783                         done = 1;
 784             }
 785         } else
 786             for (i = roll0(6), n = 0; n < 6 && !done; i = (i + 1) % 6, ++n) {
 787                 newx = new_x(x + dirx[i]);
 788                 newy = new_y(y + diry[i]);
 789                 if (try_to_grow(c, newx, newy, 0))
 790                     done = 1;
 791             }
 792         next_coast(c, x, y, &x, &y);
 793         ++coast_search;
 794     } while (!done && coast_search < COAST_SEARCH_MAX &&
 795              (isecs[c] == 1 || x != sx || y != sy));
 796     return done;
 797 }
 798
 799 /*
 800  * Grow the continents.
 801  * Return 1 on success, 0 on error.
 802  */
 803 static int
 804 grow_continents(void)
 805 {
 806     int done = 1;
 807     int c, secs;
 808
 809     for (c = 0; c < nc; ++c) {
 810         isecs[c] = 0;
 811         if (!try_to_grow(c, capx[c], capy[c], 0)
 812             || !try_to_grow(c, new_x(capx[c] + 2), capy[c], 0)) {
 813             done = 0;
 814             continue;
 815         }
 816     }
 817
 818     if (!done) {
 819         qprint("No room for continents\n");
 820         return 0;
 821     }
 822
 823     for (secs = 2; secs < sc && done; secs++) {
 824         for (c = 0; c < nc; ++c) {
 825             find_coast(c);
 826             if (!grow_one_sector(c))
 827                 done = 0;
 828         }
 829     }
 830
 831     for (c = 0; c < nc; ++c)
 832         find_coast(c);
 833
 834     if (!done)
 835         qprint("Only managed to grow %d out of %d sectors.\n",
 836                secs - 1, sc);
 837     ctot = nc;
 838     return done;
 839 }
 840
 841 /****************************************************************************
 842   GROW THE ISLANDS
 843 ****************************************************************************/
 844
 845 /* Choose a place to start growing an island from
 846 */
 847 static int
 848 place_island(int c, int *xp, int *yp)
 849 {
 850     int d, sx, sy;
 851     int ssy = roll0(WORLD_Y);
 852     int ssx = new_x(roll0(WORLD_X / 2) * 2 + ssy % 2);
 853
 854     if (ssx > WORLD_X - 2)
 855         ssx = new_x(ssx + 2);
 856     for (d = di; d >= 0; --d) {
 857         sx = ssx;
 858         sy = ssy;
 859         *xp = new_x(sx + 2);
 860         for (*yp = sy; *xp != sx || *yp != sy; *xp += 2) {
 861             if (*xp >= WORLD_X) {
 862                 *yp = new_y(*yp + 1);
 863                 *xp = *yp % 2;
 864                 if (*xp == sx && *yp == sy)
 865                     break;
 866             }
 867             if (try_to_grow(c, *xp, *yp, d))
 868                 return 1;
 869         }
 870     }
 871     return 0;
 872 }
 873
 874 /* Grow all the islands
 875 */
 876
 877 static void
 878 grow_islands(void)
 879 {
 880     int stunted_islands = 0;
 881     int c, secs, x, y, isiz;
 882
 883     for (c = nc; c < nc + ni; ++c) {
 884         if (!place_island(c, &x, &y)) {
 885             qprint("\nNo room for island #%d", c - nc + 1);
 886             break;
 887         }
 888
 889         isiz = roll(is) + roll0(is);
 890         for (secs = 1; secs < isiz; secs++) {
 891             find_coast(c);
 892             if (!grow_one_sector(c)) {
 893                 stunted_islands++;
 894                 break;
 895             }
 896         }
 897
 898         find_coast(c);
 899         qprint(" %d(%d)", c - nc + 1, secs);
 900         ctot++;
 901     }
 902
 903     if (stunted_islands)
 904         qprint("\n%d stunted island%s",
 905                stunted_islands, splur(stunted_islands));
 906 }
 907
 908 /****************************************************************************
 909   CREATE ELEVATIONS
 910 ****************************************************************************/
 911 static void
 912 create_elevations(void)
 913 {
 914     int i, j;
 915
 916     for (i = 0; i < WORLD_X; i++) {
 917         for (j = 0; j < WORLD_Y; j++)
 918             elev[i][j] = -INFINITE_ELEVATION;
 919     }
 920     elevate_land();
 921     elevate_sea();
 922 }
 923
 924 /* Generic function for finding the distance to the closest sea, land, or
 925    mountain
 926 */
 927 static int
 928 distance_to_what(int x, int y, int flag)
 929 {
 930     int d, px, py;
 931     struct hexagon_iter hexit;
 932
 933     for (d = 1; d < 5; ++d) {
 934         hexagon_first(&hexit, x, y, d, &px, &py);
 935         do {
 936             switch (flag) {
 937             case 0:             /* distance to sea */
 938                 if (own[px][py] == -1)
 939                     return d;
 940                 break;
 941             case 1:             /* distance to land */
 942                 if (own[px][py] != -1)
 943                     return d;
 944                 break;
 945             case 2:             /* distance to mountain */
 946                 if (elev[px][py] == INFINITE_ELEVATION)
 947                     return d;
 948                 break;
 949             }
 950         } while (hexagon_next(&hexit, &px, &py));
 951     }
 952     return d;
 953 }
 954
 955 #define ELEV elev[sectx[c][i]][secty[c][i]]
 956 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
 957 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
 958
 959 /* Decide where the mountains go
 960 */
 961 static void
 962 elevate_land(void)
 963 {
 964     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
 965         r, dk;
 966
 967     for (c = 0; c < ctot; ++c) {
 968         total = 0;
 969         ns = isecs[c];
 970         nm = (pm * ns) / 100;
 971
 972 /* Place the mountains */
 973
 974         for (i = 0; i < ns; ++i) {
 975             dsea[i] = distance_to_sea();
 976             weight[i] = (total += (dsea[i] * dsea[i]));
 977         }
 978
 979         for (k = nm, mountain_search = 0;
 980              k && mountain_search < MOUNTAIN_SEARCH_MAX;
 981              ++mountain_search) {
 982             r = roll0(total);
 983             for (i = 0; i < ns; ++i)
 984                 if (r < weight[i] && ELEV == -INFINITE_ELEVATION &&
 985                     (c >= nc ||
 986                      ((!(capx[c] == sectx[c][i] &&
 987                          capy[c] == secty[c][i])) &&
 988                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
 989                          capy[c] == secty[c][i]))))) {
 990                     ELEV = INFINITE_ELEVATION;
 991                     break;
 992                 }
 993             --k;
 994         }
 995
 996 /* Elevate land that is not mountain and not capital */
 997
 998         for (i = 0; i < ns; ++i)
 999             dmoun[i] = distance_to_mountain();
1000         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
1001           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
1002           100 * INFINITE_ELEVATION;
1003         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
1004             highest = 0;
1005             where = -1;
1006             for (i = 0; i < ns; ++i) {
1007                 if (ELEV == -INFINITE_ELEVATION &&
1008                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
1009                                     capy[c] == secty[c][i])) &&
1010                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1011                                     capy[c] == secty[c][i]))))) {
1012                     h = 3 * (5 - dmoun[i]) + dsea[i];
1013                     assert(h > 0);
1014                     if (h > highest) {
1015                         highest = h;
1016                         where = i;
1017                     }
1018                 }
1019             }
1020             if (where == -1)
1021                 break;
1022             newk = k / 100;
1023             if (newk >= HILLMIN && newk < PLATMIN)
1024                 newk = PLATMIN;
1025             if (newk < LANDMIN)
1026                 newk = LANDMIN;
1027             elev[sectx[c][where]][secty[c][where]] = newk;
1028         }
1029
1030 /* Elevate the mountains and capitals */
1031
1032         for (i = 0; i < ns; ++i) {
1033             if (ELEV == INFINITE_ELEVATION) {
1034                 if (dsea[i] == 1)
1035                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1036                 else
1037                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1038                       roll0((256 - HIGHMIN) / 2);
1039             } else if (c < nc &&
1040                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1041                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1042                           capy[c] == secty[c][i]))))
1043                 ELEV = PLATMIN;
1044         }
1045     }
1046 }
1047
1048 #define distance_to_land() distance_to_what(x, y, 1)
1049
1050 static void
1051 elevate_sea(void)
1052 {
1053     int x, y;
1054
1055     for (y = 0; y < WORLD_Y; ++y) {
1056         for (x = y % 2; x < WORLD_X; x += 2) {
1057             if (elev[x][y] == -INFINITE_ELEVATION)
1058                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1059         }
1060     }
1061 }
1062
1063 static int
1064 elev_to_sct_type(int elevation)
1065 {
1066     if (elevation < LANDMIN)
1067         return SCT_WATER;
1068     if (elevation < HILLMIN)
1069         return SCT_RURAL;
1070     if (elevation < PLATMIN)
1071         return SCT_MOUNT;
1072     if (elevation < HIGHMIN)
1073         return SCT_RURAL;
1074     return SCT_MOUNT;
1075 }
1076
1077 /****************************************************************************
1078   ADD THE RESOURCES
1079 ****************************************************************************/
1080
1081 static int
1082 set_fert(int e)
1083 {
1084     int fert = 0;
1085     if (e < LANDMIN)
1086         fert = LANDMIN - e + 40;
1087     else if (e < FERT_MAX)
1088         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1089     if (fert > 100)
1090         fert = 100;
1091     return fert;
1092 }
1093
1094 static int
1095 set_oil(int e)
1096 {
1097     int oil = 0;
1098     if (e < LANDMIN)
1099         oil = (LANDMIN - e) * 2 + roll0(2);
1100     else if (e <= OIL_MAX)
1101         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1102     if (oil > 100)
1103         oil = 100;
1104     return oil;
1105 }
1106
1107 static int
1108 set_iron(int e)
1109 {
1110     int iron = 0;
1111     if (e >= IRON_MIN && e < HIGHMIN)
1112         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1113     if (iron > 100)
1114         iron = 100;
1115     return iron;
1116 }
1117
1118 static int
1119 set_gold(int e)
1120 {
1121     int gold = 0;
1122     if (e >= GOLD_MIN) {
1123         if (e < HIGHMIN)
1124             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1125         else
1126             gold = 100 - 20 * HIGHMIN / e;
1127     }
1128     if (gold > 100)
1129         gold = 100;
1130     return gold;
1131 }
1132
1133 static int
1134 set_uran(int e)
1135 {
1136     int uran = 0;
1137     if (e >= URAN_MIN && e < HIGHMIN)
1138         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1139     if (uran > 100)
1140         uran = 100;
1141     return uran;
1142 }
1143
1144 static void
1145 add_resources(struct sctstr *sct)
1146 {
1147     sct->sct_fertil = set_fert(sct->sct_elev);
1148     sct->sct_oil = set_oil(sct->sct_elev);
1149     sct->sct_min = set_iron(sct->sct_elev);
1150     sct->sct_gmin = set_gold(sct->sct_elev);
1151     sct->sct_uran = set_uran(sct->sct_elev);
1152 }
1153
1154 /****************************************************************************
1155   DESIGNATE THE SECTORS
1156 ****************************************************************************/
1157
1158 static void
1159 write_sects(void)
1160 {
1161     struct sctstr *sct;
1162     int x, y;
1163
1164     for (y = 0; y < WORLD_Y; y++) {
1165         for (x = y % 2; x < WORLD_X; x += 2) {
1166             sct = getsectp(x, y);
1167             sct->sct_elev = elev[x][y];
1168             sct->sct_type = elev_to_sct_type(elev[x][y]);
1169             sct->sct_newtype = sct->sct_type;
1170             sct->sct_dterr = own[sct->sct_x][y] + 1;
1171             add_resources(sct);
1172         }
1173     }
1174     set_coastal_flags();
1175 }
1176
1177 /****************************************************************************
1178   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1179 ****************************************************************************/
1180 static void
1181 output(void)
1182 {
1183     int sx, sy, x, y, c, type;
1184
1185     if (quiet == 0) {
1186         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1187             y = YNORM(sy);
1188             puts("");
1189             if (y % 2)
1190                 printf(" ");
1191             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1192                 x = XNORM(sx);
1193                 c = own[x][y];
1194                 type = elev_to_sct_type(elev[x][y]);
1195                 if (type == SCT_WATER)
1196                     printf(". ");
1197                 else if (type == SCT_MOUNT)
1198                     printf("^ ");
1199                 else if (c >= nc)
1200                     printf("%% ");
1201                 else {
1202                     assert(0 <= c && c < nc);
1203                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1204                         && y == capy[c])
1205                         printf("%c ", numletter[c % 62]);
1206                     else
1207                         printf("# ");
1208                 }
1209             }
1210         }
1211     }
1212 }
1213
1214 /*
1215  * Print a map to help visualize own[][].
1216  * This is for debugging.
1217  */
1218 void
1219 print_own_map(void)
1220 {
1221     int sx, sy, x, y;
1222
1223     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1224         y = YNORM(sy);
1225         printf("%4d ", sy);
1226         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1227             x = XNORM(sx);
1228             if ((x + y) & 1)
1229                 putchar(' ');
1230             else if (own[x][y] == -1)
1231                 putchar('.');
1232             else
1233                 putchar(numletter[own[x][y] % 62]);
1234         }
1235         putchar('\n');
1236     }
1237 }
1238
1239 /*
1240  * Print a map to help visualize elev[][].
1241  * This is for debugging.  It expects the terminal to understand
1242  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1243  */
1244 void
1245 print_elev_map(void)
1246 {
1247     int sx, sy, x, y, sat;
1248
1249     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1250         y = YNORM(sy);
1251         printf("%4d ", sy);
1252         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1253             x = XNORM(sx);
1254             if ((x + y) & 1)
1255                 putchar(' ');
1256             else if (!elev[x][y])
1257                 putchar(' ');
1258             else if (elev[x][y] < 0) {
1259                 sat = 256 + elev[x][y] * 2;
1260                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1261             } else if (elev[x][y] < HIGHMIN / 2) {
1262                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1263                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1264             } else if (elev[x][y] < HIGHMIN) {
1265                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1266                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1267             } else {
1268                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1269                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1270             }
1271         }
1272         putchar('\n');
1273     }
1274 }
1275
1276 /***************************************************************************
1277   WRITE A SCRIPT FOR PLACING CAPITALS
1278 ****************************************************************************/
1279 static int
1280 write_newcap_script(void)
1281 {
1282     int c;
1283     FILE *script = fopen(outfile, "w");
1284
1285     if (!script) {
1286         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1287                 program_name, outfile, strerror(errno));
1288         return 0;
1289     }
1290
1291     for (c = 0; c < nc; ++c) {
1292         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1293         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1294     }
1295     fprintf(script, "add %d visitor visitor v\n", c + 1);
1296     fclose(script);
1297     return 1;
1298 }
1299
1300 static void
1301 qprint(const char *const fmt, ...)
1302 {
1303     va_list ap;
1304
1305     if (!quiet) {
1306         va_start(ap, fmt);
1307         vfprintf(stdout, fmt, ap);
1308         va_end(ap);
1309     }
1310 }
1311
1312 static void
1313 set_coastal_flags(void)
1314 {
1315     int i, j;
1316     struct sctstr *sp;
1317
1318     for (i = 0; i < nc + ni; ++i) {
1319         for (j = 0; j < isecs[i]; j++) {
1320             sp = getsectp(sectx[i][j], secty[i][j]);
1321             sp->sct_coastal = sectc[i][j];
1322         }
1323     }
1324 }