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