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