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