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