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