src/mapgen/mapgen.cpp

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