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, until they have the
  49  * specified size.
  50  *
  51  * Growth uses weighted random sampling to pick one sector from the
  52  * set of adjacent sea sectors that aren't too close to another
  53  * continent.  Growth operates in spiking mode with a chance given by
  54  * the spike percentage.  When "spiking", a sector's weight increases
  55  * with number of adjacent sea sectors.  This directs the growth away
  56  * from land, resulting in spikes.  When not spiking, the weight
  57  * increases with the number of adjacent land sectors.  This makes the
  58  * island more rounded.
  59  *
  60  * If growing fails due to lack of room, start over.  If it fails too
  61  * many times, give up and terminate unsuccessfully.
  62  *
  63  * 3. Place and grow additional islands
  64  *
  65  * Each continent has a "sphere of influence": the set of sectors
  66  * closer to it than to any other continent.  Each island is entirely
  67  * in one such sphere, and each sphere contains the same number of
  68  * islands with the same sizes.
  69  *
  70  * First, split the specified number of island sectors per continent
  71  * randomly into the island sizes.  Sort by size so that larger
  72  * islands are grown before smaller ones, to give the large ones the
  73  * best chance to grow to their planned size.
  74  *
  75  * Then place one island's first sector into each sphere, using
  76  * weighted random sampling with weights favoring sectors away from
  77  * land and other spheres.  Add one sector to each island in turn,
  78  * until they have the intended size.  Repeat until the specified
  79  * number of islands has been grown.
  80  *
  81  * If placement fails due to lack of room, start over, just like for
  82  * continents.
  83  *
  84  * Growing works as for continents, except the minimum distance for
  85  * additional islands applies, and growing simply stops when any of
  86  * the islands being grown lacks the room to grow further.  The number
  87  * of sectors not grown carries over to the next island size.
  88  *
  89  * 4. Compute elevation
  90  *
  91  * First, use a simple random hill algorithm to assign raw elevations:
  92  * initialize elevation to zero, then randomly raise circular hills on
  93  * land / lower circular depressions at sea.  Their size and height
  94  * depends on the distance to the coast.
  95  *
  96  * Then, elevate islands one after the other.
  97  *
  98  * Set the capitals' elevation to a fixed value.  Process the
  99  * remaining sectors in order of increasing raw elevation, first
 100  * non-mountains, then mountains.  Non-mountain elevation starts at 1,
 101  * and increases linearly to just below "high" elevation.  Mountain
 102  * elevation starts at "high" elevation, and increases linearly.
 103  *
 104  * This gives islands of the same size the same set of elevations.
 105  * Larger islands get more and taller mountains.
 106  *
 107  * Finally, elevate sea: normalize the raw elevations to [-127:-1].
 108  *
 109  * 5. Set resources
 110  *
 111  * Sector resources are simple functions of elevation.  You can alter
 112  * iron_conf[], gold_conf[], fert_conf[], oil_conf[], and uran_conf[]
 113  * to customize them.
 114  */
 115
 116 #include <config.h>
 117
 118 #include <assert.h>
 119 #include <errno.h>
 120 #include <limits.h>
 121 #include <stdarg.h>
 122 #include <stdio.h>
 123 #include <unistd.h>
 124 #include "chance.h"
 125 #include "optlist.h"
 126 #include "path.h"
 127 #include "prototypes.h"
 128 #include "sect.h"
 129 #include "version.h"
 130 #include "xy.h"
 131
 132 /*
 133  * Number of retries when growing land fails
 134  */
 135 #define NUMTRIES 10
 136
 137 /* do not change these defines */
 138 #define LANDMIN         1       /* plate altitude for normal land */
 139 #define PLATMIN         36      /* plate altitude for plateau */
 140 #define HIGHMIN         98      /* plate altitude for mountains */
 141
 142 /*
 143  * Resource configuration
 144
 145  * Resources are determined by elevation.  The map from elevation to
 146  * resource is defined as a linear interpolation of resource data
 147  * points (elev, res) defined in the tables below.  Elevations range
 148  * from -127 to 127, and resource values from 0 to 100.
 149  */
 150
 151 struct resource_point {
 152     int elev, res;
 153 };
 154
 155 struct resource_point iron_conf[] = {
 156     { -127, 0 },
 157     { 21, 0 },
 158     { 85, 100 },
 159     { HIGHMIN - 1, 100 },
 160     { HIGHMIN , 0 },
 161     { 127, 0 } };
 162
 163 struct resource_point gold_conf[] = {
 164     { -127, 0 },
 165     { 35, 0 },
 166     { HIGHMIN - 1, 80 },
 167     { HIGHMIN, 80 },
 168     { 127, 85 } };
 169
 170 struct resource_point fert_conf[] = {
 171     { -127, 100 },
 172     { -59, 100 },
 173     { LANDMIN - 1, 41 },
 174     { LANDMIN, 100 },
 175     { 10, 100 },
 176     { 56, 0 },
 177     { 127, 0 } };
 178
 179 struct resource_point oil_conf[] = {
 180     { -127, 100 },
 181     { -49, 100 },
 182     { LANDMIN - 1, 2 },
 183     { LANDMIN, 100 },
 184     { 6, 100 },
 185     { 34, 0 },
 186     { 127, 0 } };
 187
 188 struct resource_point uran_conf[] = {
 189     { -127, 0 },
 190     { 55, 0 },
 191     { 90, 100 },
 192     { 97, 100 },
 193     { 98, 0 },
 194     { 127, 0 } };
 195
 196 /*
 197  * Program arguments and options
 198  */
 199 static char *program_name;
 200 static int nc, sc;              /* number and size of continents */
 201 static int ni, is;              /* number and size of islands */
 202 #define DEFAULT_SPIKE 10
 203 static int sp = DEFAULT_SPIKE;  /* spike percentage */
 204 #define DEFAULT_MOUNTAIN 0
 205 static int pm = DEFAULT_MOUNTAIN; /* mountain percentage */
 206 #define DEFAULT_CONTDIST 2
 207 static int di = DEFAULT_CONTDIST; /* min. distance between continents */
 208 #define DEFAULT_ISLDIST 1
 209 static int id = DEFAULT_ISLDIST;  /* ... continents and islands */
 210 /* don't let the islands crash into each other.
 211    1 = don't merge, 0 = merge. */
 212 static int DISTINCT_ISLANDS = 1;
 213 static int quiet;
 214 #define DEFAULT_OUTFILE_NAME "newcap_script"
 215 static const char *outfile = DEFAULT_OUTFILE_NAME;
 216
 217 #define STABLE_CYCLE 4          /* stability required for perturbed capitals */
 218 #define DRIFT_BEFORE_CHECK ((WORLD_X + WORLD_Y)/2)
 219 #define DRIFT_MAX ((WORLD_X + WORLD_Y)*2)
 220
 221 #define new_x(newx) (((newx) + WORLD_X) % WORLD_X)
 222 #define new_y(newy) (((newy) + WORLD_Y) % WORLD_Y)
 223
 224 struct xy {
 225     coord x, y;
 226 };
 227
 228 /*
 229  * Capital locations
 230  * The i-th capital is at cap[i].
 231  */
 232 static struct xy *cap;
 233
 234 /*
 235  * Island sizes
 236  * isecs[i] is the size of the i-th island.
 237  */
 238 static int *isecs;
 239
 240 /*
 241  * Island sectors
 242  * The i-th island's j-th sector is at sect[i][j].
 243  */
 244 struct xy **sect;
 245
 246 /*
 247  * Island at x, y
 248  * own[XYOFFSET(x, y)] is x,y's island number, -1 if water.
 249  */
 250 static short *own;
 251
 252 /*
 253  * Adjacent land sectors
 254  * adj_land[XYOFFSET(x, y)] bit d is set exactly when the sector next
 255  * to x, y in direction d is land.
 256  */
 257 static unsigned char *adj_land;
 258
 259 /*
 260  * Elevation at x,y
 261  * elev[XYOFFSET(x, y)] is x,y's elevation.
 262  */
 263 static short *elev;
 264
 265 /*
 266  * Exclusive zones
 267  * Each island is surrounded by an exclusive zone where only it may
 268  * grow.  The width of the zone depends on minimum distances.
 269  * While growing continents, it is @di sectors wide.
 270  * While growing additional islands, it is @id sectors wide.
 271  * DISTINCT_ISLANDS nullifies the exclusive zone then.
 272  * xzone[XYOFFSET(x, y)] is -1 when the sector is in no exclusive
 273  * zone, a (non-negative) island number when it is in that island's
 274  * exclusive zone and no other, and -2 when it is in multiple
 275  * exclusive zones.
 276  */
 277 static short *xzone;
 278
 279 /*
 280  * Set of sectors seen already
 281  * Increment @cur_seen to empty the set of sectors seen, set
 282  * seen[XYOFFSET(x, y)] to @cur_seen to add x,y to the set.
 283  */
 284 static unsigned *seen;
 285 static unsigned cur_seen;
 286
 287 /*
 288  * Closest continent and "distance"
 289  * closest[XYOFFSET(x, y)] is the closest continent's number.
 290  * distance[] is complicated; see init_spheres_of_influence() and
 291  * init_distance_to_coast().
 292  */
 293 static natid *closest;
 294 static unsigned short *distance;
 295
 296 /*
 297  * Queue for breadth-first search
 298  */
 299 static int *bfs_queue;
 300 static int bfs_queue_head, bfs_queue_tail;
 301
 302 static const char *numletter =
 303     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 304
 305 static void print_vars(void);
 306 static void qprint(const char * const fmt, ...)
 307     ATTRIBUTE((format (printf, 1, 2)));
 308 static void help(char *);
 309 static void usage(void);
 310 static void parse_args(int argc, char *argv[]);
 311 static void allocate_memory(void);
 312 static void init(void);
 313 static int drift(void);
 314 static int stable(int);
 315 static void drift_capital(int);
 316 static int grow_continents(void);
 317 static int grow_islands(void);
 318 static void create_elevations(void);
 319 static void elevate_prep(void);
 320 static void elevate_land(void);
 321 static void elevate_sea(void);
 322 static void write_sects(void);
 323 static void output(void);
 324 static int write_newcap_script(void);
 325
 326 /* Debugging aids: */
 327 void print_own_map(void);
 328 void print_xzone_map(void);
 329 void print_closest_map(void);
 330 void print_distance_map(void);
 331 void print_elev_map(void);
 332
 333
 334 int
 335 main(int argc, char *argv[])
 336 {
 337     int opt;
 338     char *config_file = NULL;
 339     int try, done;
 340     unsigned rnd_seed = 0;
 341     int seed_set = 0;
 342
 343     program_name = argv[0];
 344
 345     while ((opt = getopt(argc, argv, "e:hiqR:s:v")) != EOF) {
 346         switch (opt) {
 347         case 'e':
 348             config_file = optarg;
 349             break;
 350         case 'i':
 351             DISTINCT_ISLANDS = 0;
 352             break;
 353         case 'q':
 354             quiet = 1;
 355             break;
 356         case 'R':
 357             rnd_seed = strtoul(optarg, NULL, 10);
 358             seed_set = 1;
 359             break;
 360         case 's':
 361             outfile = optarg;
 362             break;
 363         case 'h':
 364             usage();
 365             exit(0);
 366         case 'v':
 367             printf("%s\n\n%s", version, legal);
 368             exit(0);
 369         default:
 370             help(NULL);
 371             exit(1);
 372         }
 373     }
 374
 375     if (!seed_set)
 376         rnd_seed = pick_seed();
 377     seed_prng(rnd_seed);
 378     empfile_init();
 379     if (emp_config(config_file) < 0)
 380         exit(1);
 381     empfile_fixup();
 382
 383     parse_args(argc - optind, argv + optind);
 384
 385     allocate_memory();
 386     print_vars();
 387
 388     qprint("\n        #*# ...fairland rips open a rift in the datumplane... #*#\n\n");
 389     qprint("seed is %u\n", rnd_seed);
 390     try = 0;
 391     do {
 392         init();
 393         if (try)
 394             qprint("\ntry #%d (out of %d)...\n", try + 1, NUMTRIES);
 395         qprint("placing capitals...\n");
 396         if (!drift())
 397             qprint("unstable drift\n");
 398         qprint("growing continents...\n");
 399         done = grow_continents();
 400         if (!done)
 401             continue;
 402         qprint("growing islands:");
 403         done = grow_islands();
 404     } while (!done && ++try < NUMTRIES);
 405     if (!done) {
 406         fprintf(stderr, "%s: world not large enough for this much land\n",
 407                 program_name);
 408         exit(1);
 409     }
 410     qprint("elevating land...\n");
 411     create_elevations();
 412
 413     qprint("writing to sectors file...\n");
 414     if (!write_newcap_script())
 415         exit(1);
 416     if (chdir(gamedir)) {
 417         fprintf(stderr, "%s: can't chdir to %s (%s)\n",
 418                 program_name, gamedir, strerror(errno));
 419         exit(1);
 420     }
 421     if (!ef_open(EF_SECTOR, EFF_MEM | EFF_NOTIME))
 422         exit(1);
 423     write_sects();
 424     if (!ef_close(EF_SECTOR))
 425         exit(1);
 426
 427     output();
 428     qprint("\n\nA script for adding all the countries can be found in \"%s\".\n",
 429            outfile);
 430     exit(0);
 431 }
 432
 433 static void
 434 print_vars(void)
 435 {
 436     if (quiet)
 437         return;
 438     puts("Creating a planet with:\n");
 439     printf("%d continents\n", nc);
 440     printf("continent size: %d\n", sc);
 441     printf("number of islands: %d\n", ni);
 442     printf("average size of islands: %d\n", is);
 443     printf("spike: %d%%\n", sp);
 444     printf("%d%% of land is mountain (each continent will have %d mountains)\n",
 445            pm, (pm * sc) / 100);
 446     printf("minimum distance between continents: %d\n", di);
 447     printf("minimum distance from islands to continents: %d\n", id);
 448     printf("World dimensions: %dx%d\n", WORLD_X, WORLD_Y);
 449 }
 450
 451 static void
 452 qprint(const char *const fmt, ...)
 453 {
 454     va_list ap;
 455
 456     if (!quiet) {
 457         va_start(ap, fmt);
 458         vfprintf(stdout, fmt, ap);
 459         va_end(ap);
 460     }
 461 }
 462
 463 static void
 464 help(char *complaint)
 465 {
 466     if (complaint)
 467         fprintf(stderr, "%s: %s\n", program_name, complaint);
 468     fprintf(stderr, "Try -h for help.\n");
 469 }
 470
 471 static void
 472 usage(void)
 473 {
 474     printf("Usage: %s [OPTION]... NC SC [NI] [IS] [SP] [PM] [DI] [ID]\n"
 475            "  -e CONFIG-FILE  configuration file\n"
 476            "                  (default %s)\n"
 477            "  -i              islands may merge\n"
 478            "  -q              quiet\n"
 479            "  -R SEED         seed for random number generator\n"
 480            "  -s SCRIPT       name of script to create (default %s)\n"
 481            "  -h              display this help and exit\n"
 482            "  -v              display version information and exit\n"
 483            "  NC              number of continents\n"
 484            "  SC              continent size\n"
 485            "  NI              number of islands (default NC)\n"
 486            "  IS              average island size (default SC/2)\n"
 487            "  SP              spike percentage: 0 = round, 100 = snake (default %d)\n"
 488            "  PM              percentage of land that is mountain (default %d)\n"
 489            "  DI              minimum distance between continents (default %d)\n"
 490            "  ID              minimum distance from islands to continents (default %d)\n",
 491            program_name, dflt_econfig, DEFAULT_OUTFILE_NAME,
 492            DEFAULT_SPIKE, DEFAULT_MOUNTAIN, DEFAULT_CONTDIST, DEFAULT_ISLDIST);
 493 }
 494
 495 static void
 496 parse_args(int argc, char *argv[])
 497 {
 498     int dist_max = mapdist(0, 0, WORLD_X / 2, WORLD_Y / 2);
 499
 500     if (argc < 2) {
 501         help("missing arguments");
 502         exit(1);
 503     }
 504     if (argc > 8) {
 505         help("too many arguments");
 506         exit(1);
 507     }
 508     nc = atoi(argv[0]);
 509     if (nc < 1) {
 510         fprintf(stderr, "%s: number of continents must be > 0\n",
 511                 program_name);
 512         exit(1);
 513     }
 514
 515     sc = atoi(argv[1]);
 516     if (sc < 2) {
 517         fprintf(stderr, "%s: size of continents must be > 1\n",
 518                 program_name);
 519         exit(1);
 520     }
 521
 522     ni = nc;
 523     is = sc / 2;
 524
 525     if (argc > 2)
 526         ni = atoi(argv[2]);
 527     if (ni < 0) {
 528         fprintf(stderr, "%s: number of islands must be >= 0\n",
 529                 program_name);
 530         exit(1);
 531     }
 532     if (ni % nc) {
 533         fprintf(stderr, "%s: number of islands must be a multiple of"
 534                 " the number of continents\n",
 535                 program_name);
 536         exit(1);
 537     }
 538
 539     if (argc > 3)
 540         is = atoi(argv[3]);
 541     if (is < 1) {
 542         fprintf(stderr, "%s: size of islands must be > 0\n",
 543                 program_name);
 544         exit(1);
 545     }
 546
 547     if (argc > 4)
 548         sp = atoi(argv[4]);
 549     if (sp < 0 || sp > 100) {
 550         fprintf(stderr,
 551                 "%s: spike percentage must be between 0 and 100\n",
 552                 program_name);
 553         exit(1);
 554     }
 555
 556     if (argc > 5)
 557         pm = atoi(argv[5]);
 558     if (pm < 0 || pm > 100) {
 559         fprintf(stderr,
 560                 "%s: mountain percentage must be between 0 and 100\n",
 561                 program_name);
 562         exit(1);
 563     }
 564
 565     if (argc > 6)
 566         di = atoi(argv[6]);
 567     if (di < 0) {
 568         fprintf(stderr, "%s: distance between continents must be >= 0\n",
 569                 program_name);
 570         exit(1);
 571     }
 572     if (di > dist_max) {
 573         fprintf(stderr, "%s: distance between continents too large\n",
 574                 program_name);
 575         exit(1);
 576     }
 577
 578     if (argc > 7)
 579         id = atoi(argv[7]);
 580     if (id < 0) {
 581         fprintf(stderr,
 582                 "%s: distance from islands to continents must be >= 0\n",
 583                 program_name);
 584         exit(1);
 585     }
 586     if (id > dist_max) {
 587         fprintf(stderr,
 588                 "%s: distance from islands to continents too large\n",
 589                 program_name);
 590         exit(1);
 591     }
 592 }
 593
 594
 595 /*
 596  * Variable initialization
 597  */
 598
 599 static void
 600 allocate_memory(void)
 601 {
 602     int i;
 603
 604     cap = malloc(nc * sizeof(*cap));
 605     own = malloc(WORLD_SZ() * sizeof(*own));
 606     adj_land = malloc(WORLD_SZ() * sizeof(*adj_land));
 607     elev = calloc(WORLD_SZ(), sizeof(*elev));
 608     xzone = malloc(WORLD_SZ() * sizeof(*xzone));
 609     seen = calloc(WORLD_SZ(), sizeof(*seen));
 610     closest = malloc(WORLD_SZ() * sizeof(*closest));
 611     distance = malloc(WORLD_SZ() * sizeof(*distance));
 612     bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue));
 613     isecs = calloc(nc + ni, sizeof(int));
 614     sect = malloc((nc + ni) * sizeof(*sect));
 615     for (i = 0; i < nc; i++)
 616         sect[i] = malloc(sc * sizeof(**sect));
 617     for (i = nc; i < nc + ni; i++)
 618         sect[i] = malloc(is * 2 * sizeof(**sect));
 619 }
 620
 621 static void
 622 init(void)
 623 {
 624     int i;
 625
 626     for (i = 0; i < WORLD_SZ(); i++)
 627         own[i] = -1;
 628     memset(adj_land, 0, WORLD_SZ() * sizeof(*adj_land));
 629 }
 630
 631
 632 /*
 633  * Drift the capitals until they are as far away from each other as possible
 634  */
 635
 636 /*
 637  * How isolated is capital @j at @newx,@newy?
 638  * Return the distance to the closest other capital.
 639  */
 640 static int
 641 iso(int j, int newx, int newy)
 642 {
 643     int d = INT_MAX;
 644     int i, md;
 645
 646     for (i = 0; i < nc; ++i) {
 647         if (i == j)
 648             continue;
 649         md = mapdist(cap[i].x, cap[i].y, newx, newy);
 650         if (md < d)
 651             d = md;
 652     }
 653
 654     return d;
 655 }
 656
 657 /*
 658  * Drift the capitals
 659  * Return 1 for a stable drift, 0 for an unstable one.
 660  */
 661 static int
 662 drift(void)
 663 {
 664     int turns, i;
 665
 666     for (i = 0; i < nc; i++) {
 667         cap[i].y = (2 * i) / WORLD_X;
 668         cap[i].x = (2 * i) % WORLD_X + cap[i].y % 2;
 669         if (cap[i].y >= WORLD_Y) {
 670             fprintf(stderr,
 671                     "%s: world not big enough for all the continents\n",
 672                     program_name);
 673             exit(1);
 674         }
 675     }
 676
 677     for (turns = 0; turns < DRIFT_MAX; ++turns) {
 678         if (stable(turns))
 679             return 1;
 680         for (i = 0; i < nc; ++i)
 681             drift_capital(i);
 682     }
 683     return 0;
 684 }
 685
 686 /*
 687  * Has the drift stabilized?
 688  * @turns is the number of turns so far.
 689  */
 690 static int
 691 stable(int turns)
 692 {
 693     static int mc[STABLE_CYCLE];
 694     int i, isod, d = 0, stab = 1;
 695
 696     if (!turns) {
 697         for (i = 0; i < STABLE_CYCLE; i++)
 698             mc[i] = i;
 699     }
 700
 701     if (turns <= DRIFT_BEFORE_CHECK)
 702         return 0;
 703
 704     for (i = 0; i < nc; ++i) {
 705         isod = iso(i, cap[i].x, cap[i].y);
 706         if (isod > d)
 707             d = isod;
 708     }
 709
 710     for (i = 0; i < STABLE_CYCLE; ++i)
 711         if (d != mc[i])
 712             stab = 0;
 713
 714     mc[turns % STABLE_CYCLE] = d;
 715     return stab;
 716 }
 717
 718 /*
 719  * Drift capital @j.
 720  * Move it to an adjacent sector where it is at least as isolated.
 721 */
 722 static void
 723 drift_capital(int j)
 724 {
 725     int dir, i, newx, newy;
 726
 727     dir = DIR_L + roll0(6);
 728     for (i = 0; i < 6; i++) {
 729         if (dir > DIR_LAST)
 730             dir -= 6;
 731         newx = new_x(cap[j].x + diroff[dir][0]);
 732         newy = new_y(cap[j].y + diroff[dir][1]);
 733         dir++;
 734         if (iso(j, newx, newy) >= iso(j, cap[j].x, cap[j].y)) {
 735             cap[j].x = newx;
 736             cap[j].y = newy;
 737             return;
 738         }
 739     }
 740 }
 741
 742
 743 /*
 744  * Grow land
 745  */
 746
 747 static int
 748 is_coastal(int x, int y)
 749 {
 750     return adj_land[XYOFFSET(x, y)]
 751         != (1u << (DIR_LAST + 1)) - (1u << DIR_FIRST);
 752 }
 753
 754 struct hexagon_iter {
 755     int dir, i, n;
 756 };
 757
 758 /*
 759  * Start iterating around @x0,@y0 at distance @d.
 760  * Set *x,*y to coordinates of the first sector.
 761  */
 762 static inline void
 763 hexagon_first(struct hexagon_iter *iter, int x0, int y0, int n,
 764               int *x, int *y)
 765 {
 766     *x = new_x(x0 - 2 * n);
 767     *y = y0;
 768     iter->dir = DIR_FIRST;
 769     iter->i = 0;
 770     iter->n = n;
 771 }
 772
 773 /*
 774  * Continue iteration started with hexagon_first().
 775  * Set *x,*y to coordinates of the next sector.
 776  * Return whether we're back at the first sector, i.e. iteration is
 777  * complete.
 778  */
 779 static inline int
 780 hexagon_next(struct hexagon_iter *iter, int *x, int *y)
 781 {
 782     *x = new_x(*x + diroff[iter->dir][0]);
 783     *y = new_y(*y + diroff[iter->dir][1]);
 784     iter->i++;
 785     if (iter->i == iter->n) {
 786         iter->i = 0;
 787         iter->dir++;
 788     }
 789     return iter->dir <= DIR_LAST;
 790 }
 791
 792 /*
 793  * Is @x,@y in no exclusive zone other than perhaps @c's?
 794  */
 795 static int
 796 xzone_ok(int c, int x, int y)
 797 {
 798     int off = XYOFFSET(x, y);
 799
 800     return xzone[off] == c || xzone[off] == -1;
 801 }
 802
 803 /*
 804  * Add sectors within distance @dist of @x,@y to @c's exclusive zone.
 805  */
 806 static void
 807 xzone_around_sector(int c, int x, int y, int dist)
 808 {
 809     int d, x1, y1, off;
 810     struct hexagon_iter hexit;
 811
 812     assert(xzone_ok(c, x, y));
 813
 814     xzone[XYOFFSET(x, y)] = c;
 815     for (d = 1; d <= dist; d++) {
 816         hexagon_first(&hexit, x, y, d, &x1, &y1);
 817         do {
 818             off = XYOFFSET(x1, y1);
 819             if (xzone[off] == -1)
 820                 xzone[off] = c;
 821             else if (xzone[off] != c)
 822                 xzone[off] = -2;
 823         } while (hexagon_next(&hexit, &x1, &y1));
 824     }
 825 }
 826
 827 /*
 828  * Add sectors within distance @dist to island @c's exclusive zone.
 829  */
 830 static void
 831 xzone_around_island(int c, int dist)
 832 {
 833     int i;
 834
 835     for (i = 0; i < isecs[c]; i++)
 836         xzone_around_sector(c, sect[c][i].x, sect[c][i].y, dist);
 837 }
 838
 839 /*
 840  * Initialize exclusive zones around @n islands.
 841  */
 842 static void
 843 xzone_init(int n)
 844 {
 845     int i, c;
 846
 847     for (i = 0; i < WORLD_SZ(); i++)
 848         xzone[i] = -1;
 849
 850     for (c = 0; c < n; c++)
 851         xzone_around_island(c, id);
 852 }
 853
 854 /*
 855  * Initialize breadth-first search.
 856  */
 857 static void
 858 bfs_init(void)
 859 {
 860     int i;
 861
 862     for (i = 0; i < WORLD_SZ(); i++) {
 863         closest[i] = -1;
 864         distance[i] = USHRT_MAX;
 865     }
 866
 867     bfs_queue_head = bfs_queue_tail = 0;
 868 }
 869
 870 /*
 871  * Add sector @x,@y to the BFS queue.
 872  * It's closest to @c, with distance @dist.
 873  */
 874 static void
 875 bfs_enqueue(int c, int x, int y, int dist)
 876 {
 877     int off = XYOFFSET(x, y);
 878
 879     assert(dist < distance[off]);
 880     closest[off] = c;
 881     distance[off] = dist;
 882     bfs_queue[bfs_queue_tail] = off;
 883     bfs_queue_tail++;
 884     if (bfs_queue_tail >= WORLD_SZ())
 885         bfs_queue_tail = 0;
 886     assert(bfs_queue_tail != bfs_queue_head);
 887 }
 888
 889 /*
 890  * Search breadth-first until the queue is empty.
 891  */
 892 static void
 893 bfs_run_queue(void)
 894 {
 895     int off, dist, i, noff, nx, ny;
 896     coord x, y;
 897
 898     while (bfs_queue_head != bfs_queue_tail) {
 899         off = bfs_queue[bfs_queue_head];
 900         bfs_queue_head++;
 901         if (bfs_queue_head >= WORLD_SZ())
 902             bfs_queue_head = 0;
 903         dist = distance[off] + 1;
 904         sctoff2xy(&x, &y, off);
 905         for (i = DIR_FIRST; i <= DIR_LAST; i++) {
 906             nx = new_x(x + diroff[i][0]);
 907             ny = new_y(y + diroff[i][1]);
 908             noff = XYOFFSET(nx, ny);
 909             if (dist < distance[noff]) {
 910                 bfs_enqueue(closest[off], nx, ny, dist);
 911             } else if (distance[noff] == dist) {
 912                 if (closest[off] != closest[noff])
 913                     closest[noff] = (natid)-1;
 914             } else
 915                 assert(distance[noff] < dist);
 916         }
 917     }
 918 }
 919
 920 /*
 921  * Add island @c's coastal sectors to the BFS queue, with distance 0.
 922  */
 923 static void
 924 bfs_enqueue_island(int c)
 925 {
 926     int i;
 927
 928     for (i = 0; i < isecs[c]; i++) {
 929         if (is_coastal(sect[c][i].x, sect[c][i].y))
 930             bfs_enqueue(c, sect[c][i].x, sect[c][i].y, 0);
 931     }
 932 }
 933
 934 /*
 935  * Enqueue spheres of influence borders for breadth-first search.
 936  */
 937 static void
 938 bfs_enqueue_border(void)
 939 {
 940     int x, y, off, dir, nx, ny, noff;
 941
 942     for (y = 0; y < WORLD_Y; y++) {
 943         for (x = y % 2; x < WORLD_X; x += 2) {
 944             off = XYOFFSET(x, y);
 945             if (distance[off] <= id + 1)
 946                 continue;
 947             if (closest[off] == (natid)-1)
 948                 continue;
 949             for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
 950                 nx = new_x(x + diroff[dir][0]);
 951                 ny = new_y(y + diroff[dir][1]);
 952                 noff = XYOFFSET(nx, ny);
 953                 if (closest[noff] != closest[off]) {
 954                     bfs_enqueue(closest[off], x, y, id + 1);
 955                     break;
 956                 }
 957             }
 958         }
 959     }
 960 }
 961
 962 /*
 963  * Compute spheres of influence
 964  * A continent's sphere of influence is the set of sectors closer to
 965  * it than to any other continent.
 966  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 967  * -1 if no single continent is closest.
 968  * Set distance[XYOFFSET(x, y)] to the minimum of the distance to the
 969  * closest coastal land sector and the distance to just outside the
 970  * sphere of influence plus @id.  For sea sectors within a continent's
 971  * sphere of influence, distance[off] - id is the distance to the
 972  * border of the area where additional islands can be placed.
 973  */
 974 static void
 975 init_spheres_of_influence(void)
 976 {
 977     int c;
 978
 979     bfs_init();
 980     for (c = 0; c < nc; c++)
 981         bfs_enqueue_island(c);
 982     bfs_run_queue();
 983     bfs_enqueue_border();
 984     bfs_run_queue();
 985 }
 986
 987 /*
 988  * Precompute distance to coast
 989  * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
 990  * land sector.
 991  * Set closest[XYOFFSET(x, y)] to the closest continent's number,
 992  * -1 if no single continent is closest.
 993  */
 994 static void
 995 init_distance_to_coast(void)
 996 {
 997     int c;
 998
 999     bfs_init();
1000     for (c = 0; c < nc + ni; c++)
1001         bfs_enqueue_island(c);
1002     bfs_run_queue();
1003 }
1004
1005 /*
1006  * Is @x,@y in the same sphere of influence as island @c?
1007  * Always true when @c is a continent.
1008  */
1009 static int
1010 is_in_sphere(int c, int x, int y)
1011 {
1012     return c < nc || closest[XYOFFSET(x, y)] == c % nc;
1013 }
1014
1015 /*
1016  * Can island @c grow at @x,@y?
1017  */
1018 static int
1019 can_grow_at(int c, int x, int y)
1020 {
1021     return own[XYOFFSET(x, y)] == -1 && xzone_ok(c, x, y)
1022         && is_in_sphere(c, x, y);
1023 }
1024
1025 static void
1026 adj_land_update(int x, int y)
1027 {
1028     int is_land = own[XYOFFSET(x, y)] != -1;
1029     int dir, nx, ny, noff;
1030
1031     for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1032         nx = new_x(x + diroff[dir][0]);
1033         ny = new_y(y + diroff[dir][1]);
1034         noff = XYOFFSET(nx, ny);
1035         if (is_land)
1036             adj_land[noff] |= 1u << DIR_BACK(dir);
1037         else
1038             adj_land[noff] &= ~(1u << DIR_BACK(dir));
1039     }
1040 }
1041
1042 static void
1043 add_sector(int c, int x, int y)
1044 {
1045     int off = XYOFFSET(x, y);
1046
1047     assert(own[off] == -1);
1048     xzone_around_sector(c, x, y, c < nc ? di : DISTINCT_ISLANDS ? id : 0);
1049     sect[c][isecs[c]].x = x;
1050     sect[c][isecs[c]].y = y;
1051     isecs[c]++;
1052     own[off] = c;
1053     adj_land_update(x, y);
1054 }
1055
1056 static int
1057 grow_weight(int c, int x, int y, int spike)
1058 {
1059     int n, b;
1060
1061     /*
1062      * #Land neighbors is #bits set in adj_land[].
1063      * Count them Brian Kernighan's way.
1064      */
1065     n = 0;
1066     for (b = adj_land[XYOFFSET(x, y)]; b; b &= b - 1)
1067         n++;
1068     assert(n > 0 && n < 7);
1069
1070     if (spike)
1071         return (6 - n) * (6 - n);
1072
1073     return n * n * n;
1074 }
1075
1076 static int
1077 grow_one_sector(int c)
1078 {
1079     int spike = roll0(100) < sp;
1080     int wsum, newx, newy, i, x, y, off, dir, nx, ny, noff, w;
1081
1082     assert(cur_seen < UINT_MAX);
1083     cur_seen++;
1084     wsum = 0;
1085     newx = newy = -1;
1086
1087     for (i = 0; i < isecs[c]; i++) {
1088         x = sect[c][i].x;
1089         y = sect[c][i].y;
1090         off = XYOFFSET(x, y);
1091
1092         for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
1093             if (adj_land[off] & (1u << dir))
1094                 continue;
1095             nx = new_x(x + diroff[dir][0]);
1096             ny = new_y(y + diroff[dir][1]);
1097             noff = XYOFFSET(nx, ny);
1098             if (seen[noff] == cur_seen)
1099                 continue;
1100             assert(seen[noff] < cur_seen);
1101             seen[noff] = cur_seen;
1102             if (!can_grow_at(c, nx, ny))
1103                 continue;
1104             w = grow_weight(c, nx, ny, spike);
1105             assert(wsum < INT_MAX - w);
1106             wsum += w;
1107             if (roll0(wsum) < w) {
1108                 newx = nx;
1109                 newy = ny;
1110             }
1111         }
1112     }
1113
1114     if (!wsum)
1115         return 0;
1116
1117     add_sector(c, newx, newy);
1118     return 1;
1119 }
1120
1121 /*
1122  * Grow the continents.
1123  * Return 1 on success, 0 on error.
1124  */
1125 static int
1126 grow_continents(void)
1127 {
1128     int done = 1;
1129     int c, secs;
1130
1131     xzone_init(0);
1132
1133     for (c = 0; c < nc; ++c) {
1134         isecs[c] = 0;
1135         if (!can_grow_at(c, cap[c].x, cap[c].y)
1136             || !can_grow_at(c, new_x(cap[c].x + 2), cap[c].y)) {
1137             done = 0;
1138             continue;
1139         }
1140         add_sector(c, cap[c].x, cap[c].y);
1141         add_sector(c, new_x(cap[c].x + 2), cap[c].y);
1142     }
1143
1144     if (!done) {
1145         qprint("No room for continents\n");
1146         return 0;
1147     }
1148
1149     for (secs = 2; secs < sc && done; secs++) {
1150         for (c = 0; c < nc; ++c) {
1151             if (!grow_one_sector(c))
1152                 done = 0;
1153         }
1154     }
1155
1156     if (!done)
1157         qprint("Only managed to grow %d out of %d sectors.\n",
1158                secs - 1, sc);
1159     return done;
1160 }
1161
1162 /*
1163  * Place additional island @c's first sector.
1164  * Return 1 on success, 0 on error.
1165  */
1166 static int
1167 place_island(int c, int isiz)
1168 {
1169     int n, x, y, d, w, newx, newy;
1170
1171     n = 0;
1172
1173     for (y = 0; y < WORLD_Y; y++) {
1174         for (x = y % 2; x < WORLD_X; x += 2) {
1175             if (can_grow_at(c, x, y)) {
1176                 d = distance[XYOFFSET(x, y)];
1177                 assert(d > id);
1178                 w = (d - id) * (d - id);
1179                 n += MIN(w, (isiz + 2) / 3);
1180                 if (roll0(n) < w) {
1181                     newx = x;
1182                     newy = y;
1183                 }
1184             }
1185         }
1186     }
1187
1188     if (n)
1189         add_sector(c, newx, newy);
1190     return n;
1191 }
1192
1193 static int
1194 int_cmp(const void *a, const void *b)
1195 {
1196     return *(int *)b - *(int *)a;
1197 }
1198
1199 static int *
1200 size_islands(void)
1201 {
1202     int n = ni / nc;
1203     int *isiz = malloc(n * sizeof(*isiz));
1204     int r0, r1, i;
1205
1206     isiz[0] = n * is;
1207     r1 = roll0(is);
1208     for (i = 1; i < n; i++) {
1209         r0 = r1;
1210         r1 = roll0(is);
1211         isiz[i] = is + r1 - r0;
1212         isiz[0] -= isiz[i];
1213     }
1214
1215     qsort(isiz, n, sizeof(*isiz), int_cmp);
1216     return isiz;
1217 }
1218
1219 /*
1220  * Grow the additional islands.
1221  * Return 1 on success, 0 on error.
1222  */
1223 static int
1224 grow_islands(void)
1225 {
1226     int *island_size = size_islands();
1227     int xzone_valid = 0;
1228     int carry = 0;
1229     int i, j, c, done, secs, isiz, x, y;
1230
1231     init_spheres_of_influence();
1232
1233     for (i = 0; i < ni / nc; i++) {
1234         c = nc + i * nc;
1235
1236         if (!xzone_valid)
1237             xzone_init(c);
1238
1239         carry += island_size[i];
1240         isiz = MIN(2 * is, carry);
1241
1242         for (j = 0; j < nc; j++) {
1243             isecs[c + j] = 0;
1244             if (!place_island(c + j, isiz)) {
1245                 qprint("\nNo room for island #%d\n", c - nc + j + 1);
1246                 free(island_size);
1247                 return 0;
1248             }
1249         }
1250
1251         done = 1;
1252         for (secs = 1; secs < isiz && done; secs++) {
1253             for (j = 0; j < nc; j++) {
1254                 if (!grow_one_sector(c + j))
1255                     done = 0;
1256             }
1257         }
1258
1259         if (!done) {
1260             secs--;
1261             for (j = 0; j < nc; j++) {
1262                 if (isecs[c + j] != secs) {
1263                     isecs[c + j]--;
1264                     assert(isecs[c + j] == secs);
1265                     x = sect[c + j][secs].x;
1266                     y = sect[c + j][secs].y;
1267                     own[XYOFFSET(x, y)] = -1;
1268                     adj_land_update(x, y);
1269                 }
1270             }
1271             xzone_valid = 0;
1272         }
1273
1274         for (j = 0; j < nc; j++)
1275             qprint(" %d(%d)", c - nc + j + 1, isecs[c + j]);
1276
1277         carry -= secs;
1278     }
1279
1280     free(island_size);
1281     qprint("\n");
1282
1283     if (carry)
1284         qprint("Only managed to grow %d out of %d island sectors.\n",
1285                is * ni - carry * nc, is * ni);
1286
1287     return 1;
1288 }
1289
1290
1291 /*
1292  * Create elevations
1293  */
1294
1295 static void
1296 create_elevations(void)
1297 {
1298     elevate_prep();
1299     elevate_land();
1300     elevate_sea();
1301 }
1302
1303 static int
1304 elev_cmp(const void *p, const void *q)
1305 {
1306     int a = *(int *)p;
1307     int b = *(int *)q;
1308     int delev = elev[a] - elev[b];
1309
1310     return delev ? delev : a - b;
1311 }
1312
1313 static void
1314 elevate_prep(void)
1315 {
1316     int n = WORLD_SZ() * 8;
1317     int off0, r, sign, elevation, d, x1, y1, off1;
1318     coord x0, y0;
1319     struct hexagon_iter hexit;
1320
1321     init_distance_to_coast();
1322
1323     while (n > 0) {
1324         off0 = roll0(WORLD_SZ());
1325         sctoff2xy(&x0, &y0, off0);
1326         if (own[off0] == -1) {
1327             r = roll(MIN(3, distance[off0]));
1328             sign = -1;
1329         } else {
1330             r = roll(MIN(3, distance[off0]) + 1);
1331             sign = 1;
1332         }
1333         elevation = elev[off0] + sign * r * r;
1334         elev[off0] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1335         n--;
1336         for (d = 1; d < r; d++) {
1337             hexagon_first(&hexit, x0, y0, d, &x1, &y1);
1338             do {
1339                 off1 = XYOFFSET(x1, y1);
1340                 elevation = elev[off1] + sign * (r * r - d * d);
1341                 elev[off1] = LIMIT_TO(elevation, SHRT_MIN, SHRT_MAX);
1342                 n--;
1343             } while (hexagon_next(&hexit, &x1, &y1));
1344         }
1345     }
1346 }
1347
1348 static void
1349 elevate_land(void)
1350 {
1351     int *off = malloc(MAX(sc, is * 2) * sizeof(*off));
1352     int max_nm = (pm * MAX(sc, is * 2)) / 100;
1353     int c, nm, i0, n, i;
1354     double elevation, delta;
1355
1356     for (c = 0; c < nc + ni; c++) {
1357         nm = (pm * isecs[c]) / 100;
1358         i0 = c < nc ? 2 : 0;
1359         n = isecs[c] - i0;
1360         for (i = 0; i < i0; i++)
1361             elev[XYOFFSET(sect[c][i].x, sect[c][i].y)] = PLATMIN;
1362         for (i = 0; i < n; i++)
1363             off[i] = XYOFFSET(sect[c][i0 + i].x, sect[c][i0 + i].y);
1364         qsort(off, n, sizeof(*off), elev_cmp);
1365         delta = (double)(HIGHMIN - LANDMIN - 1) / (n - nm - 1);
1366         elevation = LANDMIN;
1367         for (i = 0; i < n - nm; i++) {
1368             elev[off[i]] = (int)(elevation + 0.5);
1369             elevation += delta;
1370         }
1371         elevation = HIGHMIN;
1372         delta = (127.0 - HIGHMIN) / max_nm;
1373         for (; i < n; i++) {
1374             elevation += delta;
1375             elev[off[i]] = (int)(elevation + 0.5);
1376         }
1377     }
1378
1379     free(off);
1380 }
1381
1382 static void
1383 elevate_sea(void)
1384 {
1385     int i, min;
1386
1387     min = 0;
1388     for (i = 0; i < WORLD_SZ(); i++) {
1389         if (elev[i] < min)
1390             min = elev[i];
1391     }
1392
1393     for (i = 0; i < WORLD_SZ(); i++) {
1394         if (elev[i] < 0)
1395             elev[i] = -1 - 126 * elev[i] / min;
1396     }
1397 }
1398
1399 static int
1400 elev_to_sct_type(int elevation)
1401 {
1402     if (elevation < LANDMIN)
1403         return SCT_WATER;
1404     if (elevation < HIGHMIN)
1405         return SCT_RURAL;
1406     return SCT_MOUNT;
1407 }
1408
1409
1410 /*
1411  * Add resources
1412  */
1413
1414 /*
1415  * Map elevation @elev to a resource value according to @conf.
1416  * This is a linear interpolation on the data points in @conf.
1417  */
1418 static int
1419 elev_to_resource(int elev, struct resource_point conf[])
1420 {
1421     int i, elev1, elev2, delev, res1, res2, dres;
1422
1423     for (i = 1; elev > conf[i].elev; i++) ;
1424     assert(conf[i - 1].elev <= elev);
1425
1426     elev1 = conf[i - 1].elev;
1427     elev2 = conf[i].elev;
1428     delev = elev2 - elev1;
1429     res1 = conf[i - 1].res;
1430     res2 = conf[i].res;
1431     dres = res2 - res1;
1432     return (int)(res1 + (double)((elev - elev1) * dres) / delev);
1433 }
1434
1435 static void
1436 add_resources(struct sctstr *sct)
1437 {
1438     sct->sct_min = elev_to_resource(sct->sct_elev, iron_conf);
1439     sct->sct_gmin = elev_to_resource(sct->sct_elev, gold_conf);
1440     sct->sct_fertil = elev_to_resource(sct->sct_elev, fert_conf);
1441     sct->sct_oil = elev_to_resource(sct->sct_elev, oil_conf);
1442     sct->sct_uran = elev_to_resource(sct->sct_elev, uran_conf);
1443 }
1444
1445
1446 /*
1447  * Designate the sectors
1448  */
1449
1450 static void
1451 write_sects(void)
1452 {
1453     struct sctstr *sp;
1454     int i;
1455
1456     for (i = 0; i < WORLD_SZ(); i++) {
1457         sp = getsectid(i);
1458         sp->sct_elev = elev[i];
1459         sp->sct_type = elev_to_sct_type(sp->sct_elev);
1460         sp->sct_newtype = sp->sct_type;
1461         sp->sct_dterr = own[i] + 1;
1462         sp->sct_coastal = is_coastal(sp->sct_x, sp->sct_y);
1463         add_resources(sp);
1464     }
1465 }
1466
1467
1468 /*
1469  * Print a picture of the map
1470  */
1471
1472 static void
1473 output(void)
1474 {
1475     int sx, sy, x, y, off, c, type;
1476
1477     if (quiet == 0) {
1478         for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1479             y = YNORM(sy);
1480             puts("");
1481             if (y % 2)
1482                 printf(" ");
1483             for (sx = -WORLD_X / 2 + y % 2; sx < WORLD_X / 2; sx += 2) {
1484                 x = XNORM(sx);
1485                 off = XYOFFSET(x, y);
1486                 c = own[off];
1487                 type = elev_to_sct_type(elev[off]);
1488                 if (type == SCT_WATER)
1489                     printf(". ");
1490                 else if (type == SCT_MOUNT)
1491                     printf("^ ");
1492                 else if (c >= nc)
1493                     printf("%% ");
1494                 else {
1495                     assert(0 <= c && c < nc);
1496                     if ((x == cap[c].x || x == new_x(cap[c].x + 2))
1497                         && y == cap[c].y)
1498                         printf("%c ", numletter[c % 62]);
1499                     else
1500                         printf("# ");
1501                 }
1502             }
1503         }
1504     }
1505 }
1506
1507 /*
1508  * Print a map to help visualize own[].
1509  * This is for debugging.
1510  */
1511 void
1512 print_own_map(void)
1513 {
1514     int sx, sy, x, y, off;
1515
1516     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1517         y = YNORM(sy);
1518         printf("%4d ", sy);
1519         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1520             x = XNORM(sx);
1521             off = XYOFFSET(x, y);
1522             if ((x + y) & 1)
1523                 putchar(' ');
1524             else if (own[off] == -1)
1525                 putchar('.');
1526             else
1527                 putchar(numletter[own[off] % 62]);
1528         }
1529         putchar('\n');
1530     }
1531 }
1532
1533 /*
1534  * Print a map to help visualize elev[].
1535  * This is for debugging.  It expects the terminal to understand
1536  * 24-bit color escape sequences \e[48;2;$red;$green;$blue;m.
1537  */
1538 void
1539 print_elev_map(void)
1540 {
1541     int sx, sy, x, y, off, sat;
1542
1543     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1544         y = YNORM(sy);
1545         printf("%4d ", sy);
1546         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1547             x = XNORM(sx);
1548             off = XYOFFSET(x, y);
1549             if ((x + y) & 1)
1550                 putchar(' ');
1551             else if (!elev[off])
1552                 putchar(' ');
1553             else if (elev[off] < 0) {
1554                 sat = 256 + elev[off] * 2;
1555                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat, 255);
1556             } else if (elev[off] < HIGHMIN / 2) {
1557                 sat = (HIGHMIN / 2 - elev[off]) * 4;
1558                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, 255, sat);
1559             } else if (elev[off] < HIGHMIN) {
1560                 sat = 128 + (HIGHMIN - elev[off]) * 2;
1561                 printf("\033[48;2;%d;%d;%dm \033[0m", sat, sat / 2, sat / 4);
1562             } else {
1563                 sat = 128 + (elev[off] - HIGHMIN) * 2;
1564                 printf("\033[48;2;%d;%d;%dm^\033[0m", sat, sat, sat);
1565             }
1566         }
1567         putchar('\n');
1568     }
1569 }
1570
1571 /*
1572  * Print a map to help visualize xzone[].
1573  * This is for debugging.
1574  */
1575 void
1576 print_xzone_map(void)
1577 {
1578     int sx, sy, x, y, off;
1579
1580     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1581         y = YNORM(sy);
1582         printf("%4d ", sy);
1583         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1584             x = XNORM(sx);
1585             off = XYOFFSET(x, y);
1586             if ((x + y) & 1)
1587                 putchar(' ');
1588             else if (own[off] >= 0)
1589                 putchar('-');
1590             else if (xzone[off] >= 0)
1591                 putchar(numletter[xzone[off] % 62]);
1592             else {
1593                 assert(own[off] == -1);
1594                 putchar(xzone[off] == -1 ? '.' : '!');
1595             }
1596         }
1597         putchar('\n');
1598     }
1599 }
1600
1601 /*
1602  * Print a map to help visualize closest[].
1603  * This is for debugging.
1604  */
1605 void
1606 print_closest_map(void)
1607 {
1608     int sx, sy, x, y, off;
1609
1610     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1611         y = YNORM(sy);
1612         printf("%4d ", sy);
1613         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1614             x = XNORM(sx);
1615             off = XYOFFSET(x, y);
1616             if ((x + y) & 1)
1617                 putchar(' ');
1618             else if (closest[off] == (natid)-1)
1619                 putchar('.');
1620             else if (!distance[off]) {
1621                 assert(closest[off] == own[off]);
1622                 putchar('-');
1623             } else {
1624                 putchar(numletter[closest[off] % 62]);
1625             }
1626         }
1627         printf("\n");
1628     }
1629 }
1630
1631 void
1632 print_distance_map(void)
1633 {
1634     int sx, sy, x, y, off;
1635
1636     for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) {
1637         y = YNORM(sy);
1638         printf("%4d ", sy);
1639         for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) {
1640             x = XNORM(sx);
1641             off = XYOFFSET(x, y);
1642             if ((x + y) & 1)
1643                 putchar(' ');
1644             else if (closest[off] == (natid)-1)
1645                 putchar('.');
1646             else if (!distance[off]) {
1647                 assert(closest[off] == own[off]);
1648                 putchar('-');
1649             } else {
1650                 putchar(numletter[distance[off] % 62]);
1651             }
1652         }
1653         printf("\n");
1654     }
1655 }
1656
1657
1658 /*
1659  * Write a script for placing capitals
1660  */
1661
1662 static int
1663 write_newcap_script(void)
1664 {
1665     int c;
1666     FILE *script = fopen(outfile, "w");
1667
1668     if (!script) {
1669         fprintf(stderr, "%s: unable to write to %s (%s)\n",
1670                 program_name, outfile, strerror(errno));
1671         return 0;
1672     }
1673
1674     for (c = 0; c < nc; ++c) {
1675         fprintf(script, "add %d %d %d p\n", c + 1, c + 1, c + 1);
1676         fprintf(script, "newcap %d %d,%d\n", c + 1, cap[c].x, cap[c].y);
1677     }
1678     fprintf(script, "add %d visitor visitor v\n", c + 1);
1679     fclose(script);
1680     return 1;
1681 }