src/mapgen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2015 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
   4 Copyright (C) 2010-2015 celeron55, Perttu Ahola <celeron55@gmail.com>
   5
   6 This program is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU Lesser General Public License as published by
   8 the Free Software Foundation; either version 2.1 of the License, or
   9 (at your option) any later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU Lesser General Public License for more details.
  15
  16 You should have received a copy of the GNU Lesser General Public License along
  17 with this program; if not, write to the Free Software Foundation, Inc.,
  18 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  19 */
  20
  21 #include "mapgen.h"
  22 #include "voxel.h"
  23 #include "noise.h"
  24 #include "gamedef.h"
  25 #include "mg_biome.h"
  26 #include "mapblock.h"
  27 #include "mapnode.h"
  28 #include "map.h"
  29 #include "content_sao.h"
  30 #include "nodedef.h"
  31 #include "emerge.h"
  32 #include "voxelalgorithms.h"
  33 #include "porting.h"
  34 #include "profiler.h"
  35 #include "settings.h"
  36 #include "treegen.h"
  37 #include "serialization.h"
  38 #include "util/serialize.h"
  39 #include "util/numeric.h"
  40 #include "filesys.h"
  41 #include "log.h"
  42 #include "cavegen.h"
  43 #include "dungeongen.h"
  44
  45 FlagDesc flagdesc_mapgen[] = {
  46         {"trees",       MG_TREES},
  47         {"caves",       MG_CAVES},
  48         {"dungeons",    MG_DUNGEONS},
  49         {"flat",        MG_FLAT},
  50         {"light",       MG_LIGHT},
  51         {"decorations", MG_DECORATIONS},
  52         {NULL,       0}
  53 };
  54
  55 FlagDesc flagdesc_gennotify[] = {
  56         {"dungeon",          1 << GENNOTIFY_DUNGEON},
  57         {"temple",           1 << GENNOTIFY_TEMPLE},
  58         {"cave_begin",       1 << GENNOTIFY_CAVE_BEGIN},
  59         {"cave_end",         1 << GENNOTIFY_CAVE_END},
  60         {"large_cave_begin", 1 << GENNOTIFY_LARGECAVE_BEGIN},
  61         {"large_cave_end",   1 << GENNOTIFY_LARGECAVE_END},
  62         {"decoration",       1 << GENNOTIFY_DECORATION},
  63         {NULL,               0}
  64 };
  65
  66
  67 ////
  68 //// Mapgen
  69 ////
  70
  71 Mapgen::Mapgen()
  72 {
  73         generating  = false;
  74         id          = -1;
  75         seed        = 0;
  76         water_level = 0;
  77         flags       = 0;
  78
  79         vm        = NULL;
  80         ndef      = NULL;
  81         biomegen  = NULL;
  82         biomemap  = NULL;
  83         heightmap = NULL;
  84 }
  85
  86
  87 Mapgen::Mapgen(int mapgenid, MapgenParams *params, EmergeManager *emerge) :
  88         gennotify(emerge->gen_notify_on, &emerge->gen_notify_on_deco_ids)
  89 {
  90         generating  = false;
  91         id          = mapgenid;
  92         water_level = params->water_level;
  93         flags       = params->flags;
  94         csize       = v3s16(1, 1, 1) * (params->chunksize * MAP_BLOCKSIZE);
  95
  96         /*
  97                 We are losing half our entropy by doing this, but it is necessary to
  98                 preserve reverse compatibility.  If the top half of our current 64 bit
  99                 seeds ever starts getting used, existing worlds will break due to a
 100                 different hash outcome and no way to differentiate between versions.
 101
 102                 A solution could be to add a new bit to designate that the top half of
 103                 the seed value should be used, essentially a 1-bit version code, but
 104                 this would require increasing the total size of a seed to 9 bytes (yuck)
 105
 106                 It's probably okay if this never gets fixed.  4.2 billion possibilities
 107                 ought to be enough for anyone.
 108         */
 109         seed = (s32)params->seed;
 110
 111         vm        = NULL;
 112         ndef      = emerge->ndef;
 113         biomegen  = NULL;
 114         biomemap  = NULL;
 115         heightmap = NULL;
 116 }
 117
 118
 119 Mapgen::~Mapgen()
 120 {
 121 }
 122
 123
 124 u32 Mapgen::getBlockSeed(v3s16 p, s32 seed)
 125 {
 126         return (u32)seed   +
 127                 p.Z * 38134234 +
 128                 p.Y * 42123    +
 129                 p.X * 23;
 130 }
 131
 132
 133 u32 Mapgen::getBlockSeed2(v3s16 p, s32 seed)
 134 {
 135         u32 n = 1619 * p.X + 31337 * p.Y + 52591 * p.Z + 1013 * seed;
 136         n = (n >> 13) ^ n;
 137         return (n * (n * n * 60493 + 19990303) + 1376312589);
 138 }
 139
 140
 141 // Returns Y one under area minimum if not found
 142 s16 Mapgen::findGroundLevelFull(v2s16 p2d)
 143 {
 144         v3s16 em = vm->m_area.getExtent();
 145         s16 y_nodes_max = vm->m_area.MaxEdge.Y;
 146         s16 y_nodes_min = vm->m_area.MinEdge.Y;
 147         u32 i = vm->m_area.index(p2d.X, y_nodes_max, p2d.Y);
 148         s16 y;
 149
 150         for (y = y_nodes_max; y >= y_nodes_min; y--) {
 151                 MapNode &n = vm->m_data[i];
 152                 if (ndef->get(n).walkable)
 153                         break;
 154
 155                 vm->m_area.add_y(em, i, -1);
 156         }
 157         return (y >= y_nodes_min) ? y : y_nodes_min - 1;
 158 }
 159
 160
 161 // Returns -MAX_MAP_GENERATION_LIMIT if not found
 162 s16 Mapgen::findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax)
 163 {
 164         v3s16 em = vm->m_area.getExtent();
 165         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 166         s16 y;
 167
 168         for (y = ymax; y >= ymin; y--) {
 169                 MapNode &n = vm->m_data[i];
 170                 if (ndef->get(n).walkable)
 171                         break;
 172
 173                 vm->m_area.add_y(em, i, -1);
 174         }
 175         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 176 }
 177
 178
 179 // Returns -MAX_MAP_GENERATION_LIMIT if not found or if ground is found first
 180 s16 Mapgen::findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax)
 181 {
 182         v3s16 em = vm->m_area.getExtent();
 183         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 184         s16 y;
 185
 186         for (y = ymax; y >= ymin; y--) {
 187                 MapNode &n = vm->m_data[i];
 188                 if (ndef->get(n).walkable)
 189                         return -MAX_MAP_GENERATION_LIMIT;
 190                 else if (ndef->get(n).isLiquid())
 191                         break;
 192
 193                 vm->m_area.add_y(em, i, -1);
 194         }
 195         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 196 }
 197
 198
 199 void Mapgen::updateHeightmap(v3s16 nmin, v3s16 nmax)
 200 {
 201         if (!heightmap)
 202                 return;
 203
 204         //TimeTaker t("Mapgen::updateHeightmap", NULL, PRECISION_MICRO);
 205         int index = 0;
 206         for (s16 z = nmin.Z; z <= nmax.Z; z++) {
 207                 for (s16 x = nmin.X; x <= nmax.X; x++, index++) {
 208                         s16 y = findGroundLevel(v2s16(x, z), nmin.Y, nmax.Y);
 209
 210                         heightmap[index] = y;
 211                 }
 212         }
 213         //printf("updateHeightmap: %dus\n", t.stop());
 214 }
 215
 216 inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
 217 {
 218         u32 vi_neg_x = vi;
 219         vm->m_area.add_x(em, vi_neg_x, -1);
 220         if (vm->m_data[vi_neg_x].getContent() != CONTENT_IGNORE) {
 221                 const ContentFeatures &c_nx = ndef->get(vm->m_data[vi_neg_x]);
 222                 if (c_nx.floodable && !c_nx.isLiquid())
 223                         return true;
 224         }
 225         u32 vi_pos_x = vi;
 226         vm->m_area.add_x(em, vi_pos_x, +1);
 227         if (vm->m_data[vi_pos_x].getContent() != CONTENT_IGNORE) {
 228                 const ContentFeatures &c_px = ndef->get(vm->m_data[vi_pos_x]);
 229                 if (c_px.floodable && !c_px.isLiquid())
 230                         return true;
 231         }
 232         u32 vi_neg_z = vi;
 233         vm->m_area.add_z(em, vi_neg_z, -1);
 234         if (vm->m_data[vi_neg_z].getContent() != CONTENT_IGNORE) {
 235                 const ContentFeatures &c_nz = ndef->get(vm->m_data[vi_neg_z]);
 236                 if (c_nz.floodable && !c_nz.isLiquid())
 237                         return true;
 238         }
 239         u32 vi_pos_z = vi;
 240         vm->m_area.add_z(em, vi_pos_z, +1);
 241         if (vm->m_data[vi_pos_z].getContent() != CONTENT_IGNORE) {
 242                 const ContentFeatures &c_pz = ndef->get(vm->m_data[vi_pos_z]);
 243                 if (c_pz.floodable && !c_pz.isLiquid())
 244                         return true;
 245         }
 246         return false;
 247 }
 248
 249 void Mapgen::updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax)
 250 {
 251         bool isignored, isliquid, wasignored, wasliquid, waschecked, waspushed;
 252         v3s16 em  = vm->m_area.getExtent();
 253
 254         for (s16 z = nmin.Z + 1; z <= nmax.Z - 1; z++)
 255         for (s16 x = nmin.X + 1; x <= nmax.X - 1; x++) {
 256                 wasignored = true;
 257                 wasliquid = false;
 258                 waschecked = false;
 259                 waspushed = false;
 260
 261                 u32 vi = vm->m_area.index(x, nmax.Y, z);
 262                 for (s16 y = nmax.Y; y >= nmin.Y; y--) {
 263                         isignored = vm->m_data[vi].getContent() == CONTENT_IGNORE;
 264                         isliquid = ndef->get(vm->m_data[vi]).isLiquid();
 265
 266                         if (isignored || wasignored || isliquid == wasliquid) {
 267                                 // Neither topmost node of liquid column nor topmost node below column
 268                                 waschecked = false;
 269                                 waspushed = false;
 270                         } else if (isliquid) {
 271                                 // This is the topmost node in the column
 272                                 bool ispushed = false;
 273                                 if (isLiquidHorizontallyFlowable(vi, em)) {
 274                                         trans_liquid->push_back(v3s16(x, y, z));
 275                                         ispushed = true;
 276                                 }
 277                                 // Remember waschecked and waspushed to avoid repeated
 278                                 // checks/pushes in case the column consists of only this node
 279                                 waschecked = true;
 280                                 waspushed = ispushed;
 281                         } else {
 282                                 // This is the topmost node below a liquid column
 283                                 u32 vi_above = vi;
 284                                 vm->m_area.add_y(em, vi_above, 1);
 285                                 if (!waspushed && (ndef->get(vm->m_data[vi]).floodable ||
 286                                                 (!waschecked && isLiquidHorizontallyFlowable(vi_above, em)))) {
 287                                         // Push back the lowest node in the column which is one
 288                                         // node above this one
 289                                         trans_liquid->push_back(v3s16(x, y + 1, z));
 290                                 }
 291                         }
 292
 293                         wasliquid = isliquid;
 294                         wasignored = isignored;
 295                         vm->m_area.add_y(em, vi, -1);
 296                 }
 297         }
 298 }
 299
 300
 301 void Mapgen::setLighting(u8 light, v3s16 nmin, v3s16 nmax)
 302 {
 303         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 304         VoxelArea a(nmin, nmax);
 305
 306         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 307                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 308                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 309                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++)
 310                                 vm->m_data[i].param1 = light;
 311                 }
 312         }
 313 }
 314
 315
 316 void Mapgen::lightSpread(VoxelArea &a, v3s16 p, u8 light)
 317 {
 318         if (light <= 1 || !a.contains(p))
 319                 return;
 320
 321         u32 vi = vm->m_area.index(p);
 322         MapNode &n = vm->m_data[vi];
 323
 324         // Decay light in each of the banks separately
 325         u8 light_day = light & 0x0F;
 326         if (light_day > 0)
 327                 light_day -= 0x01;
 328
 329         u8 light_night = light & 0xF0;
 330         if (light_night > 0)
 331                 light_night -= 0x10;
 332
 333         // Bail out only if we have no more light from either bank to propogate, or
 334         // we hit a solid block that light cannot pass through.
 335         if ((light_day  <= (n.param1 & 0x0F) &&
 336                 light_night <= (n.param1 & 0xF0)) ||
 337                 !ndef->get(n).light_propagates)
 338                 return;
 339
 340         // Since this recursive function only terminates when there is no light from
 341         // either bank left, we need to take the max of both banks into account for
 342         // the case where spreading has stopped for one light bank but not the other.
 343         light = MYMAX(light_day, n.param1 & 0x0F) |
 344                         MYMAX(light_night, n.param1 & 0xF0);
 345
 346         n.param1 = light;
 347
 348         lightSpread(a, p + v3s16(0, 0, 1), light);
 349         lightSpread(a, p + v3s16(0, 1, 0), light);
 350         lightSpread(a, p + v3s16(1, 0, 0), light);
 351         lightSpread(a, p - v3s16(0, 0, 1), light);
 352         lightSpread(a, p - v3s16(0, 1, 0), light);
 353         lightSpread(a, p - v3s16(1, 0, 0), light);
 354 }
 355
 356
 357 void Mapgen::calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
 358         bool propagate_shadow)
 359 {
 360         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 361         //TimeTaker t("updateLighting");
 362
 363         propagateSunlight(nmin, nmax, propagate_shadow);
 364         spreadLight(full_nmin, full_nmax);
 365
 366         //printf("updateLighting: %dms\n", t.stop());
 367 }
 368
 369
 370 void Mapgen::propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow)
 371 {
 372         //TimeTaker t("propagateSunlight");
 373         VoxelArea a(nmin, nmax);
 374         bool block_is_underground = (water_level >= nmax.Y);
 375         v3s16 em = vm->m_area.getExtent();
 376
 377         // NOTE: Direct access to the low 4 bits of param1 is okay here because,
 378         // by definition, sunlight will never be in the night lightbank.
 379
 380         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 381                 for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++) {
 382                         // see if we can get a light value from the overtop
 383                         u32 i = vm->m_area.index(x, a.MaxEdge.Y + 1, z);
 384                         if (vm->m_data[i].getContent() == CONTENT_IGNORE) {
 385                                 if (block_is_underground)
 386                                         continue;
 387                         } else if ((vm->m_data[i].param1 & 0x0F) != LIGHT_SUN &&
 388                                         propagate_shadow) {
 389                                 continue;
 390                         }
 391                         vm->m_area.add_y(em, i, -1);
 392
 393                         for (int y = a.MaxEdge.Y; y >= a.MinEdge.Y; y--) {
 394                                 MapNode &n = vm->m_data[i];
 395                                 if (!ndef->get(n).sunlight_propagates)
 396                                         break;
 397                                 n.param1 = LIGHT_SUN;
 398                                 vm->m_area.add_y(em, i, -1);
 399                         }
 400                 }
 401         }
 402         //printf("propagateSunlight: %dms\n", t.stop());
 403 }
 404
 405
 406 void Mapgen::spreadLight(v3s16 nmin, v3s16 nmax)
 407 {
 408         //TimeTaker t("spreadLight");
 409         VoxelArea a(nmin, nmax);
 410
 411         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 412                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 413                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 414                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++) {
 415                                 MapNode &n = vm->m_data[i];
 416                                 if (n.getContent() == CONTENT_IGNORE)
 417                                         continue;
 418
 419                                 const ContentFeatures &cf = ndef->get(n);
 420                                 if (!cf.light_propagates)
 421                                         continue;
 422
 423                                 // TODO(hmmmmm): Abstract away direct param1 accesses with a
 424                                 // wrapper, but something lighter than MapNode::get/setLight
 425
 426                                 u8 light_produced = cf.light_source;
 427                                 if (light_produced)
 428                                         n.param1 = light_produced | (light_produced << 4);
 429
 430                                 u8 light = n.param1;
 431                                 if (light) {
 432                                         lightSpread(a, v3s16(x,     y,     z + 1), light);
 433                                         lightSpread(a, v3s16(x,     y + 1, z    ), light);
 434                                         lightSpread(a, v3s16(x + 1, y,     z    ), light);
 435                                         lightSpread(a, v3s16(x,     y,     z - 1), light);
 436                                         lightSpread(a, v3s16(x,     y - 1, z    ), light);
 437                                         lightSpread(a, v3s16(x - 1, y,     z    ), light);
 438                                 }
 439                         }
 440                 }
 441         }
 442
 443         //printf("spreadLight: %dms\n", t.stop());
 444 }
 445
 446
 447 ////
 448 //// MapgenBasic
 449 ////
 450
 451 MapgenBasic::MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge)
 452         : Mapgen(mapgenid, params, emerge)
 453 {
 454         this->m_emerge = emerge;
 455         this->m_bmgr   = emerge->biomemgr;
 456
 457         //// Here, 'stride' refers to the number of elements needed to skip to index
 458         //// an adjacent element for that coordinate in noise/height/biome maps
 459         //// (*not* vmanip content map!)
 460
 461         // Note there is no X stride explicitly defined.  Items adjacent in the X
 462         // coordinate are assumed to be adjacent in memory as well (i.e. stride of 1).
 463
 464         // Number of elements to skip to get to the next Y coordinate
 465         this->ystride = csize.X;
 466
 467         // Number of elements to skip to get to the next Z coordinate
 468         this->zstride = csize.X * csize.Y;
 469
 470         // Z-stride value for maps oversized for 1-down overgeneration
 471         this->zstride_1d = csize.X * (csize.Y + 1);
 472
 473         // Z-stride value for maps oversized for 1-up 1-down overgeneration
 474         this->zstride_1u1d = csize.X * (csize.Y + 2);
 475
 476         //// Allocate heightmap
 477         this->heightmap = new s16[csize.X * csize.Z];
 478
 479         //// Initialize biome generator
 480         // TODO(hmmmm): should we have a way to disable biomemanager biomes?
 481         biomegen = m_bmgr->createBiomeGen(BIOMEGEN_ORIGINAL, params->bparams, csize);
 482         biomemap = biomegen->biomemap;
 483
 484         //// Look up some commonly used content
 485         c_stone              = ndef->getId("mapgen_stone");
 486         c_water_source       = ndef->getId("mapgen_water_source");
 487         c_desert_stone       = ndef->getId("mapgen_desert_stone");
 488         c_sandstone          = ndef->getId("mapgen_sandstone");
 489         c_river_water_source = ndef->getId("mapgen_river_water_source");
 490
 491         // Fall back to more basic content if not defined
 492         if (c_desert_stone == CONTENT_IGNORE)
 493                 c_desert_stone = c_stone;
 494         if (c_sandstone == CONTENT_IGNORE)
 495                 c_sandstone = c_stone;
 496         if (c_river_water_source == CONTENT_IGNORE)
 497                 c_river_water_source = c_water_source;
 498
 499         //// Content used for dungeon generation
 500         c_cobble               = ndef->getId("mapgen_cobble");
 501         c_stair_cobble         = ndef->getId("mapgen_stair_cobble");
 502         c_mossycobble          = ndef->getId("mapgen_mossycobble");
 503         c_sandstonebrick       = ndef->getId("mapgen_sandstonebrick");
 504         c_stair_sandstonebrick = ndef->getId("mapgen_stair_sandstonebrick");
 505
 506         // Fall back to more basic content if not defined
 507         if (c_mossycobble == CONTENT_IGNORE)
 508                 c_mossycobble = c_cobble;
 509         if (c_stair_cobble == CONTENT_IGNORE)
 510                 c_stair_cobble = c_cobble;
 511         if (c_sandstonebrick == CONTENT_IGNORE)
 512                 c_sandstonebrick = c_sandstone;
 513         if (c_stair_sandstonebrick == CONTENT_IGNORE)
 514                 c_stair_sandstonebrick = c_sandstone;
 515 }
 516
 517
 518 MapgenBasic::~MapgenBasic()
 519 {
 520         delete biomegen;
 521         delete []heightmap;
 522 }
 523
 524
 525 MgStoneType MapgenBasic::generateBiomes()
 526 {
 527         // can't generate biomes without a biome generator!
 528         assert(biomegen);
 529         assert(biomemap);
 530
 531         v3s16 em = vm->m_area.getExtent();
 532         u32 index = 0;
 533         MgStoneType stone_type = MGSTONE_STONE;
 534
 535         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 536
 537         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 538         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 539                 Biome *biome = NULL;
 540                 u16 depth_top = 0;
 541                 u16 base_filler = 0;
 542                 u16 depth_water_top = 0;
 543                 u16 depth_riverbed = 0;
 544                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 545
 546                 // Check node at base of mapchunk above, either a node of a previously
 547                 // generated mapchunk or if not, a node of overgenerated base terrain.
 548                 content_t c_above = vm->m_data[vi + em.X].getContent();
 549                 bool air_above = c_above == CONTENT_AIR;
 550                 bool river_water_above = c_above == c_river_water_source;
 551                 bool water_above = c_above == c_water_source || river_water_above;
 552
 553                 biomemap[index] = BIOME_NONE;
 554
 555                 // If there is air or water above enable top/filler placement, otherwise force
 556                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 557                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 558
 559                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 560                         content_t c = vm->m_data[vi].getContent();
 561
 562                         // Biome is recalculated each time an upper surface is detected while
 563                         // working down a column. The selected biome then remains in effect for
 564                         // all nodes below until the next surface and biome recalculation.
 565                         // Biome is recalculated:
 566                         // 1. At the surface of stone below air or water.
 567                         // 2. At the surface of water below air.
 568                         // 3. When stone or water is detected but biome has not yet been calculated.
 569                         bool is_stone_surface = (c == c_stone) &&
 570                                 (air_above || water_above || !biome);
 571
 572                         bool is_water_surface =
 573                                 (c == c_water_source || c == c_river_water_source) &&
 574                                 (air_above || !biome);
 575
 576                         if (is_stone_surface || is_water_surface) {
 577                                 biome = biomegen->getBiomeAtIndex(index, y);
 578
 579                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 580                                         biomemap[index] = biome->index;
 581
 582                                 depth_top = biome->depth_top;
 583                                 base_filler = MYMAX(depth_top +
 584                                         biome->depth_filler +
 585                                         noise_filler_depth->result[index], 0.f);
 586                                 depth_water_top = biome->depth_water_top;
 587                                 depth_riverbed = biome->depth_riverbed;
 588
 589                                 // Detect stone type for dungeons during every biome calculation.
 590                                 // This is more efficient than detecting per-node and will not
 591                                 // miss any desert stone or sandstone biomes.
 592                                 if (biome->c_stone == c_desert_stone)
 593                                         stone_type = MGSTONE_DESERT_STONE;
 594                                 else if (biome->c_stone == c_sandstone)
 595                                         stone_type = MGSTONE_SANDSTONE;
 596                         }
 597
 598                         if (c == c_stone) {
 599                                 content_t c_below = vm->m_data[vi - em.X].getContent();
 600
 601                                 // If the node below isn't solid, make this node stone, so that
 602                                 // any top/filler nodes above are structurally supported.
 603                                 // This is done by aborting the cycle of top/filler placement
 604                                 // immediately by forcing nplaced to stone level.
 605                                 if (c_below == CONTENT_AIR
 606                                                 || c_below == c_water_source
 607                                                 || c_below == c_river_water_source)
 608                                         nplaced = U16_MAX;
 609
 610                                 if (river_water_above) {
 611                                         if (nplaced < depth_riverbed) {
 612                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 613                                                 nplaced++;
 614                                         } else {
 615                                                 nplaced = U16_MAX;  // Disable top/filler placement
 616                                                 river_water_above = false;
 617                                         }
 618                                 } else if (nplaced < depth_top) {
 619                                         vm->m_data[vi] = MapNode(biome->c_top);
 620                                         nplaced++;
 621                                 } else if (nplaced < base_filler) {
 622                                         vm->m_data[vi] = MapNode(biome->c_filler);
 623                                         nplaced++;
 624                                 } else {
 625                                         vm->m_data[vi] = MapNode(biome->c_stone);
 626                                 }
 627
 628                                 air_above = false;
 629                                 water_above = false;
 630                         } else if (c == c_water_source) {
 631                                 vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
 632                                                 ? biome->c_water_top : biome->c_water);
 633                                 nplaced = 0;  // Enable top/filler placement for next surface
 634                                 air_above = false;
 635                                 water_above = true;
 636                         } else if (c == c_river_water_source) {
 637                                 vm->m_data[vi] = MapNode(biome->c_river_water);
 638                                 nplaced = 0;  // Enable riverbed placement for next surface
 639                                 air_above = false;
 640                                 water_above = true;
 641                                 river_water_above = true;
 642                         } else if (c == CONTENT_AIR) {
 643                                 nplaced = 0;  // Enable top/filler placement for next surface
 644                                 air_above = true;
 645                                 water_above = false;
 646                         } else {  // Possible various nodes overgenerated from neighbouring mapchunks
 647                                 nplaced = U16_MAX;  // Disable top/filler placement
 648                                 air_above = false;
 649                                 water_above = false;
 650                         }
 651
 652                         vm->m_area.add_y(em, vi, -1);
 653                 }
 654         }
 655
 656         return stone_type;
 657 }
 658
 659
 660 void MapgenBasic::dustTopNodes()
 661 {
 662         if (node_max.Y < water_level)
 663                 return;
 664
 665         v3s16 em = vm->m_area.getExtent();
 666         u32 index = 0;
 667
 668         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 669         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 670                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 671
 672                 if (biome->c_dust == CONTENT_IGNORE)
 673                         continue;
 674
 675                 u32 vi = vm->m_area.index(x, full_node_max.Y, z);
 676                 content_t c_full_max = vm->m_data[vi].getContent();
 677                 s16 y_start;
 678
 679                 if (c_full_max == CONTENT_AIR) {
 680                         y_start = full_node_max.Y - 1;
 681                 } else if (c_full_max == CONTENT_IGNORE) {
 682                         vi = vm->m_area.index(x, node_max.Y + 1, z);
 683                         content_t c_max = vm->m_data[vi].getContent();
 684
 685                         if (c_max == CONTENT_AIR)
 686                                 y_start = node_max.Y;
 687                         else
 688                                 continue;
 689                 } else {
 690                         continue;
 691                 }
 692
 693                 vi = vm->m_area.index(x, y_start, z);
 694                 for (s16 y = y_start; y >= node_min.Y - 1; y--) {
 695                         if (vm->m_data[vi].getContent() != CONTENT_AIR)
 696                                 break;
 697
 698                         vm->m_area.add_y(em, vi, -1);
 699                 }
 700
 701                 content_t c = vm->m_data[vi].getContent();
 702                 if (!ndef->get(c).buildable_to && c != CONTENT_IGNORE && c != biome->c_dust) {
 703                         vm->m_area.add_y(em, vi, 1);
 704                         vm->m_data[vi] = MapNode(biome->c_dust);
 705                 }
 706         }
 707 }
 708
 709
 710 void MapgenBasic::generateCaves(s16 max_stone_y, s16 large_cave_depth)
 711 {
 712         if (max_stone_y < node_min.Y)
 713                 return;
 714
 715         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 716                 &np_cave1, &np_cave2, seed, cave_width);
 717
 718         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 719
 720         if (node_max.Y > large_cave_depth)
 721                 return;
 722
 723         PseudoRandom ps(blockseed + 21343);
 724         u32 bruises_count = ps.range(0, 2);
 725         for (u32 i = 0; i < bruises_count; i++) {
 726                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 727                         c_water_source, CONTENT_IGNORE);
 728
 729                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
 730         }
 731 }
 732
 733
 734 void MapgenBasic::generateDungeons(s16 max_stone_y, MgStoneType stone_type)
 735 {
 736         if (max_stone_y < node_min.Y)
 737                 return;
 738
 739         DungeonParams dp;
 740
 741         dp.seed          = seed;
 742         dp.c_water       = c_water_source;
 743         dp.c_river_water = c_river_water_source;
 744         dp.rooms_min     = 2;
 745         dp.rooms_max     = 16;
 746         dp.y_min         = -MAX_MAP_GENERATION_LIMIT;
 747         dp.y_max         = MAX_MAP_GENERATION_LIMIT;
 748         dp.np_density    = nparams_dungeon_density;
 749         dp.np_alt_wall   = nparams_dungeon_alt_wall;
 750
 751         switch (stone_type) {
 752         default:
 753         case MGSTONE_STONE:
 754                 dp.c_wall     = c_cobble;
 755                 dp.c_alt_wall = c_mossycobble;
 756                 dp.c_stair    = c_stair_cobble;
 757
 758                 dp.diagonal_dirs = false;
 759                 dp.holesize      = v3s16(1, 2, 1);
 760                 dp.roomsize      = v3s16(0, 0, 0);
 761                 dp.notifytype    = GENNOTIFY_DUNGEON;
 762                 break;
 763         case MGSTONE_DESERT_STONE:
 764                 dp.c_wall     = c_desert_stone;
 765                 dp.c_alt_wall = CONTENT_IGNORE;
 766                 dp.c_stair    = c_desert_stone;
 767
 768                 dp.diagonal_dirs = true;
 769                 dp.holesize      = v3s16(2, 3, 2);
 770                 dp.roomsize      = v3s16(2, 5, 2);
 771                 dp.notifytype    = GENNOTIFY_TEMPLE;
 772                 break;
 773         case MGSTONE_SANDSTONE:
 774                 dp.c_wall     = c_sandstonebrick;
 775                 dp.c_alt_wall = CONTENT_IGNORE;
 776                 dp.c_stair    = c_sandstonebrick;
 777
 778                 dp.diagonal_dirs = false;
 779                 dp.holesize      = v3s16(2, 2, 2);
 780                 dp.roomsize      = v3s16(2, 0, 2);
 781                 dp.notifytype    = GENNOTIFY_DUNGEON;
 782                 break;
 783         }
 784
 785         DungeonGen dgen(ndef, &gennotify, &dp);
 786         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 787 }
 788
 789
 790 ////
 791 //// GenerateNotifier
 792 ////
 793
 794 GenerateNotifier::GenerateNotifier()
 795 {
 796         m_notify_on = 0;
 797 }
 798
 799
 800 GenerateNotifier::GenerateNotifier(u32 notify_on,
 801         std::set<u32> *notify_on_deco_ids)
 802 {
 803         m_notify_on = notify_on;
 804         m_notify_on_deco_ids = notify_on_deco_ids;
 805 }
 806
 807
 808 void GenerateNotifier::setNotifyOn(u32 notify_on)
 809 {
 810         m_notify_on = notify_on;
 811 }
 812
 813
 814 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
 815 {
 816         m_notify_on_deco_ids = notify_on_deco_ids;
 817 }
 818
 819
 820 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
 821 {
 822         if (!(m_notify_on & (1 << type)))
 823                 return false;
 824
 825         if (type == GENNOTIFY_DECORATION &&
 826                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
 827                 return false;
 828
 829         GenNotifyEvent gne;
 830         gne.type = type;
 831         gne.pos  = pos;
 832         gne.id   = id;
 833         m_notify_events.push_back(gne);
 834
 835         return true;
 836 }
 837
 838
 839 void GenerateNotifier::getEvents(
 840         std::map<std::string, std::vector<v3s16> > &event_map,
 841         bool peek_events)
 842 {
 843         std::list<GenNotifyEvent>::iterator it;
 844
 845         for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
 846                 GenNotifyEvent &gn = *it;
 847                 std::string name = (gn.type == GENNOTIFY_DECORATION) ?
 848                         "decoration#"+ itos(gn.id) :
 849                         flagdesc_gennotify[gn.type].name;
 850
 851                 event_map[name].push_back(gn.pos);
 852         }
 853
 854         if (!peek_events)
 855                 m_notify_events.clear();
 856 }
 857
 858
 859 ////
 860 //// MapgenParams
 861 ////
 862
 863
 864 MapgenParams::~MapgenParams()
 865 {
 866         delete bparams;
 867         delete sparams;
 868 }
 869
 870
 871 void MapgenParams::load(const Settings &settings)
 872 {
 873         std::string seed_str;
 874         const char *seed_name = (&settings == g_settings) ? "fixed_map_seed" : "seed";
 875
 876         if (settings.getNoEx(seed_name, seed_str) && !seed_str.empty())
 877                 seed = read_seed(seed_str.c_str());
 878         else
 879                 myrand_bytes(&seed, sizeof(seed));
 880
 881         settings.getNoEx("mg_name", mg_name);
 882         settings.getS16NoEx("water_level", water_level);
 883         settings.getS16NoEx("chunksize", chunksize);
 884         settings.getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
 885
 886         delete bparams;
 887         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
 888         if (bparams) {
 889                 bparams->readParams(&settings);
 890                 bparams->seed = seed;
 891         }
 892
 893         delete sparams;
 894         MapgenFactory *mgfactory = EmergeManager::getMapgenFactory(mg_name);
 895         if (mgfactory) {
 896                 sparams = mgfactory->createMapgenParams();
 897                 sparams->readParams(&settings);
 898         }
 899 }
 900
 901
 902 void MapgenParams::save(Settings &settings) const
 903 {
 904         settings.set("mg_name", mg_name);
 905         settings.setU64("seed", seed);
 906         settings.setS16("water_level", water_level);
 907         settings.setS16("chunksize", chunksize);
 908         settings.setFlagStr("mg_flags", flags, flagdesc_mapgen, U32_MAX);
 909
 910         if (bparams)
 911                 bparams->writeParams(&settings);
 912
 913         if (sparams)
 914                 sparams->writeParams(&settings);
 915 }