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