src/mapgen.cpp

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