src/mapgen/cavegen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2020 celeron55, Perttu Ahola <celeron55@gmail.com>
   4 Copyright (C) 2015-2020 paramat
   5 Copyright (C) 2010-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
   6
   7 This program is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 2.1 of the License, or
  10 (at your option) any later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU Lesser General Public License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License along
  18 with this program; if not, write to the Free Software Foundation, Inc.,
  19 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20 */
  21
  22 #include "util/numeric.h"
  23 #include <cmath>
  24 #include "map.h"
  25 #include "mapgen.h"
  26 #include "mapgen_v5.h"
  27 #include "mapgen_v6.h"
  28 #include "mapgen_v7.h"
  29 #include "mg_biome.h"
  30 #include "cavegen.h"
  31
  32 // TODO Remove this. Cave liquids are now defined and located using biome definitions
  33 static NoiseParams nparams_caveliquids(0, 1, v3f(150.0, 150.0, 150.0), 776, 3, 0.6, 2.0);
  34
  35
  36 ////
  37 //// CavesNoiseIntersection
  38 ////
  39
  40 CavesNoiseIntersection::CavesNoiseIntersection(
  41         const NodeDefManager *nodedef, BiomeManager *biomemgr, v3s16 chunksize,
  42         NoiseParams *np_cave1, NoiseParams *np_cave2, s32 seed, float cave_width)
  43 {
  44         assert(nodedef);
  45         assert(biomemgr);
  46
  47         m_ndef = nodedef;
  48         m_bmgr = biomemgr;
  49
  50         m_csize = chunksize;
  51         m_cave_width = cave_width;
  52
  53         m_ystride    = m_csize.X;
  54         m_zstride_1d = m_csize.X * (m_csize.Y + 1);
  55
  56         // Noises are created using 1-down overgeneration
  57         // A Nx-by-1-by-Nz-sized plane is at the bottom of the desired for
  58         // re-carving the solid overtop placed for blocking sunlight
  59         noise_cave1 = new Noise(np_cave1, seed, m_csize.X, m_csize.Y + 1, m_csize.Z);
  60         noise_cave2 = new Noise(np_cave2, seed, m_csize.X, m_csize.Y + 1, m_csize.Z);
  61 }
  62
  63
  64 CavesNoiseIntersection::~CavesNoiseIntersection()
  65 {
  66         delete noise_cave1;
  67         delete noise_cave2;
  68 }
  69
  70
  71 void CavesNoiseIntersection::generateCaves(MMVManip *vm,
  72         v3s16 nmin, v3s16 nmax, biome_t *biomemap)
  73 {
  74         assert(vm);
  75         assert(biomemap);
  76
  77         noise_cave1->perlinMap3D(nmin.X, nmin.Y - 1, nmin.Z);
  78         noise_cave2->perlinMap3D(nmin.X, nmin.Y - 1, nmin.Z);
  79
  80         const v3s16 &em = vm->m_area.getExtent();
  81         u32 index2d = 0;  // Biomemap index
  82
  83         for (s16 z = nmin.Z; z <= nmax.Z; z++)
  84         for (s16 x = nmin.X; x <= nmax.X; x++, index2d++) {
  85                 bool column_is_open = false;  // Is column open to overground
  86                 bool is_under_river = false;  // Is column under river water
  87                 bool is_under_tunnel = false;  // Is tunnel or is under tunnel
  88                 bool is_top_filler_above = false;  // Is top or filler above node
  89                 // Indexes at column top
  90                 u32 vi = vm->m_area.index(x, nmax.Y, z);
  91                 u32 index3d = (z - nmin.Z) * m_zstride_1d + m_csize.Y * m_ystride +
  92                         (x - nmin.X);  // 3D noise index
  93                 // Biome of column
  94                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index2d]);
  95                 u16 depth_top = biome->depth_top;
  96                 u16 base_filler = depth_top + biome->depth_filler;
  97                 u16 depth_riverbed = biome->depth_riverbed;
  98                 u16 nplaced = 0;
  99                 // Don't excavate the overgenerated stone at nmax.Y + 1,
 100                 // this creates a 'roof' over the tunnel, preventing light in
 101                 // tunnels at mapchunk borders when generating mapchunks upwards.
 102                 // This 'roof' is removed when the mapchunk above is generated.
 103                 for (s16 y = nmax.Y; y >= nmin.Y - 1; y--,
 104                                 index3d -= m_ystride,
 105                                 VoxelArea::add_y(em, vi, -1)) {
 106                         content_t c = vm->m_data[vi].getContent();
 107
 108                         if (c == CONTENT_AIR || c == biome->c_water_top ||
 109                                         c == biome->c_water) {
 110                                 column_is_open = true;
 111                                 is_top_filler_above = false;
 112                                 continue;
 113                         }
 114
 115                         if (c == biome->c_river_water) {
 116                                 column_is_open = true;
 117                                 is_under_river = true;
 118                                 is_top_filler_above = false;
 119                                 continue;
 120                         }
 121
 122                         // Ground
 123                         float d1 = contour(noise_cave1->result[index3d]);
 124                         float d2 = contour(noise_cave2->result[index3d]);
 125
 126                         if (d1 * d2 > m_cave_width && m_ndef->get(c).is_ground_content) {
 127                                 // In tunnel and ground content, excavate
 128                                 vm->m_data[vi] = MapNode(CONTENT_AIR);
 129                                 is_under_tunnel = true;
 130                                 // If tunnel roof is top or filler, replace with stone
 131                                 if (is_top_filler_above)
 132                                         vm->m_data[vi + em.X] = MapNode(biome->c_stone);
 133                                 is_top_filler_above = false;
 134                         } else if (column_is_open && is_under_tunnel &&
 135                                         (c == biome->c_stone || c == biome->c_filler)) {
 136                                 // Tunnel entrance floor, place biome surface nodes
 137                                 if (is_under_river) {
 138                                         if (nplaced < depth_riverbed) {
 139                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 140                                                 is_top_filler_above = true;
 141                                                 nplaced++;
 142                                         } else {
 143                                                 // Disable top/filler placement
 144                                                 column_is_open = false;
 145                                                 is_under_river = false;
 146                                                 is_under_tunnel = false;
 147                                         }
 148                                 } else if (nplaced < depth_top) {
 149                                         vm->m_data[vi] = MapNode(biome->c_top);
 150                                         is_top_filler_above = true;
 151                                         nplaced++;
 152                                 } else if (nplaced < base_filler) {
 153                                         vm->m_data[vi] = MapNode(biome->c_filler);
 154                                         is_top_filler_above = true;
 155                                         nplaced++;
 156                                 } else {
 157                                         // Disable top/filler placement
 158                                         column_is_open = false;
 159                                         is_under_tunnel = false;
 160                                 }
 161                         } else {
 162                                 // Not tunnel or tunnel entrance floor
 163                                 // Check node for possible replacing with stone for tunnel roof
 164                                 if (c == biome->c_top || c == biome->c_filler)
 165                                         is_top_filler_above = true;
 166
 167                                 column_is_open = false;
 168                         }
 169                 }
 170         }
 171 }
 172
 173
 174 ////
 175 //// CavernsNoise
 176 ////
 177
 178 CavernsNoise::CavernsNoise(
 179         const NodeDefManager *nodedef, v3s16 chunksize, NoiseParams *np_cavern,
 180         s32 seed, float cavern_limit, float cavern_taper, float cavern_threshold)
 181 {
 182         assert(nodedef);
 183
 184         m_ndef  = nodedef;
 185
 186         m_csize            = chunksize;
 187         m_cavern_limit     = cavern_limit;
 188         m_cavern_taper     = cavern_taper;
 189         m_cavern_threshold = cavern_threshold;
 190
 191         m_ystride = m_csize.X;
 192         m_zstride_1d = m_csize.X * (m_csize.Y + 1);
 193
 194         // Noise is created using 1-down overgeneration
 195         // A Nx-by-1-by-Nz-sized plane is at the bottom of the desired for
 196         // re-carving the solid overtop placed for blocking sunlight
 197         noise_cavern = new Noise(np_cavern, seed, m_csize.X, m_csize.Y + 1, m_csize.Z);
 198
 199         c_water_source = m_ndef->getId("mapgen_water_source");
 200         if (c_water_source == CONTENT_IGNORE)
 201                 c_water_source = CONTENT_AIR;
 202
 203         c_lava_source = m_ndef->getId("mapgen_lava_source");
 204         if (c_lava_source == CONTENT_IGNORE)
 205                 c_lava_source = CONTENT_AIR;
 206 }
 207
 208
 209 CavernsNoise::~CavernsNoise()
 210 {
 211         delete noise_cavern;
 212 }
 213
 214
 215 bool CavernsNoise::generateCaverns(MMVManip *vm, v3s16 nmin, v3s16 nmax)
 216 {
 217         assert(vm);
 218
 219         // Calculate noise
 220         noise_cavern->perlinMap3D(nmin.X, nmin.Y - 1, nmin.Z);
 221
 222         // Cache cavern_amp values
 223         float *cavern_amp = new float[m_csize.Y + 1];
 224         u8 cavern_amp_index = 0;  // Index zero at column top
 225         for (s16 y = nmax.Y; y >= nmin.Y - 1; y--, cavern_amp_index++) {
 226                 cavern_amp[cavern_amp_index] =
 227                         MYMIN((m_cavern_limit - y) / (float)m_cavern_taper, 1.0f);
 228         }
 229
 230         //// Place nodes
 231         bool near_cavern = false;
 232         const v3s16 &em = vm->m_area.getExtent();
 233         u32 index2d = 0;
 234
 235         for (s16 z = nmin.Z; z <= nmax.Z; z++)
 236         for (s16 x = nmin.X; x <= nmax.X; x++, index2d++) {
 237                 // Reset cave_amp index to column top
 238                 cavern_amp_index = 0;
 239                 // Initial voxelmanip index at column top
 240                 u32 vi = vm->m_area.index(x, nmax.Y, z);
 241                 // Initial 3D noise index at column top
 242                 u32 index3d = (z - nmin.Z) * m_zstride_1d + m_csize.Y * m_ystride +
 243                         (x - nmin.X);
 244                 // Don't excavate the overgenerated stone at node_max.Y + 1,
 245                 // this creates a 'roof' over the cavern, preventing light in
 246                 // caverns at mapchunk borders when generating mapchunks upwards.
 247                 // This 'roof' is excavated when the mapchunk above is generated.
 248                 for (s16 y = nmax.Y; y >= nmin.Y - 1; y--,
 249                                 index3d -= m_ystride,
 250                                 VoxelArea::add_y(em, vi, -1),
 251                                 cavern_amp_index++) {
 252                         content_t c = vm->m_data[vi].getContent();
 253                         float n_absamp_cavern = std::fabs(noise_cavern->result[index3d]) *
 254                                 cavern_amp[cavern_amp_index];
 255                         // Disable CavesRandomWalk at a safe distance from caverns
 256                         // to avoid excessively spreading liquids in caverns.
 257                         if (n_absamp_cavern > m_cavern_threshold - 0.1f) {
 258                                 near_cavern = true;
 259                                 if (n_absamp_cavern > m_cavern_threshold &&
 260                                                 m_ndef->get(c).is_ground_content)
 261                                         vm->m_data[vi] = MapNode(CONTENT_AIR);
 262                         }
 263                 }
 264         }
 265
 266         delete[] cavern_amp;
 267
 268         return near_cavern;
 269 }
 270
 271
 272 ////
 273 //// CavesRandomWalk
 274 ////
 275
 276 CavesRandomWalk::CavesRandomWalk(
 277         const NodeDefManager *ndef,
 278         GenerateNotifier *gennotify,
 279         s32 seed,
 280         int water_level,
 281         content_t water_source,
 282         content_t lava_source,
 283         float large_cave_flooded,
 284         BiomeGen *biomegen)
 285 {
 286         assert(ndef);
 287
 288         this->ndef               = ndef;
 289         this->gennotify          = gennotify;
 290         this->seed               = seed;
 291         this->water_level        = water_level;
 292         this->np_caveliquids     = &nparams_caveliquids;
 293         this->large_cave_flooded = large_cave_flooded;
 294         this->bmgn               = biomegen;
 295
 296         c_water_source = water_source;
 297         if (c_water_source == CONTENT_IGNORE)
 298                 c_water_source = ndef->getId("mapgen_water_source");
 299         if (c_water_source == CONTENT_IGNORE)
 300                 c_water_source = CONTENT_AIR;
 301
 302         c_lava_source = lava_source;
 303         if (c_lava_source == CONTENT_IGNORE)
 304                 c_lava_source = ndef->getId("mapgen_lava_source");
 305         if (c_lava_source == CONTENT_IGNORE)
 306                 c_lava_source = CONTENT_AIR;
 307 }
 308
 309
 310 void CavesRandomWalk::makeCave(MMVManip *vm, v3s16 nmin, v3s16 nmax,
 311         PseudoRandom *ps, bool is_large_cave, int max_stone_height, s16 *heightmap)
 312 {
 313         assert(vm);
 314         assert(ps);
 315
 316         this->vm         = vm;
 317         this->ps         = ps;
 318         this->node_min   = nmin;
 319         this->node_max   = nmax;
 320         this->heightmap  = heightmap;
 321         this->large_cave = is_large_cave;
 322
 323         this->ystride = nmax.X - nmin.X + 1;
 324
 325         flooded = ps->range(1, 1000) <= large_cave_flooded * 1000.0f;
 326
 327         // If flooded:
 328         // Get biome at mapchunk midpoint. If cave liquid defined for biome, use it.
 329         // If defined liquid is "air", disable 'flooded' to avoid placing "air".
 330         use_biome_liquid = false;
 331         if (flooded && bmgn) {
 332                 v3s16 midp = node_min + (node_max - node_min) / v3s16(2, 2, 2);
 333                 Biome *biome = (Biome *)bmgn->getBiomeAtPoint(midp);
 334                 if (biome->c_cave_liquid[0] != CONTENT_IGNORE) {
 335                         use_biome_liquid = true;
 336                         c_biome_liquid =
 337                                 biome->c_cave_liquid[ps->range(0, biome->c_cave_liquid.size() - 1)];
 338                         if (c_biome_liquid == CONTENT_AIR)
 339                                 flooded = false;
 340                 }
 341         }
 342
 343         // Set initial parameters from randomness
 344         int dswitchint = ps->range(1, 14);
 345
 346         if (large_cave) {
 347                 part_max_length_rs = ps->range(2, 4);
 348                 tunnel_routepoints = ps->range(5, ps->range(15, 30));
 349                 min_tunnel_diameter = 5;
 350                 max_tunnel_diameter = ps->range(7, ps->range(8, 24));
 351         } else {
 352                 part_max_length_rs = ps->range(2, 9);
 353                 tunnel_routepoints = ps->range(10, ps->range(15, 30));
 354                 min_tunnel_diameter = 2;
 355                 max_tunnel_diameter = ps->range(2, 6);
 356         }
 357
 358         large_cave_is_flat = (ps->range(0, 1) == 0);
 359
 360         main_direction = v3f(0, 0, 0);
 361
 362         // Allowed route area size in nodes
 363         ar = node_max - node_min + v3s16(1, 1, 1);
 364         // Area starting point in nodes
 365         of = node_min;
 366
 367         // Allow caves to extend up to 16 nodes beyond the mapchunk edge, to allow
 368         // connecting with caves of neighbor mapchunks.
 369         // 'insure' is needed to avoid many 'out of voxelmanip' cave nodes.
 370         const s16 insure = 2;
 371         s16 more = MYMAX(MAP_BLOCKSIZE - max_tunnel_diameter / 2 - insure, 1);
 372         ar += v3s16(1, 1, 1) * more * 2;
 373         of -= v3s16(1, 1, 1) * more;
 374
 375         route_y_min = 0;
 376         // Allow half a diameter + 7 over stone surface
 377         route_y_max = -of.Y + max_stone_height + max_tunnel_diameter / 2 + 7;
 378
 379         // Limit maximum to area
 380         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
 381
 382         if (large_cave) {
 383                 s16 minpos = 0;
 384                 if (node_min.Y < water_level && node_max.Y > water_level) {
 385                         minpos = water_level - max_tunnel_diameter / 3 - of.Y;
 386                         route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
 387                 }
 388                 route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
 389                 route_y_min = rangelim(route_y_min, 0, route_y_max);
 390         }
 391
 392         s16 route_start_y_min = route_y_min;
 393         s16 route_start_y_max = route_y_max;
 394
 395         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 396         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 397
 398         // Randomize starting position
 399         orp.Z = (float)(ps->next() % ar.Z) + 0.5f;
 400         orp.Y = (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5f;
 401         orp.X = (float)(ps->next() % ar.X) + 0.5f;
 402
 403         // Add generation notify begin event
 404         if (gennotify) {
 405                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 406                 GenNotifyType notifytype = large_cave ?
 407                         GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
 408                 gennotify->addEvent(notifytype, abs_pos);
 409         }
 410
 411         // Generate some tunnel starting from orp
 412         for (u16 j = 0; j < tunnel_routepoints; j++)
 413                 makeTunnel(j % dswitchint == 0);
 414
 415         // Add generation notify end event
 416         if (gennotify) {
 417                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 418                 GenNotifyType notifytype = large_cave ?
 419                         GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
 420                 gennotify->addEvent(notifytype, abs_pos);
 421         }
 422 }
 423
 424
 425 void CavesRandomWalk::makeTunnel(bool dirswitch)
 426 {
 427         if (dirswitch && !large_cave) {
 428                 main_direction.Z = ((float)(ps->next() % 20) - (float)10) / 10;
 429                 main_direction.Y = ((float)(ps->next() % 20) - (float)10) / 30;
 430                 main_direction.X = ((float)(ps->next() % 20) - (float)10) / 10;
 431
 432                 main_direction *= (float)ps->range(0, 10) / 10;
 433         }
 434
 435         // Randomize size
 436         s16 min_d = min_tunnel_diameter;
 437         s16 max_d = max_tunnel_diameter;
 438         rs = ps->range(min_d, max_d);
 439         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 440
 441         v3s16 maxlen;
 442         if (large_cave) {
 443                 maxlen = v3s16(
 444                         rs_part_max_length_rs,
 445                         rs_part_max_length_rs / 2,
 446                         rs_part_max_length_rs
 447                 );
 448         } else {
 449                 maxlen = v3s16(
 450                         rs_part_max_length_rs,
 451                         ps->range(1, rs_part_max_length_rs),
 452                         rs_part_max_length_rs
 453                 );
 454         }
 455
 456         v3f vec;
 457         // Jump downward sometimes
 458         if (!large_cave && ps->range(0, 12) == 0) {
 459                 vec.Z = (float)(ps->next() % (maxlen.Z * 1)) - (float)maxlen.Z / 2;
 460                 vec.Y = (float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y;
 461                 vec.X = (float)(ps->next() % (maxlen.X * 1)) - (float)maxlen.X / 2;
 462         } else {
 463                 vec.Z = (float)(ps->next() % (maxlen.Z * 1)) - (float)maxlen.Z / 2;
 464                 vec.Y = (float)(ps->next() % (maxlen.Y * 1)) - (float)maxlen.Y / 2;
 465                 vec.X = (float)(ps->next() % (maxlen.X * 1)) - (float)maxlen.X / 2;
 466         }
 467
 468         // Do not make caves that are above ground.
 469         // It is only necessary to check the startpoint and endpoint.
 470         v3s16 p1 = v3s16(orp.X, orp.Y, orp.Z) + of + rs / 2;
 471         v3s16 p2 = v3s16(vec.X, vec.Y, vec.Z) + p1;
 472         if (isPosAboveSurface(p1) || isPosAboveSurface(p2))
 473                 return;
 474
 475         vec += main_direction;
 476
 477         v3f rp = orp + vec;
 478         if (rp.X < 0)
 479                 rp.X = 0;
 480         else if (rp.X >= ar.X)
 481                 rp.X = ar.X - 1;
 482
 483         if (rp.Y < route_y_min)
 484                 rp.Y = route_y_min;
 485         else if (rp.Y >= route_y_max)
 486                 rp.Y = route_y_max - 1;
 487
 488         if (rp.Z < 0)
 489                 rp.Z = 0;
 490         else if (rp.Z >= ar.Z)
 491                 rp.Z = ar.Z - 1;
 492
 493         vec = rp - orp;
 494
 495         float veclen = vec.getLength();
 496         if (veclen < 0.05f)
 497                 veclen = 1.0f;
 498
 499         // Every second section is rough
 500         bool randomize_xz = (ps->range(1, 2) == 1);
 501
 502         // Carve routes
 503         for (float f = 0.f; f < 1.0f; f += 1.0f / veclen)
 504                 carveRoute(vec, f, randomize_xz);
 505
 506         orp = rp;
 507 }
 508
 509
 510 void CavesRandomWalk::carveRoute(v3f vec, float f, bool randomize_xz)
 511 {
 512         MapNode airnode(CONTENT_AIR);
 513         MapNode waternode(c_water_source);
 514         MapNode lavanode(c_lava_source);
 515
 516         v3s16 startp(orp.X, orp.Y, orp.Z);
 517         startp += of;
 518
 519         v3f fp = orp + vec * f;
 520         fp.X += 0.1f * ps->range(-10, 10);
 521         fp.Z += 0.1f * ps->range(-10, 10);
 522         v3s16 cp(fp.X, fp.Y, fp.Z);
 523
 524         // Choose cave liquid
 525         MapNode liquidnode = CONTENT_IGNORE;
 526
 527         if (flooded) {
 528                 if (use_biome_liquid) {
 529                         liquidnode = c_biome_liquid;
 530                 } else {
 531                         // If cave liquid not defined by biome, fallback to old hardcoded behaviour.
 532                         // TODO 'np_caveliquids' is deprecated and should eventually be removed.
 533                         // Cave liquids are now defined and located using biome definitions.
 534                         float nval = NoisePerlin3D(np_caveliquids, startp.X,
 535                                 startp.Y, startp.Z, seed);
 536                         liquidnode = (nval < 0.40f && node_max.Y < water_level - 256) ?
 537                                 lavanode : waternode;
 538                 }
 539         }
 540
 541         s16 d0 = -rs / 2;
 542         s16 d1 = d0 + rs;
 543         if (randomize_xz) {
 544                 d0 += ps->range(-1, 1);
 545                 d1 += ps->range(-1, 1);
 546         }
 547
 548         bool flat_cave_floor = !large_cave && ps->range(0, 2) == 2;
 549
 550         for (s16 z0 = d0; z0 <= d1; z0++) {
 551                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 552                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 553                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 554
 555                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 556
 557                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 558                                 // Make better floors in small caves
 559                                 if (flat_cave_floor && y0 <= -rs / 2 && rs <= 7)
 560                                         continue;
 561
 562                                 if (large_cave_is_flat) {
 563                                         // Make large caves not so tall
 564                                         if (rs > 7 && abs(y0) >= rs / 3)
 565                                                 continue;
 566                                 }
 567
 568                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 569                                 p += of;
 570
 571                                 if (!vm->m_area.contains(p))
 572                                         continue;
 573
 574                                 u32 i = vm->m_area.index(p);
 575                                 content_t c = vm->m_data[i].getContent();
 576                                 if (!ndef->get(c).is_ground_content)
 577                                         continue;
 578
 579                                 if (large_cave) {
 580                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 581                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 582
 583                                         if (flooded && full_ymin < water_level && full_ymax > water_level)
 584                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 585                                         else if (flooded && full_ymax < water_level)
 586                                                 vm->m_data[i] = (p.Y < startp.Y - 4) ? liquidnode : airnode;
 587                                         else
 588                                                 vm->m_data[i] = airnode;
 589                                 } else {
 590                                         vm->m_data[i] = airnode;
 591                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 592                                 }
 593                         }
 594                 }
 595         }
 596 }
 597
 598
 599 inline bool CavesRandomWalk::isPosAboveSurface(v3s16 p)
 600 {
 601         if (heightmap != NULL &&
 602                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 603                         p.X >= node_min.X && p.X <= node_max.X) {
 604                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 605                 if (heightmap[index] < p.Y)
 606                         return true;
 607         } else if (p.Y > water_level) {
 608                 return true;
 609         }
 610
 611         return false;
 612 }
 613
 614
 615 ////
 616 //// CavesV6
 617 ////
 618
 619 CavesV6::CavesV6(const NodeDefManager *ndef, GenerateNotifier *gennotify,
 620         int water_level, content_t water_source, content_t lava_source)
 621 {
 622         assert(ndef);
 623
 624         this->ndef        = ndef;
 625         this->gennotify   = gennotify;
 626         this->water_level = water_level;
 627
 628         c_water_source = water_source;
 629         if (c_water_source == CONTENT_IGNORE)
 630                 c_water_source = ndef->getId("mapgen_water_source");
 631         if (c_water_source == CONTENT_IGNORE)
 632                 c_water_source = CONTENT_AIR;
 633
 634         c_lava_source = lava_source;
 635         if (c_lava_source == CONTENT_IGNORE)
 636                 c_lava_source = ndef->getId("mapgen_lava_source");
 637         if (c_lava_source == CONTENT_IGNORE)
 638                 c_lava_source = CONTENT_AIR;
 639 }
 640
 641
 642 void CavesV6::makeCave(MMVManip *vm, v3s16 nmin, v3s16 nmax,
 643         PseudoRandom *ps, PseudoRandom *ps2,
 644         bool is_large_cave, int max_stone_height, s16 *heightmap)
 645 {
 646         assert(vm);
 647         assert(ps);
 648         assert(ps2);
 649
 650         this->vm         = vm;
 651         this->ps         = ps;
 652         this->ps2        = ps2;
 653         this->node_min   = nmin;
 654         this->node_max   = nmax;
 655         this->heightmap  = heightmap;
 656         this->large_cave = is_large_cave;
 657
 658         this->ystride = nmax.X - nmin.X + 1;
 659
 660         // Set initial parameters from randomness
 661         min_tunnel_diameter = 2;
 662         max_tunnel_diameter = ps->range(2, 6);
 663         int dswitchint      = ps->range(1, 14);
 664         if (large_cave) {
 665                 part_max_length_rs  = ps->range(2, 4);
 666                 tunnel_routepoints  = ps->range(5, ps->range(15, 30));
 667                 min_tunnel_diameter = 5;
 668                 max_tunnel_diameter = ps->range(7, ps->range(8, 24));
 669         } else {
 670                 part_max_length_rs = ps->range(2, 9);
 671                 tunnel_routepoints = ps->range(10, ps->range(15, 30));
 672         }
 673         large_cave_is_flat = (ps->range(0, 1) == 0);
 674
 675         main_direction = v3f(0, 0, 0);
 676
 677         // Allowed route area size in nodes
 678         ar = node_max - node_min + v3s16(1, 1, 1);
 679         // Area starting point in nodes
 680         of = node_min;
 681
 682         // Allow a bit more
 683         //(this should be more than the maximum radius of the tunnel)
 684         const s16 max_spread_amount = MAP_BLOCKSIZE;
 685         const s16 insure = 10;
 686         s16 more = MYMAX(max_spread_amount - max_tunnel_diameter / 2 - insure, 1);
 687         ar += v3s16(1, 0, 1) * more * 2;
 688         of -= v3s16(1, 0, 1) * more;
 689
 690         route_y_min = 0;
 691         // Allow half a diameter + 7 over stone surface
 692         route_y_max = -of.Y + max_stone_height + max_tunnel_diameter / 2 + 7;
 693
 694         // Limit maximum to area
 695         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
 696
 697         if (large_cave) {
 698                 s16 minpos = 0;
 699                 if (node_min.Y < water_level && node_max.Y > water_level) {
 700                         minpos = water_level - max_tunnel_diameter / 3 - of.Y;
 701                         route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
 702                 }
 703                 route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
 704                 route_y_min = rangelim(route_y_min, 0, route_y_max);
 705         }
 706
 707         s16 route_start_y_min = route_y_min;
 708         s16 route_start_y_max = route_y_max;
 709
 710         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 711         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 712
 713         // Randomize starting position
 714         orp.Z = (float)(ps->next() % ar.Z) + 0.5f;
 715         orp.Y = (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5f;
 716         orp.X = (float)(ps->next() % ar.X) + 0.5f;
 717
 718         // Add generation notify begin event
 719         if (gennotify != NULL) {
 720                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 721                 GenNotifyType notifytype = large_cave ?
 722                         GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
 723                 gennotify->addEvent(notifytype, abs_pos);
 724         }
 725
 726         // Generate some tunnel starting from orp
 727         for (u16 j = 0; j < tunnel_routepoints; j++)
 728                 makeTunnel(j % dswitchint == 0);
 729
 730         // Add generation notify end event
 731         if (gennotify != NULL) {
 732                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 733                 GenNotifyType notifytype = large_cave ?
 734                         GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
 735                 gennotify->addEvent(notifytype, abs_pos);
 736         }
 737 }
 738
 739
 740 void CavesV6::makeTunnel(bool dirswitch)
 741 {
 742         if (dirswitch && !large_cave) {
 743                 main_direction.Z = ((float)(ps->next() % 20) - (float)10) / 10;
 744                 main_direction.Y = ((float)(ps->next() % 20) - (float)10) / 30;
 745                 main_direction.X = ((float)(ps->next() % 20) - (float)10) / 10;
 746
 747                 main_direction *= (float)ps->range(0, 10) / 10;
 748         }
 749
 750         // Randomize size
 751         s16 min_d = min_tunnel_diameter;
 752         s16 max_d = max_tunnel_diameter;
 753         rs = ps->range(min_d, max_d);
 754         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 755
 756         v3s16 maxlen;
 757         if (large_cave) {
 758                 maxlen = v3s16(
 759                         rs_part_max_length_rs,
 760                         rs_part_max_length_rs / 2,
 761                         rs_part_max_length_rs
 762                 );
 763         } else {
 764                 maxlen = v3s16(
 765                         rs_part_max_length_rs,
 766                         ps->range(1, rs_part_max_length_rs),
 767                         rs_part_max_length_rs
 768                 );
 769         }
 770
 771         v3f vec;
 772         vec.Z = (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2;
 773         vec.Y = (float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2;
 774         vec.X = (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2;
 775
 776         // Jump downward sometimes
 777         if (!large_cave && ps->range(0, 12) == 0) {
 778                 vec.Z = (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2;
 779                 vec.Y = (float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y;
 780                 vec.X = (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2;
 781         }
 782
 783         // Do not make caves that are entirely above ground, to fix shadow bugs
 784         // caused by overgenerated large caves.
 785         // It is only necessary to check the startpoint and endpoint.
 786         v3s16 p1 = v3s16(orp.X, orp.Y, orp.Z) + of + rs / 2;
 787         v3s16 p2 = v3s16(vec.X, vec.Y, vec.Z) + p1;
 788
 789         // If startpoint and endpoint are above ground, disable placement of nodes
 790         // in carveRoute while still running all PseudoRandom calls to ensure caves
 791         // are consistent with existing worlds.
 792         bool tunnel_above_ground =
 793                 p1.Y > getSurfaceFromHeightmap(p1) &&
 794                 p2.Y > getSurfaceFromHeightmap(p2);
 795
 796         vec += main_direction;
 797
 798         v3f rp = orp + vec;
 799         if (rp.X < 0)
 800                 rp.X = 0;
 801         else if (rp.X >= ar.X)
 802                 rp.X = ar.X - 1;
 803
 804         if (rp.Y < route_y_min)
 805                 rp.Y = route_y_min;
 806         else if (rp.Y >= route_y_max)
 807                 rp.Y = route_y_max - 1;
 808
 809         if (rp.Z < 0)
 810                 rp.Z = 0;
 811         else if (rp.Z >= ar.Z)
 812                 rp.Z = ar.Z - 1;
 813
 814         vec = rp - orp;
 815
 816         float veclen = vec.getLength();
 817         // As odd as it sounds, veclen is *exactly* 0.0 sometimes, causing a FPE
 818         if (veclen < 0.05f)
 819                 veclen = 1.0f;
 820
 821         // Every second section is rough
 822         bool randomize_xz = (ps2->range(1, 2) == 1);
 823
 824         // Carve routes
 825         for (float f = 0.f; f < 1.0f; f += 1.0f / veclen)
 826                 carveRoute(vec, f, randomize_xz, tunnel_above_ground);
 827
 828         orp = rp;
 829 }
 830
 831
 832 void CavesV6::carveRoute(v3f vec, float f, bool randomize_xz,
 833         bool tunnel_above_ground)
 834 {
 835         MapNode airnode(CONTENT_AIR);
 836         MapNode waternode(c_water_source);
 837         MapNode lavanode(c_lava_source);
 838
 839         v3s16 startp(orp.X, orp.Y, orp.Z);
 840         startp += of;
 841
 842         v3f fp = orp + vec * f;
 843         fp.X += 0.1f * ps->range(-10, 10);
 844         fp.Z += 0.1f * ps->range(-10, 10);
 845         v3s16 cp(fp.X, fp.Y, fp.Z);
 846
 847         s16 d0 = -rs / 2;
 848         s16 d1 = d0 + rs;
 849         if (randomize_xz) {
 850                 d0 += ps->range(-1, 1);
 851                 d1 += ps->range(-1, 1);
 852         }
 853
 854         for (s16 z0 = d0; z0 <= d1; z0++) {
 855                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 856                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 857                         if (tunnel_above_ground)
 858                                 continue;
 859
 860                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 861                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 862                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 863                                 if (large_cave_is_flat) {
 864                                         // Make large caves not so tall
 865                                         if (rs > 7 && abs(y0) >= rs / 3)
 866                                                 continue;
 867                                 }
 868
 869                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 870                                 p += of;
 871
 872                                 if (!vm->m_area.contains(p))
 873                                         continue;
 874
 875                                 u32 i = vm->m_area.index(p);
 876                                 content_t c = vm->m_data[i].getContent();
 877                                 if (!ndef->get(c).is_ground_content)
 878                                         continue;
 879
 880                                 if (large_cave) {
 881                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 882                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 883
 884                                         if (full_ymin < water_level && full_ymax > water_level) {
 885                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 886                                         } else if (full_ymax < water_level) {
 887                                                 vm->m_data[i] = (p.Y < startp.Y - 2) ? lavanode : airnode;
 888                                         } else {
 889                                                 vm->m_data[i] = airnode;
 890                                         }
 891                                 } else {
 892                                         if (c == CONTENT_AIR)
 893                                                 continue;
 894
 895                                         vm->m_data[i] = airnode;
 896                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 897                                 }
 898                         }
 899                 }
 900         }
 901 }
 902
 903
 904 inline s16 CavesV6::getSurfaceFromHeightmap(v3s16 p)
 905 {
 906         if (heightmap != NULL &&
 907                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 908                         p.X >= node_min.X && p.X <= node_max.X) {
 909                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 910                 return heightmap[index];
 911         }
 912
 913         return water_level;
 914
 915 }