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