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