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_desert_stone       = ndef->getId("mapgen_desert_stone");
 591         c_sandstone          = ndef->getId("mapgen_sandstone");
 592         c_water_source       = ndef->getId("mapgen_water_source");
 593         c_river_water_source = ndef->getId("mapgen_river_water_source");
 594
 595         // Fall back to more basic content if not defined
 596         // river_water_source cannot fallback to water_source because river water
 597         // needs to be non-renewable and have a short flow range.
 598         if (c_desert_stone == CONTENT_IGNORE)
 599                 c_desert_stone = c_stone;
 600         if (c_sandstone == CONTENT_IGNORE)
 601                 c_sandstone = c_stone;
 602
 603         //// Content used for dungeon generation
 604         c_cobble               = ndef->getId("mapgen_cobble");
 605         c_mossycobble          = ndef->getId("mapgen_mossycobble");
 606         c_stair_cobble         = ndef->getId("mapgen_stair_cobble");
 607         c_stair_desert_stone   = ndef->getId("mapgen_stair_desert_stone");
 608         c_sandstonebrick       = ndef->getId("mapgen_sandstonebrick");
 609         c_stair_sandstonebrick = ndef->getId("mapgen_stair_sandstonebrick");
 610
 611         // Fall back to more basic content if not defined
 612         if (c_mossycobble == CONTENT_IGNORE)
 613                 c_mossycobble = c_cobble;
 614         if (c_stair_cobble == CONTENT_IGNORE)
 615                 c_stair_cobble = c_cobble;
 616         if (c_stair_desert_stone == CONTENT_IGNORE)
 617                 c_stair_desert_stone = c_desert_stone;
 618         if (c_sandstonebrick == CONTENT_IGNORE)
 619                 c_sandstonebrick = c_sandstone;
 620         if (c_stair_sandstonebrick == CONTENT_IGNORE)
 621                 c_stair_sandstonebrick = c_sandstonebrick;
 622 }
 623
 624
 625 MapgenBasic::~MapgenBasic()
 626 {
 627         delete biomegen;
 628         delete []heightmap;
 629 }
 630
 631
 632 MgStoneType MapgenBasic::generateBiomes()
 633 {
 634         // can't generate biomes without a biome generator!
 635         assert(biomegen);
 636         assert(biomemap);
 637
 638         v3s16 em = vm->m_area.getExtent();
 639         u32 index = 0;
 640         MgStoneType stone_type = MGSTONE_STONE;
 641
 642         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 643
 644         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 645         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 646                 Biome *biome = NULL;
 647                 u16 depth_top = 0;
 648                 u16 base_filler = 0;
 649                 u16 depth_water_top = 0;
 650                 u16 depth_riverbed = 0;
 651                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 652
 653                 // Check node at base of mapchunk above, either a node of a previously
 654                 // generated mapchunk or if not, a node of overgenerated base terrain.
 655                 content_t c_above = vm->m_data[vi + em.X].getContent();
 656                 bool air_above = c_above == CONTENT_AIR;
 657                 bool river_water_above = c_above == c_river_water_source;
 658                 bool water_above = c_above == c_water_source || river_water_above;
 659
 660                 biomemap[index] = BIOME_NONE;
 661
 662                 // If there is air or water above enable top/filler placement, otherwise force
 663                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 664                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 665
 666                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 667                         content_t c = vm->m_data[vi].getContent();
 668
 669                         // Biome is recalculated each time an upper surface is detected while
 670                         // working down a column. The selected biome then remains in effect for
 671                         // all nodes below until the next surface and biome recalculation.
 672                         // Biome is recalculated:
 673                         // 1. At the surface of stone below air or water.
 674                         // 2. At the surface of water below air.
 675                         // 3. When stone or water is detected but biome has not yet been calculated.
 676                         bool is_stone_surface = (c == c_stone) &&
 677                                 (air_above || water_above || !biome);
 678
 679                         bool is_water_surface =
 680                                 (c == c_water_source || c == c_river_water_source) &&
 681                                 (air_above || !biome);
 682
 683                         if (is_stone_surface || is_water_surface) {
 684                                 biome = biomegen->getBiomeAtIndex(index, y);
 685
 686                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 687                                         biomemap[index] = biome->index;
 688
 689                                 depth_top = biome->depth_top;
 690                                 base_filler = MYMAX(depth_top +
 691                                         biome->depth_filler +
 692                                         noise_filler_depth->result[index], 0.f);
 693                                 depth_water_top = biome->depth_water_top;
 694                                 depth_riverbed = biome->depth_riverbed;
 695
 696                                 // Detect stone type for dungeons during every biome calculation.
 697                                 // This is more efficient than detecting per-node and will not
 698                                 // miss any desert stone or sandstone biomes.
 699                                 if (biome->c_stone == c_desert_stone)
 700                                         stone_type = MGSTONE_DESERT_STONE;
 701                                 else if (biome->c_stone == c_sandstone)
 702                                         stone_type = MGSTONE_SANDSTONE;
 703                         }
 704
 705                         if (c == c_stone) {
 706                                 content_t c_below = vm->m_data[vi - em.X].getContent();
 707
 708                                 // If the node below isn't solid, make this node stone, so that
 709                                 // any top/filler nodes above are structurally supported.
 710                                 // This is done by aborting the cycle of top/filler placement
 711                                 // immediately by forcing nplaced to stone level.
 712                                 if (c_below == CONTENT_AIR
 713                                                 || c_below == c_water_source
 714                                                 || c_below == c_river_water_source)
 715                                         nplaced = U16_MAX;
 716
 717                                 if (river_water_above) {
 718                                         if (nplaced < depth_riverbed) {
 719                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 720                                                 nplaced++;
 721                                         } else {
 722                                                 nplaced = U16_MAX;  // Disable top/filler placement
 723                                                 river_water_above = false;
 724                                         }
 725                                 } else if (nplaced < depth_top) {
 726                                         vm->m_data[vi] = MapNode(biome->c_top);
 727                                         nplaced++;
 728                                 } else if (nplaced < base_filler) {
 729                                         vm->m_data[vi] = MapNode(biome->c_filler);
 730                                         nplaced++;
 731                                 } else {
 732                                         vm->m_data[vi] = MapNode(biome->c_stone);
 733                                 }
 734
 735                                 air_above = false;
 736                                 water_above = false;
 737                         } else if (c == c_water_source) {
 738                                 vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
 739                                                 ? biome->c_water_top : biome->c_water);
 740                                 nplaced = 0;  // Enable top/filler placement for next surface
 741                                 air_above = false;
 742                                 water_above = true;
 743                         } else if (c == c_river_water_source) {
 744                                 vm->m_data[vi] = MapNode(biome->c_river_water);
 745                                 nplaced = 0;  // Enable riverbed placement for next surface
 746                                 air_above = false;
 747                                 water_above = true;
 748                                 river_water_above = true;
 749                         } else if (c == CONTENT_AIR) {
 750                                 nplaced = 0;  // Enable top/filler placement for next surface
 751                                 air_above = true;
 752                                 water_above = false;
 753                         } else {  // Possible various nodes overgenerated from neighbouring mapchunks
 754                                 nplaced = U16_MAX;  // Disable top/filler placement
 755                                 air_above = false;
 756                                 water_above = false;
 757                         }
 758
 759                         vm->m_area.add_y(em, vi, -1);
 760                 }
 761         }
 762
 763         return stone_type;
 764 }
 765
 766
 767 void MapgenBasic::dustTopNodes()
 768 {
 769         if (node_max.Y < water_level)
 770                 return;
 771
 772         v3s16 em = vm->m_area.getExtent();
 773         u32 index = 0;
 774
 775         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 776         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 777                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 778
 779                 if (biome->c_dust == CONTENT_IGNORE)
 780                         continue;
 781
 782                 u32 vi = vm->m_area.index(x, full_node_max.Y, z);
 783                 content_t c_full_max = vm->m_data[vi].getContent();
 784                 s16 y_start;
 785
 786                 if (c_full_max == CONTENT_AIR) {
 787                         y_start = full_node_max.Y - 1;
 788                 } else if (c_full_max == CONTENT_IGNORE) {
 789                         vi = vm->m_area.index(x, node_max.Y + 1, z);
 790                         content_t c_max = vm->m_data[vi].getContent();
 791
 792                         if (c_max == CONTENT_AIR)
 793                                 y_start = node_max.Y;
 794                         else
 795                                 continue;
 796                 } else {
 797                         continue;
 798                 }
 799
 800                 vi = vm->m_area.index(x, y_start, z);
 801                 for (s16 y = y_start; y >= node_min.Y - 1; y--) {
 802                         if (vm->m_data[vi].getContent() != CONTENT_AIR)
 803                                 break;
 804
 805                         vm->m_area.add_y(em, vi, -1);
 806                 }
 807
 808                 content_t c = vm->m_data[vi].getContent();
 809                 if (!ndef->get(c).buildable_to && c != CONTENT_IGNORE && c != biome->c_dust) {
 810                         vm->m_area.add_y(em, vi, 1);
 811                         vm->m_data[vi] = MapNode(biome->c_dust);
 812                 }
 813         }
 814 }
 815
 816
 817 void MapgenBasic::generateCaves(s16 max_stone_y, s16 large_cave_depth)
 818 {
 819         if (max_stone_y < node_min.Y)
 820                 return;
 821
 822         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 823                 &np_cave1, &np_cave2, seed, cave_width);
 824
 825         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 826
 827         if (node_max.Y > large_cave_depth)
 828                 return;
 829
 830         PseudoRandom ps(blockseed + 21343);
 831         u32 bruises_count = ps.range(0, 2);
 832         for (u32 i = 0; i < bruises_count; i++) {
 833                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 834                         c_water_source, CONTENT_IGNORE);
 835
 836                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
 837         }
 838 }
 839
 840
 841 void MapgenBasic::generateDungeons(s16 max_stone_y, MgStoneType stone_type)
 842 {
 843         if (max_stone_y < node_min.Y)
 844                 return;
 845
 846         DungeonParams dp;
 847
 848         dp.seed          = seed;
 849         dp.c_water       = c_water_source;
 850         dp.c_river_water = c_river_water_source;
 851         dp.rooms_min     = 2;
 852         dp.rooms_max     = 16;
 853         dp.y_min         = -MAX_MAP_GENERATION_LIMIT;
 854         dp.y_max         = MAX_MAP_GENERATION_LIMIT;
 855         dp.np_density    = nparams_dungeon_density;
 856         dp.np_alt_wall   = nparams_dungeon_alt_wall;
 857
 858         switch (stone_type) {
 859         default:
 860         case MGSTONE_STONE:
 861                 dp.c_wall     = c_cobble;
 862                 dp.c_alt_wall = c_mossycobble;
 863                 dp.c_stair    = c_stair_cobble;
 864
 865                 dp.diagonal_dirs = false;
 866                 dp.holesize      = v3s16(1, 2, 1);
 867                 dp.roomsize      = v3s16(0, 0, 0);
 868                 dp.notifytype    = GENNOTIFY_DUNGEON;
 869                 break;
 870         case MGSTONE_DESERT_STONE:
 871                 dp.c_wall     = c_desert_stone;
 872                 dp.c_alt_wall = CONTENT_IGNORE;
 873                 dp.c_stair    = c_stair_desert_stone;
 874
 875                 dp.diagonal_dirs = true;
 876                 dp.holesize      = v3s16(2, 3, 2);
 877                 dp.roomsize      = v3s16(2, 5, 2);
 878                 dp.notifytype    = GENNOTIFY_TEMPLE;
 879                 break;
 880         case MGSTONE_SANDSTONE:
 881                 dp.c_wall     = c_sandstonebrick;
 882                 dp.c_alt_wall = CONTENT_IGNORE;
 883                 dp.c_stair    = c_stair_sandstonebrick;
 884
 885                 dp.diagonal_dirs = false;
 886                 dp.holesize      = v3s16(2, 2, 2);
 887                 dp.roomsize      = v3s16(2, 0, 2);
 888                 dp.notifytype    = GENNOTIFY_DUNGEON;
 889                 break;
 890         }
 891
 892         DungeonGen dgen(ndef, &gennotify, &dp);
 893         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 894 }
 895
 896
 897 ////
 898 //// GenerateNotifier
 899 ////
 900
 901 GenerateNotifier::GenerateNotifier()
 902 {
 903         m_notify_on = 0;
 904 }
 905
 906
 907 GenerateNotifier::GenerateNotifier(u32 notify_on,
 908         std::set<u32> *notify_on_deco_ids)
 909 {
 910         m_notify_on = notify_on;
 911         m_notify_on_deco_ids = notify_on_deco_ids;
 912 }
 913
 914
 915 void GenerateNotifier::setNotifyOn(u32 notify_on)
 916 {
 917         m_notify_on = notify_on;
 918 }
 919
 920
 921 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
 922 {
 923         m_notify_on_deco_ids = notify_on_deco_ids;
 924 }
 925
 926
 927 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
 928 {
 929         if (!(m_notify_on & (1 << type)))
 930                 return false;
 931
 932         if (type == GENNOTIFY_DECORATION &&
 933                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
 934                 return false;
 935
 936         GenNotifyEvent gne;
 937         gne.type = type;
 938         gne.pos  = pos;
 939         gne.id   = id;
 940         m_notify_events.push_back(gne);
 941
 942         return true;
 943 }
 944
 945
 946 void GenerateNotifier::getEvents(
 947         std::map<std::string, std::vector<v3s16> > &event_map,
 948         bool peek_events)
 949 {
 950         std::list<GenNotifyEvent>::iterator it;
 951
 952         for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
 953                 GenNotifyEvent &gn = *it;
 954                 std::string name = (gn.type == GENNOTIFY_DECORATION) ?
 955                         "decoration#"+ itos(gn.id) :
 956                         flagdesc_gennotify[gn.type].name;
 957
 958                 event_map[name].push_back(gn.pos);
 959         }
 960
 961         if (!peek_events)
 962                 m_notify_events.clear();
 963 }
 964
 965
 966 ////
 967 //// MapgenParams
 968 ////
 969
 970
 971 MapgenParams::~MapgenParams()
 972 {
 973         delete bparams;
 974 }
 975
 976
 977 void MapgenParams::readParams(const Settings *settings)
 978 {
 979         std::string seed_str;
 980         const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";
 981
 982         if (settings->getNoEx(seed_name, seed_str)) {
 983                 if (!seed_str.empty())
 984                         seed = read_seed(seed_str.c_str());
 985                 else
 986                         myrand_bytes(&seed, sizeof(seed));
 987         }
 988
 989         std::string mg_name;
 990         if (settings->getNoEx("mg_name", mg_name))
 991                 this->mgtype = Mapgen::getMapgenType(mg_name);
 992
 993         settings->getS16NoEx("water_level", water_level);
 994         settings->getS16NoEx("chunksize", chunksize);
 995         settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
 996
 997         delete bparams;
 998         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
 999         if (bparams) {
1000                 bparams->readParams(settings);
1001                 bparams->seed = seed;
1002         }
1003 }
1004
1005
1006 void MapgenParams::writeParams(Settings *settings) const
1007 {
1008         settings->set("mg_name", Mapgen::getMapgenName(mgtype));
1009         settings->setU64("seed", seed);
1010         settings->setS16("water_level", water_level);
1011         settings->setS16("chunksize", chunksize);
1012         settings->setFlagStr("mg_flags", flags, flagdesc_mapgen, U32_MAX);
1013
1014         if (bparams)
1015                 bparams->writeParams(settings);
1016 }