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 /* define ORE 1 to add resources, define ORE 0 if you want to use another
 113    program to add the resources */
 114 static int ORE = 1;
 115 static int quiet = 0;
 116
 117 /* If you don't specify these command line arguments, then these are the
 118    defaults */
 119 #define DEFAULT_SPIKE 10
 120 #define DEFAULT_MOUNTAIN 0
 121 #define DEFAULT_CONTDIST 2
 122 #define DEFAULT_ISLDIST 1
 123
 124 /* The following five numbers refer to elevation under which (in the case of
 125    fertility or oil) or over which (in the case of iron, gold, and uranium)
 126    sectors with that elevation will contain that resource.  Elevation ranges
 127    from 0 to 100 */
 128
 129 /* raise FERT_MAX for more fertility */
 130 #define FERT_MAX   56
 131
 132 /* raise OIL_MAX for more oil */
 133 #define OIL_MAX    33
 134
 135 /* lower IRON_MIN for more iron */
 136 #define IRON_MIN   22
 137
 138 /* lower GOLD_MIN for more gold */
 139 #define GOLD_MIN   36
 140
 141 /* lower URAN_MIN for more uranium */
 142 #define URAN_MIN   56
 143
 144 /* do not change these 4 defines */
 145 #define LANDMIN         1       /* plate altitude for normal land */
 146 #define HILLMIN         34      /* plate altitude for hills */
 147 #define PLATMIN         36      /* plate altitude for plateau */
 148 #define HIGHMIN         98      /* plate altitude for mountains */
 149
 150 static void qprint(const char * const fmt, ...)
 151     ATTRIBUTE((format (printf, 1, 2)));
 152
 153 #define DEFAULT_OUTFILE_NAME "newcap_script"
 154 static const char *outfile = DEFAULT_OUTFILE_NAME;
 155
 156 /* don't let the islands crash into each other.
 157    1 = don't merge, 0 = merge. */
 158 static int DISTINCT_ISLANDS = 1;
 159
 160 static char *program_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 nc, sc, di, sp, pm, ni, is, id; /* the 8 args to this program */
 185 static int *capx, *capy;        /* location of the nc capitals */
 186 static int *mc, mcc;            /* array and counter used for stability
 187                                    check when perturbing */
 188 static int spike;               /* are we spiking? */
 189 static int mind;                /* the final distance between capitals that
 190                                    we achieved */
 191 static int dirx[] = { -2, -1, 1, 2, 1, -1 }; /* gyujnb */
 192 static int diry[] = { 0, -1, -1, 0, 1, 1 };
 193
 194 static int **own;               /* owner of the sector.  -1 means water */
 195 static int **elev;              /* elevation of the sectors */
 196 static int **sectx, **secty;    /* the sectors for each continent */
 197 static int **sectc;             /* which sectors are on the coast? */
 198 static int *vector;             /* used for measuring distances */
 199 static int *weight;             /* used for placing mountains */
 200 static int *dsea, *dmoun;       /* the dist to the ocean and mountain */
 201 static int fl_status;           /* is anything wrong? */
 202 #define STATUS_NO_ROOM 1        /* there was no room to grow */
 203 #define NUMTRIES 10             /* keep trying to grow this many times */
 204
 205 static const char *numletter =
 206     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 207
 208 static void help(char *);
 209 static void usage(void);
 210 static void parse_args(int argc, char *argv[]);
 211 static void allocate_memory(void);
 212 static void init(void);
 213 static int drift(void);
 214 static void grow_continents(void);
 215 static void create_elevations(void);
 216 static void write_sects(void);
 217 static void output(void);
 218 static int write_newcap_script(void);
 219 static int stable(void);
 220 static void elevate_land(void);
 221 static void elevate_sea(void);
 222 static int map_symbol(int x, int y);
 223 static void set_coastal_flags(void);
 224
 225 static void print_vars(void);
 226 static void fl_move(int);
 227 static void grow_islands(void);
 228
 229 /* Debugging aids: */
 230 void print_own_map(void);
 231 void print_elev_map(void);
 232
 233 /****************************************************************************
 234   MAIN
 235 ****************************************************************************/
 236
 237 int
 238 main(int argc, char *argv[])
 239 {
 240     int opt;
 241     char *config_file = NULL;
 242     int i = 0;
 243     unsigned rnd_seed = 0;
 244     int seed_set = 0;
 245
 246     program_name = argv[0];
 247
 248     while ((opt = getopt(argc, argv, "e:hioqR:s:v")) != EOF) {
 249         switch (opt) {
 250         case 'e':
 251             config_file = optarg;
 252             break;
 253         case 'i':
 254             DISTINCT_ISLANDS = 0;
 255             break;
 256         case 'o':
 257             ORE = 0;
 258             break;
 259         case 'q':
 260             quiet = 1;
 261             break;
 262         case 'R':
 263             rnd_seed = strtoul(optarg, NULL, 10);
 264             seed_set = 1;
 265             break;
 266         case 's':
 267             outfile = optarg;
 268             break;
 269         case 'h':
 270             usage();
 271             exit(0);
 272         case 'v':
 273             printf("%s\n\n%s", version, legal);
 274             exit(0);
 275         default:
 276             help(NULL);
 277             exit(1);
 278         }
 279     }
 280     parse_args(argc - optind, argv + optind);
 281
 282     if (!seed_set)
 283         rnd_seed = pick_seed();
 284     seed_prng(rnd_seed);
 285     empfile_init();
 286     if (emp_config(config_file) < 0)
 287         exit(1);
 288     empfile_fixup();
 289
 290     allocate_memory();
 291     print_vars();
 292
 293     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
 294     qprint("seed is %u\n", rnd_seed);
 295     do {
 296         init();
 297         if (i)
 298             qprint("\ntry #%d (out of %d)...\n", i + 1, NUMTRIES);
 299         qprint("placing capitals...\n");
 300         if (!drift())
 301             qprint("fairland: unstable drift -- try increasing DRIFT_MAX\n");
 302         qprint("growing continents...\n");
 303         grow_continents();
 304     } while (fl_status && ++i < NUMTRIES);
 305     if (fl_status) {
 306         fputs("ERROR: World not large enough to hold continents\n",
 307               stderr);
 308         exit(1);
 309     }
 310     qprint("growing islands:");
 311     grow_islands();
 312     qprint("\nelevating land...\n");
 313     create_elevations();
 314     qprint("designating sectors...\n");
 315     if (ORE)
 316         qprint("adding resources...\n");
 317     if (!write_newcap_script())
 318         exit(1);
 319
 320     if (chdir(gamedir)) {
 321         fprintf(stderr, "Can't chdir to %s (%s)\n", gamedir, strerror(errno));
 322         exit(EXIT_FAILURE);
 323     }
 324     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
 325         exit(1);
 326     write_sects();
 327     qprint("writing to sectors file...\n");
 328     if (!ef_close(EF_SECTOR))
 329         exit(1);
 330
 331     output();
 332     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
 333            outfile);
 334     if (!ORE)
 335         qprint("\t*** Resources have not been added ***\n");
 336     exit(0);
 337 }
 338
 339 static void
 340 print_vars(void)
 341 {
 342     if (quiet)
 343         return;
 344     puts("Creating a planet with:\n");
 345     printf("%d continents\n", nc);
 346     printf("continent size: %d\n", sc);
 347     printf("number of islands: %d\n", ni);
 348     printf("average size of islands: %d\n", is);
 349     printf("spike: %d%%\n", sp);
 350     printf("%d%% of land is mountain (each continent will have %d mountains)\n",
 351            pm, (pm * sc) / 100);
 352     printf("minimum distance between continents: %d\n", di);
 353     printf("minimum distance from islands to continents: %d\n", id);
 354     printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
 355 }
 356
 357 static int
 358 my_sqrt(int n)
 359 {
 360     int i;
 361
 362     for (i = 1; i * i < n * 10000; ++i) ;
 363     return (i + 50) / 100;
 364 }
 365
 366 /****************************************************************************
 367   PARSE COMMAND LINE ARGUMENTS
 368 ****************************************************************************/
 369
 370 static void
 371 help(char *complaint)
 372 {
 373     if (complaint)
 374         fprintf(stderr, "%s: %s\n", program_name, complaint);
 375     fprintf(stderr, "Try -h for help.\n");
 376 }
 377
 378 static void
 379 usage(void)
 380 {
 381     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
 382            "  -e CONFIG-FILE  configuration file\n"
 383            "                  (default %s)\n"
 384            "  -i              islands may merge\n"
 385            "  -o              don't set resources\n"
 386            "  -q              quiet\n"
 387            "  -R SEED         seed for random number generator\n"
 388            "  -s SCRIPT       name of script to create (default %s)\n"
 389            "  -h              display this help and exit\n"
 390            "  -v              display version information and exit\n"
 391            "  NC              number of continents\n"
 392            "  SC              continent size\n"
 393            "  NI              number of islands (default NC)\n"
 394            "  IS              average island size (default SC/2)\n"
 395            "  SP              spike percentage: 0 = round, 100 = snake (default %d)\n"
 396            "  PM              percentage of land that is mountain (default %d)\n"
 397            "  DI              minimum distance between continents (default %d)\n"
 398            "  ID              minimum distance from islands to continents (default %d)\n",
 399            program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
 400            DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
 401 }
 402
 403 static void
 404 parse_args(int argc, char *argv[])
 405 {
 406     if (argc < 2) {
 407         help("missing arguments");
 408         exit(1);
 409     }
 410     if (argc > 8) {
 411         help("too many arguments");
 412         exit(1);
 413     }
 414     nc = atoi(argv[0]);
 415     if (nc < 1) {
 416         puts("fairland: error -- number of continents must be > 0");
 417         exit(1);
 418     }
 419
 420     sc = atoi(argv[1]);
 421     if (sc < 1) {
 422         puts("fairland: error -- size of continents must be > 0");
 423         exit(1);
 424     }
 425
 426     if (argc > 2)
 427         ni = atoi(argv[2]);
 428     else
 429         ni = nc;
 430
 431     if (argc > 3)
 432         is = atoi(argv[3]);
 433     else
 434         is = sc / 2;
 435     if (is < 1)
 436         is = 1;
 437
 438     if (argc > 4)
 439         sp = atoi(argv[4]);
 440     else
 441         sp = DEFAULT_SPIKE;
 442     sp = LIMIT_TO(sp, 0, 100);
 443
 444     if (argc > 5)
 445         pm = atoi(argv[5]);
 446     else
 447         pm = DEFAULT_MOUNTAIN;
 448     if (pm < 0)
 449         pm = 0;
 450
 451     if (argc > 6)
 452         di = atoi(argv[6]);
 453     else
 454         di = DEFAULT_CONTDIST;
 455
 456     if (di < 0) {
 457         puts("fairland: error -- distance between continents must be >= 0");
 458         exit(1);
 459     }
 460     if (di > WORLD_X / 2 || di > WORLD_Y / 2) {
 461         puts("fairland: error -- distance between continents too large");
 462         exit(1);
 463     }
 464
 465     if (argc > 7)
 466         id = atoi(argv[7]);
 467     else
 468         id = DEFAULT_ISLDIST;
 469     if (id < 0) {
 470         puts("fairland: error -- distance from islands to continents must be >= 0");
 471         exit(1);
 472     }
 473     if (id > WORLD_X || id > WORLD_Y) {
 474         puts("fairland: error -- distance from islands to continents too large");
 475         exit(1);
 476     }
 477     if (nc * sc + nc * my_sqrt(sc) * 2 * (di + 1) > WORLD_X * WORLD_Y) {
 478         puts("fairland: warning -- world might be too small to fit continents.");
 479         puts("arguments should satisfy:");
 480         puts("nc*sc*sc + nc*sqrt(sc)*2*(di+1) < WORLD_X * WORLD_Y");
 481     }
 482 }
 483
 484 /****************************************************************************
 485   VARIABLE INITIALIZATION
 486 ****************************************************************************/
 487
 488 static void
 489 allocate_memory(void)
 490 {
 491     int i;
 492
 493     capx = calloc(nc, sizeof(int));
 494     capy = calloc(nc, sizeof(int));
 495     vector = calloc(WORLD_X + WORLD_Y, sizeof(int));
 496     mc = calloc(STABLE_CYCLE, sizeof(int));
 497     own = calloc(WORLD_X, sizeof(int *));
 498     elev = calloc(WORLD_X, sizeof(int *));
 499     for (i = 0; i < WORLD_X; ++i) {
 500         own[i] = calloc(WORLD_Y, sizeof(int));
 501         elev[i] = calloc(WORLD_Y, sizeof(int));
 502     }
 503     sectx = calloc(nc + ni, sizeof(int *));
 504     secty = calloc(nc + ni, sizeof(int *));
 505     sectc = calloc(nc + ni, sizeof(int *));
 506     isecs = calloc(nc + ni, sizeof(int));
 507     weight = calloc(MAX(sc, is * 2), sizeof(int));
 508     dsea = calloc(MAX(sc, is * 2), sizeof(int));
 509     dmoun = calloc(MAX(sc, is * 2), sizeof(int));
 510     for (i = 0; i < nc; ++i) {
 511         sectx[i] = calloc(sc, sizeof(int));
 512         secty[i] = calloc(sc, sizeof(int));
 513         sectc[i] = calloc(sc, sizeof(int));
 514     }
 515     for (i = nc; i < nc + ni; ++i) {
 516         sectx[i] = calloc(is * 2, sizeof(int));
 517         secty[i] = calloc(is * 2, sizeof(int));
 518         sectc[i] = calloc(is * 2, sizeof(int));
 519     }
 520
 521 }
 522
 523 static void
 524 init(void)
 525 {
 526     int i, j, xx = 0, yy = 0;
 527
 528     mcc = 0;
 529     fl_status = 0;
 530
 531     for (i = 0; i < WORLD_X; ++i) {
 532         for (j = 0; j < WORLD_Y; ++j) {
 533             own[i][j] = -1;
 534             elev[i][j] = -INFINITY;
 535         }
 536     }
 537
 538     for (i = 0; i < nc; ++i) {
 539         if (xx >= WORLD_X) {
 540             ++yy;
 541             xx = yy % 2;
 542             if (yy == WORLD_Y) {
 543                 puts("fairland error: world not big enough for all the continents.\n");
 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         qprint("fairland: error -- continent %c had no room to grow!\n",
 792                numletter[c % 62]);
 793         fl_status |= STATUS_NO_ROOM;
 794     }
 795     return done;
 796 }
 797
 798 /* Grow all the continents
 799 */
 800 static void
 801 grow_continents(void)
 802 {
 803     int c;
 804
 805     for (c = 0; c < nc; ++c) {
 806         sectx[c][0] = capx[c];
 807         secty[c][0] = capy[c];
 808         own[sectx[c][0]][secty[c][0]] = c;
 809         sectx[c][1] = new_x(capx[c] + 2);
 810         secty[c][1] = capy[c];
 811         own[sectx[c][1]][secty[c][1]] = c;
 812     }
 813
 814     for (secs = 2; secs < sc && !fl_status; ++secs) {
 815         for (c = 0; c < nc; ++c) {
 816             find_coast(c);
 817             grow_one_sector(c);
 818         }
 819     }
 820     for (c = 0; c < nc; ++c)
 821         find_coast(c);
 822
 823     if (fl_status)
 824         qprint("Only managed to grow %d out of %d sectors.\n", secs, sc);
 825     ctot = nc;
 826 }
 827
 828 /****************************************************************************
 829   GROW THE ISLANDS
 830 ****************************************************************************/
 831
 832 /* Choose a place to start growing an island from
 833 */
 834 static int
 835 place_island(int c, int *xp, int *yp)
 836 {
 837     int d, sx, sy;
 838     int ssy = roll0(WORLD_Y);
 839     int ssx = new_x(roll0(WORLD_X / 2) * 2 + ssy % 2);
 840
 841     if (ssx > WORLD_X - 2)
 842         ssx = new_x(ssx + 2);
 843     for (d = di + id; d >= id; --d) {
 844         sx = ssx;
 845         sy = ssy;
 846         *xp = new_x(sx + 2);
 847         for (*yp = sy; *xp != sx || *yp != sy; *xp += 2) {
 848             if (*xp >= WORLD_X) {
 849                 *yp = new_y(*yp + 1);
 850                 *xp = *yp % 2;
 851                 if (*xp == sx && *yp == sy)
 852                     break;
 853             }
 854             if (own[*xp][*yp] == -1 && try_to_grow(c, *xp, *yp, d))
 855                 return 1;
 856         }
 857     }
 858     return 0;
 859 }
 860
 861 /* Grow all the islands
 862 */
 863
 864 static void
 865 grow_islands(void)
 866 {
 867     int c, x, y, isiz;
 868
 869     for (c = nc; c < nc + ni; ++c) {
 870         secs = 0;
 871         if (!place_island(c, &x, &y))
 872             return;
 873         isiz = roll(is) + roll0(is);
 874         do {
 875             ++secs;
 876             find_coast(c);
 877         } while (secs < isiz && grow_one_sector(c));
 878         find_coast(c);
 879         qprint(" %d(%d)", c - nc + 1, secs);
 880         isecs[c] = secs;
 881         ctot++;
 882     }
 883 }
 884
 885 /****************************************************************************
 886   CREATE ELEVATIONS
 887 ****************************************************************************/
 888 static void
 889 create_elevations(void)
 890 {
 891     elevate_land();
 892     elevate_sea();
 893 }
 894
 895 /* Generic function for finding the distance to the closest sea, land, or
 896    mountain
 897 */
 898 static int
 899 distance_to_what(int x, int y, int flag)
 900 {
 901     int j, d, px, py;
 902
 903     for (d = 1; d < 5; ++d) {
 904         for (j = 0; j < d; ++j)
 905             vector[j] = 0;
 906         do {
 907             px = x;
 908             py = y;
 909             for (j = 0; j < d; ++j) {
 910                 px = new_x(px + dirx[vector[j]]);
 911                 py = new_y(py + diry[vector[j]]);
 912             }
 913             switch (flag) {
 914             case 0:             /* distance to sea */
 915                 if (own[px][py] == -1)
 916                     return d;
 917                 break;
 918             case 1:             /* distance to land */
 919                 if (own[px][py] != -1)
 920                     return d;
 921                 break;
 922             case 2:             /* distance to mountain */
 923                 if (elev[px][py] == INFINITY)
 924                     return d;
 925                 break;
 926             }
 927         } while (next_vector(d));
 928     }
 929     return d;
 930 }
 931
 932 #define ELEV elev[sectx[c][i]][secty[c][i]]
 933 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
 934 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
 935
 936 /* Decide where the mountains go
 937 */
 938 static void
 939 elevate_land(void)
 940 {
 941     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
 942         r, dk;
 943
 944     for (c = 0; c < ctot; ++c) {
 945         total = 0;
 946         ns = (c < nc) ? sc : isecs[c];
 947         nm = (pm * ns) / 100;
 948
 949 /* Place the mountains */
 950
 951         for (i = 0; i < ns; ++i) {
 952             dsea[i] = distance_to_sea();
 953             weight[i] = (total += (dsea[i] * dsea[i]));
 954         }
 955
 956         for (k = nm, mountain_search = 0;
 957              k && mountain_search < MOUNTAIN_SEARCH_MAX;
 958              ++mountain_search) {
 959             r = roll0(total);
 960             for (i = 0; i < ns; ++i)
 961                 if (r < weight[i] && ELEV == -INFINITY &&
 962                     (c >= nc ||
 963                      ((!(capx[c] == sectx[c][i] &&
 964                          capy[c] == secty[c][i])) &&
 965                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
 966                          capy[c] == secty[c][i]))))) {
 967                     ELEV = INFINITY;
 968                     break;
 969                 }
 970             --k;
 971         }
 972
 973 /* Elevate land that is not mountain and not capital */
 974
 975         for (i = 0; i < ns; ++i)
 976             dmoun[i] = distance_to_mountain();
 977         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
 978           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
 979           100 * INFINITY;
 980         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
 981             highest = -INFINITY;
 982             where = -1;
 983             for (i = 0; i < ns; ++i) {
 984                 if (ELEV != INFINITY &&
 985                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
 986                                     capy[c] == secty[c][i])) &&
 987                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
 988                                     capy[c] == secty[c][i]))))) {
 989                     h = 3 * (5 - dmoun[i]) + dsea[i];
 990                     if (h > highest) {
 991                         highest = h;
 992                         where = i;
 993                     }
 994                 }
 995             }
 996             if (where == -1)
 997                 break;
 998             newk = k / 100;
 999             if (newk >= HILLMIN && newk < PLATMIN)
