src/mapgen/cavegen.cpp

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