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