1000                 newk = PLATMIN;
1001             if (newk < LANDMIN)
1002                 newk = LANDMIN;
1003             elev[sectx[c][where]][secty[c][where]] = newk;
1004             dsea[where] = -INFINITY;
1005             dmoun[where] = INFINITY;
1006         }
1007
1008 /* Elevate the mountains and capitals */
1009
1010         for (i = 0; i < ns; ++i) {
1011             if (ELEV == INFINITY) {
1012                 if (dsea[i] == 1)
1013                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1014                 else
1015                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1016                       roll0((256 - HIGHMIN) / 2);
1017             } else if (c < nc &&
1018                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1019                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1020                           capy[c] == secty[c][i]))))
1021                 ELEV = PLATMIN;
1022         }
1023     }
1024 }
1025
1026 #define distance_to_land() distance_to_what(x, y, 1)
1027
1028 static void
1029 elevate_sea(void)
1030 {
1031     int x, y;
1032
1033     for (y = 0; y < WORLD_Y; ++y) {
1034         for (x = y % 2; x < WORLD_X; x += 2) {
1035             if (elev[x][y] == -INFINITY)
1036                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1037         }
1038     }
1039 }
1040
1041 /****************************************************************************
1042   ADD THE RESOURCES
1043 ****************************************************************************/
1044
1045 static int
1046 set_fert(int e)
1047 {
1048     int fert = 0;
1049     if (e < LANDMIN)
1050         fert = LANDMIN - e + 40;
1051     else if (e < FERT_MAX)
1052         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1053     if (fert > 100)
1054         fert = 100;
1055     return fert;
1056 }
1057
1058 static int
1059 set_oil(int e)
1060 {
1061     int oil = 0;
1062     if (e < LANDMIN)
1063         oil = (LANDMIN - e) * 2 + roll0(2);
1064     else if (e <= OIL_MAX)
1065         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1066     if (oil > 100)
1067         oil = 100;
1068     return oil;
1069 }
1070
1071 static int
1072 set_iron(int e)
1073 {
1074     int iron = 0;
1075     if (e >= IRON_MIN && e < HIGHMIN)
1076         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1077     if (iron > 100)
1078         iron = 100;
1079     return iron;
1080 }
1081
1082 static int
1083 set_gold(int e)
1084 {
1085     int gold = 0;
1086     if (e >= GOLD_MIN) {
1087         if (e < HIGHMIN)
1088             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1089         else
1090             gold = 100 - 20 * HIGHMIN / e;
1091     }
1092     if (gold > 100)
1093         gold = 100;
1094     return gold;
1095 }
1096
1097 static int
1098 set_uran(int e)
1099 {
1100     int uran = 0;
1101     if (e >= URAN_MIN && e < HIGHMIN)
1102         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1103     if (uran > 100)
1104         uran = 100;
1105     return uran;
1106 }
1107
1108 static void
1109 add_resources(struct sctstr *sct)
1110 {
1111     sct->sct_fertil = set_fert(sct->sct_elev);
1112     sct->sct_oil = set_oil(sct->sct_elev);
1113     sct->sct_min = set_iron(sct->sct_elev);
1114     sct->sct_gmin = set_gold(sct->sct_elev);
1115     sct->sct_uran = set_uran(sct->sct_elev);
1116 }
1117
1118 /****************************************************************************
1119   DESIGNATE THE SECTORS
1120 ****************************************************************************/
1121
1122 static void
1123 write_sects(void)
1124 {
1125     struct sctstr *sct;
1126     int x, y, total;
1127
1128     for (y = 0; y < WORLD_Y; y++) {
1129         for (x = y % 2; x < WORLD_X; x += 2) {
1130             sct = getsectp(x, y);
1131             total = elev[x][y];
1132             if (total < LANDMIN) {
1133                 sct->sct_type = SCT_WATER;
1134             } else if (total < HILLMIN)
1135                 sct->sct_type = SCT_RURAL;
1136             else if (total < PLATMIN)
1137                 sct->sct_type = SCT_MOUNT;
1138             else if (total < HIGHMIN)
1139                 sct->sct_type = SCT_RURAL;
1140             else
1141                 sct->sct_type = SCT_MOUNT;
1142             sct->sct_elev = total;
1143             sct->sct_newtype = sct->sct_type;
1144             sct->sct_dterr = own[sct->sct_x][y] + 1;
1145             if (ORE)
1146                 add_resources(sct);
1147         }
1148     }
1149     set_coastal_flags();
1150 }
1151
1152 /****************************************************************************
1153   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1154 ****************************************************************************/
1155 static void
1156 output(void)
1157 {
1158     int sx, sy, x, y;
1159
1160     if (quiet == 0) {
1161         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1162             y = YNORM(sy);
1163             puts("");
1164             if (y % 2)
1165                 printf(" ");
1166             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1167                 x = XNORM(sx);
1168                 if (own[x][y] == -1)
1169                     printf(". ");
1170                 else {
1171                     printf("%c ", map_symbol(x, y));
1172                 }
1173             }
1174         }
1175     }
1176 }
1177
1178 static int
1179 map_symbol(int x, int y)
1180 {
1181     int c;
1182
1183     for (c = 0; c < nc; ++c)
1184         if ((x == capx[c] && y == capy[c])
1185             || (x == new_x(capx[c] + 2) && y == capy[c]))
1186             return numletter[own[x][y] % 62];
1187     if ((elev[x][y] >= HILLMIN && elev[x][y] < PLATMIN)
1188         || elev[x][y] >= HIGHMIN)
1189         return '^';
1190     return own[x][y] >= nc ? '%' : '#';
1191 }
1192
1193 /*
1194  * Print a map to help visualize own[][].
1195  * This is for debugging.
1196  */
1197 void
1198 print_own_map(void)
1199 {
1200     int sx, sy, x, y;
1201
1202     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1203         y = YNORM(sy);
1204         printf("%4d ", sy);
1205         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1206             x = XNORM(sx);
1207             if ((x + y) & 1)
1208                 putchar(' ');
1209             else if (own[x][y] == -1)
1210                 putchar('.');
1211             else
1212                 putchar(numletter[own[x][y] % 62]);
1213         }
1214         putchar('\n');
1215     }
1216 }
1217
1218 /*
1219  * Print a map to help visualize elev[][].
1220  * This is for debugging.  It expects the terminal to understand
1221  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1222  */
1223 void
1224 print_elev_map(void)
1225 {
1226     int sx, sy, x, y, sat;
1227
1228     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1229         y = YNORM(sy);
1230         printf("%4d ", sy);
1231         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1232             x = XNORM(sx);
1233             if ((x + y) & 1)
1234                 putchar(' ');
1235             else if (!elev[x][y])
1236                 putchar(' ');
1237             else if (elev[x][y] < 0) {
1238                 sat = 256 + elev[x][y] * 2;
1239                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1240             } else if (elev[x][y] < HIGHMIN / 2) {
1241                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1242                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1243             } else if (elev[x][y] < HIGHMIN) {
1244                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1245                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1246             } else {
1247                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1248                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1249             }
1250         }
1251         putchar('\n');
1252     }
1253 }
1254
1255 /***************************************************************************
1256   WRITE A SCRIPT FOR PLACING CAPITALS
1257 ****************************************************************************/
1258 static int
1259 write_newcap_script(void)
1260 {
1261     int c;
1262     FILE *script = fopen(outfile, "w");
1263
1264     if (!script) {
1265         printf("fairland: error, unable to write to %s.\n", outfile);
1266         return 0;
1267     }
1268
1269     for (c = 0; c < nc; ++c) {
1270         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1271         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1272     }
1273     fprintf(script, "add %d visitor visitor v\n", c + 1);
1274     fclose(script);
1275     return 1;
1276 }
1277
1278 static void
1279 qprint(const char *const fmt, ...)
1280 {
1281     va_list ap;
1282
1283     if (!quiet) {
1284         va_start(ap, fmt);
1285         vfprintf(stdout, fmt, ap);
1286         va_end(ap);
1287     }
1288 }
1289
1290 static void
1291 set_coastal_flags(void)
1292 {
1293     int i, j;
1294     struct sctstr *sp;
1295
1296     qprint("setting coastal flags...\n");
1297     for (i = 0; i < nc; ++i) {
1298         for (j = 0; j < sc; j++) {
1299             sp = getsectp(sectx[i][j], secty[i][j]);
1300             sp->sct_coastal = sectc[i][j];
1301         }
1302     }
1303     for (i = nc; i < nc + ni; ++i) {
1304         for (j = 0; j < isecs[i]; j++) {
1305             sp = getsectp(sectx[i][j], secty[i][j]);
1306             sp->sct_coastal = sectc[i][j];
1307         }
1308     }
1309 }