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

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