src/mapgen.cpp

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