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