home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / games / volume4 / xconq5 / part13 / mkmap.c < prev    next >
C/C++ Source or Header  |  1988-07-01  |  14KB  |  458 lines

  1. /* Copyright (c) 1987, 1988  Stanley T. Shebs, University of Utah. */
  2. /* This program may be used, copied, modified, and redistributed freely */
  3. /* for noncommercial purposes, so long as this notice remains intact. */
  4.  
  5. /* RCS $Header: mkmap.c,v 1.1 88/06/21 12:30:21 shebs Exp $ */
  6.  
  7. /* Terrain generation is based on fractal ideas, although this version */
  8. /* is not directly derived from a published technique. */
  9. /* Speed is important; most of the code has been integerized. */
  10. /* Extra steps produce maps more suitable for conquest, including a way to */
  11. /* control the amount of each type of terrain appearing in the result. */
  12. /* The process is actually done for elevation and water separately, then */
  13. /* the terrain type is dependent on both. */
  14.  
  15. /* (Note that this is no longer a separate program as in the first version.) */
  16.  
  17. #include "config.h"
  18. #include "misc.h"
  19. #include "period.h"
  20. #include "dir.h"
  21. #include "map.h"
  22.  
  23. /* Values of altitude and moisture must be firmly bounded, so that */
  24. /* histogramming doesn't take too much space. */
  25.  
  26. #define MAXALT 16384
  27.  
  28. /* Abstraction of 2D malloced array references.  Names from Lisp... */
  29.  
  30. #define aref(m,x,y) ((m)[(x)+world.width*(y)])
  31.  
  32. #define aset(m,x,y,v) ((m)[(x)+world.width*(y)] = (v))
  33.  
  34. #define aadd(m,x,y,v) ((m)[(x)+world.width*(y)] += (v))
  35.  
  36. /* Values ultimately arriving from the command line. */
  37.  
  38. extern int givenwidth, givenheight, givenseen;
  39.  
  40. /* Arrays here should contain only nonnegative values (for simplicity). */
  41. /* They are potentially large and used only once, so we malloc and free... */
  42.  
  43. int *relief;            /* pointer to array of elevations */
  44. int *water;             /* pointer to array of moisture levels */
  45. int *aux;               /* auxiliary array */
  46. int *histo;             /* histogram array */
  47. int *alts;              /* percentile for each elevation */
  48. int *wets;              /* percentile for level of moisture */
  49.  
  50. /* The main function looks a little strange in spots, since it is derived */
  51. /* from a former standalone program (the mkmap of version 1). */
  52.  
  53. make_up_map()
  54. {
  55.     int width, height;
  56.  
  57.     width = givenwidth;  height = givenheight;
  58.     if (Debug) printf("Going to make up a %dx%d map ...\n", width, height);
  59.     /* Heuristic limit - algorithms get weird on small maps */
  60.     if (width < 9 || height < 9) {
  61.     fprintf(stderr, "Cannot generate such a small map!\n");
  62.     exit(1);
  63.     }
  64.     world.width = width;  world.height = height;
  65.     world.scale = period.scale;
  66.     world.known = givenseen;
  67.     relief = (int *) malloc(world.width * world.height * sizeof(int));
  68.     aux    = (int *) malloc(world.width * world.height * sizeof(int));
  69.     water  = (int *) malloc(world.width * world.height * sizeof(int));
  70.     histo  = (int *) malloc(MAXALT * sizeof(int));
  71.     alts   = (int *) malloc(MAXALT * sizeof(int));
  72.     wets   = (int *) malloc(MAXALT * sizeof(int));
  73.     /* Build a full relief map */
  74.     make_bumps(relief, period.altroughness);
  75.     smooth_map(relief);
  76.     add_curves(relief, period.altroughness);
  77.     smooth_map(relief);
  78.     limit_map(relief, MAXALT-1, 0);
  79.     percentile(relief, alts);
  80.     /* Build a "moisture relief" map */
  81.     make_bumps(water, period.wetroughness);
  82.     smooth_map(water);
  83.     smooth_map(water);
  84.     limit_map(water, MAXALT-1, 0);
  85.     percentile(water, wets);
  86.     /* Put it all together */
  87.     compose_map();
  88.     free(relief);
  89.     free(water);
  90.     free(aux);
  91.     free(histo);
  92.     free(alts);
  93.     free(wets);
  94.     if (Debug) printf("... Done making up a map.\n");
  95. }
  96.  
  97. /* The main map generators produces bumps, of sizes and numbers dictated */
  98. /* by the roughness.  The size is a percentage of map dimensions, while */
  99. /* number is set to approximately cover the entire map.  Each bump is a */
  100. /* hexagonal shape, and the elevation of interior points varies. */
  101.  
  102. make_bumps(map, roughness)
  103. int *map, roughness;
  104. {
  105.     int blocks, i, scale, var, dx, dy, tries;
  106.     int x0, y0, x1, y1, d0, d1, xt, yt, flag, x, y, dz, z, oz;
  107.     int dn1, dn2, dn3, dn4, dn5, dn6, numer1, denom1, numer2, denom2;
  108.     int farx[10], fary[10];
  109.     int peakx[10], peaky[10], peakz[10], peakf[10], numpeaks = 0, p;
  110.  
  111.     scale = max(1, ((100 - roughness) * min(world.width, world.height)) / 100);
  112.     var = MAXALT/8 + (MAXALT/8 * roughness) / 100;
  113.     blocks = (world.width * world.height) / (scale * scale);
  114.     blocks *= 2;
  115.     if (Debug) printf("Playing with blocks (%d)...\n", blocks);
  116.     for (x = 0; x < world.width; ++x) {
  117.     for (y = 0; y < world.height; ++y) {
  118.         aset(map, x, y, MAXALT/2);
  119.     }
  120.     }
  121.     for (i = 0; i < blocks; ++i) {
  122.     flag = ((i == 0 || flip_coin()) ? 1 : -1);
  123.     if (scale <= 1) {
  124.         x = random(world.width) + world.width;
  125.         y = random(world.height);
  126.         z = var + random(var/2);
  127.         aadd(map, wrap(x), y, flag * z);
  128.     } else {
  129.         dx = scale/2 + random(scale/2);
  130.         dy = scale/2 + random(scale/2);
  131.         /* All x values shifted, so as to avoid negatives */
  132.         x0 = random(world.width) + world.width;
  133.         y0 = random(world.height - dy - 1);
  134.         x1 = x0 + dx + 1;
  135.         y1 = y0 + dy + 1;
  136.         d0 = min(x1 - x0, y1 - y0) / 4;
  137.         d0 = d0 + random(3*d0);
  138.         d1 = min(x1 - x0, y1 - y0) / 4;
  139.         d1 = d1 + random(3*d1);
  140.         /* Cheap way to ensure most high points actually within hexagon */
  141.         xt = yt = -1;  tries = 10;
  142.         while (((xt-x0+yt-y0 < d0) || (x1-xt+y1-yt > d1)) && tries-- > 0) {
  143.         xt = x0 + (random(x1 - x0) + random(x1 - x0)) / 2;
  144.         yt = y0 + (random(y1 - y0) + random(y1 - y0)) / 2;
  145.         }
  146.         /* Compute distances from high point to hexagon corners */
  147.         dn1 = distance(xt, yt, x1-d1, y1);
  148.         dn2 = distance(xt, yt, x1, y1-d1);
  149.         dn3 = distance(xt, yt, x1, y0);
  150.         dn4 = distance(xt, yt, x0+d0, y0);
  151.         dn5 = distance(xt, yt, x0, y0+d0);
  152.         dn6 = distance(xt, yt, x0, y1);
  153.         for (y = y0; y <= y1; ++y) {
  154.         for (x = x0; x <= x1; ++x) {
  155.             if ((x-x0+y-y0 > d0) && (x1-x+y1-y > d1)) {
  156.             dx = x - xt;  dy = y - yt;
  157.             if (dx > 0) {
  158.                 if (dy > 0) {
  159.                 numer1 = distance(x, y, x1, y1-d1);
  160.                 denom1 = dn2;
  161.                 numer2 = distance(x, y, x1-d1, y1);
  162.                 denom2 = dn1;
  163.                 } else if (dy > (0 - dx)) {
  164.                 numer1 = distance(x, y, x1, y0);
  165.                 denom1 = dn3;
  166.                 numer2 = distance(x, y, x1, y1-d1);
  167.                 denom2 = dn2;
  168.                 } else {
  169.                 numer1 = distance(x, y, x0+d0, y0);
  170.                 denom1 = dn4;
  171.                 numer2 = distance(x, y, x1, y0);
  172.                 denom2 = dn3;
  173.                 }
  174.             } else {
  175.                 if (dy < 0) {
  176.                 numer1 = distance(x, y, x0, y0+d0);
  177.                 denom1 = dn5;
  178.                 numer2 = distance(x, y, x0+d0, y0);
  179.                 denom2 = dn4;
  180.                 } else if (dy < (0 - dx)) {
  181.                 numer1 = distance(x, y, x0, y1);
  182.                 denom1 = dn6;
  183.                 numer2 = distance(x, y, x0, y0+d0);
  184.                 denom2 = dn5;
  185.                 } else {
  186.                 numer1 = distance(x, y, x1-d1, y1);
  187.                 denom1 = dn1;
  188.                 numer2 = distance(x, y, x0, y1);
  189.                 denom2 = dn6;
  190.                 }
  191.             }
  192.             if (denom1 == 0) denom1 = 1;
  193.             if (denom2 == 0) denom2 = 1;
  194.             dz = (flag * ((var * numer1) / denom1 +
  195.                       (var * numer2) / denom2));
  196.             oz = aref(map, wrap(x), y);
  197.             if (!between(0, dz + oz, MAXALT)) dz /= 2;
  198.             aset(map, wrap(x), y, oz + dz + random(var/2));
  199.             }
  200.         }
  201.         }
  202.     }
  203.     /* Remember some high points for use in hitting untouched areas */
  204.     if (numpeaks < 10) {
  205.         peakx[numpeaks] = wrap(xt);
  206.         peaky[numpeaks] = yt;
  207.         peakf[numpeaks] = flag;
  208.         peakz[numpeaks] = var;
  209.         farx[numpeaks] = wrap(xt+world.width/2);
  210.         fary[numpeaks] = random(world.height);
  211.         numpeaks++;
  212.     }
  213.     }
  214.     /* This is to make smoothly varying terrain in formerly flat areas */
  215.     for (x = 0; x < world.width; ++x) {
  216.     for (y = 0; y < world.height; ++y) {
  217.         if (aref(map, x, y) == MAXALT/2) {
  218.         z = 0;
  219.         for (p = 0; p < numpeaks; ++p) { 
  220.             dz = ((peakz[p] * cyldist(x, y, farx[p], fary[p])) /
  221.               (cyldist(peakx[p], peaky[p], farx[p], fary[p])+1));
  222.             dz -= (peakz[p] * scale) / world.width;
  223.             z += peakf[p] * dz;
  224.         }
  225.         z /= numpeaks;
  226.         aadd(map, x, y, z + random(var/4));
  227.         }
  228.     }
  229.     }
  230.     limit_map(map, MAXALT-1, 0); 
  231. }
  232.  
  233. /* Returns shortest distance around the world (can be either direction). */
  234.  
  235. cyldist(x1, y1, x2, y2)
  236. int x1, y1, x2, y2;
  237. {
  238.     int dist = distance(x1, y1, x2, y2), dist2;
  239.  
  240.     if ((dist2 = distance(x1+world.width, y1, x2, y2)) < dist) {
  241.     dist = dist2;
  242.     } else if ((dist2 = distance(x1, y1, x2+world.width, y2)) < dist) {
  243.     dist = dist2;
  244.     }
  245.     return dist;
  246. }
  247.  
  248. /* Exponent with *small* integer power. (used with Bezier curves) */
  249.  
  250. float
  251. expt(f, i)
  252. float f;
  253. int i;
  254. {
  255.     float rslt = 1.0;
  256.  
  257.     while (i-- > 0) rslt = rslt * f;
  258.     return rslt;
  259. }
  260.  
  261. /* Combination of n objects taken i at a time. (used for Bezier) */
  262.  
  263. comb(n, i)
  264. int n, i;
  265. {
  266.     if (i <= 0) return 1;
  267.     else if (n <= 0) return 0;
  268.     else return (comb(n-1, i) + comb(n-1,i-1));
  269. }
  270.  
  271. /* Put in random Bezier mountain chains.  Number and size are scaled to */
  272. /* the size of the map.  To prevent criss-crossing from creating very */
  273. /* high spots, just set the aux map to values, and only add in later. */
  274.  
  275. add_curves(map, roughness)
  276. int *map, roughness;
  277. {
  278.     int i, j, n, x, y, flag, curves, mindim, var;
  279.     float u, f, cpx[4], cpy[4], px[500], py[500];
  280.  
  281.     curves = (world.width * world.height * roughness) / 50000;
  282.     if (Debug) printf("Throwing curves (%d)...\n", curves);
  283.     for (x = 0; x < world.width; ++x) {
  284.     for (y = 0; y < world.height; ++y) {
  285.         aset(aux, x, y, 0);
  286.     }
  287.     }
  288.     mindim = min(500, min(world.width, world.height));
  289.     var = (MAXALT/8 * roughness) / 100;
  290.     for (n = 0; n < curves; ++n) {
  291.     cpx[0] = 1.0 * (random(world.width-2)+1);
  292.     cpy[0] = 1.0 * (random(world.height-2)+1);
  293.     for (j = 1; j < 4; ++j) {
  294.         cpx[j] = cpx[0] + (random(mindim) - mindim/2);
  295.         if (cpx[j] > world.width-1) cpx[j] = world.width-1;
  296.         if (cpx[j] < 0) cpx[j] = 0;
  297.         cpy[j] = cpy[0] + (random(mindim) - mindim/2);
  298.         if (cpy[j] > world.height-1) cpy[j] = world.height-1;
  299.         if (cpy[j] < 0) cpy[j] = 0;
  300.     }
  301.     for (i = 0; i < mindim; ++i) {
  302.         u = (1.0 * i) / mindim;
  303.         px[i] = py[i] = 0.0;
  304.         for (j = 0; j < 4; ++j) {
  305.         f = comb(3,j)*expt(u,j)*expt(1-u,3-j);
  306.         px[i] += cpx[j]*f; 
  307.         py[i] += cpy[j]*f;
  308.         }
  309.     }
  310.     flag = random(3) ? 1 : -1;
  311.     for (i = 0; i < mindim; ++i) {
  312.         x = (int) px[i];  y = (int) py[i];
  313.         aset(aux, x, y, flag * (MAXALT/8 + var));
  314.     }
  315.     }
  316.     add_maps(map, aux, map);
  317.     limit_map(map, MAXALT-1, 0);
  318. }
  319.  
  320. /* Ensure that map values stay within given range. */
  321.  
  322. limit_map(map, hi, lo)
  323. int *map, hi, lo;
  324. {
  325.     int x, y, m;
  326.     
  327.     for (x = 0; x < world.width; ++x) {
  328.     for (y = 0; y < world.height; ++y) {
  329.         m = aref(map, x, y);
  330.         aset(map, x, y, max(lo, min(m, hi)));
  331.     }
  332.     }
  333. }
  334.  
  335. /* Form the point-wise sum of two maps into a third one. */
  336.  
  337. add_maps(m1, m2, rslt)
  338. int *m1, *m2, *rslt;
  339. {
  340.     int x, y;
  341.  
  342.     for (x = 0; x < world.width; ++x) {
  343.     for (y = 0; y < world.height; ++y) {
  344.         aset(rslt, x, y, aref(m1, x, y) + aref(m2, x, y));
  345.     }
  346.     }
  347. }
  348.  
  349. /* Average out things to keep peaks from getting too sharp. */
  350. /* The array "aux" is the buffer for this operation. */
  351. /* The edges of the map remain unaltered. (dubious) */
  352.  
  353. smooth_map(map)
  354. int *map;
  355. {
  356.     int x, y, nx, px, sum;
  357.  
  358.     if (Debug) printf("Smoothing...\n");
  359.     for (x = 0; x < world.width; ++x) {
  360.     nx = wrap(x+1);  px = wrap(x-1);
  361.     for (y = 1; y < world.height-1; ++y) {
  362.         sum  = aref(map, x, y);
  363.         sum += aref(map, x, y+1);
  364.         sum += aref(map, nx, y);
  365.         sum += aref(map, nx, y-1);
  366.         sum += aref(map, x, y-1);
  367.         sum += aref(map, px, y);
  368.         sum += aref(map, px, y+1);
  369.         aset(aux, x, y, sum / 7);
  370.     }
  371.     }
  372.     for (x = 0; x < world.width; ++x) {
  373.     for (y = 1; y < world.height-1; ++y) {
  374.         aset(map, x, y, aref(aux, x, y));
  375.     }
  376.     }
  377. }
  378.  
  379. /* Terrain types are specified in terms of percentage cover on a map, so */
  380. /* for instance the Earth is 70% sea.  Since each of several types will have */
  381. /* its own percentages (both for elevation and moisture), the simplest thing */
  382. /* to do is to calculate the percentile for each elevation and moisture */
  383. /* level, and save them all away.  This would be a one-liner in APL... */
  384.  
  385. /* Percentile computation is inefficient, should be done incrementally */
  386. /* somehow instead of with * and / */
  387.  
  388. percentile(map, percentiles)
  389. int *map, *percentiles;
  390. {
  391.     int i, x, y, total;
  392.     
  393.     if (Debug) printf("Computing percentiles...\n");
  394.     for (i = 0; i < MAXALT; ++i) {
  395.     histo[i] = 0;
  396.     percentiles[i] = 0;
  397.     }
  398.     /* Make the basic histogram, but don't count the edges */
  399.     for (x = 0; x < world.width; ++x) {
  400.     for (y = 1; y < world.height-1; ++y) {
  401.         ++histo[aref(map, x, y)];
  402.     }
  403.     }
  404.     /* Integrate over the histogram */
  405.     for (i = 1; i < MAXALT; ++i)
  406.     histo[i] += histo[i-1];
  407.     /* Total here should actually be the same as number of cells in the map */
  408.     total = histo[MAXALT-1];
  409.     /* Compute the percentile position */
  410.     for (i = 0; i < MAXALT; ++i)
  411.     percentiles[i] = (100 * histo[i]) / total;
  412. }
  413.  
  414. /* Final creation and output of the map. */
  415.  
  416. compose_map()
  417. {
  418.     int x, y;
  419.  
  420.     if (Debug) printf("Assigning terrain types...\n");
  421.     allocate_map();
  422.     for (y = 0; y < world.height; ++y) {
  423.     for (x = 0; x < world.width; ++x) {
  424.         set_terrain_at(x, y, terrain(x, y));
  425.         set_unit_at(x, y, NULL);
  426.     }
  427.     }
  428.     /* Add a border if specified */
  429.     if (period.edgeterrain >= 0) {
  430.     for (x = 0; x < world.width; ++x) {
  431.         set_terrain_at(x, 0, period.edgeterrain);
  432.         set_terrain_at(x, world.height-1, period.edgeterrain);
  433.     }
  434.     }
  435. }
  436.  
  437. /* Do final output of terrain types.  This is basically a process of */
  438. /* checking the percentile limits on each type against what is actually */
  439. /* there.  (could and maybe should be more efficient) */
  440. /* Error checking important for period designers... */
  441.  
  442. terrain(x, y)
  443. int x, y;
  444. {
  445.     int t, a = aref(relief, x, y), w = aref(water, x, y);
  446.  
  447.     for_all_terrain_types(t) {
  448.     if (between(ttypes[t].minalt, alts[a], ttypes[t].maxalt) &&
  449.         between(ttypes[t].minwet, wets[w], ttypes[t].maxwet)) {
  450.         return t;
  451.     }
  452.     }
  453.     printf("Unknown terrain in percentiles alt %d, wet %d.\n",
  454.        alts[a], wets[w]);
  455.     /* Not great, but valid if nothing else */
  456.     return (max(0, period.defaultterrain));
  457. }
  458.