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