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