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