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