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 "content_sao.h"
  32 #include "nodedef.h"
  33 #include "emerge.h"
  34 #include "voxelalgorithms.h"
  35 #include "porting.h"
  36 #include "profiler.h"
  37 #include "settings.h"
  38 #include "treegen.h"
  39 #include "serialization.h"
  40 #include "util/serialize.h"
  41 #include "util/numeric.h"
  42 #include "util/directiontables.h"
  43 #include "filesys.h"
  44 #include "log.h"
  45 #include "mapgen_carpathian.h"
  46 #include "mapgen_flat.h"
  47 #include "mapgen_fractal.h"
  48 #include "mapgen_v5.h"
  49 #include "mapgen_v6.h"
  50 #include "mapgen_v7.h"
  51 #include "mapgen_valleys.h"
  52 #include "mapgen_singlenode.h"
  53 #include "cavegen.h"
  54 #include "dungeongen.h"
  55
  56 FlagDesc flagdesc_mapgen[] = {
  57         {"caves",       MG_CAVES},
  58         {"dungeons",    MG_DUNGEONS},
  59         {"light",       MG_LIGHT},
  60         {"decorations", MG_DECORATIONS},
  61         {"biomes",      MG_BIOMES},
  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, EmergeManager *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         EmergeManager *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);
 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         u32 n = 1619 * p.X + 31337 * p.Y + 52591 * p.Z + 1013 * seed;
 242         n = (n >> 13) ^ n;
 243         return (n * (n * n * 60493 + 19990303) + 1376312589);
 244 }
 245
 246
 247 // Returns Y one under area minimum if not found
 248 s16 Mapgen::findGroundLevelFull(v2s16 p2d)
 249 {
 250         const v3s16 &em = vm->m_area.getExtent();
 251         s16 y_nodes_max = vm->m_area.MaxEdge.Y;
 252         s16 y_nodes_min = vm->m_area.MinEdge.Y;
 253         u32 i = vm->m_area.index(p2d.X, y_nodes_max, p2d.Y);
 254         s16 y;
 255
 256         for (y = y_nodes_max; y >= y_nodes_min; y--) {
 257                 MapNode &n = vm->m_data[i];
 258                 if (ndef->get(n).walkable)
 259                         break;
 260
 261                 VoxelArea::add_y(em, i, -1);
 262         }
 263         return (y >= y_nodes_min) ? y : y_nodes_min - 1;
 264 }
 265
 266
 267 // Returns -MAX_MAP_GENERATION_LIMIT if not found
 268 s16 Mapgen::findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax)
 269 {
 270         const v3s16 &em = vm->m_area.getExtent();
 271         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 272         s16 y;
 273
 274         for (y = ymax; y >= ymin; y--) {
 275                 MapNode &n = vm->m_data[i];
 276                 if (ndef->get(n).walkable)
 277                         break;
 278
 279                 VoxelArea::add_y(em, i, -1);
 280         }
 281         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 282 }
 283
 284
 285 // Returns -MAX_MAP_GENERATION_LIMIT if not found or if ground is found first
 286 s16 Mapgen::findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax)
 287 {
 288         const v3s16 &em = vm->m_area.getExtent();
 289         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 290         s16 y;
 291
 292         for (y = ymax; y >= ymin; y--) {
 293                 MapNode &n = vm->m_data[i];
 294                 if (ndef->get(n).walkable)
 295                         return -MAX_MAP_GENERATION_LIMIT;
 296
 297                 if (ndef->get(n).isLiquid())
 298                         break;
 299
 300                 VoxelArea::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
 323 void Mapgen::getSurfaces(v2s16 p2d, s16 ymin, s16 ymax,
 324         std::vector<s16> &floors, std::vector<s16> &ceilings)
 325 {
 326         const v3s16 &em = vm->m_area.getExtent();
 327
 328         bool is_walkable = false;
 329         u32 vi = vm->m_area.index(p2d.X, ymax, p2d.Y);
 330         MapNode mn_max = vm->m_data[vi];
 331         bool walkable_above = ndef->get(mn_max).walkable;
 332         VoxelArea::add_y(em, vi, -1);
 333
 334         for (s16 y = ymax - 1; y >= ymin; y--) {
 335                 MapNode mn = vm->m_data[vi];
 336                 is_walkable = ndef->get(mn).walkable;
 337
 338                 if (is_walkable && !walkable_above) {
 339                         floors.push_back(y);
 340                 } else if (!is_walkable && walkable_above) {
 341                         ceilings.push_back(y + 1);
 342                 }
 343
 344                 VoxelArea::add_y(em, vi, -1);
 345                 walkable_above = is_walkable;
 346         }
 347 }
 348
 349
 350 inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
 351 {
 352         u32 vi_neg_x = vi;
 353         VoxelArea::add_x(em, vi_neg_x, -1);
 354         if (vm->m_data[vi_neg_x].getContent() != CONTENT_IGNORE) {
 355                 const ContentFeatures &c_nx = ndef->get(vm->m_data[vi_neg_x]);
 356                 if (c_nx.floodable && !c_nx.isLiquid())
 357                         return true;
 358         }
 359         u32 vi_pos_x = vi;
 360         VoxelArea::add_x(em, vi_pos_x, +1);
 361         if (vm->m_data[vi_pos_x].getContent() != CONTENT_IGNORE) {
 362                 const ContentFeatures &c_px = ndef->get(vm->m_data[vi_pos_x]);
 363                 if (c_px.floodable && !c_px.isLiquid())
 364                         return true;
 365         }
 366         u32 vi_neg_z = vi;
 367         VoxelArea::add_z(em, vi_neg_z, -1);
 368         if (vm->m_data[vi_neg_z].getContent() != CONTENT_IGNORE) {
 369                 const ContentFeatures &c_nz = ndef->get(vm->m_data[vi_neg_z]);
 370                 if (c_nz.floodable && !c_nz.isLiquid())
 371                         return true;
 372         }
 373         u32 vi_pos_z = vi;
 374         VoxelArea::add_z(em, vi_pos_z, +1);
 375         if (vm->m_data[vi_pos_z].getContent() != CONTENT_IGNORE) {
 376                 const ContentFeatures &c_pz = ndef->get(vm->m_data[vi_pos_z]);
 377                 if (c_pz.floodable && !c_pz.isLiquid())
 378                         return true;
 379         }
 380         return false;
 381 }
 382
 383 void Mapgen::updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax)
 384 {
 385         bool isignored, isliquid, wasignored, wasliquid, waschecked, waspushed;
 386         const v3s16 &em  = vm->m_area.getExtent();
 387
 388         for (s16 z = nmin.Z + 1; z <= nmax.Z - 1; z++)
 389         for (s16 x = nmin.X + 1; x <= nmax.X - 1; x++) {
 390                 wasignored = true;
 391                 wasliquid = false;
 392                 waschecked = false;
 393                 waspushed = false;
 394
 395                 u32 vi = vm->m_area.index(x, nmax.Y, z);
 396                 for (s16 y = nmax.Y; y >= nmin.Y; y--) {
 397                         isignored = vm->m_data[vi].getContent() == CONTENT_IGNORE;
 398                         isliquid = ndef->get(vm->m_data[vi]).isLiquid();
 399
 400                         if (isignored || wasignored || isliquid == wasliquid) {
 401                                 // Neither topmost node of liquid column nor topmost node below column
 402                                 waschecked = false;
 403                                 waspushed = false;
 404                         } else if (isliquid) {
 405                                 // This is the topmost node in the column
 406                                 bool ispushed = false;
 407                                 if (isLiquidHorizontallyFlowable(vi, em)) {
 408                                         trans_liquid->push_back(v3s16(x, y, z));
 409                                         ispushed = true;
 410                                 }
 411                                 // Remember waschecked and waspushed to avoid repeated
 412                                 // checks/pushes in case the column consists of only this node
 413                                 waschecked = true;
 414                                 waspushed = ispushed;
 415                         } else {
 416                                 // This is the topmost node below a liquid column
 417                                 u32 vi_above = vi;
 418                                 VoxelArea::add_y(em, vi_above, 1);
 419                                 if (!waspushed && (ndef->get(vm->m_data[vi]).floodable ||
 420                                                 (!waschecked && isLiquidHorizontallyFlowable(vi_above, em)))) {
 421                                         // Push back the lowest node in the column which is one
 422                                         // node above this one
 423                                         trans_liquid->push_back(v3s16(x, y + 1, z));
 424                                 }
 425                         }
 426
 427                         wasliquid = isliquid;
 428                         wasignored = isignored;
 429                         VoxelArea::add_y(em, vi, -1);
 430                 }
 431         }
 432 }
 433
 434
 435 void Mapgen::setLighting(u8 light, v3s16 nmin, v3s16 nmax)
 436 {
 437         ScopeProfiler sp(g_profiler, "EmergeThread: update lighting", SPT_AVG);
 438         VoxelArea a(nmin, nmax);
 439
 440         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 441                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 442                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 443                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++)
 444                                 vm->m_data[i].param1 = light;
 445                 }
 446         }
 447 }
 448
 449
 450 void Mapgen::lightSpread(VoxelArea &a, std::queue<std::pair<v3s16, u8>> &queue,
 451         const v3s16 &p, u8 light)
 452 {
 453         if (light <= 1 || !a.contains(p))
 454                 return;
 455
 456         u32 vi = vm->m_area.index(p);
 457         MapNode &n = vm->m_data[vi];
 458
 459         // Decay light in each of the banks separately
 460         u8 light_day = light & 0x0F;
 461         if (light_day > 0)
 462                 light_day -= 0x01;
 463
 464         u8 light_night = light & 0xF0;
 465         if (light_night > 0)
 466                 light_night -= 0x10;
 467
 468         // Bail out only if we have no more light from either bank to propogate, or
 469         // we hit a solid block that light cannot pass through.
 470         if ((light_day  <= (n.param1 & 0x0F) &&
 471                         light_night <= (n.param1 & 0xF0)) ||
 472                         !ndef->get(n).light_propagates)
 473                 return;
 474
 475         // Since this recursive function only terminates when there is no light from
 476         // either bank left, we need to take the max of both banks into account for
 477         // the case where spreading has stopped for one light bank but not the other.
 478         light = MYMAX(light_day, n.param1 & 0x0F) |
 479                         MYMAX(light_night, n.param1 & 0xF0);
 480
 481         n.param1 = light;
 482
 483         // add to queue
 484         queue.emplace(p, light);
 485 }
 486
 487
 488 void Mapgen::calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
 489         bool propagate_shadow)
 490 {
 491         ScopeProfiler sp(g_profiler, "EmergeThread: update lighting", SPT_AVG);
 492         //TimeTaker t("updateLighting");
 493
 494         propagateSunlight(nmin, nmax, propagate_shadow);
 495         spreadLight(full_nmin, full_nmax);
 496
 497         //printf("updateLighting: %dms\n", t.stop());
 498 }
 499
 500
 501 void Mapgen::propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow)
 502 {
 503         //TimeTaker t("propagateSunlight");
 504         VoxelArea a(nmin, nmax);
 505         bool block_is_underground = (water_level >= nmax.Y);
 506         const v3s16 &em = vm->m_area.getExtent();
 507
 508         // NOTE: Direct access to the low 4 bits of param1 is okay here because,
 509         // by definition, sunlight will never be in the night lightbank.
 510
 511         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 512                 for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++) {
 513                         // see if we can get a light value from the overtop
 514                         u32 i = vm->m_area.index(x, a.MaxEdge.Y + 1, z);
 515                         if (vm->m_data[i].getContent() == CONTENT_IGNORE) {
 516                                 if (block_is_underground)
 517                                         continue;
 518                         } else if ((vm->m_data[i].param1 & 0x0F) != LIGHT_SUN &&
 519                                         propagate_shadow) {
 520                                 continue;
 521                         }
 522                         VoxelArea::add_y(em, i, -1);
 523
 524                         for (int y = a.MaxEdge.Y; y >= a.MinEdge.Y; y--) {
 525                                 MapNode &n = vm->m_data[i];
 526                                 if (!ndef->get(n).sunlight_propagates)
 527                                         break;
 528                                 n.param1 = LIGHT_SUN;
 529                                 VoxelArea::add_y(em, i, -1);
 530                         }
 531                 }
 532         }
 533         //printf("propagateSunlight: %dms\n", t.stop());
 534 }
 535
 536
 537 void Mapgen::spreadLight(const v3s16 &nmin, const v3s16 &nmax)
 538 {
 539         //TimeTaker t("spreadLight");
 540         std::queue<std::pair<v3s16, u8>> queue;
 541         VoxelArea a(nmin, nmax);
 542
 543         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 544                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 545                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 546                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++) {
 547                                 MapNode &n = vm->m_data[i];
 548                                 if (n.getContent() == CONTENT_IGNORE)
 549                                         continue;
 550
 551                                 const ContentFeatures &cf = ndef->get(n);
 552                                 if (!cf.light_propagates)
 553                                         continue;
 554
 555                                 // TODO(hmmmmm): Abstract away direct param1 accesses with a
 556                                 // wrapper, but something lighter than MapNode::get/setLight
 557
 558                                 u8 light_produced = cf.light_source;
 559                                 if (light_produced)
 560                                         n.param1 = light_produced | (light_produced << 4);
 561
 562                                 u8 light = n.param1;
 563                                 if (light) {
 564                                         const v3s16 p(x, y, z);
 565                                         // spread to all 6 neighbor nodes
 566                                         for (const auto &dir : g_6dirs)
 567                                                 lightSpread(a, queue, p + dir, light);
 568                                 }
 569                         }
 570                 }
 571         }
 572
 573         while (!queue.empty()) {
 574                 const auto &i = queue.front();
 575                 // spread to all 6 neighbor nodes
 576                 for (const auto &dir : g_6dirs)
 577                         lightSpread(a, queue, i.first + dir, i.second);
 578                 queue.pop();
 579         }
 580
 581         //printf("spreadLight: %lums\n", t.stop());
 582 }
 583
 584
 585 ////
 586 //// MapgenBasic
 587 ////
 588
 589 MapgenBasic::MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge)
 590         : Mapgen(mapgenid, params, emerge)
 591 {
 592         this->m_emerge = emerge;
 593         this->m_bmgr   = emerge->biomemgr;
 594
 595         //// Here, 'stride' refers to the number of elements needed to skip to index
 596         //// an adjacent element for that coordinate in noise/height/biome maps
 597         //// (*not* vmanip content map!)
 598
 599         // Note there is no X stride explicitly defined.  Items adjacent in the X
 600         // coordinate are assumed to be adjacent in memory as well (i.e. stride of 1).
 601
 602         // Number of elements to skip to get to the next Y coordinate
 603         this->ystride = csize.X;
 604
 605         // Number of elements to skip to get to the next Z coordinate
 606         this->zstride = csize.X * csize.Y;
 607
 608         // Z-stride value for maps oversized for 1-down overgeneration
 609         this->zstride_1d = csize.X * (csize.Y + 1);
 610
 611         // Z-stride value for maps oversized for 1-up 1-down overgeneration
 612         this->zstride_1u1d = csize.X * (csize.Y + 2);
 613
 614         //// Allocate heightmap
 615         this->heightmap = new s16[csize.X * csize.Z];
 616
 617         //// Initialize biome generator
 618         biomegen = m_bmgr->createBiomeGen(BIOMEGEN_ORIGINAL, params->bparams, csize);
 619         biomemap = biomegen->biomemap;
 620
 621         //// Look up some commonly used content
 622         c_stone              = ndef->getId("mapgen_stone");
 623         c_water_source       = ndef->getId("mapgen_water_source");
 624         c_river_water_source = ndef->getId("mapgen_river_water_source");
 625         c_lava_source        = ndef->getId("mapgen_lava_source");
 626         c_cobble             = ndef->getId("mapgen_cobble");
 627
 628         // Fall back to more basic content if not defined.
 629         // Lava falls back to water as both are suitable as cave liquids.
 630         if (c_lava_source == CONTENT_IGNORE)
 631                 c_lava_source = c_water_source;
 632
 633         if (c_stone == CONTENT_IGNORE)
 634                 errorstream << "Mapgen: Mapgen alias 'mapgen_stone' is invalid!" << std::endl;
 635         if (c_water_source == CONTENT_IGNORE)
 636                 errorstream << "Mapgen: Mapgen alias 'mapgen_water_source' is invalid!" << std::endl;
 637         if (c_river_water_source == CONTENT_IGNORE)
 638                 warningstream << "Mapgen: Mapgen alias 'mapgen_river_water_source' is invalid!" << std::endl;
 639 }
 640
 641
 642 MapgenBasic::~MapgenBasic()
 643 {
 644         delete biomegen;
 645         delete []heightmap;
 646 }
 647
 648
 649 void MapgenBasic::generateBiomes()
 650 {
 651         // can't generate biomes without a biome generator!
 652         assert(biomegen);
 653         assert(biomemap);
 654
 655         const v3s16 &em = vm->m_area.getExtent();
 656         u32 index = 0;
 657
 658         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 659
 660         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 661         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 662                 Biome *biome = NULL;
 663                 biome_t water_biome_index = 0;
 664                 u16 depth_top = 0;
 665                 u16 base_filler = 0;
 666                 u16 depth_water_top = 0;
 667                 u16 depth_riverbed = 0;
 668                 s16 biome_y_min = -MAX_MAP_GENERATION_LIMIT;
 669                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 670
 671                 // Check node at base of mapchunk above, either a node of a previously
 672                 // generated mapchunk or if not, a node of overgenerated base terrain.
 673                 content_t c_above = vm->m_data[vi + em.X].getContent();
 674                 bool air_above = c_above == CONTENT_AIR;
 675                 bool river_water_above = c_above == c_river_water_source;
 676                 bool water_above = c_above == c_water_source || river_water_above;
 677
 678                 biomemap[index] = BIOME_NONE;
 679
 680                 // If there is air or water above enable top/filler placement, otherwise force
 681                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 682                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 683
 684                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 685                         content_t c = vm->m_data[vi].getContent();
 686                         // Biome is (re)calculated:
 687                         // 1. At the surface of stone below air or water.
 688                         // 2. At the surface of water below air.
 689                         // 3. When stone or water is detected but biome has not yet been calculated.
 690                         // 4. When stone or water is detected just below a biome's lower limit.
 691                         bool is_stone_surface = (c == c_stone) &&
 692                                 (air_above || water_above || !biome || y < biome_y_min); // 1, 3, 4
 693
 694                         bool is_water_surface =
 695                                 (c == c_water_source || c == c_river_water_source) &&
 696                                 (air_above || !biome || y < biome_y_min); // 2, 3, 4
 697
 698                         if (is_stone_surface || is_water_surface) {
 699                                 // (Re)calculate biome
 700                                 biome = biomegen->getBiomeAtIndex(index, v3s16(x, y, z));
 701
 702                                 // Add biome to biomemap at first stone surface detected
 703                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 704                                         biomemap[index] = biome->index;
 705
 706                                 // Store biome of first water surface detected, as a fallback
 707                                 // entry for the biomemap.
 708                                 if (water_biome_index == 0 && is_water_surface)
 709                                         water_biome_index = biome->index;
 710
 711                                 depth_top = biome->depth_top;
 712                                 base_filler = MYMAX(depth_top +
 713                                         biome->depth_filler +
 714                                         noise_filler_depth->result[index], 0.0f);
 715                                 depth_water_top = biome->depth_water_top;
 716                                 depth_riverbed = biome->depth_riverbed;
 717                                 biome_y_min = biome->min_pos.Y;
 718                         }
 719
 720                         if (c == c_stone) {
 721                                 content_t c_below = vm->m_data[vi - em.X].getContent();
 722
 723                                 // If the node below isn't solid, make this node stone, so that
 724                                 // any top/filler nodes above are structurally supported.
 725                                 // This is done by aborting the cycle of top/filler placement
 726                                 // immediately by forcing nplaced to stone level.
 727                                 if (c_below == CONTENT_AIR
 728                                                 || c_below == c_water_source
 729                                                 || c_below == c_river_water_source)
 730                                         nplaced = U16_MAX;
 731
 732                                 if (river_water_above) {
 733                                         if (nplaced < depth_riverbed) {
 734                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 735                                                 nplaced++;
 736                                         } else {
 737                                                 nplaced = U16_MAX;  // Disable top/filler placement
 738                                                 river_water_above = false;
 739                                         }
 740                                 } else if (nplaced < depth_top) {
 741                                         vm->m_data[vi] = MapNode(biome->c_top);
 742                                         nplaced++;
 743                                 } else if (nplaced < base_filler) {
 744                                         vm->m_data[vi] = MapNode(biome->c_filler);
 745                                         nplaced++;
 746                                 } else {
 747                                         vm->m_data[vi] = MapNode(biome->c_stone);
 748                                         nplaced = U16_MAX;  // Disable top/filler placement
 749                                 }
 750
 751                                 air_above = false;
 752                                 water_above = false;
 753                         } else if (c == c_water_source) {
 754                                 vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
 755                                                 ? biome->c_water_top : biome->c_water);
 756                                 nplaced = 0;  // Enable top/filler placement for next surface
 757                                 air_above = false;
 758                                 water_above = true;
 759                         } else if (c == c_river_water_source) {
 760                                 vm->m_data[vi] = MapNode(biome->c_river_water);
 761                                 nplaced = 0;  // Enable riverbed placement for next surface
 762                                 air_above = false;
 763                                 water_above = true;
 764                                 river_water_above = true;
 765                         } else if (c == CONTENT_AIR) {
 766                                 nplaced = 0;  // Enable top/filler placement for next surface
 767                                 air_above = true;
 768                                 water_above = false;
 769                         } else {  // Possible various nodes overgenerated from neighbouring mapchunks
 770                                 nplaced = U16_MAX;  // Disable top/filler placement
 771                                 air_above = false;
 772                                 water_above = false;
 773                         }
 774
 775                         VoxelArea::add_y(em, vi, -1);
 776                 }
 777                 // If no stone surface detected in mapchunk column and a water surface
 778                 // biome fallback exists, add it to the biomemap. This avoids water
 779                 // surface decorations failing in deep water.
 780                 if (biomemap[index] == BIOME_NONE && water_biome_index != 0)
 781                         biomemap[index] = water_biome_index;
 782         }
 783 }
 784
 785
 786 void MapgenBasic::dustTopNodes()
 787 {
 788         if (node_max.Y < water_level)
 789                 return;
 790
 791         const v3s16 &em = vm->m_area.getExtent();
 792         u32 index = 0;
 793
 794         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 795         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 796                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 797
 798                 if (biome->c_dust == CONTENT_IGNORE)
 799                         continue;
 800
 801                 // Check if mapchunk above has generated, if so, drop dust from 16 nodes
 802                 // above current mapchunk top, above decorations that will extend above
 803                 // the current mapchunk. If the mapchunk above has not generated, it
 804                 // will provide this required dust when it does.
 805                 u32 vi = vm->m_area.index(x, full_node_max.Y, z);
 806                 content_t c_full_max = vm->m_data[vi].getContent();
 807                 s16 y_start;
 808
 809                 if (c_full_max == CONTENT_AIR) {
 810                         y_start = full_node_max.Y - 1;
 811                 } else if (c_full_max == CONTENT_IGNORE) {
 812                         vi = vm->m_area.index(x, node_max.Y + 1, z);
 813                         content_t c_max = vm->m_data[vi].getContent();
 814
 815                         if (c_max == CONTENT_AIR)
 816                                 y_start = node_max.Y;
 817                         else
 818                                 continue;
 819                 } else {
 820                         continue;
 821                 }
 822
 823                 vi = vm->m_area.index(x, y_start, z);
 824                 for (s16 y = y_start; y >= node_min.Y - 1; y--) {
 825                         if (vm->m_data[vi].getContent() != CONTENT_AIR)
 826                                 break;
 827
 828                         VoxelArea::add_y(em, vi, -1);
 829                 }
 830
 831                 content_t c = vm->m_data[vi].getContent();
 832                 NodeDrawType dtype = ndef->get(c).drawtype;
 833                 // Only place on cubic, walkable, non-dust nodes.
 834                 // Dust check needed due to avoid double layer of dust caused by
 835                 // dropping dust from 16 nodes above mapchunk top.
 836                 if ((dtype == NDT_NORMAL ||
 837                                 dtype == NDT_ALLFACES ||
 838                                 dtype == NDT_ALLFACES_OPTIONAL ||
 839                                 dtype == NDT_GLASSLIKE ||
 840                                 dtype == NDT_GLASSLIKE_FRAMED ||
 841                                 dtype == NDT_GLASSLIKE_FRAMED_OPTIONAL) &&
 842                                 ndef->get(c).walkable && c != biome->c_dust) {
 843                         VoxelArea::add_y(em, vi, 1);
 844                         vm->m_data[vi] = MapNode(biome->c_dust);
 845                 }
 846         }
 847 }
 848
 849
 850 void MapgenBasic::generateCavesNoiseIntersection(s16 max_stone_y)
 851 {
 852         // cave_width >= 10 is used to disable generation and avoid the intensive
 853         // 3D noise calculations. Tunnels already have zero width when cave_width > 1.
 854         if (node_min.Y > max_stone_y || cave_width >= 10.0f)
 855                 return;
 856
 857         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 858                 &np_cave1, &np_cave2, seed, cave_width);
 859
 860         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 861 }
 862
 863
 864 void MapgenBasic::generateCavesRandomWalk(s16 max_stone_y, s16 large_cave_ymax)
 865 {
 866         if (node_min.Y > max_stone_y)
 867                 return;
 868
 869         PseudoRandom ps(blockseed + 21343);
 870         // Small randomwalk caves
 871         u32 num_small_caves = ps.range(small_cave_num_min, small_cave_num_max);
 872
 873         for (u32 i = 0; i < num_small_caves; i++) {
 874                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 875                         c_water_source, c_lava_source, large_cave_flooded, biomegen);
 876                 cave.makeCave(vm, node_min, node_max, &ps, false, max_stone_y, heightmap);
 877         }
 878
 879         if (node_max.Y > large_cave_ymax)
 880                 return;
 881
 882         // Large randomwalk caves below 'large_cave_ymax'.
 883         // 'large_cave_ymax' can differ from the 'large_cave_depth' mapgen parameter,
 884         // it is set to world base to disable large caves in or near caverns.
 885         u32 num_large_caves = ps.range(large_cave_num_min, large_cave_num_max);
 886
 887         for (u32 i = 0; i < num_large_caves; i++) {
 888                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 889                         c_water_source, c_lava_source, large_cave_flooded, biomegen);
 890                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
 891         }
 892 }
 893
 894
 895 bool MapgenBasic::generateCavernsNoise(s16 max_stone_y)
 896 {
 897         if (node_min.Y > max_stone_y || node_min.Y > cavern_limit)
 898                 return false;
 899
 900         CavernsNoise caverns_noise(ndef, csize, &np_cavern,
 901                 seed, cavern_limit, cavern_taper, cavern_threshold);
 902
 903         return caverns_noise.generateCaverns(vm, node_min, node_max);
 904 }
 905
 906
 907 void MapgenBasic::generateDungeons(s16 max_stone_y)
 908 {
 909         if (node_min.Y > max_stone_y || node_min.Y > dungeon_ymax ||
 910                         node_max.Y < dungeon_ymin)
 911                 return;
 912
 913         u16 num_dungeons = std::fmax(std::floor(
 914                 NoisePerlin3D(&np_dungeons, node_min.X, node_min.Y, node_min.Z, seed)), 0.0f);
 915         if (num_dungeons == 0)
 916                 return;
 917
 918         PseudoRandom ps(blockseed + 70033);
 919
 920         DungeonParams dp;
 921
 922         dp.np_alt_wall =
 923                 NoiseParams(-0.4, 1.0, v3f(40.0, 40.0, 40.0), 32474, 6, 1.1, 2.0);
 924
 925         dp.seed                = seed;
 926         dp.only_in_ground      = true;
 927         dp.num_dungeons        = num_dungeons;
 928         dp.notifytype          = GENNOTIFY_DUNGEON;
 929         dp.num_rooms           = ps.range(2, 16);
 930         dp.room_size_min       = v3s16(5, 5, 5);
 931         dp.room_size_max       = v3s16(12, 6, 12);
 932         dp.room_size_large_min = v3s16(12, 6, 12);
 933         dp.room_size_large_max = v3s16(16, 16, 16);
 934         dp.large_room_chance   = (ps.range(1, 4) == 1) ? 8 : 0;
 935         dp.diagonal_dirs       = ps.range(1, 8) == 1;
 936         // Diagonal corridors must have 'hole' width >=2 to be passable
 937         u8 holewidth           = (dp.diagonal_dirs) ? 2 : ps.range(1, 2);
 938         dp.holesize            = v3s16(holewidth, 3, holewidth);
 939         dp.corridor_len_min    = 1;
 940         dp.corridor_len_max    = 13;
 941
 942         // Get biome at mapchunk midpoint
 943         v3s16 chunk_mid = node_min + (node_max - node_min) / v3s16(2, 2, 2);
 944         Biome *biome = (Biome *)biomegen->getBiomeAtPoint(chunk_mid);
 945
 946         // Use biome-defined dungeon nodes if defined
 947         if (biome->c_dungeon != CONTENT_IGNORE) {
 948                 dp.c_wall = biome->c_dungeon;
 949                 // If 'node_dungeon_alt' is not defined by biome, it and dp.c_alt_wall
 950                 // become CONTENT_IGNORE which skips the alt wall node placement loop in
 951                 // dungeongen.cpp.
 952                 dp.c_alt_wall = biome->c_dungeon_alt;
 953                 // Stairs fall back to 'c_dungeon' if not defined by biome
 954                 dp.c_stair = (biome->c_dungeon_stair != CONTENT_IGNORE) ?
 955                         biome->c_dungeon_stair : biome->c_dungeon;
 956         // Fallback to using cobble mapgen alias if defined
 957         } else if (c_cobble != CONTENT_IGNORE) {
 958                 dp.c_wall     = c_cobble;
 959                 dp.c_alt_wall = CONTENT_IGNORE;
 960                 dp.c_stair    = c_cobble;
 961         // Fallback to using biome-defined stone
 962         } else {
 963                 dp.c_wall     = biome->c_stone;
 964                 dp.c_alt_wall = CONTENT_IGNORE;
 965                 dp.c_stair    = biome->c_stone;
 966         }
 967
 968         DungeonGen dgen(ndef, &gennotify, &dp);
 969         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 970 }
 971
 972
 973 ////
 974 //// GenerateNotifier
 975 ////
 976
 977 GenerateNotifier::GenerateNotifier(u32 notify_on,
 978         std::set<u32> *notify_on_deco_ids)
 979 {
 980         m_notify_on = notify_on;
 981         m_notify_on_deco_ids = notify_on_deco_ids;
 982 }
 983
 984
 985 void GenerateNotifier::setNotifyOn(u32 notify_on)
 986 {
 987         m_notify_on = notify_on;
 988 }
 989
 990
 991 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
 992 {
 993         m_notify_on_deco_ids = notify_on_deco_ids;
 994 }
 995
 996
 997 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
 998 {
 999         if (!(m_notify_on & (1 << type)))
1000                 return false;
1001
1002         if (type == GENNOTIFY_DECORATION &&
1003                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
1004                 return false;
1005
1006         GenNotifyEvent gne;
1007         gne.type = type;
1008         gne.pos  = pos;
1009         gne.id   = id;
1010         m_notify_events.push_back(gne);
1011
1012         return true;
1013 }
1014
1015
1016 void GenerateNotifier::getEvents(
1017         std::map<std::string, std::vector<v3s16> > &event_map)
1018 {
1019         std::list<GenNotifyEvent>::iterator it;
1020
1021         for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
1022                 GenNotifyEvent &gn = *it;
1023                 std::string name = (gn.type == GENNOTIFY_DECORATION) ?
1024                         "decoration#"+ itos(gn.id) :
1025                         flagdesc_gennotify[gn.type].name;
1026
1027                 event_map[name].push_back(gn.pos);
1028         }
1029 }
1030
1031
1032 void GenerateNotifier::clearEvents()
1033 {
1034         m_notify_events.clear();
1035 }
1036
1037
1038 ////
1039 //// MapgenParams
1040 ////
1041
1042
1043 MapgenParams::~MapgenParams()
1044 {
1045         delete bparams;
1046 }
1047
1048
1049 void MapgenParams::readParams(const Settings *settings)
1050 {
1051         std::string seed_str;
1052         const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";
1053
1054         if (settings->getNoEx(seed_name, seed_str)) {
1055                 if (!seed_str.empty())
1056                         seed = read_seed(seed_str.c_str());
1057                 else
1058                         myrand_bytes(&seed, sizeof(seed));
1059         }
1060
1061         std::string mg_name;
1062         if (settings->getNoEx("mg_name", mg_name)) {
1063                 mgtype = Mapgen::getMapgenType(mg_name);
1064                 if (mgtype == MAPGEN_INVALID)
1065                         mgtype = MAPGEN_DEFAULT;
1066         }
1067
1068         settings->getS16NoEx("water_level", water_level);
1069         settings->getS16NoEx("mapgen_limit", mapgen_limit);
1070         settings->getS16NoEx("chunksize", chunksize);
1071         settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
1072
1073         delete bparams;
1074         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
1075         if (bparams) {
1076                 bparams->readParams(settings);
1077                 bparams->seed = seed;
1078         }
1079 }
1080
1081
1082 void MapgenParams::writeParams(Settings *settings) const
1083 {
1084         settings->set("mg_name", Mapgen::getMapgenName(mgtype));
1085         settings->setU64("seed", seed);
1086         settings->setS16("water_level", water_level);
1087         settings->setS16("mapgen_limit", mapgen_limit);
1088         settings->setS16("chunksize", chunksize);
1089         settings->setFlagStr("mg_flags", flags, flagdesc_mapgen);
1090
1091         if (bparams)
1092                 bparams->writeParams(settings);
1093 }
1094
1095
1096 // Calculate exact edges of the outermost mapchunks that are within the
1097 // set 'mapgen_limit'.
1098 void MapgenParams::calcMapgenEdges()
1099 {
1100         // Central chunk offset, in blocks
1101         s16 ccoff_b = -chunksize / 2;
1102         // Chunksize, in nodes
1103         s32 csize_n = chunksize * MAP_BLOCKSIZE;
1104         // Minp/maxp of central chunk, in nodes
1105         s16 ccmin = ccoff_b * MAP_BLOCKSIZE;
1106         s16 ccmax = ccmin + csize_n - 1;
1107         // Fullminp/fullmaxp of central chunk, in nodes
1108         s16 ccfmin = ccmin - MAP_BLOCKSIZE;
1109         s16 ccfmax = ccmax + MAP_BLOCKSIZE;
1110         // Effective mapgen limit, in blocks
1111         // Uses same calculation as ServerMap::blockpos_over_mapgen_limit(v3s16 p)
1112         s16 mapgen_limit_b = rangelim(mapgen_limit,
1113                 0, MAX_MAP_GENERATION_LIMIT) / MAP_BLOCKSIZE;
1114         // Effective mapgen limits, in nodes
1115         s16 mapgen_limit_min = -mapgen_limit_b * MAP_BLOCKSIZE;
1116         s16 mapgen_limit_max = (mapgen_limit_b + 1) * MAP_BLOCKSIZE - 1;
1117         // Number of complete chunks from central chunk fullminp/fullmaxp
1118         // to effective mapgen limits.
1119         s16 numcmin = MYMAX((ccfmin - mapgen_limit_min) / csize_n, 0);
1120         s16 numcmax = MYMAX((mapgen_limit_max - ccfmax) / csize_n, 0);
1121         // Mapgen edges, in nodes
1122         mapgen_edge_min = ccmin - numcmin * csize_n;
1123         mapgen_edge_max = ccmax + numcmax * csize_n;
1124
1125         m_mapgen_edges_calculated = true;
1126 }
1127
1128
1129 s32 MapgenParams::getSpawnRangeMax()
1130 {
1131         if (!m_mapgen_edges_calculated)
1132                 calcMapgenEdges();
1133
1134         return MYMIN(-mapgen_edge_min, mapgen_edge_max);
1135 }