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