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 = (Biome *)bmgn->calcBiomeAtPoint(cpabs);
 511                 if (biome->c_cave_liquid != CONTENT_IGNORE)
 512                         liquidnode = biome->c_cave_liquid;
 513         }
 514
 515         if (liquidnode == CONTENT_IGNORE) {
 516                 // Fallback to classic behaviour using point 'startp'
 517                 float nval = NoisePerlin3D(np_caveliquids, startp.X,
 518                         startp.Y, startp.Z, seed);
 519                 liquidnode = (nval < 0.40f && node_max.Y < lava_depth) ?
 520                         lavanode : waternode;
 521         }
 522
 523         s16 d0 = -rs / 2;
 524         s16 d1 = d0 + rs;
 525         if (randomize_xz) {
 526                 d0 += ps->range(-1, 1);
 527                 d1 += ps->range(-1, 1);
 528         }
 529
 530         bool flat_cave_floor = !large_cave && ps->range(0, 2) == 2;
 531
 532         for (s16 z0 = d0; z0 <= d1; z0++) {
 533                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 534                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 535                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 536
 537                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 538
 539                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 540                                 // Make better floors in small caves
 541                                 if (flat_cave_floor && y0 <= -rs / 2 && rs <= 7)
 542                                         continue;
 543
 544                                 if (large_cave_is_flat) {
 545                                         // Make large caves not so tall
 546                                         if (rs > 7 && abs(y0) >= rs / 3)
 547                                                 continue;
 548                                 }
 549
 550                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 551                                 p += of;
 552
 553                                 if (!vm->m_area.contains(p))
 554                                         continue;
 555
 556                                 u32 i = vm->m_area.index(p);
 557                                 content_t c = vm->m_data[i].getContent();
 558                                 if (!ndef->get(c).is_ground_content)
 559                                         continue;
 560
 561                                 if (large_cave) {
 562                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 563                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 564
 565                                         if (flooded && full_ymin < water_level && full_ymax > water_level)
 566                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 567                                         else if (flooded && full_ymax < water_level)
 568                                                 vm->m_data[i] = (p.Y < startp.Y - 4) ? liquidnode : airnode;
 569                                         else
 570                                                 vm->m_data[i] = airnode;
 571                                 } else {
 572                                         if (c == CONTENT_IGNORE)
 573                                                 continue;
 574
 575                                         vm->m_data[i] = airnode;
 576                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 577                                 }
 578                         }
 579                 }
 580         }
 581 }
 582
 583
 584 inline bool CavesRandomWalk::isPosAboveSurface(v3s16 p)
 585 {
 586         if (heightmap != NULL &&
 587                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 588                         p.X >= node_min.X && p.X <= node_max.X) {
 589                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 590                 if (heightmap[index] < p.Y)
 591                         return true;
 592         } else if (p.Y > water_level) {
 593                 return true;
 594         }
 595
 596         return false;
 597 }
 598
 599
 600 ////
 601 //// CavesV6
 602 ////
 603
 604 CavesV6::CavesV6(const NodeDefManager *ndef, GenerateNotifier *gennotify,
 605         int water_level, content_t water_source, content_t lava_source)
 606 {
 607         assert(ndef);
 608
 609         this->ndef        = ndef;
 610         this->gennotify   = gennotify;
 611         this->water_level = water_level;
 612
 613         c_water_source = water_source;
 614         if (c_water_source == CONTENT_IGNORE)
 615                 c_water_source = ndef->getId("mapgen_water_source");
 616         if (c_water_source == CONTENT_IGNORE)
 617                 c_water_source = CONTENT_AIR;
 618
 619         c_lava_source = lava_source;
 620         if (c_lava_source == CONTENT_IGNORE)
 621                 c_lava_source = ndef->getId("mapgen_lava_source");
 622         if (c_lava_source == CONTENT_IGNORE)
 623                 c_lava_source = CONTENT_AIR;
 624 }
 625
 626
 627 void CavesV6::makeCave(MMVManip *vm, v3s16 nmin, v3s16 nmax,
 628         PseudoRandom *ps, PseudoRandom *ps2,
 629         bool is_large_cave, int max_stone_height, s16 *heightmap)
 630 {
 631         assert(vm);
 632         assert(ps);
 633         assert(ps2);
 634
 635         this->vm         = vm;
 636         this->ps         = ps;
 637         this->ps2        = ps2;
 638         this->node_min   = nmin;
 639         this->node_max   = nmax;
 640         this->heightmap  = heightmap;
 641         this->large_cave = is_large_cave;
 642
 643         this->ystride = nmax.X - nmin.X + 1;
 644
 645         // Set initial parameters from randomness
 646         min_tunnel_diameter = 2;
 647         max_tunnel_diameter = ps->range(2, 6);
 648         int dswitchint      = ps->range(1, 14);
 649         if (large_cave) {
 650                 part_max_length_rs  = ps->range(2, 4);
 651                 tunnel_routepoints  = ps->range(5, ps->range(15, 30));
 652                 min_tunnel_diameter = 5;
 653                 max_tunnel_diameter = ps->range(7, ps->range(8, 24));
 654         } else {
 655                 part_max_length_rs = ps->range(2, 9);
 656                 tunnel_routepoints = ps->range(10, ps->range(15, 30));
 657         }
 658         large_cave_is_flat = (ps->range(0, 1) == 0);
 659
 660         main_direction = v3f(0, 0, 0);
 661
 662         // Allowed route area size in nodes
 663         ar = node_max - node_min + v3s16(1, 1, 1);
 664         // Area starting point in nodes
 665         of = node_min;
 666
 667         // Allow a bit more
 668         //(this should be more than the maximum radius of the tunnel)
 669         const s16 max_spread_amount = MAP_BLOCKSIZE;
 670         const s16 insure = 10;
 671         s16 more = MYMAX(max_spread_amount - max_tunnel_diameter / 2 - insure, 1);
 672         ar += v3s16(1, 0, 1) * more * 2;
 673         of -= v3s16(1, 0, 1) * more;
 674
 675         route_y_min = 0;
 676         // Allow half a diameter + 7 over stone surface
 677         route_y_max = -of.Y + max_stone_height + max_tunnel_diameter / 2 + 7;
 678
 679         // Limit maximum to area
 680         route_y_max = rangelim(route_y_max, 0, ar.Y - 1);
 681
 682         if (large_cave) {
 683                 s16 minpos = 0;
 684                 if (node_min.Y < water_level && node_max.Y > water_level) {
 685                         minpos = water_level - max_tunnel_diameter / 3 - of.Y;
 686                         route_y_max = water_level + max_tunnel_diameter / 3 - of.Y;
 687                 }
 688                 route_y_min = ps->range(minpos, minpos + max_tunnel_diameter);
 689                 route_y_min = rangelim(route_y_min, 0, route_y_max);
 690         }
 691
 692         s16 route_start_y_min = route_y_min;
 693         s16 route_start_y_max = route_y_max;
 694
 695         route_start_y_min = rangelim(route_start_y_min, 0, ar.Y - 1);
 696         route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y - 1);
 697
 698         // Randomize starting position
 699         orp.Z = (float)(ps->next() % ar.Z) + 0.5f;
 700         orp.Y = (float)(ps->range(route_start_y_min, route_start_y_max)) + 0.5f;
 701         orp.X = (float)(ps->next() % ar.X) + 0.5f;
 702
 703         // Add generation notify begin event
 704         if (gennotify != NULL) {
 705                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 706                 GenNotifyType notifytype = large_cave ?
 707                         GENNOTIFY_LARGECAVE_BEGIN : GENNOTIFY_CAVE_BEGIN;
 708                 gennotify->addEvent(notifytype, abs_pos);
 709         }
 710
 711         // Generate some tunnel starting from orp
 712         for (u16 j = 0; j < tunnel_routepoints; j++)
 713                 makeTunnel(j % dswitchint == 0);
 714
 715         // Add generation notify end event
 716         if (gennotify != NULL) {
 717                 v3s16 abs_pos(of.X + orp.X, of.Y + orp.Y, of.Z + orp.Z);
 718                 GenNotifyType notifytype = large_cave ?
 719                         GENNOTIFY_LARGECAVE_END : GENNOTIFY_CAVE_END;
 720                 gennotify->addEvent(notifytype, abs_pos);
 721         }
 722 }
 723
 724
 725 void CavesV6::makeTunnel(bool dirswitch)
 726 {
 727         if (dirswitch && !large_cave) {
 728                 main_direction.Z = ((float)(ps->next() % 20) - (float)10) / 10;
 729                 main_direction.Y = ((float)(ps->next() % 20) - (float)10) / 30;
 730                 main_direction.X = ((float)(ps->next() % 20) - (float)10) / 10;
 731
 732                 main_direction *= (float)ps->range(0, 10) / 10;
 733         }
 734
 735         // Randomize size
 736         s16 min_d = min_tunnel_diameter;
 737         s16 max_d = max_tunnel_diameter;
 738         rs = ps->range(min_d, max_d);
 739         s16 rs_part_max_length_rs = rs * part_max_length_rs;
 740
 741         v3s16 maxlen;
 742         if (large_cave) {
 743                 maxlen = v3s16(
 744                         rs_part_max_length_rs,
 745                         rs_part_max_length_rs / 2,
 746                         rs_part_max_length_rs
 747                 );
 748         } else {
 749                 maxlen = v3s16(
 750                         rs_part_max_length_rs,
 751                         ps->range(1, rs_part_max_length_rs),
 752                         rs_part_max_length_rs
 753                 );
 754         }
 755
 756         v3f vec;
 757         vec.Z = (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2;
 758         vec.Y = (float)(ps->next() % maxlen.Y) - (float)maxlen.Y / 2;
 759         vec.X = (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2;
 760
 761         // Jump downward sometimes
 762         if (!large_cave && ps->range(0, 12) == 0) {
 763                 vec.Z = (float)(ps->next() % maxlen.Z) - (float)maxlen.Z / 2;
 764                 vec.Y = (float)(ps->next() % (maxlen.Y * 2)) - (float)maxlen.Y;
 765                 vec.X = (float)(ps->next() % maxlen.X) - (float)maxlen.X / 2;
 766         }
 767
 768         // Do not make caves that are entirely above ground, to fix shadow bugs
 769         // caused by overgenerated large caves.
 770         // It is only necessary to check the startpoint and endpoint.
 771         v3s16 p1 = v3s16(orp.X, orp.Y, orp.Z) + of + rs / 2;
 772         v3s16 p2 = v3s16(vec.X, vec.Y, vec.Z) + p1;
 773
 774         // If startpoint and endpoint are above ground, disable placement of nodes
 775         // in carveRoute while still running all PseudoRandom calls to ensure caves
 776         // are consistent with existing worlds.
 777         bool tunnel_above_ground =
 778                 p1.Y > getSurfaceFromHeightmap(p1) &&
 779                 p2.Y > getSurfaceFromHeightmap(p2);
 780
 781         vec += main_direction;
 782
 783         v3f rp = orp + vec;
 784         if (rp.X < 0)
 785                 rp.X = 0;
 786         else if (rp.X >= ar.X)
 787                 rp.X = ar.X - 1;
 788
 789         if (rp.Y < route_y_min)
 790                 rp.Y = route_y_min;
 791         else if (rp.Y >= route_y_max)
 792                 rp.Y = route_y_max - 1;
 793
 794         if (rp.Z < 0)
 795                 rp.Z = 0;
 796         else if (rp.Z >= ar.Z)
 797                 rp.Z = ar.Z - 1;
 798
 799         vec = rp - orp;
 800
 801         float veclen = vec.getLength();
 802         // As odd as it sounds, veclen is *exactly* 0.0 sometimes, causing a FPE
 803         if (veclen < 0.05f)
 804                 veclen = 1.0f;
 805
 806         // Every second section is rough
 807         bool randomize_xz = (ps2->range(1, 2) == 1);
 808
 809         // Carve routes
 810         for (float f = 0.f; f < 1.0f; f += 1.0f / veclen)
 811                 carveRoute(vec, f, randomize_xz, tunnel_above_ground);
 812
 813         orp = rp;
 814 }
 815
 816
 817 void CavesV6::carveRoute(v3f vec, float f, bool randomize_xz,
 818         bool tunnel_above_ground)
 819 {
 820         MapNode airnode(CONTENT_AIR);
 821         MapNode waternode(c_water_source);
 822         MapNode lavanode(c_lava_source);
 823
 824         v3s16 startp(orp.X, orp.Y, orp.Z);
 825         startp += of;
 826
 827         v3f fp = orp + vec * f;
 828         fp.X += 0.1f * ps->range(-10, 10);
 829         fp.Z += 0.1f * ps->range(-10, 10);
 830         v3s16 cp(fp.X, fp.Y, fp.Z);
 831
 832         s16 d0 = -rs / 2;
 833         s16 d1 = d0 + rs;
 834         if (randomize_xz) {
 835                 d0 += ps->range(-1, 1);
 836                 d1 += ps->range(-1, 1);
 837         }
 838
 839         for (s16 z0 = d0; z0 <= d1; z0++) {
 840                 s16 si = rs / 2 - MYMAX(0, abs(z0) - rs / 7 - 1);
 841                 for (s16 x0 = -si - ps->range(0,1); x0 <= si - 1 + ps->range(0,1); x0++) {
 842                         if (tunnel_above_ground)
 843                                 continue;
 844
 845                         s16 maxabsxz = MYMAX(abs(x0), abs(z0));
 846                         s16 si2 = rs / 2 - MYMAX(0, maxabsxz - rs / 7 - 1);
 847                         for (s16 y0 = -si2; y0 <= si2; y0++) {
 848                                 if (large_cave_is_flat) {
 849                                         // Make large caves not so tall
 850                                         if (rs > 7 && abs(y0) >= rs / 3)
 851                                                 continue;
 852                                 }
 853
 854                                 v3s16 p(cp.X + x0, cp.Y + y0, cp.Z + z0);
 855                                 p += of;
 856
 857                                 if (!vm->m_area.contains(p))
 858                                         continue;
 859
 860                                 u32 i = vm->m_area.index(p);
 861                                 content_t c = vm->m_data[i].getContent();
 862                                 if (!ndef->get(c).is_ground_content)
 863                                         continue;
 864
 865                                 if (large_cave) {
 866                                         int full_ymin = node_min.Y - MAP_BLOCKSIZE;
 867                                         int full_ymax = node_max.Y + MAP_BLOCKSIZE;
 868
 869                                         if (full_ymin < water_level && full_ymax > water_level) {
 870                                                 vm->m_data[i] = (p.Y <= water_level) ? waternode : airnode;
 871                                         } else if (full_ymax < water_level) {
 872                                                 vm->m_data[i] = (p.Y < startp.Y - 2) ? lavanode : airnode;
 873                                         } else {
 874                                                 vm->m_data[i] = airnode;
 875                                         }
 876                                 } else {
 877                                         if (c == CONTENT_IGNORE || c == CONTENT_AIR)
 878                                                 continue;
 879
 880                                         vm->m_data[i] = airnode;
 881                                         vm->m_flags[i] |= VMANIP_FLAG_CAVE;
 882                                 }
 883                         }
 884                 }
 885         }
 886 }
 887
 888
 889 inline s16 CavesV6::getSurfaceFromHeightmap(v3s16 p)
 890 {
 891         if (heightmap != NULL &&
 892                         p.Z >= node_min.Z && p.Z <= node_max.Z &&
 893                         p.X >= node_min.X && p.X <= node_max.X) {
 894                 u32 index = (p.Z - node_min.Z) * ystride + (p.X - node_min.X);
 895                 return heightmap[index];
 896         }
 897
 898         return water_level;
 899
 900 }