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