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;
 510
 511     for (i = 0; i < WORLD_X; ++i) {
 512         for (j = 0; j < WORLD_Y; ++j) {
 513             own[i][j] = -1;
 514         }
 515     }
 516 }
 517
 518 /****************************************************************************
 519   DRIFT THE CAPITALS UNTIL THEY ARE AS FAR AWAY FROM EACH OTHER AS POSSIBLE
 520 ****************************************************************************/
 521
 522 /* How isolated is capital j?
 523 */
 524 static int
 525 iso(int j, int newx, int newy)
 526 {
 527     int i, md, d = WORLD_X + WORLD_Y;
 528
 529     for (i = 0; i < nc; ++i) {
 530         if (i == j)
 531             continue;
 532         md = mapdist(capx[i], capy[i], newx, newy);
 533         if (md < d)
 534             d = md;
 535     }
 536
 537     return d;
 538 }
 539
 540 /*
 541  * Drift the capitals
 542  * Return 1 for a stable drift, 0 for an unstable one.
 543  */
 544 static int
 545 drift(void)
 546 {
 547     int turns, i;
 548
 549     for (i = 0; i < nc; i++) {
 550         capy[i] = (2 * i) / WORLD_X;
 551         capx[i] = (2 * i) % WORLD_X + capy[i] % 2;
 552         if (capy[i] >= WORLD_Y) {
 553             fprintf(stderr,
 554                     "%s: world not big enough for all the continents\n",
 555                     program_name);
 556             exit(1);
 557         }
 558     }
 559
 560     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 561         if (stable(turns))
 562             return 1;
 563         for (i = 0; i < nc; ++i)
 564             fl_move(i);
 565     }
 566     return 0;
 567 }
 568
 569 /*
 570  * Has the drift stabilized?
 571  * @turns is the number of turns so far.
 572  */
 573 static int
 574 stable(int turns)
 575 {
 576     static int mc[STABLE_CYCLE];
 577     int i, isod, d = 0, stab = 1;
 578
 579     if (!turns) {
 580         for (i = 0; i < STABLE_CYCLE; i++)
 581             mc[i] = i;
 582     }
 583
 584     if (turns <= DRIFT_BEFORE_CHECK)
 585         return 0;
 586
 587     for (i = 0; i < nc; ++i) {
 588         isod = iso(i, capx[i], capy[i]);
 589         if (isod > d)
 590             d = isod;
 591     }
 592
 593     for (i = 0; i < STABLE_CYCLE; ++i)
 594         if (d != mc[i])
 595             stab = 0;
 596
 597     mc[turns % STABLE_CYCLE] = d;
 598     return stab;
 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     if (own[newx][newy] != -1)
 666         return 0;
 667
 668     for (i = 1; i <= d; ++i) {
 669         for (j = 0; j < i; ++j)
 670             vector[j] = 0;
 671         do {
 672             px = newx;
 673             py = newy;
 674             for (j = 0; j < i; ++j) {
 675                 px = new_x(px + dirx[vector[j]]);
 676                 py = new_y(py + diry[vector[j]]);
 677             }
 678             if (own[px][py] != -1 &&
 679                 own[px][py] != c &&
 680                 (DISTINCT_ISLANDS || own[px][py] < nc))
 681                 return 0;
 682         } while (next_vector(i));
 683     }
 684     sectx[c][isecs[c]] = newx;
 685     secty[c][isecs[c]] = newy;
 686     isecs[c]++;
 687     own[newx][newy] = c;
 688     return 1;
 689 }
 690
 691 /* Move along the coast in a clockwise direction.
 692 */
 693
 694 static void
 695 next_coast(int c, int x, int y, int *xp, int *yp)
 696 {
 697     int i, nx, ny, wat = 0;
 698
 699     if (isecs[c] == 1) {
 700         *xp = x;
 701         *yp = y;
 702         return;
 703     }
 704
 705     for (i = 0; i < 12; ++i) {
 706         nx = new_x(x + dirx[i % 6]);
 707         ny = new_y(y + diry[i % 6]);
 708         if (own[nx][ny] == -1)
 709             wat = 1;
 710         if (wat && own[nx][ny] == c) {
 711             *xp = nx;
 712             *yp = ny;
 713             return;
 714         }
 715     }
 716 }
 717
 718 /* Choose a sector to grow from
 719 */
 720
 721 static int
 722 new_try(int c, int spike)
 723 {
 724     int secs = isecs[c];
 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 spike = roll0(100) < sp;
 750     int done, coast_search, try1, x, y, newx, newy, i, n, sx, sy;
 751
 752     if ((try1 = new_try(c, spike)) == -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 (n > 5 ||
 764                     (own[new_x(x+dirx[(i+5)%6])][new_y(y+diry[(i+5)%6])] == -1 &&
 765                      own[new_x(x+dirx[(i+1)%6])][new_y(y+diry[(i+1)%6])] == -1))
 766                     if (try_to_grow(c, newx, newy, c < nc ? di : id))
 767                         done = 1;
 768             }
 769         } else
 770             for (i = roll0(6), n = 0; n < 6 && !done; i = (i + 1) % 6, ++n) {
 771                 newx = new_x(x + dirx[i]);
 772                 newy = new_y(y + diry[i]);
 773                 if (try_to_grow(c, newx, newy, c < nc ? di : id))
 774                     done = 1;
 775             }
 776         next_coast(c, x, y, &x, &y);
 777         ++coast_search;
 778     } while (!done && coast_search < COAST_SEARCH_MAX &&
 779              (isecs[c] == 1 || x != sx || y != sy));
 780     return done;
 781 }
 782
 783 /*
 784  * Grow the continents.
 785  * Return 1 on success, 0 on error.
 786  */
 787 static int
 788 grow_continents(void)
 789 {
 790     int done = 1;
 791     int c, secs;
 792
 793     for (c = 0; c < nc; ++c) {
 794         isecs[c] = 0;
 795         if (!try_to_grow(c, capx[c], capy[c], di)
 796             || !try_to_grow(c, new_x(capx[c] + 2), capy[c], di)) {
 797             done = 0;
 798             continue;
 799         }
 800     }
 801
 802     if (!done) {
 803         qprint("No room for continents\n");
 804         return 0;
 805     }
 806
 807     for (secs = 2; secs < sc && done; secs++) {
 808         for (c = 0; c < nc; ++c) {
 809             find_coast(c);
 810             if (!grow_one_sector(c))
 811                 done = 0;
 812         }
 813     }
 814
 815     for (c = 0; c < nc; ++c)
 816         find_coast(c);
 817
 818     if (!done)
 819         qprint("Only managed to grow %d out of %d sectors.\n",
 820                secs - 1, sc);
 821     ctot = nc;
 822     return done;
 823 }
 824
 825 /****************************************************************************
 826   GROW THE ISLANDS
 827 ****************************************************************************/
 828
 829 /* Choose a place to start growing an island from
 830 */
 831 static int
 832 place_island(int c, int *xp, int *yp)
 833 {
 834     int d, sx, sy;
 835     int ssy = roll0(WORLD_Y);
 836     int ssx = new_x(roll0(WORLD_X / 2) * 2 + ssy % 2);
 837
 838     if (ssx > WORLD_X - 2)
 839         ssx = new_x(ssx + 2);
 840     for (d = di + id; d >= id; --d) {
 841         sx = ssx;
 842         sy = ssy;
 843         *xp = new_x(sx + 2);
 844         for (*yp = sy; *xp != sx || *yp != sy; *xp += 2) {
 845             if (*xp >= WORLD_X) {
 846                 *yp = new_y(*yp + 1);
 847                 *xp = *yp % 2;
 848                 if (*xp == sx && *yp == sy)
 849                     break;
 850             }
 851             if (try_to_grow(c, *xp, *yp, d))
 852                 return 1;
 853         }
 854     }
 855     return 0;
 856 }
 857
 858 /* Grow all the islands
 859 */
 860
 861 static void
 862 grow_islands(void)
 863 {
 864     int stunted_islands = 0;
 865     int c, secs, x, y, isiz;
 866
 867     for (c = nc; c < nc + ni; ++c) {
 868         if (!place_island(c, &x, &y)) {
 869             qprint("\nNo room for island #%d", c - nc + 1);
 870             break;
 871         }
 872
 873         isiz = roll(is) + roll0(is);
 874         for (secs = 1; secs < isiz; secs++) {
 875             find_coast(c);
 876             if (!grow_one_sector(c)) {
 877                 stunted_islands++;
 878                 break;
 879             }
 880         }
 881
 882         find_coast(c);
 883         qprint(" %d(%d)", c - nc + 1, secs);
 884         ctot++;
 885     }
 886
 887     if (stunted_islands)
 888         qprint("\n%d stunted island%s",
 889                stunted_islands, splur(stunted_islands));
 890 }
 891
 892 /****************************************************************************
 893   CREATE ELEVATIONS
 894 ****************************************************************************/
 895 static void
 896 create_elevations(void)
 897 {
 898     int i, j;
 899
 900     for (i = 0; i < WORLD_X; i++) {
 901         for (j = 0; j < WORLD_Y; j++)
 902             elev[i][j] = -INFINITY;
 903     }
 904     elevate_land();
 905     elevate_sea();
 906 }
 907
 908 /* Generic function for finding the distance to the closest sea, land, or
 909    mountain
 910 */
 911 static int
 912 distance_to_what(int x, int y, int flag)
 913 {
 914     int j, d, px, py;
 915
 916     for (d = 1; d < 5; ++d) {
 917         for (j = 0; j < d; ++j)
 918             vector[j] = 0;
 919         do {
 920             px = x;
 921             py = y;
 922             for (j = 0; j < d; ++j) {
 923                 px = new_x(px + dirx[vector[j]]);
 924                 py = new_y(py + diry[vector[j]]);
 925             }
 926             switch (flag) {
 927             case 0:             /* distance to sea */
 928                 if (own[px][py] == -1)
 929                     return d;
 930                 break;
 931             case 1:             /* distance to land */
 932                 if (own[px][py] != -1)
 933                     return d;
 934                 break;
 935             case 2:             /* distance to mountain */
 936                 if (elev[px][py] == INFINITY)
 937                     return d;
 938                 break;
 939             }
 940         } while (next_vector(d));
 941     }
 942     return d;
 943 }
 944
 945 #define ELEV elev[sectx[c][i]][secty[c][i]]
 946 #define distance_to_sea() (sectc[c][i]?1:distance_to_what(sectx[c][i], secty[c][i], 0))
 947 #define distance_to_mountain() distance_to_what(sectx[c][i], secty[c][i], 2)
 948
 949 /* Decide where the mountains go
 950 */
 951 static void
 952 elevate_land(void)
 953 {
 954     int i, mountain_search, k, c, total, ns, nm, highest, where, h, newk,
 955         r, dk;
 956
 957     for (c = 0; c < ctot; ++c) {
 958         total = 0;
 959         ns = isecs[c];
 960         nm = (pm * ns) / 100;
 961
 962 /* Place the mountains */
 963
 964         for (i = 0; i < ns; ++i) {
 965             dsea[i] = distance_to_sea();
 966             weight[i] = (total += (dsea[i] * dsea[i]));
 967         }
 968
 969         for (k = nm, mountain_search = 0;
 970              k && mountain_search < MOUNTAIN_SEARCH_MAX;
 971              ++mountain_search) {
 972             r = roll0(total);
 973             for (i = 0; i < ns; ++i)
 974                 if (r < weight[i] && ELEV == -INFINITY &&
 975                     (c >= nc ||
 976                      ((!(capx[c] == sectx[c][i] &&
 977                          capy[c] == secty[c][i])) &&
 978                       (!(new_x(capx[c] + 2) == sectx[c][i] &&
 979                          capy[c] == secty[c][i]))))) {
 980                     ELEV = INFINITY;
 981                     break;
 982                 }
 983             --k;
 984         }
 985
 986 /* Elevate land that is not mountain and not capital */
 987
 988         for (i = 0; i < ns; ++i)
 989             dmoun[i] = distance_to_mountain();
 990         dk = (ns - nm - ((c < nc) ? 3 : 1) > 0) ?
 991           (100 * (HIGHMIN - LANDMIN)) / (ns - nm - ((c < nc) ? 3 : 1)) :
 992           100 * INFINITY;
 993         for (k = 100 * (HIGHMIN - 1);; k -= dk) {
 994             highest = -INFINITY;
 995             where = -1;
 996             for (i = 0; i < ns; ++i) {
 997                 if (ELEV != INFINITY &&
 998                     (c >= nc || ((!(capx[c] == sectx[c][i] &&
 999                                     capy[c] == secty[c][i])) &&
1000                                  (!(new_x(capx[c] + 2) == sectx[c][i] &&
1001                                     capy[c] == secty[c][i]))))) {
1002                     h = 3 * (5 - dmoun[i]) + dsea[i];
1003                     if (h > highest) {
1004                         highest = h;
1005                         where = i;
1006                     }
1007                 }
1008             }
1009             if (where == -1)
1010                 break;
1011             newk = k / 100;
1012             if (newk >= HILLMIN && newk < PLATMIN)
1013                 newk = PLATMIN;
1014             if (newk < LANDMIN)
1015                 newk = LANDMIN;
1016             elev[sectx[c][where]][secty[c][where]] = newk;
1017             dsea[where] = -INFINITY;
1018             dmoun[where] = INFINITY;
1019         }
1020
1021 /* Elevate the mountains and capitals */
1022
1023         for (i = 0; i < ns; ++i) {
1024             if (ELEV == INFINITY) {
1025                 if (dsea[i] == 1)
1026                     ELEV = HILLMIN + roll0(PLATMIN - HILLMIN);
1027                 else
1028                     ELEV = HIGHMIN + roll0((256 - HIGHMIN) / 2) +
1029                       roll0((256 - HIGHMIN) / 2);
1030             } else if (c < nc &&
1031                        (((capx[c] == sectx[c][i] && capy[c] == secty[c][i])) ||
1032                         ((new_x(capx[c] + 2) == sectx[c][i] &&
1033                           capy[c] == secty[c][i]))))
1034                 ELEV = PLATMIN;
1035         }
1036     }
1037 }
1038
1039 #define distance_to_land() distance_to_what(x, y, 1)
1040
1041 static void
1042 elevate_sea(void)
1043 {
1044     int x, y;
1045
1046     for (y = 0; y < WORLD_Y; ++y) {
1047         for (x = y % 2; x < WORLD_X; x += 2) {
1048             if (elev[x][y] == -INFINITY)
1049                 elev[x][y] = -roll(distance_to_land() * 20 + 27);
1050         }
1051     }
1052 }
1053
1054 static int
1055 elev_to_sct_type(int elevation)
1056 {
1057     if (elevation < LANDMIN)
1058         return SCT_WATER;
1059     if (elevation < HILLMIN)
1060         return SCT_RURAL;
1061     if (elevation < PLATMIN)
1062         return SCT_MOUNT;
1063     if (elevation < HIGHMIN)
1064         return SCT_RURAL;
1065     return SCT_MOUNT;
1066 }
1067
1068 /****************************************************************************
1069   ADD THE RESOURCES
1070 ****************************************************************************/
1071
1072 static int
1073 set_fert(int e)
1074 {
1075     int fert = 0;
1076     if (e < LANDMIN)
1077         fert = LANDMIN - e + 40;
1078     else if (e < FERT_MAX)
1079         fert = (120 * (FERT_MAX - e)) / (FERT_MAX - LANDMIN);
1080     if (fert > 100)
1081         fert = 100;
1082     return fert;
1083 }
1084
1085 static int
1086 set_oil(int e)
1087 {
1088     int oil = 0;
1089     if (e < LANDMIN)
1090         oil = (LANDMIN - e) * 2 + roll0(2);
1091     else if (e <= OIL_MAX)
1092         oil = (120 * (OIL_MAX - e + 1)) / (OIL_MAX - LANDMIN + 1);
1093     if (oil > 100)
1094         oil = 100;
1095     return oil;
1096 }
1097
1098 static int
1099 set_iron(int e)
1100 {
1101     int iron = 0;
1102     if (e >= IRON_MIN && e < HIGHMIN)
1103         iron = (120 * (e - IRON_MIN + 1)) / (HIGHMIN - IRON_MIN);
1104     if (iron > 100)
1105         iron = 100;
1106     return iron;
1107 }
1108
1109 static int
1110 set_gold(int e)
1111 {
1112     int gold = 0;
1113     if (e >= GOLD_MIN) {
1114         if (e < HIGHMIN)
1115             gold = (80 * (e - GOLD_MIN + 1)) / (HIGHMIN - GOLD_MIN);
1116         else
1117             gold = 100 - 20 * HIGHMIN / e;
1118     }
1119     if (gold > 100)
1120         gold = 100;
1121     return gold;
1122 }
1123
1124 static int
1125 set_uran(int e)
1126 {
1127     int uran = 0;
1128     if (e >= URAN_MIN && e < HIGHMIN)
1129         uran = (120 * (e - URAN_MIN + 1)) / (HIGHMIN - URAN_MIN);
1130     if (uran > 100)
1131         uran = 100;
1132     return uran;
1133 }
1134
1135 static void
1136 add_resources(struct sctstr *sct)
1137 {
1138     sct->sct_fertil = set_fert(sct->sct_elev);
1139     sct->sct_oil = set_oil(sct->sct_elev);
1140     sct->sct_min = set_iron(sct->sct_elev);
1141     sct->sct_gmin = set_gold(sct->sct_elev);
1142     sct->sct_uran = set_uran(sct->sct_elev);
1143 }
1144
1145 /****************************************************************************
1146   DESIGNATE THE SECTORS
1147 ****************************************************************************/
1148
1149 static void
1150 write_sects(void)
1151 {
1152     struct sctstr *sct;
1153     int x, y;
1154
1155     for (y = 0; y < WORLD_Y; y++) {
1156         for (x = y % 2; x < WORLD_X; x += 2) {
1157             sct = getsectp(x, y);
1158             sct->sct_elev = elev[x][y];
1159             sct->sct_type = elev_to_sct_type(elev[x][y]);
1160             sct->sct_newtype = sct->sct_type;
1161             sct->sct_dterr = own[sct->sct_x][y] + 1;
1162             add_resources(sct);
1163         }
1164     }
1165     set_coastal_flags();
1166 }
1167
1168 /****************************************************************************
1169   PRINT A PICTURE OF THE MAP TO YOUR SCREEN
1170 ****************************************************************************/
1171 static void
1172 output(void)
1173 {
1174     int sx, sy, x, y, c, type;
1175
1176     if (quiet == 0) {
1177         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1178             y = YNORM(sy);
1179             puts("");
1180             if (y % 2)
1181                 printf(" ");
1182             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1183                 x = XNORM(sx);
1184                 c = own[x][y];
1185                 type = elev_to_sct_type(elev[x][y]);
1186                 if (type == SCT_WATER)
1187                     printf(". ");
1188                 else if (type == SCT_MOUNT)
1189                     printf("^ ");
1190                 else if (c >= nc)
1191                     printf("%% ");
1192                 else {
1193                     assert(0 <= c && c < nc);
1194                     if ((x == capx[c] || x == new_x(capx[c] + 2))
1195                         && y == capy[c])
1196                         printf("%c ", numletter[c % 62]);
1197                     else
1198                         printf("# ");
1199                 }
1200             }
1201         }
1202     }
1203 }
1204
1205 /*
1206  * Print a map to help visualize own[][].
1207  * This is for debugging.
1208  */
1209 void
1210 print_own_map(void)
1211 {
1212     int sx, sy, x, y;
1213
1214     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1215         y = YNORM(sy);
1216         printf("%4d ", sy);
1217         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1218             x = XNORM(sx);
1219             if ((x + y) & 1)
1220                 putchar(' ');
1221             else if (own[x][y] == -1)
1222                 putchar('.');
1223             else
1224                 putchar(numletter[own[x][y] % 62]);
1225         }
1226         putchar('\n');
1227     }
1228 }
1229
1230 /*
1231  * Print a map to help visualize elev[][].
1232  * This is for debugging.  It expects the terminal to understand
1233  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1234  */
1235 void
1236 print_elev_map(void)
1237 {
1238     int sx, sy, x, y, sat;
1239
1240     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1241         y = YNORM(sy);
1242         printf("%4d ", sy);
1243         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1244             x = XNORM(sx);
1245             if ((x + y) & 1)
1246                 putchar(' ');
1247             else if (!elev[x][y])
1248                 putchar(' ');
1249             else if (elev[x][y] < 0) {
1250                 sat = 256 + elev[x][y] * 2;
1251                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1252             } else if (elev[x][y] < HIGHMIN / 2) {
1253                 sat = (HIGHMIN / 2 - elev[x][y]) * 4;
1254                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1255             } else if (elev[x][y] < HIGHMIN) {
1256                 sat = 128 + (HIGHMIN - elev[x][y]) * 2;
1257                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1258             } else {
1259                 sat = 128 + (elev[x][y] - HIGHMIN) * 4 / 5;
1260                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1261             }
1262         }
1263         putchar('\n');
1264     }
1265 }
1266
1267 /***************************************************************************
1268   WRITE A SCRIPT FOR PLACING CAPITALS
1269 ****************************************************************************/
1270 static int
1271 write_newcap_script(void)
1272 {
1273     int c;
1274     FILE *script = fopen(outfile, "w");
1275
1276     if (!script) {
1277         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1278                 program_name, outfile, strerror(errno));
1279         return 0;
1280     }
1281
1282     for (c = 0; c < nc; ++c) {
1283         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1284         fprintf(script, "newcap %d %d,%d\n", c + 1, capx[c], capy[c]);
1285     }
1286     fprintf(script, "add %d visitor visitor v\n", c + 1);
1287     fclose(script);
1288     return 1;
1289 }
1290
1291 static void
1292 qprint(const char *const fmt, ...)
1293 {
1294     va_list ap;
1295
1296     if (!quiet) {
1297         va_start(ap, fmt);
1298         vfprintf(stdout, fmt, ap);
1299         va_end(ap);
1300     }
1301 }
1302
1303 static void
1304 set_coastal_flags(void)
1305 {
1306     int i, j;
1307     struct sctstr *sp;
1308
1309     for (i = 0; i < nc + ni; ++i) {
1310         for (j = 0; j < isecs[i]; j++) {
1311             sp = getsectp(sectx[i][j], secty[i][j]);
1312             sp->sct_coastal = sectc[i][j];
1313         }
1314     }
1315 }