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