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 {
 284         assert(ndef);
 285
 286         this->ndef           = ndef;
 287         this->gennotify      = gennotify;
 288         this->seed           = seed;
 289         this->water_level    = water_level;
 290         this->np_caveliquids = &nparams_caveliquids;
 291         this->lava_depth     = lava_depth;
 292
 293         c_water_source = water_source;
 294         if (c_water_source == CONTENT_IGNORE)
 295                 c_water_source = ndef->getId("mapgen_water_source");
 296         if (c_water_source == CONTENT_IGNORE)
 297                 c_water_source = CONTENT_AIR;
 298
 299         c_lava_source = lava_source;
 300         if (c_lava_source == CONTENT_IGNORE)
 301                 c_lava_source = ndef->getId("mapgen_lava_source");
 302         if (c_lava_source == CONTENT_IGNORE)
 303                 c_lava_source = CONTENT_AIR;
 304 }
 305
 306
 307 void CavesRandomWalk::makeCave(MMVManip *vm, v3s16 nmin, v3s16 nmax,
 308         PseudoRandom *ps, bool is_large_cave, int max_stone_height, s16 *heightmap)
 309 {
 310         assert(vm);
 311         assert(ps);
 312
 313         this->vm         = vm;
 314         this->ps         = ps;
 315         this->node_min   = nmin;
 316         this->node_max   = nmax;
 317         this->heightmap  = heightmap;
 318         this->large_cave = is_large_cave;
 319
 320         this->ystride = nmax.X - nmin.X + 1;
 321
 322         // Set initial parameters from randomness
 323         int dswitchint = ps->range(1, 14);
 324         flooded = ps->range(1, 2) == 2;
 325
 326         if (large_cave) {
 327                 part_max_length_rs = ps->range(2, 4);
 328                 tunnel_routepoints = ps->range(5, ps->range(15, 30));
 329                 min_tunnel_diameter = 5;
 330                 max_tunnel_diameter = ps->range(7, ps->range(8, 24));
 331         } else {
 332                 part_max_length_rs = ps->range(2, 9);
 333                 tunnel_routepoints = ps->range(10, ps->range(15, 30));
 334                 min_tunnel_diameter = 2;
 335                 max_tunnel_diameter = ps->range(2, 6);
 336         }
 337
 338         large_cave_is_flat = (ps->range(0, 1) == 0);
 339
 340         main_direction = v3f(0, 0, 0);
 341
 342         // Allowed route area size in nodes
 343         ar = node_max - node_min + v3s16(1, 1, 1);
 344         // Area starting point in nodes
 345         of = node_min;
 346
 347         // Allow a bit more
 348         //(this should be more than the maximum radius of the tunnel)
 349         const s16 insure = 10;
 350         s16 more = MYMAX(MAP_BLOCKSIZE - max_tunnel_diameter / 2 - insure, 1);
 351         ar += v3s16(1, 0, 1) * more * 2;
 352         of -= v3s16(1, 0, 1) * more;
 353
 354         route_y_min = 0;
 355         // Allow half a diameter + 7 over stone surface
 356         route_y_max = -of.Y + max_stone_y + max_tunnel_diameter / 2 + 7;
 357
 358         // Limit maximum to area
 359         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
 360
 361         if (large_cave) {
 362                 s16 minpos = 0;
 363                 if (node_min.Y < water_level && node_max.Y > water_level) {
 364                         minpos = water_level - max_tunnel_diameter / 3 - of.Y;
 365                         route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
 366                 }
 367                 route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
 368                 route_y_min = rangelim(route_y_min, 0, route_y_max);
 369         }
 370
 371         s16 route_start_y_min = route_y_min;
 372         s16 route_start_y_max = route_y_max;
 373
 374         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 375         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 376
 377         // Randomize starting position
 378         orp.Z = (float)(ps->next() % ar.Z) + 0.5f;
 379         orp.Y = (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5f;
 380         orp.X = (float)(ps->next() % ar.X) + 0.5f;
 381
 382         // Add generation notify begin event
 383         if (gennotify) {
 384                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 385                 GenNotifyType notifytype = large_cave ?
 386                         GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
 387                 gennotify->addEvent(notifytype, abs_pos);
 388         }
 389
 390         // Generate some tunnel starting from orp
 391         for (u16 j = 0; j < tunnel_routepoints; j++)
 392                 makeTunnel(j % dswitchint == 0);
 393
 394         // Add generation notify end event
 395         if (gennotify) {
 396                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 397                 GenNotifyType notifytype = large_cave ?
 398                         GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
 399                 gennotify->addEvent(notifytype, abs_pos);
 400         }
 401 }
 402
 403
 404 void CavesRandomWalk::makeTunnel(bool dirswitch)
 405 {
 406         if (dirswitch && !large_cave) {
 407                 main_direction.Z = ((float)(ps->next() % 20) - (float)10) / 10;
 408                 main_direction.Y = ((float)(ps->next() % 20) - (float)10) / 30;
 409                 main_direction.X = ((float)(ps->next() % 20) - (float)10) / 10;
 410
 411                 main_direction *= (float)ps->range(0, 10) / 10;
 412         }
 413
 414         // Randomize size
 415         s16 min_d = min_tunnel_diameter;
 416         s16 max_d = max_tunnel_diameter;
 417         rs = ps->range(min_d, max_d);
 418         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 419
 420         v3s16 maxlen;
 421         if (large_cave) {
 422                 maxlen = v3s16(
 423                         rs_part_max_length_rs,
 424                         rs_part_max_length_rs / 2,
 425                         rs_part_max_length_rs
 426                 );
 427         } else {
 428                 maxlen = v3s16(
 429                         rs_part_max_length_rs,
 430                         ps->range(1, rs_part_max_length_rs),
 431                         rs_part_max_length_rs
 432                 );
 433         }
 434
 435         v3f vec;
 436         // Jump downward sometimes
 437         if (!large_cave && ps->range(0, 12) == 0) {
 438                 vec.Z = (float)(ps->next() % (maxlen.Z * 1)) - (float)maxlen.Z / 2;
 439                 vec.Y = (float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y;
 440                 vec.X = (float)(ps->next() % (maxlen.X * 1)) - (float)maxlen.X / 2;
 441         } else {
 442                 vec.Z = (float)(ps->next() % (maxlen.Z * 1)) - (float)maxlen.Z / 2;
 443                 vec.Y = (float)(ps->next() % (maxlen.Y * 1)) - (float)maxlen.Y / 2;
 444                 vec.X = (float)(ps->next() % (maxlen.X * 1)) - (float)maxlen.X / 2;
 445         }
 446
 447         // Do not make caves that are above ground.
 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         if (isPosAboveSurface(p1) || isPosAboveSurface(p2))
 452                 return;
 453
 454         vec += main_direction;
 455
 456         v3f rp = orp + vec;
 457         if (rp.X < 0)
 458                 rp.X = 0;
 459         else if (rp.X >= ar.X)
 460                 rp.X = ar.X - 1;
 461
 462         if (rp.Y < route_y_min)
 463                 rp.Y = route_y_min;
 464         else if (rp.Y >= route_y_max)
 465                 rp.Y = route_y_max - 1;
 466
 467         if (rp.Z < 0)
 468                 rp.Z = 0;
 469         else if (rp.Z >= ar.Z)
 470                 rp.Z = ar.Z - 1;
 471
 472         vec = rp - orp;
 473
 474         float veclen = vec.getLength();
 475         if (veclen < 0.05f)
 476                 veclen = 1.0f;
 477
 478         // Every second section is rough
 479         bool randomize_xz = (ps->range(1, 2) == 1);
 480
 481         // Carve routes
 482         for (float f = 0.f; f < 1.0f; f += 1.0f / veclen)
 483                 carveRoute(vec, f, randomize_xz);
 484
 485         orp = rp;
 486 }
 487
 488
 489 void CavesRandomWalk::carveRoute(v3f vec, float f, bool randomize_xz)
 490 {
 491         MapNode airnode(CONTENT_AIR);
 492         MapNode waternode(c_water_source);
 493         MapNode lavanode(c_lava_source);
 494
 495         v3s16 startp(orp.X, orp.Y, orp.Z);
 496         startp += of;
 497
 498         float nval = NoisePerlin3D(np_caveliquids, startp.X,
 499                 startp.Y, startp.Z, seed);
 500         MapNode liquidnode = (nval < 0.40f && node_max.Y < lava_depth) ?
 501                 lavanode : waternode;
 502
 503         v3f fp = orp + vec * f;
 504         fp.X += 0.1f * ps->range(-10, 10);
 505         fp.Z += 0.1f * ps->range(-10, 10);
 506         v3s16 cp(fp.X, fp.Y, fp.Z);
 507
 508         s16 d0 = -rs / 2;
 509         s16 d1 = d0 + rs;
 510         if (randomize_xz) {
 511                 d0 += ps->range(-1, 1);
 512                 d1 += ps->range(-1, 1);
 513         }
 514
 515         bool flat_cave_floor = !large_cave && ps->range(0, 2) == 2;
 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                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 521
 522                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 523
 524                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 525                                 // Make better floors in small caves
 526                                 if (flat_cave_floor && y0 <= -rs / 2 && rs <= 7)
 527                                         continue;
 528
 529                                 if (large_cave_is_flat) {
 530                                         // Make large caves not so tall
 531                                         if (rs > 7 && abs(y0) >= rs / 3)
 532                                                 continue;
 533                                 }
 534
 535                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 536                                 p += of;
 537
 538                                 if (!vm->m_area.contains(p))
 539                                         continue;
 540
 541                                 u32 i = vm->m_area.index(p);
 542                                 content_t c = vm->m_data[i].getContent();
 543                                 if (!ndef->get(c).is_ground_content)
 544                                         continue;
 545
 546                                 if (large_cave) {
 547                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 548                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 549
 550                                         if (flooded && full_ymin < water_level && full_ymax > water_level)
 551                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 552                                         else if (flooded && full_ymax < water_level)
 553                                                 vm->m_data[i] = (p.Y < startp.Y - 4) ? liquidnode : airnode;
 554                                         else
 555                                                 vm->m_data[i] = airnode;
 556                                 } else {
 557                                         if (c == CONTENT_IGNORE)
 558                                                 continue;
 559
 560                                         vm->m_data[i] = airnode;
 561                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 562                                 }
 563                         }
 564                 }
 565         }
 566 }
 567
 568
 569 inline bool CavesRandomWalk::isPosAboveSurface(v3s16 p)
 570 {
 571         if (heightmap != NULL &&
 572                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 573                         p.X >= node_min.X && p.X <= node_max.X) {
 574                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 575                 if (heightmap[index] < p.Y)
 576                         return true;
 577         } else if (p.Y > water_level) {
 578                 return true;
 579         }
 580
 581         return false;
 582 }
 583
 584
 585 ////
 586 //// CavesV6
 587 ////
 588
 589 CavesV6::CavesV6(const NodeDefManager *ndef, GenerateNotifier *gennotify,
 590         int water_level, content_t water_source, content_t lava_source)
 591 {
 592         assert(ndef);
 593
 594         this->ndef        = ndef;
 595         this->gennotify   = gennotify;
 596         this->water_level = water_level;
 597
 598         c_water_source = water_source;
 599         if (c_water_source == CONTENT_IGNORE)
 600                 c_water_source = ndef->getId("mapgen_water_source");
 601         if (c_water_source == CONTENT_IGNORE)
 602                 c_water_source = CONTENT_AIR;
 603
 604         c_lava_source = lava_source;
 605         if (c_lava_source == CONTENT_IGNORE)
 606                 c_lava_source = ndef->getId("mapgen_lava_source");
 607         if (c_lava_source == CONTENT_IGNORE)
 608                 c_lava_source = CONTENT_AIR;
 609 }
 610
 611
 612 void CavesV6::makeCave(MMVManip *vm, v3s16 nmin, v3s16 nmax,
 613         PseudoRandom *ps, PseudoRandom *ps2,
 614         bool is_large_cave, int max_stone_height, s16 *heightmap)
 615 {
 616         assert(vm);
 617         assert(ps);
 618         assert(ps2);
 619
 620         this->vm         = vm;
 621         this->ps         = ps;
 622         this->ps2        = ps2;
 623         this->node_min   = nmin;
 624         this->node_max   = nmax;
 625         this->heightmap  = heightmap;
 626         this->large_cave = is_large_cave;
 627
 628         this->ystride = nmax.X - nmin.X + 1;
 629
 630         // Set initial parameters from randomness
 631         min_tunnel_diameter = 2;
 632         max_tunnel_diameter = ps->range(2, 6);
 633         int dswitchint      = ps->range(1, 14);
 634         if (large_cave) {
 635                 part_max_length_rs  = ps->range(2, 4);
 636                 tunnel_routepoints  = ps->range(5, ps->range(15, 30));
 637                 min_tunnel_diameter = 5;
 638                 max_tunnel_diameter = ps->range(7, ps->range(8, 24));
 639         } else {
 640                 part_max_length_rs = ps->range(2, 9);
 641                 tunnel_routepoints = ps->range(10, ps->range(15, 30));
 642         }
 643         large_cave_is_flat = (ps->range(0, 1) == 0);
 644
 645         main_direction = v3f(0, 0, 0);
 646
 647         // Allowed route area size in nodes
 648         ar = node_max - node_min + v3s16(1, 1, 1);
 649         // Area starting point in nodes
 650         of = node_min;
 651
 652         // Allow a bit more
 653         //(this should be more than the maximum radius of the tunnel)
 654         const s16 max_spread_amount = MAP_BLOCKSIZE;
 655         const s16 insure = 10;
 656         s16 more = MYMAX(max_spread_amount - max_tunnel_diameter / 2 - insure, 1);
 657         ar += v3s16(1, 0, 1) * more * 2;
 658         of -= v3s16(1, 0, 1) * more;
 659
 660         route_y_min = 0;
 661         // Allow half a diameter + 7 over stone surface
 662         route_y_max = -of.Y + max_stone_height + max_tunnel_diameter / 2 + 7;
 663
 664         // Limit maximum to area
 665         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
 666
 667         if (large_cave) {
 668                 s16 minpos = 0;
 669                 if (node_min.Y < water_level && node_max.Y > water_level) {
 670                         minpos = water_level - max_tunnel_diameter / 3 - of.Y;
 671                         route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
 672                 }
 673                 route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
 674                 route_y_min = rangelim(route_y_min, 0, route_y_max);
 675         }
 676
 677         s16 route_start_y_min = route_y_min;
 678         s16 route_start_y_max = route_y_max;
 679
 680         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 681         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 682
 683         // Randomize starting position
 684         orp.Z = (float)(ps->next() % ar.Z) + 0.5f;
 685         orp.Y = (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5f;
 686         orp.X = (float)(ps->next() % ar.X) + 0.5f;
 687
 688         // Add generation notify begin event
 689         if (gennotify != NULL) {
 690                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 691                 GenNotifyType notifytype = large_cave ?
 692                         GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
 693                 gennotify->addEvent(notifytype, abs_pos);
 694         }
 695
 696         // Generate some tunnel starting from orp
 697         for (u16 j = 0; j < tunnel_routepoints; j++)
 698                 makeTunnel(j % dswitchint == 0);
 699
 700         // Add generation notify end event
 701         if (gennotify != NULL) {
 702                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 703                 GenNotifyType notifytype = large_cave ?
 704                         GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
 705                 gennotify->addEvent(notifytype, abs_pos);
 706         }
 707 }
 708
 709
 710 void CavesV6::makeTunnel(bool dirswitch)
 711 {
 712         if (dirswitch && !large_cave) {
 713                 main_direction.Z = ((float)(ps->next() % 20) - (float)10) / 10;
 714                 main_direction.Y = ((float)(ps->next() % 20) - (float)10) / 30;
 715                 main_direction.X = ((float)(ps->next() % 20) - (float)10) / 10;
 716
 717                 main_direction *= (float)ps->range(0, 10) / 10;
 718         }
 719
 720         // Randomize size
 721         s16 min_d = min_tunnel_diameter;
 722         s16 max_d = max_tunnel_diameter;
 723         rs = ps->range(min_d, max_d);
 724         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 725
 726         v3s16 maxlen;
 727         if (large_cave) {
 728                 maxlen = v3s16(
 729                         rs_part_max_length_rs,
 730                         rs_part_max_length_rs / 2,
 731                         rs_part_max_length_rs
 732                 );
 733         } else {
 734                 maxlen = v3s16(
 735                         rs_part_max_length_rs,
 736                         ps->range(1, rs_part_max_length_rs),
 737                         rs_part_max_length_rs
 738                 );
 739         }
 740
 741         v3f vec;
 742         vec.Z = (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2;
 743         vec.Y = (float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2;
 744         vec.X = (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2;
 745
 746         // Jump downward sometimes
 747         if (!large_cave && ps->range(0, 12) == 0) {
 748                 vec.Z = (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2;
 749                 vec.Y = (float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y;
 750                 vec.X = (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2;
 751         }
 752
 753         // Do not make caves that are entirely above ground, to fix shadow bugs
 754         // caused by overgenerated large caves.
 755         // It is only necessary to check the startpoint and endpoint.
 756         v3s16 p1 = v3s16(orp.X, orp.Y, orp.Z) + of + rs / 2;
 757         v3s16 p2 = v3s16(vec.X, vec.Y, vec.Z) + p1;
 758
 759         // If startpoint and endpoint are above ground, disable placement of nodes
 760         // in carveRoute while still running all PseudoRandom calls to ensure caves
 761         // are consistent with existing worlds.
 762         bool tunnel_above_ground =
 763                 p1.Y > getSurfaceFromHeightmap(p1) &&
 764                 p2.Y > getSurfaceFromHeightmap(p2);
 765
 766         vec += main_direction;
 767
 768         v3f rp = orp + vec;
 769         if (rp.X < 0)
 770                 rp.X = 0;
 771         else if (rp.X >= ar.X)
 772                 rp.X = ar.X - 1;
 773
 774         if (rp.Y < route_y_min)
 775                 rp.Y = route_y_min;
 776         else if (rp.Y >= route_y_max)
 777                 rp.Y = route_y_max - 1;
 778
 779         if (rp.Z < 0)
 780                 rp.Z = 0;
 781         else if (rp.Z >= ar.Z)
 782                 rp.Z = ar.Z - 1;
 783
 784         vec = rp - orp;
 785
 786         float veclen = vec.getLength();
 787         // As odd as it sounds, veclen is *exactly* 0.0 sometimes, causing a FPE
 788         if (veclen < 0.05f)
 789                 veclen = 1.0f;
 790
 791         // Every second section is rough
 792         bool randomize_xz = (ps2->range(1, 2) == 1);
 793
 794         // Carve routes
 795         for (float f = 0.f; f < 1.0f; f += 1.0f / veclen)
 796                 carveRoute(vec, f, randomize_xz, tunnel_above_ground);
 797
 798         orp = rp;
 799 }
 800
 801
 802 void CavesV6::carveRoute(v3f vec, float f, bool randomize_xz,
 803         bool tunnel_above_ground)
 804 {
 805         MapNode airnode(CONTENT_AIR);
 806         MapNode waternode(c_water_source);
 807         MapNode lavanode(c_lava_source);
 808
 809         v3s16 startp(orp.X, orp.Y, orp.Z);
 810         startp += of;
 811
 812         v3f fp = orp + vec * f;
 813         fp.X += 0.1f * ps->range(-10, 10);
 814         fp.Z += 0.1f * ps->range(-10, 10);
 815         v3s16 cp(fp.X, fp.Y, fp.Z);
 816
 817         s16 d0 = -rs / 2;
 818         s16 d1 = d0 + rs;
 819         if (randomize_xz) {
 820                 d0 += ps->range(-1, 1);
 821                 d1 += ps->range(-1, 1);
 822         }
 823
 824         for (s16 z0 = d0; z0 <= d1; z0++) {
 825                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 826                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 827                         if (tunnel_above_ground)
 828                                 continue;
 829
 830                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 831                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 832                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 833                                 if (large_cave_is_flat) {
 834                                         // Make large caves not so tall
 835                                         if (rs > 7 && abs(y0) >= rs / 3)
 836                                                 continue;
 837                                 }
 838
 839                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 840                                 p += of;
 841
 842                                 if (!vm->m_area.contains(p))
 843                                         continue;
 844
 845                                 u32 i = vm->m_area.index(p);
 846                                 content_t c = vm->m_data[i].getContent();
 847                                 if (!ndef->get(c).is_ground_content)
 848                                         continue;
 849
 850                                 if (large_cave) {
 851                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 852                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 853
 854                                         if (full_ymin < water_level && full_ymax > water_level) {
 855                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 856                                         } else if (full_ymax < water_level) {
 857                                                 vm->m_data[i] = (p.Y < startp.Y - 2) ? lavanode : airnode;
 858                                         } else {
 859                                                 vm->m_data[i] = airnode;
 860                                         }
 861                                 } else {
 862                                         if (c == CONTENT_IGNORE || c == CONTENT_AIR)
 863                                                 continue;
 864
 865                                         vm->m_data[i] = airnode;
 866                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 867                                 }
 868                         }
 869                 }
 870         }
 871 }
 872
 873
 874 inline s16 CavesV6::getSurfaceFromHeightmap(v3s16 p)
 875 {
 876         if (heightmap != NULL &&
 877                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 878                         p.X >= node_min.X && p.X <= node_max.X) {
 879                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 880                 return heightmap[index];
 881         }
 882
 883         return water_level;
 884
 885 }