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