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