git.pond.sub.org Git - empserver/blob - src/util/fairland.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2020, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                Ken Stevens, Steve McClure, Markus Armbruster
   5  *
   6  *  Empire is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  *
  19  *  ---
  20  *
  21  *  See files README, COPYING and CREDITS in the root of the source
  22  *  tree for related information and legal notices.  It is expected
  23  *  that future projects/authors will amend these files as needed.
  24  *
  25  *  ---
  26  *
  27  *  fairland.c: Create a nice, new world
  28  *
  29  *  Known contributors to this file:
  30  *     Ken Stevens, 1995
  31  *     Steve McClure, 1998
  32  *     Markus Armbruster, 2004-2020
  33  */
  34
  35 /*
  36  * How fairland works
  37  *
  38  * 1. Place capitals
  39  *
  40  * Place the capitals on the torus in such a way so as to maximize
  41  * their distances from one another.  This uses the perturbation
  42  * technique of calculus of variations.
  43  *
  44  * 2. Grow start islands ("continents")
  45  *
  46  * For all continents, add the first sector at the capital's location,
  47  * and the second right to it.  These are the capital sectors.  Then
  48  * add one sector to each continent in turn, obeying the minimum
  49  * distance between continents, until they have the specified size.
  50  *
  51  * The kind of shape they grow into is determined by the "spike
  52  * percentage" --- the higher the spike, the more spindly they will
  53  * be.  If you lower the spike, the continents will be more round.
  54  *
  55  * If growing fails due to lack of room, start over.  If it fails too
  56  * many times, give up and terminate unsuccessfully.
  57  *
  58  * 3. Place and grow additional islands
  59  *
  60  * Place and grow islands one after the other.  Place the first sector
  61  * randomly, pick an island size, then grow the island to that size.
  62  *
  63  * Growing works as for continents, except the minimum distance for
  64  * additional islands applies, and growing simply stops when there is
  65  * no room.
  66  *
  67  * 4. Compute elevation
  68  *
  69  * Elevate islands one after the other.
  70  *
  71  * First, place the specified number of mountains randomly.
  72  * Probability increases with distance to sea.
  73  *
  74  * Last, elevate mountains and the capitals.  Pick coastal mountain
  75  * elevation randomly from an interval of medium elevations reserved
  76  * for them.  Pick non-coastal mountain elevation randomly from an
  77  * interval of high elevation reserved for them.  Set capital
  78  * elevation to a fixed, medium value.
  79  *
  80  * In between, elevate the remaining land one by one, working from
  81  * mountains towards the sea, and from the elevation just below the
  82  * non-coastal mountains' interval linearly down to 1, avoiding the
  83  * coastal mountains' interval.
  84  *
  85  * This gives islands of the same size the same set of elevations,
  86  * except for mountains.
  87  *
  88  * Elevate sea: pick a random depth from an interval that deepens with
  89  * the distance to land.
  90  *
  91  * 5. Set resources
  92  *
  93  * Sector resources are simple functions of elevation.  You can alter
  94  * macros OIL_MAX, IRON_MIN, GOLD_MIN, FERT_MAX, and URAN_MIN to
  95  * customize them.
  96  */
  97
  98 #include <config.h>
  99
 100 #include <assert.h>
 101 #include <errno.h>
 102 #include <stdarg.h>
 103 #include <stdio.h>
 104 #include <unistd.h>
 105 #include "chance.h"
 106 #include "optlist.h"
 107 #include "prototypes.h"
 108 #include "sect.h"
 109 #include "version.h"
 110 #include "xy.h"
 111
 112 /* define ORE 1 to add resources, define ORE 0 if you want to use another
 113    program to add the resources */
 114 static int ORE = 1;
 115 static int quiet = 0;
 116
 117 /* If you don't specify these command line arguments, then these are the
 118    defaults */
 119 #define DEFAULT_SPIKE 10
 120 #define DEFAULT_MOUNTAIN 0
 121 #define DEFAULT_CONTDIST 2
 122 #define DEFAULT_ISLDIST 1
 123
 124 /* The following five numbers refer to elevation under which (in the case of
 125    fertility or oil) or over which (in the case of iron, gold, and uranium)
 126    sectors with that elevation will contain that resource.  Elevation ranges
 127    from 0 to 100 */
 128
 129 /* raise FERT_MAX for more fertility */
 130 #define FERT_MAX   56
 131
 132 /* raise OIL_MAX for more oil */
 133 #define OIL_MAX    33
 134
 135 /* lower IRON_MIN for more iron */
 136 #define IRON_MIN   22
 137
 138 /* lower GOLD_MIN for more gold */
 139 #define GOLD_MIN   36
 140
 141 /* lower URAN_MIN for more uranium */
 142 #define URAN_MIN   56
 143
 144 /* do not change these 4 defines */
 145 #define LANDMIN         1       /* plate altitude for normal land */
 146 #define HILLMIN         34      /* plate altitude for hills */
 147 #define PLATMIN         36      /* plate altitude for plateau */
 148 #define HIGHMIN         98      /* plate altitude for mountains */
 149
 150 static void qprint(const char * const fmt, ...)
 151     ATTRIBUTE((format (printf, 1, 2)));
 152
 153 #define DEFAULT_OUTFILE_NAME "newcap_script"
 154 static const char *outfile = DEFAULT_OUTFILE_NAME;
 155 /* mark the continents with a * so you can tell them
 156    from the islands 1 = mark, 0 = don't mark. */
 157 static int AIRPORT_MARKER = 0;
 158
 159 /* don't let the islands crash into each other.
 160    1 = don't merge, 0 = merge. */
 161 static int DISTINCT_ISLANDS = 1;
 162
 163 static char *program_name;
 164
 165 #define STABLE_CYCLE 4          /* stability required for perterbed capitals */
 166 #define INFINITY        999     /* a number which means "BIG" */
 167
 168 /* these defines prevent infinite loops:
 169 */
 170
 171 #define COAST_SEARCH_MAX 200    /* how many times do we look for a coast sector
 172                                    when growing continents and islands */
 173 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
 174 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
 175 #define MOUNTAIN_SEARCH_MAX 1000        /* how long do we try to place mountains */
 176
 177 /* handy macros:
 178 */
 179
 180 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
 181 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
 182
 183 static int secs;                /* number of sectors grown */
 184 static int ctot;                /* total number of continents and islands grown */
 185 static int *isecs;              /* array of how large each island is */
 186
 187 static int nc, sc, di, sp, pm, ni, is, id; /* the 8 args to this program */
 188 static int *capx, *capy;        /* location of the nc capitals */
 189 static int *mc, mcc;            /* array and counter used for stability
 190                                    check when perturbing */
 191 static int spike;               /* are we spiking? */
 192 static int mind;                /* the final distance between capitals that
 193                                    we achieved */
 194 static int dirx[] = { -2, -1, 1, 2, 1, -1 }; /* gyujnb */
 195 static int diry[] = { 0, -1, -1, 0, 1, 1 };
 196
 197 static int **own;               /* owner of the sector.  -1 means water */
 198 static int **elev;              /* elevation of the sectors */
 199 static int **sectx, **secty;    /* the sectors for each continent */
 200 static int **sectc;             /* which sectors are on the coast? */
 201 static int *vector;             /* used for measuring distances */
 202 static int *weight;             /* used for placing mountains */
 203 static int *dsea, *dmoun;       /* the dist to the ocean and mountain */
 204 static int fl_status;           /* is anything wrong? */
 205 #define STATUS_NO_ROOM 1        /* there was no room to grow */
 206 #define NUMTRIES 10             /* keep trying to grow this many times */
 207
 208 static const char *numletter =
 209     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 210
 211 static void help(char *);
 212 static void usage(void);
 213 static void parse_args(int argc, char *argv[]);
 214 static void allocate_memory(void);
 215 static void init(void);
 216 static int drift(void);
 217 static void grow_continents(void);
 218 static void create_elevations(void);
 219 static void write_sects(void);
 220 static void output(void);
 221 static int write_newcap_script(void);
 222 static int stable(void);
 223 static void elevate_land(void);
 224 static void elevate_sea(void);
 225 static int map_symbol(int x, int y);
 226 static void set_coastal_flags(void);
 227
 228 static void print_vars(void);
 229 static void fl_move(int);
 230 static void grow_islands(void);
 231
 232 /* Debugging aids: */
 233 void print_own_map(void);
 234 void print_elev_map(void);
 235
 236 /****************************************************************************
 237   MAIN
 238 ****************************************************************************/
 239
 240 int
 241 main(int argc, char *argv[])
 242 {
 243     int opt;
 244     char *config_file = NULL;
 245     int i = 0;
 246     unsigned rnd_seed = 0;
 247     int seed_set = 0;
 248
 249     program_name = argv[0];
 250
 251     while ((opt = getopt(argc, argv, "ae:hioqR:s:v")) != EOF) {
 252         switch (opt) {
 253         case 'a':
 254             AIRPORT_MARKER = 1;
 255             break;
 256         case 'e':
 257             config_file = optarg;
 258             break;
 259         case 'i':
 260             DISTINCT_ISLANDS = 0;
 261             break;
 262         case 'o':
 263             ORE = 0;
 264             break;
 265         case 'q':
 266             quiet = 1;
 267             break;
 268         case 'R':
 269             rnd_seed = strtoul(optarg, NULL, 10);
 270             seed_set = 1;
 271             break;
 272         case 's':
 273             outfile = optarg;
 274             break;
 275         case 'h':
 276             usage();
 277             exit(0);
 278         case 'v':
 279             printf("%s\n\n%s", version, legal);
 280             exit(0);
 281         default:
 282             help(NULL);
 283             exit(1);
 284         }
 285     }
 286     parse_args(argc - optind, argv + optind);
 287
 288     if (!seed_set)
 289         rnd_seed = pick_seed();
 290     seed_prng(rnd_seed);
 291     empfile_init();
 292     if (emp_config(config_file) < 0)
 293         exit(1);
 294     empfile_fixup();
 295
 296     allocate_memory();
 297     print_vars();
 298
 299     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
 300     qprint("seed is %u\n", rnd_seed);
 301     do {
 302         init();
 303         if (i)
 304             qprint("\ntry #%d (out of %d)...\n", i + 1, NUMTRIES);
 305         qprint("placing capitals...\n");
 306         if (!drift())
 307             qprint("fairland: unstable drift -- try increasing DRIFT_MAX\n");
 308         qprint("growing continents...\n");
 309         grow_continents();
 310     } while (fl_status && ++i < NUMTRIES);
 311     if (fl_status) {
 312         fputs("ERROR: World not large enough to hold continents\n",
 313               stderr);
 314         exit(1);
 315     }
 316     qprint("growing islands:");
 317     grow_islands();
 318     qprint("\nelevating land...\n");
 319     create_elevations();
 320     qprint("designating sectors...\n");
 321     if (ORE)
 322         qprint("adding resources...\n");
 323     if (!write_newcap_script())
 324         exit(1);
 325
 326     if (chdir(gamedir)) {
 327         fprintf(stderr, "Can't chdir to %s (%s)\n", gamedir, strerror(errno));
 328         exit(EXIT_FAILURE);
 329     }
 330     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
 331         exit(1);
 332     write_sects();
 333     qprint("writing to sectors file...\n");
 334     if (!ef_close(EF_SECTOR))
 335         exit(1);
 336
 337     output();
 338     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
 339            outfile);
 340     if (!ORE)
 341         qprint("\t*** Resources have not been added ***\n");
 342     exit(0);
 343 }
 344
 345 static void
 346 print_vars(void)
 347 {
 348     if (quiet)
 349         return;
 350     puts("Creating a planet with:\n");
 351     printf("%d continents\n", nc);
 352     printf("continent size: %d\n", sc);
 353     printf("number of islands: %d\n", ni);
 354     printf("average size of islands: %d\n", is);
 355     printf("spike: %d%%\n", sp);
 356     printf("%d%% of land is mountain (each continent will have %d mountains)\n",
 357            pm, (pm * sc) / 100);
 358     printf("minimum distance between continents: %d\n", di);
 359     printf("minimum distance from islands to continents: %d\n", id);
 360     printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
 361 }
 362
 363 static int
 364 my_sqrt(int n)
 365 {
 366     int i;
 367
 368     for (i = 1; i * i < n * 10000; ++i) ;
 369     return (i + 50) / 100;
 370 }
 371
 372 /****************************************************************************
 373   PARSE COMMAND LINE ARGUMENTS
 374 ****************************************************************************/
 375
 376 static void
 377 help(char *complaint)
 378 {
 379     if (complaint)
 380         fprintf(stderr, "%s: %s\n", program_name, complaint);
 381     fprintf(stderr, "Try -h for help.\n");
 382 }
 383
 384 static void
 385 usage(void)
 386 {
 387     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
 388            "  -a              airport marker for continents\n"
 389            "  -e CONFIG-FILE  configuration file\n"
 390            "                  (default %s)\n"
 391            "  -i              islands may merge\n"
 392            "  -o              don't set resources\n"
 393            "  -q              quiet\n"
 394            "  -R SEED         seed for random number generator\n"
 395            "  -s SCRIPT       name of script to create (default %s)\n"
 396            "  -h              display this help and exit\n"
 397            "  -v              display version information and exit\n"
 398            "  NC              number of continents\n"
 399            "  SC              continent size\n"
 400            "  NI              number of islands (default NC)\n"
 401            "  IS              average island size (default SC/2)\n"
 402            "  SP              spike percentage: 0 = round, 100 = snake (default %d)\n"
 403            "  PM              percentage of land that is mountain (default %d)\n"
 404            "  DI              minimum distance between continents (default %d)\n"
 405            "  ID              minimum distance from islands to continents (default %d)\n",
 406            program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
 407            DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
 408 }
 409
 410 static void
 411 parse_args(int argc, char *argv[])
 412 {
 413     if (argc < 2) {
 414         help("missing arguments");
 415         exit(1);
 416     }
 417     if (argc > 8) {
 418         help("too many arguments");
 419         exit(1);
 420     }
 421     nc = atoi(argv[0]);
 422     if (nc < 1) {
 423         puts("fairland: error -- number of continents must be > 0");
 424         exit(1);
 425     }
 426
 427     sc = atoi(argv[1]);
 428     if (sc < 1) {
 429         puts("fairland: error -- size of continents must be > 0");
 430         exit(1);
 431     }
 432
 433     if (argc > 2)
 434         ni = atoi(argv[2]);
 435     else
 436         ni = nc;
 437
 438     if (argc > 3)
 439         is = atoi(argv[3]);
 440     else
 441         is = sc / 2;
 442     if (is < 1)
 443         is = 1;
 444
 445     if (argc > 4)
 446         sp = atoi(argv[4]);
 447     else
 448         sp = DEFAULT_SPIKE;
 449     sp = LIMIT_TO(sp, 0, 100);
 450
 451     if (argc > 5)
 452         pm = atoi(argv[5]);
 453     else
 454         pm = DEFAULT_MOUNTAIN;
 455     if (pm < 0)
 456         pm = 0;
 457
 458     if (argc > 6)
 459         di = atoi(argv[6]);
 460     else
 461         di = DEFAULT_CONTDIST;
 462
 463     if (di < 0) {
 464         puts("fairland: error -- distance between continents must be >= 0");
 465         exit(1);
 466     }
 467     if (di > WORLD_X / 2 || di > WORLD_Y / 2) {
 468         puts("fairland: error -- distance between continents too large");
 469         exit(1);
 470     }
 471
 472     if (argc > 7)
 473         id = atoi(argv[7]);
 474     else
 475         id = DEFAULT_ISLDIST;
 476     if (id < 0) {
 477         puts("fairland: error -- distance from islands to continents must be >= 0");
 478         exit(1);
 479     }
 480     if (id > WORLD_X || id > WORLD_Y) {
 481         puts("fairland: error -- distance from islands to continents too large");
 482         exit(1);
 483     }
 484     if (nc * sc + nc * my_sqrt(sc) * 2 * (di + 1) > WORLD_X * WORLD_Y) {
 485         puts("fairland: warning -- world might be too small to fit continents.");
 486         puts("arguments should satisfy:");
 487         puts("nc*sc*sc + nc*sqrt(sc)*2*(di+1) < WORLD_X * WORLD_Y");
 488     }
 489 }
 490
 491 /****************************************************************************
 492   VARIABLE INITIALIZATION
 493 ****************************************************************************/
 494
 495 static void
 496 allocate_memory(void)
 497 {
 498     int i;
 499
 500     capx = calloc(nc, sizeof(int));
 501     capy = calloc(nc, sizeof(int));
 502     vector = calloc(WORLD_X + WORLD_Y, sizeof(int));
 503     mc = calloc(STABLE_CYCLE, sizeof(int));
 504     own = calloc(WORLD_X, sizeof(int *));
 505     elev = calloc(WORLD_X, sizeof(int *));
 506     for (i = 0; i < WORLD_X; ++i) {
 507         own[i] = calloc(WORLD_Y, sizeof(int));
 508         elev[i] = calloc(WORLD_Y, sizeof(int));
 509     }
 510     sectx = calloc(nc + ni, sizeof(int *));
 511     secty = calloc(nc + ni, sizeof(int *));
 512     sectc = calloc(nc + ni, sizeof(int *));
 513     isecs = calloc(nc + ni, sizeof(int));
 514     weight = calloc(MAX(sc, is * 2), sizeof(int));
 515     dsea = calloc(MAX(sc, is * 2), sizeof(int));
 516     dmoun = calloc(MAX(sc, is * 2), sizeof(int));
 517     for (i = 0; i < nc; ++i) {
 518         sectx[i] = calloc(sc, sizeof(int));
 519         secty[i] = calloc(sc, sizeof(int));
 520         sectc[i] = calloc(sc, sizeof(int));
 521     }
 522     for (i = nc; i < nc + ni; ++i) {
 523         sectx[i] = calloc(is * 2, sizeof(int));
 524         secty[i] = calloc(is * 2, sizeof(int));
 525         sectc[i] = calloc(is * 2, sizeof(int));
 526     }
 527
 528 }
 529
 530 static void
 531 init(void)
 532 {
 533     int i, j, xx = 0, yy = 0;
 534
 535     mcc = 0;
 536     fl_status = 0;
 537
 538     for (i = 0; i < WORLD_X; ++i) {
 539         for (j = 0; j < WORLD_Y; ++j) {
 540             own[i][j] = -1;
 541             elev[i][j] = -INFINITY;
 542         }
 543     }
 544
 545     for (i = 0; i < nc; ++i) {
 546         if (xx >= WORLD_X) {
 547             ++yy;
 548             xx = yy % 2;
 549             if (yy == WORLD_Y) {
 550                 puts("fairland error: world not big enough for all the continents.\n");
 551                 exit(1);
 552             }
 553         }
 554         capx[i] = xx;
 555         capy[i] = yy;
 556         xx += 2;
 557     }
 558     for (i = 0; i < STABLE_CYCLE; ++i)
 559         mc[i] = i;
 560 }
 561
 562 /****************************************************************************
 563   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
 564 ****************************************************************************/
 565
 566 /* How isolated is capital j?
 567 */
 568 static int
 569 iso(int j, int newx, int newy)
 570 {
 571     int i, md, d = WORLD_X + WORLD_Y;
 572
 573     for (i = 0; i < nc; ++i) {
 574         if (i == j)
 575             continue;
 576         md = mapdist(capx[i], capy[i], newx, newy);
 577         if (md < d)
 578             d = md;
 579     }
 580
 581     return d;
 582 }
 583
 584 /* Drift all the capitals
 585 */
 586 static int
 587 drift(void)
 588 {
 589     int i, turns;
 590
 591     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 592         if (turns > DRIFT_BEFORE_CHECK && (mind = stable()))
 593             return 1;
 594         for (i = 0; i < nc; ++i)
 595             fl_move(i);
 596     }
 597     return 0;
 598 }
 599
 600 /* Check to see if we have stabilized--can we stop drifting the capitals?
 601 */
 602
 603 static int
 604 stable(void)
 605 {
 606     int i, isod, d = 0, stab = 1;
 607
 608     for (i = 0; i < nc; ++i) {
 609         isod = iso(i, capx[i], capy[i]);
 610         if (isod > d)
 611             d = isod;
 612     }
 613     for (i = 0; i < STABLE_CYCLE; ++i)
 614         if (d != mc[i])
 615             stab = 0;
 616     mc[mcc] = d;
 617     mcc = (mcc + 1) % STABLE_CYCLE;
 618     return stab ? d : 0;
 619 }
 620
 621 /* This routine does the actual drifting
 622 */
 623
 624 static void
 625 fl_move(int j)
 626 {
 627     int i, n, newx, newy;
 628
 629     for (i = roll0(6), n = 0; n < 6; i = (i + 1) % 6, ++n) {
 630         newx = new_x(capx[j] + dirx[i]);
 631         newy = new_y(capy[j] + diry[i]);
 632         if (iso(j, newx, newy) >= iso(j, capx[j], capy[j])) {
 633             capx[j] = newx;
 634             capy[j] = newy;
 635             return;
 636         }
 637     }
 638 }
 639
 640 /****************************************************************************
 641   GROW THE CONTINENTS
 642 ****************************************************************************/
 643
 644 /* Look for a coastal sector of continent c
 645 */
 646
 647 static void
 648 find_coast(int c)
 649 {
 650     int i, j;
 651
 652     for (i = 0; i < secs; ++i) {
 653         sectc[c][i] = 0;
 654         for (j = 0; j < 6; ++j)
 655             if (own[new_x(sectx[c][i] + dirx[j])][new_y(secty[c][i] + diry[j])] == -1)
 656                 sectc[c][i] = 1;
 657     }
 658 }
 659
 660 /* Used for measuring distances
 661 */
 662 static int
 663 next_vector(int n)
 664 {
 665     int i;
 666
 667     if (n == 1) {
 668         vector[0] += 1;
 669         vector[0] %= 6;
 670         return vector[0];
 671     }
 672     for (i = 1; i < n && vector[i] == vector[i - 1]; ++i) ;
 673     vector[i - 1] += 1;
 674     vector[i - 1] %= 6;
 675     return i > 1 || vector[0] > 0;
 676 }
 677
 678 /* Test to see if we're allowed to grow there: the arguments di and id
 679 */
 680 static int
 681 try_to_grow(int c, int newx, int newy, int d)
 682 {
 683     int i, j, px, py;
 684
 685     for (i = 1; i <= d; ++i) {
 686         for (j = 0; j < i; ++j)
 687             vector[j] = 0;
 688         do {
 689             px = newx;
 690             py = newy;
 691             for (j = 0; j < i; ++j) {
 692                 px = new_x(px + dirx[vector[j]]);
 693                 py = new_y(py + diry[vector[j]]);
 694             }
 695             if (own[px][py] != -1 &&
 696                 own[px][py] != c &&
 697                 (DISTINCT_ISLANDS || own[px][py] < nc))
 698                 return 0;
 699         } while (next_vector(i));
 700     }
 701     sectx[c][secs] = newx;
 702     secty[c][secs] = newy;
 703     own[newx][newy] = c;
 704     return 1;
 705 }
 706
 707 /* Move along the coast in a clockwise direction.
 708 */
 709
 710 static void
 711 next_coast(int c, int x, int y, int *xp, int *yp)
 712 {
 713     int i, nx, ny, wat = 0;
 714
 715     if (secs == 1) {
 716         *xp = x;
 717         *yp = y;
 718         return;
 719     }
 720
 721     for (i = 0; i < 12; ++i) {
 722         nx = new_x(x + dirx[i % 6]);
 723         ny = new_y(y + diry[i % 6]);
 724         if (own[nx][ny] == -1)
 725             wat = 1;
 726         if (wat && own[nx][ny] == c) {
 727             *xp = nx;
 728             *yp = ny;
 729             return;
 730         }
 731     }
 732 }
 733
 734 /* Choose a sector to grow from
 735 */
 736
 737 static int
 738 new_try(int c)
 739 {
 740     int i, starti;
 741
 742     if (secs == 1) {
 743         if (sectc[c][0])
 744             return 0;
 745     } else {
 746         i = starti = (spike && sectc[c][secs - 1]) ? secs - 1 : roll0(secs);
 747         do {
 748             if (sectc[c][i])
 749                 return i;
 750             i = (i + 1) % secs;
 751         } while (i != starti);
 752         assert(c >= nc);
 753         return -1;
 754     }
 755     return -1;
 756 }
 757
 758 /* Grow continent c by 1 sector
 759 */
 760
 761 static int
 762 grow_one_sector(int c)
 763 {
 764     int done, coast_search, try1, x, y, newx, newy, i, n, sx, sy;
 765
 766     spike = roll0(100) < sp;
 767     if ((try1 = new_try(c)) == -1)
 768         return 0;
 769     x = sx = sectx[c][try1];
 770     y = sy = secty[c][try1];
 771     coast_search = 0;
 772     done = 0;
 773     do {
 774         if (spike) {
 775             for (i = roll0(6), n = 0; n < 12 && !done; i = (i + 1) % 6, ++n) {
 776                 newx = new_x(x + dirx[i]);
 777                 newy = new_y(y + diry[i]);
 778                 if (own[newx][newy] == -1 &&
 779                     (n > 5 ||
 780                      (own[new_x(x+dirx[(i+5)%6])][new_y(y+diry[(i+5)%6])] == -1 &&
 781                       own[new_x(x+dirx[(i+1)%6])][new_y(y+diry[(i+1)%6])] == -1)))
 782                     if (try_to_grow(c, newx, newy, c < nc ? di : id))
 783                         done = 1;
 784             }
 785         } else
 786             for (i = roll0(6), n = 0; n < 6 && !done; i = (i + 1) % 6, ++n) {
 787                 newx = new_x(x + dirx[i]);
 788                 newy = new_y(y + diry[i]);
 789                 if (own[newx][newy] == -1)
 790                     if (try_to_grow(c, newx, newy, c < nc ? di : id))
 791                         done = 1;
 792             }
 793         next_coast(c, x, y, &x, &y);
 794         ++coast_search;
 795     } while (!done && coast_search < COAST_SEARCH_MAX &&
 796              (secs == 1 || x != sx || y != sy));
 797     if (!done && c < nc) {
 798         qprint("fairland: error -- continent %c had no room to grow!\n",
 799                numletter[c % 62]);
 800         fl_status |= STATUS_NO_ROOM;
 801     }
 802     return done;
 803 }
 804
 805 /* Grow all the continents
 806 */
 807 static void
 808 grow_continents(void)
 809 {
 810     int c;
 811
 812     for (c = 0; c < nc; ++c) {
 813         sectx[c][0] = capx[c];
 814         secty[c][0] = capy[c];
 815         own[sectx[c][0]][secty[c][0]] = c;
 816         sectx[c][1] = new_x(capx[c] + 2);
 817         secty[c][1] = capy[c];
 818         own[sectx[c][1]][secty[c][1]] = c;
 819     }
 820
 821     for (secs = 2; secs < sc && !fl_status; ++secs) {
 822         for (c = 0; c < nc; ++c) {
 823             find_coast(c);
 824             grow_one_sector(c);
 825         }
 826     }
 827     for (c = 0; c < nc; ++c)
 828         find_coast(c);
 829
 830     if (fl_status)
 831         qprint("Only managed to grow %d out of %d sectors.\n", secs, sc);
 832     ctot = nc;
 833 }
 834
 835 /****************************************************************************
 836   GROW THE ISLANDS
 837 ****************************************************************************/
 838
 839 /* Choose a place to start growing an island from
 840 */
 841 static int
 842 place_island(int c, int *xp, int *yp)
 843 {
 844     int d, sx, sy;
 845     int ssy = roll0(WORLD_Y);
 846     int ssx = new_x(roll0(WORLD_X / 2) * 2 + ssy % 2);
 847
 848     if (ssx > WORLD_X - 2)
 849         ssx = new_x(ssx + 2);
 850     for (d = di + id; d >= id; --d) {
 851         sx = ssx;
 852         sy = ssy;
 853         *xp = new_x(sx + 2);
 854         for (*yp = sy; *xp != sx || *yp != sy; *xp += 2) {
 855             if (*xp >= WORLD_X) {
 856                 *yp = new_y(*yp + 1);
 857                 *xp = *yp % 2;
 858                 if (*xp == sx && *yp == sy)
 859                     break;
 860             }
 861             if (own[*xp][*yp] == -1 && try_to_grow(c, *xp, *yp, d))
 862                 return 1;
 863         }
 864     }
 865     return 0;
 866 }
 867
 868 /* Grow all the islands
 869 */
 870
 871 static void
 872 grow_islands(void)
 873 {
 874     int c, x, y, isiz;
 875
 876     for (c = nc; c < nc + ni; ++c) {
 877         secs = 0;
 878         if (!place_island(c, &x, &y))
 879             return;
 880         isiz = roll(is) + roll0(is);
 881         do {
 882             ++secs;
 883             find_coast(c);
 884         } while (secs < isiz && grow_one_sector(c));
 885         find_coast(c);
 886         qprint(" %d(%d)", c - nc + 1, secs);
 887         isecs[c] = secs;
 888         ctot++;
 889     }
 890 }
 891
 892 /****************************************************************************
 893   CREATE ELEVATIONS
 894 ****************************************************************************/
 895 static void
 896 create_elevations(void)
 897 {
 898     elevate_land();
 899     elevate_sea();
 900 }
 901
 902 /* Generic function for finding the distance to the closest sea, land, or
 903    mountain
 904 */
 905 static int
 906 distance_to_what(int x, int y, int flag)
 907 {
 908     int j, d, px, py;
 909
 910     for (d = 1; d < 5; ++d) {
 911         for (j = 0; j < d; ++j)
 912             vector[j] = 0;
 913         do {
 914             px = x;
 915             py = y;
 916             for (j = 0; j < d; ++j) {
 917                 px = new_x(px + dirx[vector[j]]);
 918                 py = new_y(py + diry[vector[j]]);
 919             }
 920             switch (flag) {
 921             case 0:             /* distance to sea */
 922                 if (own[px][py] == -1)
 923                     return d;
 924                 break;
 925             case 1:             /* distance to land */
 926                 if (own[px][py] != -1)
 927                     return d;
 928                 break;
 929             case 2:             /* distance to mountain */
 930                 if (elev[px][py] == INFINITY)
 931                     return d;
 932                 break;
 933             }
 934         } while (next_vector(d));
 935     }
 936     return d;
 937 }
 938
 939 #define ELEV elev[sectx[c][i]][secty[c][i]]
 940 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
 941 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
 942
 943 /* Decide where the mountains go
 944 */
 945 static void
 946 elevate_land(void)
 947 {
 948     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
 949         r, dk;
 950
 951     for (c = 0; c < ctot; ++c) {
 952         total = 0;
 953         ns = (c < nc) ? sc : isecs[c];
 954         nm = (pm * ns) / 100;
 955
 956 /* Place the mountains */
 957
 958         for (i = 0; i < ns; ++i) {
 959             dsea[i] = distance_to_sea();
 960             weight[i] = (total += (dsea[i] * dsea[i]));
 961         }
 962
 963         for (k = nm, mountain_search = 0;
 964              k && mountain_search < MOUNTAIN_SEARCH_MAX;
 965              ++mountain_search) {
 966             r = roll0(total);
 967             for (i = 0; i < ns; ++i)
 968                 if (r < weight[i] && ELEV == -INFINITY &&
 969                     (c >= nc ||
 970                      ((!(capx[c] == sectx[c][i] &&
 971                          capy[c] == secty[c][i])) &&
 972                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
 973                          capy[c] == secty[c][i]))))) {
 974                     ELEV = INFINITY;
 975                     break;
 976                 }
 977             --k;
 978         }
 979
 980 /* Elevate land that is not mountain and not capital */
 981
 982         for (i = 0; i < ns; ++i)
 983             dmoun[i] = distance_to_mountain();
 984         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
 985           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
 986           100 * INFINITY;
 987         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
 988             highest = -INFINITY;
 989             where = -1;
 990             for (i = 0; i < ns; ++i) {
 991                 if (ELEV != INFINITY &&
 992                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
 993                                     capy[c] == secty[c][i])) &&
 994                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
 995                                     capy[c] == secty[c][i]))))) {
 996                     h = 3 * (5 - dmoun[i]) + dsea[i];
 997                     if (h > highest) {
 998                         highest = h;
 999                         where = i;
1000                     }
1001                 }
1002             }
1003             if (where == -1)
1004                 break;
1005             newk = k / 100;
1006             if (newk >= HILLMIN && newk < PLATMIN)
1007                 newk = PLATMIN;
1008             if (newk < LANDMIN)
1009                 newk = LANDMIN;
1010             elev[sectx[c][where]][secty[c][where]] = newk;
1011             dsea[where] = -INFINITY;
1012             dmoun[where] = INFINITY;
1013         }
1014
1015 /* Elevate the mountains and capitals */
1016
1017         for (i = 0; i < ns; ++i) {
1018             if (ELEV == INFINITY) {
1019                 if (dsea[i] == 1)
1020                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1021                 else
1022                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1023                       roll0((256 - HIGHMIN) / 2);
1024             } else if (c < nc &&
1025                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1026                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1027                           capy[c] == secty[c][i]))))
1028                 ELEV = PLATMIN;
1029         }
1030     }
1031 }
1032
1033 #define distance_to_land() distance_to_what(x, y, 1)
1034
1035 static void
1036 elevate_sea(void)
1037 {
1038     int x, y;
1039
1040     for (y = 0; y < WORLD_Y; ++y) {
1041         for (x = y % 2; x < WORLD_X; x += 2) {
1042             if (elev[x][y] == -INFINITY)
1043                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1044         }
1045     }
1046 }
1047
1048 /****************************************************************************
1049   ADD THE RESOURCES
1050 ****************************************************************************/
1051
1052 static int
1053 set_fert(int e)
1054 {
1055     int fert = 0;
1056     if (e < LANDMIN)
1057         fert = LANDMIN - e + 40;
1058     else if (e < FERT_MAX)
1059         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1060     if (fert > 100)
1061         fert = 100;
1062     return fert;
1063 }
1064
1065 static int
1066 set_oil(int e)
1067 {
1068     int oil = 0;
1069     if (e < LANDMIN)
1070         oil = (LANDMIN - e) * 2 + roll0(2);
1071     else if (e <= OIL_MAX)
1072         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1073     if (oil > 100)
1074         oil = 100;
1075     return oil;
1076 }
1077
1078 static int
1079 set_iron(int e)
1080 {
1081     int iron = 0;
1082     if (e >= IRON_MIN && e < HIGHMIN)
1083         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1084     if (iron > 100)
1085         iron = 100;
1086     return iron;
1087 }
1088
1089 static int
1090 set_gold(int e)
1091 {
1092     int gold = 0;
1093     if (e >= GOLD_MIN) {
1094         if (e < HIGHMIN)
1095             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1096         else
1097             gold = 100 - 20 * HIGHMIN / e;
1098     }
1099     if (gold > 100)
1100         gold = 100;
1101     return gold;
1102 }
1103
1104 static int
1105 set_uran(int e)
1106 {
1107     int uran = 0;
1108     if (e >= URAN_MIN && e < HIGHMIN)
1109         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1110     if (uran > 100)
1111         uran = 100;
1112     return uran;
1113 }
1114
1115 static void
1116 add_resources(struct sctstr *sct)
1117 {
1118     sct->sct_fertil = set_fert(sct->sct_elev);
1119     sct->sct_oil = set_oil(sct->sct_elev);
1120     sct->sct_min = set_iron(sct->sct_elev);
1121     sct->sct_gmin = set_gold(sct->sct_elev);
1122     sct->sct_uran = set_uran(sct->sct_elev);
1123 }
1124
1125 /****************************************************************************
1126   DESIGNATE THE SECTORS
1127 ****************************************************************************/
1128
1129 static void
1130 write_sects(void)
1131 {
1132     struct sctstr *sct;
1133     int c, x, y, total;
1134
1135     for (y = 0; y < WORLD_Y; y++) {
1136         for (x = y % 2; x < WORLD_X; x += 2) {
1137             sct = getsectp(x, y);
1138             total = elev[x][y];
1139             if (total < LANDMIN) {
1140                 sct->sct_type = SCT_WATER;
1141             } else if (total < HILLMIN)
1142                 sct->sct_type = SCT_RURAL;
1143             else if (total < PLATMIN)
1144                 sct->sct_type = SCT_MOUNT;
1145             else if (total < HIGHMIN)
1146                 sct->sct_type = SCT_RURAL;
1147             else
1148                 sct->sct_type = SCT_MOUNT;
1149             sct->sct_elev = total;
1150             sct->sct_newtype = sct->sct_type;
1151             sct->sct_dterr = own[sct->sct_x][y] + 1;
1152             if (ORE)
1153                 add_resources(sct);
1154         }
1155     }
1156     if (AIRPORT_MARKER)
1157         for (c = 0; c < nc; ++c) {
1158             sct = getsectp(capx[c], capy[c]);
1159             sct->sct_type = SCT_AIRPT;
1160             sct->sct_newtype = SCT_AIRPT;
1161         }
1162     set_coastal_flags();
1163 }
1164
1165 /****************************************************************************
1166   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1167 ****************************************************************************/
1168 static void
1169 output(void)
1170 {
1171     int sx, sy, x, y;
1172
1173     if (quiet == 0) {
1174         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1175             y = YNORM(sy);
1176             puts("");
1177             if (y % 2)
1178                 printf(" ");
1179             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1180                 x = XNORM(sx);
1181                 if (own[x][y] == -1)
1182                     printf(". ");
1183                 else {
1184                     printf("%c ", map_symbol(x, y));
1185                 }
1186             }
1187         }
1188     }
1189     if (AIRPORT_MARKER)
1190         printf("\n\nEach continent is marked by a \"*\" on the map (to distinguish them from\n"
1191                "the islands).  You can redesignate these airfields to wilderness sectors\n"
1192                "one at a time, each time you add a new country to the game.\n");
1193 }
1194
1195 static int
1196 map_symbol(int x, int y)
1197 {
1198     int c;
1199
1200     for (c = 0; c < nc; ++c)
1201         if ((x == capx[c] && y == capy[c])
1202             || (x == new_x(capx[c] + 2) && y == capy[c]))
1203             return numletter[own[x][y] % 62];
1204     if ((elev[x][y] >= HILLMIN && elev[x][y] < PLATMIN)
1205         || elev[x][y] >= HIGHMIN)
1206         return '^';
1207     return own[x][y] >= nc ? '%' : '#';
1208 }
1209
1210 /*
1211  * Print a map to help visualize own[][].
1212  * This is for debugging.
1213  */
1214 void
1215 print_own_map(void)
1216 {
1217     int sx, sy, x, y;
1218
1219     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1220         y = YNORM(sy);
1221         printf("%4d ", sy);
1222         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1223             x = XNORM(sx);
1224             if ((x + y) & 1)
1225                 putchar(' ');
1226             else if (own[x][y] == -1)
1227                 putchar('.');
1228             else
1229                 putchar(numletter[own[x][y] % 62]);
1230         }
1231         putchar('\n');
1232     }
1233 }
1234
1235 /*
1236  * Print a map to help visualize elev[][].
1237  * This is for debugging.  It expects the terminal to understand
1238  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1239  */
1240 void
1241 print_elev_map(void)
1242 {
1243     int sx, sy, x, y, sat;
1244
1245     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1246         y = YNORM(sy);
1247         printf("%4d ", sy);
1248         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1249             x = XNORM(sx);
1250             if ((x + y) & 1)
1251                 putchar(' ');
1252             else if (!elev[x][y])
1253                 putchar(' ');
1254             else if (elev[x][y] < 0) {
1255                 sat = 256 + elev[x][y] * 2;
1256                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1257             } else if (elev[x][y] < HIGHMIN / 2) {
1258                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1259                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1260             } else if (elev[x][y] < HIGHMIN) {
1261                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1262                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1263             } else {
1264                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1265                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1266             }
1267         }
1268         putchar('\n');
1269     }
1270 }
1271
1272 /***************************************************************************
1273   WRITE A SCRIPT FOR PLACING CAPITALS
1274 ****************************************************************************/
1275 static int
1276 write_newcap_script(void)
1277 {
1278     int c;
1279     FILE *script = fopen(outfile, "w");
1280
1281     if (!script) {
1282         printf("fairland: error, unable to write to %s.\n", outfile);
1283         return 0;
1284     }
1285
1286     for (c = 0; c < nc; ++c) {
1287         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1288         if (AIRPORT_MARKER)
1289             fprintf(script, "des %d,%d -\n", capx[c], capy[c]);
1290         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1291     }
1292     fprintf(script, "add %d visitor visitor v\n", c + 1);
1293     fclose(script);
1294     return 1;
1295 }
1296
1297 static void
1298 qprint(const char *const fmt, ...)
1299 {
1300     va_list ap;
1301
1302     if (!quiet) {
1303         va_start(ap, fmt);
1304         vfprintf(stdout, fmt, ap);
1305         va_end(ap);
1306     }
1307 }
1308
1309 static void
1310 set_coastal_flags(void)
1311 {
1312     int i, j;
1313     struct sctstr *sp;
1314
1315     qprint("setting coastal flags...\n");
1316     for (i = 0; i < nc; ++i) {
1317         for (j = 0; j < sc; j++) {
1318             sp = getsectp(sectx[i][j], secty[i][j]);
1319             sp->sct_coastal = sectc[i][j];
1320         }
1321     }
1322     for (i = nc; i < nc + ni; ++i) {
1323         for (j = 0; j < isecs[i]; j++) {
1324             sp = getsectp(sectx[i][j], secty[i][j]);
1325             sp->sct_coastal = sectc[i][j];
1326         }
1327     }
1328 }