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