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

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