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