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