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