src/cavegen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "util/numeric.h"
  21 #include "map.h"
  22 #include "mapgen.h"
  23 #include "mapgen_v5.h"
  24 #include "mapgen_v6.h"
  25 #include "mapgen_v7.h"
  26 #include "cavegen.h"
  27
  28 NoiseParams nparams_caveliquids(0, 1, v3f(150.0, 150.0, 150.0), 776, 3, 0.6, 2.0);
  29
  30 ////
  31 //// CavesRandomWalk
  32 ////
  33
  34 CavesRandomWalk::CavesRandomWalk(Mapgen *mg, PseudoRandom *ps)
  35 {
  36         this->mg             = mg;
  37         this->vm             = mg->vm;
  38         this->ndef           = mg->ndef;
  39         this->water_level    = mg->water_level;
  40         this->ps             = ps;
  41         c_water_source       = ndef->getId("mapgen_water_source");
  42         c_lava_source        = ndef->getId("mapgen_lava_source");
  43         c_ice                = ndef->getId("mapgen_ice");
  44         this->np_caveliquids = &nparams_caveliquids;
  45         this->ystride        = mg->csize.X;
  46         this->lava_depth     = DEFAULT_LAVA_DEPTH;
  47
  48         if (c_ice == CONTENT_IGNORE)
  49                 c_ice = CONTENT_AIR;
  50
  51         dswitchint = ps->range(1, 14);
  52         flooded    = ps->range(1, 2) == 2;
  53
  54         part_max_length_rs  = ps->range(2, 4);
  55         tunnel_routepoints  = ps->range(5, ps->range(15, 30));
  56         min_tunnel_diameter = 5;
  57         max_tunnel_diameter = ps->range(7, ps->range(8, 24));
  58
  59         large_cave_is_flat = (ps->range(0, 1) == 0);
  60 }
  61
  62
  63 void CavesRandomWalk::makeCave(v3s16 nmin, v3s16 nmax, int max_stone_height)
  64 {
  65         node_min = nmin;
  66         node_max = nmax;
  67         main_direction = v3f(0, 0, 0);
  68
  69         // Allowed route area size in nodes
  70         ar = node_max - node_min + v3s16(1, 1, 1);
  71         // Area starting point in nodes
  72         of = node_min;
  73
  74         // Allow a bit more
  75         //(this should be more than the maximum radius of the tunnel)
  76         s16 insure = 10;
  77         s16 more = MYMAX(MAP_BLOCKSIZE - max_tunnel_diameter / 2 - insure, 1);
  78         ar += v3s16(1,0,1) * more * 2;
  79         of -= v3s16(1,0,1) * more;
  80
  81         route_y_min = 0;
  82         // Allow half a diameter + 7 over stone surface
  83         route_y_max = -of.Y + max_stone_y + max_tunnel_diameter / 2 + 7;
  84
  85         // Limit maximum to area
  86         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
  87
  88         s16 minpos = 0;
  89         if (node_min.Y < water_level && node_max.Y > water_level) {
  90                 minpos = water_level - max_tunnel_diameter / 3 - of.Y;
  91                 route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
  92         }
  93         route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
  94         route_y_min = rangelim(route_y_min, 0, route_y_max);
  95
  96         s16 route_start_y_min = route_y_min;
  97         s16 route_start_y_max = route_y_max;
  98
  99         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 100         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 101
 102         // Randomize starting position
 103         orp = v3f(
 104                 (float)(ps->next() % ar.X) + 0.5,
 105                 (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5,
 106                 (float)(ps->next() % ar.Z) + 0.5
 107         );
 108
 109         // Add generation notify begin event
 110         v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 111         GenNotifyType notifytype = GENNOTIFY_LARGECAVE_BEGIN;
 112         mg->gennotify.addEvent(notifytype, abs_pos);
 113
 114         // Generate some tunnel starting from orp
 115         for (u16 j = 0; j < tunnel_routepoints; j++)
 116                 makeTunnel(j % dswitchint == 0);
 117
 118         // Add generation notify end event
 119         abs_pos = v3s16(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 120         notifytype = GENNOTIFY_LARGECAVE_END;
 121         mg->gennotify.addEvent(notifytype, abs_pos);
 122 }
 123
 124
 125 void CavesRandomWalk::makeTunnel(bool dirswitch)
 126 {
 127         // Randomize size
 128         s16 min_d = min_tunnel_diameter;
 129         s16 max_d = max_tunnel_diameter;
 130         rs = ps->range(min_d, max_d);
 131         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 132
 133         v3s16 maxlen;
 134         maxlen = v3s16(
 135                 rs_part_max_length_rs,
 136                 rs_part_max_length_rs / 2,
 137                 rs_part_max_length_rs
 138         );
 139
 140         v3f vec;
 141         // Jump downward sometimes
 142         vec = v3f(
 143                 (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
 144                 (float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2,
 145                 (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
 146         );
 147
 148         // Do not make caves that are above ground.
 149         // It is only necessary to check the startpoint and endpoint.
 150         v3s16 p1 = v3s16(orp.X, orp.Y, orp.Z) + of + rs / 2;
 151         v3s16 p2 = v3s16(vec.X, vec.Y, vec.Z) + p1;
 152         if (isPosAboveSurface(p1) || isPosAboveSurface(p2))
 153                 return;
 154
 155         vec += main_direction;
 156
 157         v3f rp = orp + vec;
 158         if (rp.X < 0)
 159                 rp.X = 0;
 160         else if (rp.X >= ar.X)
 161                 rp.X = ar.X - 1;
 162
 163         if (rp.Y < route_y_min)
 164                 rp.Y = route_y_min;
 165         else if (rp.Y >= route_y_max)
 166                 rp.Y = route_y_max - 1;
 167
 168         if (rp.Z < 0)
 169                 rp.Z = 0;
 170         else if (rp.Z >= ar.Z)
 171                 rp.Z = ar.Z - 1;
 172
 173         vec = rp - orp;
 174
 175         float veclen = vec.getLength();
 176         if (veclen < 0.05)
 177                 veclen = 1.0;
 178
 179         // Every second section is rough
 180         bool randomize_xz = (ps->range(1, 2) == 1);
 181
 182         // Carve routes
 183         for (float f = 0; f < 1.0; f += 1.0 / veclen)
 184                 carveRoute(vec, f, randomize_xz);
 185
 186         orp = rp;
 187 }
 188
 189
 190 void CavesRandomWalk::carveRoute(v3f vec, float f, bool randomize_xz)
 191 {
 192         MapNode airnode(CONTENT_AIR);
 193         MapNode waternode(c_water_source);
 194         MapNode lavanode(c_lava_source);
 195
 196         v3s16 startp(orp.X, orp.Y, orp.Z);
 197         startp += of;
 198
 199         float nval = NoisePerlin3D(np_caveliquids, startp.X,
 200                 startp.Y, startp.Z, mg->seed);
 201         MapNode liquidnode = (nval < 0.40 && node_max.Y < lava_depth) ?
 202                 lavanode : waternode;
 203
 204         v3f fp = orp + vec * f;
 205         fp.X += 0.1 * ps->range(-10, 10);
 206         fp.Z += 0.1 * ps->range(-10, 10);
 207         v3s16 cp(fp.X, fp.Y, fp.Z);
 208
 209         s16 d0 = -rs/2;
 210         s16 d1 = d0 + rs;
 211         if (randomize_xz) {
 212                 d0 += ps->range(-1, 1);
 213                 d1 += ps->range(-1, 1);
 214         }
 215
 216         for (s16 z0 = d0; z0 <= d1; z0++) {
 217                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 218                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 219                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 220
 221                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 222
 223                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 224                                 if (large_cave_is_flat) {
 225                                         // Make large caves not so tall
 226                                         if (rs > 7 && abs(y0) >= rs / 3)
 227                                                 continue;
 228                                 }
 229
 230                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 231                                 p += of;
 232
 233                                 if (vm->m_area.contains(p) == false)
 234                                         continue;
 235
 236                                 u32 i = vm->m_area.index(p);
 237                                 content_t c = vm->m_data[i].getContent();
 238                                 if (!ndef->get(c).is_ground_content)
 239                                         continue;
 240
 241                                 int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 242                                 int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 243
 244                                 if (flooded && full_ymin < water_level && full_ymax > water_level)
 245                                         vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 246                                 else if (flooded && full_ymax < water_level)
 247                                         vm->m_data[i] = (p.Y < startp.Y - 4) ? liquidnode : airnode;
 248                                 else
 249                                         vm->m_data[i] = airnode;
 250                         }
 251                 }
 252         }
 253 }
 254
 255
 256 inline bool CavesRandomWalk::isPosAboveSurface(v3s16 p)
 257 {
 258         if (heightmap != NULL &&
 259                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 260                         p.X >= node_min.X && p.X <= node_max.X) {
 261                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 262                 if (heightmap[index] < p.Y)
 263                         return true;
 264         } else if (p.Y > water_level) {
 265                 return true;
 266         }
 267
 268         return false;
 269 }
 270
 271
 272 ////
 273 //// CavesV6
 274 ////
 275
 276 CavesV6::CavesV6(INodeDefManager *ndef, GenerateNotifier *gennotify,
 277         int water_level, content_t water_source, content_t lava_source)
 278 {
 279         assert(ndef);
 280
 281         this->ndef        = ndef;
 282         this->gennotify   = gennotify;
 283         this->water_level = water_level;
 284
 285         c_water_source = water_source;
 286         if (c_water_source == CONTENT_IGNORE)
 287                 c_water_source = ndef->getId("mapgen_water_source");
 288         if (c_water_source == CONTENT_IGNORE)
 289                 c_water_source = CONTENT_AIR;
 290
 291         c_lava_source = lava_source;
 292         if (c_lava_source == CONTENT_IGNORE)
 293                 c_lava_source = ndef->getId("mapgen_lava_source");
 294         if (c_lava_source == CONTENT_IGNORE)
 295                 c_lava_source = CONTENT_AIR;
 296 }
 297
 298
 299 void CavesV6::makeCave(MMVManip *vm, v3s16 nmin, v3s16 nmax,
 300         PseudoRandom *ps, PseudoRandom *ps2,
 301         bool is_large_cave, int max_stone_height, s16 *heightmap)
 302 {
 303         assert(vm);
 304         assert(ps);
 305         assert(ps2);
 306
 307         this->vm         = vm;
 308         this->ps         = ps;
 309         this->ps2        = ps2;
 310         this->node_min   = nmin;
 311         this->node_max   = nmax;
 312         this->heightmap  = heightmap;
 313         this->large_cave = is_large_cave;
 314
 315         this->ystride = nmax.X - nmin.X + 1;
 316
 317         // Set initial parameters from randomness
 318         min_tunnel_diameter = 2;
 319         max_tunnel_diameter = ps->range(2, 6);
 320         dswitchint          = ps->range(1, 14);
 321         if (large_cave) {
 322                 part_max_length_rs  = ps->range(2, 4);
 323                 tunnel_routepoints  = ps->range(5, ps->range(15, 30));
 324                 min_tunnel_diameter = 5;
 325                 max_tunnel_diameter = ps->range(7, ps->range(8, 24));
 326         } else {
 327                 part_max_length_rs = ps->range(2, 9);
 328                 tunnel_routepoints = ps->range(10, ps->range(15, 30));
 329         }
 330         large_cave_is_flat = (ps->range(0, 1) == 0);
 331
 332         main_direction = v3f(0, 0, 0);
 333
 334         // Allowed route area size in nodes
 335         ar = node_max - node_min + v3s16(1, 1, 1);
 336         // Area starting point in nodes
 337         of = node_min;
 338
 339         // Allow a bit more
 340         //(this should be more than the maximum radius of the tunnel)
 341         const s16 max_spread_amount = MAP_BLOCKSIZE;
 342         s16 insure = 10;
 343         s16 more = MYMAX(max_spread_amount - max_tunnel_diameter / 2 - insure, 1);
 344         ar += v3s16(1, 0, 1) * more * 2;
 345         of -= v3s16(1, 0, 1) * more;
 346
 347         route_y_min = 0;
 348         // Allow half a diameter + 7 over stone surface
 349         route_y_max = -of.Y + max_stone_height + max_tunnel_diameter / 2 + 7;
 350
 351         // Limit maximum to area
 352         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
 353
 354         if (large_cave) {
 355                 s16 minpos = 0;
 356                 if (node_min.Y < water_level && node_max.Y > water_level) {
 357                         minpos = water_level - max_tunnel_diameter / 3 - of.Y;
 358                         route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
 359                 }
 360                 route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
 361                 route_y_min = rangelim(route_y_min, 0, route_y_max);
 362         }
 363
 364         s16 route_start_y_min = route_y_min;
 365         s16 route_start_y_max = route_y_max;
 366
 367         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 368         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 369
 370         // Randomize starting position
 371         orp = v3f(
 372                 (float)(ps->next() % ar.X) + 0.5,
 373                 (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5,
 374                 (float)(ps->next() % ar.Z) + 0.5
 375         );
 376
 377         // Add generation notify begin event
 378         if (gennotify != NULL) {
 379                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 380                 GenNotifyType notifytype = large_cave ?
 381                         GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
 382                 gennotify->addEvent(notifytype, abs_pos);
 383         }
 384
 385         // Generate some tunnel starting from orp
 386         for (u16 j = 0; j < tunnel_routepoints; j++)
 387                 makeTunnel(j % dswitchint == 0);
 388
 389         // Add generation notify end event
 390         if (gennotify != NULL) {
 391                 v3s16 abs_pos = v3s16(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 392                 GenNotifyType notifytype = large_cave ?
 393                         GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
 394                 gennotify->addEvent(notifytype, abs_pos);
 395         }
 396 }
 397
 398
 399 void CavesV6::makeTunnel(bool dirswitch)
 400 {
 401         if (dirswitch && !large_cave) {
 402                 main_direction = v3f(
 403                         ((float)(ps->next() % 20) - (float)10) / 10,
 404                         ((float)(ps->next() % 20) - (float)10) / 30,
 405                         ((float)(ps->next() % 20) - (float)10) / 10
 406                 );
 407                 main_direction *= (float)ps->range(0, 10) / 10;
 408         }
 409
 410         // Randomize size
 411         s16 min_d = min_tunnel_diameter;
 412         s16 max_d = max_tunnel_diameter;
 413         rs = ps->range(min_d, max_d);
 414         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 415
 416         v3s16 maxlen;
 417         if (large_cave) {
 418                 maxlen = v3s16(
 419                         rs_part_max_length_rs,
 420                         rs_part_max_length_rs / 2,
 421                         rs_part_max_length_rs
 422                 );
 423         } else {
 424                 maxlen = v3s16(
 425                         rs_part_max_length_rs,
 426                         ps->range(1, rs_part_max_length_rs),
 427                         rs_part_max_length_rs
 428                 );
 429         }
 430
 431         v3f vec(
 432                 (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
 433                 (float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2,
 434                 (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
 435         );
 436
 437         // Jump downward sometimes
 438         if (!large_cave && ps->range(0, 12) == 0) {
 439                 vec = v3f(
 440                         (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2,
 441                         (float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y,
 442                         (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2
 443                 );
 444         }
 445
 446         // Do not make caves that are entirely above ground, to fix shadow bugs
 447         // caused by overgenerated large caves.
 448         // It is only necessary to check the startpoint and endpoint.
 449         v3s16 p1 = v3s16(orp.X, orp.Y, orp.Z) + of + rs / 2;
 450         v3s16 p2 = v3s16(vec.X, vec.Y, vec.Z) + p1;
 451
 452         // If startpoint and endpoint are above ground, disable placement of nodes
 453         // in carveRoute while still running all PseudoRandom calls to ensure caves
 454         // are consistent with existing worlds.
 455         bool tunnel_above_ground =
 456                 p1.Y > getSurfaceFromHeightmap(p1) &&
 457                 p2.Y > getSurfaceFromHeightmap(p2);
 458
 459         vec += main_direction;
 460
 461         v3f rp = orp + vec;
 462         if (rp.X < 0)
 463                 rp.X = 0;
 464         else if (rp.X >= ar.X)
 465                 rp.X = ar.X - 1;
 466
 467         if (rp.Y < route_y_min)
 468                 rp.Y = route_y_min;
 469         else if (rp.Y >= route_y_max)
 470                 rp.Y = route_y_max - 1;
 471
 472         if (rp.Z < 0)
 473                 rp.Z = 0;
 474         else if (rp.Z >= ar.Z)
 475                 rp.Z = ar.Z - 1;
 476
 477         vec = rp - orp;
 478
 479         float veclen = vec.getLength();
 480         // As odd as it sounds, veclen is *exactly* 0.0 sometimes, causing a FPE
 481         if (veclen < 0.05)
 482                 veclen = 1.0;
 483
 484         // Every second section is rough
 485         bool randomize_xz = (ps2->range(1, 2) == 1);
 486
 487         // Carve routes
 488         for (float f = 0; f < 1.0; f += 1.0 / veclen)
 489                 carveRoute(vec, f, randomize_xz, tunnel_above_ground);
 490
 491         orp = rp;
 492 }
 493
 494
 495 void CavesV6::carveRoute(v3f vec, float f, bool randomize_xz,
 496         bool tunnel_above_ground)
 497 {
 498         MapNode airnode(CONTENT_AIR);
 499         MapNode waternode(c_water_source);
 500         MapNode lavanode(c_lava_source);
 501
 502         v3s16 startp(orp.X, orp.Y, orp.Z);
 503         startp += of;
 504
 505         v3f fp = orp + vec * f;
 506         fp.X += 0.1 * ps->range(-10, 10);
 507         fp.Z += 0.1 * ps->range(-10, 10);
 508         v3s16 cp(fp.X, fp.Y, fp.Z);
 509
 510         s16 d0 = -rs / 2;
 511         s16 d1 = d0 + rs;
 512         if (randomize_xz) {
 513                 d0 += ps->range(-1, 1);
 514                 d1 += ps->range(-1, 1);
 515         }
 516
 517         for (s16 z0 = d0; z0 <= d1; z0++) {
 518                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 519                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 520                         if (tunnel_above_ground)
 521                                 continue;
 522
 523                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 524                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 525                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 526                                 if (large_cave_is_flat) {
 527                                         // Make large caves not so tall
 528                                         if (rs > 7 && abs(y0) >= rs / 3)
 529                                                 continue;
 530                                 }
 531
 532                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 533                                 p += of;
 534
 535                                 if (vm->m_area.contains(p) == false)
 536                                         continue;
 537
 538                                 u32 i = vm->m_area.index(p);
 539                                 content_t c = vm->m_data[i].getContent();
 540                                 if (!ndef->get(c).is_ground_content)
 541                                         continue;
 542
 543                                 if (large_cave) {
 544                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 545                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 546
 547                                         if (full_ymin < water_level && full_ymax > water_level) {
 548                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 549                                         } else if (full_ymax < water_level) {
 550                                                 vm->m_data[i] = (p.Y < startp.Y - 2) ? lavanode : airnode;
 551                                         } else {
 552                                                 vm->m_data[i] = airnode;
 553                                         }
 554                                 } else {
 555                                         if (c == CONTENT_IGNORE || c == CONTENT_AIR)
 556                                                 continue;
 557
 558                                         vm->m_data[i] = airnode;
 559                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 560                                 }
 561                         }
 562                 }
 563         }
 564 }
 565
 566
 567 inline s16 CavesV6::getSurfaceFromHeightmap(v3s16 p)
 568 {
 569         if (heightmap != NULL &&
 570                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 571                         p.X >= node_min.X && p.X <= node_max.X) {
 572                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 573                 return heightmap[index];
 574         } else {
 575                 return water_level;
 576         }
 577 }