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