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
 634
 635 MapgenBasic::~MapgenBasic()
 636 {
 637         delete biomegen;
 638         delete []heightmap;
 639 }
 640
 641
 642 void MapgenBasic::generateBiomes()
 643 {
 644         // can't generate biomes without a biome generator!
 645         assert(biomegen);
 646         assert(biomemap);
 647
 648         const v3s16 &em = vm->m_area.getExtent();
 649         u32 index = 0;
 650
 651         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 652
 653         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 654         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 655                 Biome *biome = NULL;
 656                 biome_t water_biome_index = 0;
 657                 u16 depth_top = 0;
 658                 u16 base_filler = 0;
 659                 u16 depth_water_top = 0;
 660                 u16 depth_riverbed = 0;
 661                 s16 biome_y_min = -MAX_MAP_GENERATION_LIMIT;
 662                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 663
 664                 // Check node at base of mapchunk above, either a node of a previously
 665                 // generated mapchunk or if not, a node of overgenerated base terrain.
 666                 content_t c_above = vm->m_data[vi + em.X].getContent();
 667                 bool air_above = c_above == CONTENT_AIR;
 668                 bool river_water_above = c_above == c_river_water_source;
 669                 bool water_above = c_above == c_water_source || river_water_above;
 670
 671                 biomemap[index] = BIOME_NONE;
 672
 673                 // If there is air or water above enable top/filler placement, otherwise force
 674                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 675                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 676
 677                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 678                         content_t c = vm->m_data[vi].getContent();
 679                         // Biome is (re)calculated:
 680                         // 1. At the surface of stone below air or water.
 681                         // 2. At the surface of water below air.
 682                         // 3. When stone or water is detected but biome has not yet been calculated.
 683                         // 4. When stone or water is detected just below a biome's lower limit.
 684                         bool is_stone_surface = (c == c_stone) &&
 685                                 (air_above || water_above || !biome || y < biome_y_min); // 1, 3, 4
 686
 687                         bool is_water_surface =
 688                                 (c == c_water_source || c == c_river_water_source) &&
 689                                 (air_above || !biome || y < biome_y_min); // 2, 3, 4
 690
 691                         if (is_stone_surface || is_water_surface) {
 692                                 // (Re)calculate biome
 693                                 biome = biomegen->getBiomeAtIndex(index, v3s16(x, y, z));
 694
 695                                 // Add biome to biomemap at first stone surface detected
 696                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 697                                         biomemap[index] = biome->index;
 698
 699                                 // Store biome of first water surface detected, as a fallback
 700                                 // entry for the biomemap.
 701                                 if (water_biome_index == 0 && is_water_surface)
 702                                         water_biome_index = biome->index;
 703
 704                                 depth_top = biome->depth_top;
 705                                 base_filler = MYMAX(depth_top +
 706                                         biome->depth_filler +
 707                                         noise_filler_depth->result[index], 0.0f);
 708                                 depth_water_top = biome->depth_water_top;
 709                                 depth_riverbed = biome->depth_riverbed;
 710                                 biome_y_min = biome->min_pos.Y;
 711                         }
 712
 713                         if (c == c_stone) {
 714                                 content_t c_below = vm->m_data[vi - em.X].getContent();
 715
 716                                 // If the node below isn't solid, make this node stone, so that
 717                                 // any top/filler nodes above are structurally supported.
 718                                 // This is done by aborting the cycle of top/filler placement
 719                                 // immediately by forcing nplaced to stone level.
 720                                 if (c_below == CONTENT_AIR
 721                                                 || c_below == c_water_source
 722                                                 || c_below == c_river_water_source)
 723                                         nplaced = U16_MAX;
 724
 725                                 if (river_water_above) {
 726                                         if (nplaced < depth_riverbed) {
 727                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 728                                                 nplaced++;
 729                                         } else {
 730                                                 nplaced = U16_MAX;  // Disable top/filler placement
 731                                                 river_water_above = false;
 732                                         }
 733                                 } else if (nplaced < depth_top) {
 734                                         vm->m_data[vi] = MapNode(biome->c_top);
 735                                         nplaced++;
 736                                 } else if (nplaced < base_filler) {
 737                                         vm->m_data[vi] = MapNode(biome->c_filler);
 738                                         nplaced++;
 739                                 } else {
 740                                         vm->m_data[vi] = MapNode(biome->c_stone);
 741                                         nplaced = U16_MAX;  // Disable top/filler placement
 742                                 }
 743
 744                                 air_above = false;
 745                                 water_above = false;
 746                         } else if (c == c_water_source) {
 747                                 vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
 748                                                 ? biome->c_water_top : biome->c_water);
 749                                 nplaced = 0;  // Enable top/filler placement for next surface
 750                                 air_above = false;
 751                                 water_above = true;
 752                         } else if (c == c_river_water_source) {
 753                                 vm->m_data[vi] = MapNode(biome->c_river_water);
 754                                 nplaced = 0;  // Enable riverbed placement for next surface
 755                                 air_above = false;
 756                                 water_above = true;
 757                                 river_water_above = true;
 758                         } else if (c == CONTENT_AIR) {
 759                                 nplaced = 0;  // Enable top/filler placement for next surface
 760                                 air_above = true;
 761                                 water_above = false;
 762                         } else {  // Possible various nodes overgenerated from neighbouring mapchunks
 763                                 nplaced = U16_MAX;  // Disable top/filler placement
 764                                 air_above = false;
 765                                 water_above = false;
 766                         }
 767
 768                         VoxelArea::add_y(em, vi, -1);
 769                 }
 770                 // If no stone surface detected in mapchunk column and a water surface
 771                 // biome fallback exists, add it to the biomemap. This avoids water
 772                 // surface decorations failing in deep water.
 773                 if (biomemap[index] == BIOME_NONE && water_biome_index != 0)
 774                         biomemap[index] = water_biome_index;
 775         }
 776 }
 777
 778
 779 void MapgenBasic::dustTopNodes()
 780 {
 781         if (node_max.Y < water_level)
 782                 return;
 783
 784         const v3s16 &em = vm->m_area.getExtent();
 785         u32 index = 0;
 786
 787         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 788         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 789                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 790
 791                 if (biome->c_dust == CONTENT_IGNORE)
 792                         continue;
 793
 794                 // Check if mapchunk above has generated, if so, drop dust from 16 nodes
 795                 // above current mapchunk top, above decorations that will extend above
 796                 // the current mapchunk. If the mapchunk above has not generated, it
 797                 // will provide this required dust when it does.
 798                 u32 vi = vm->m_area.index(x, full_node_max.Y, z);
 799                 content_t c_full_max = vm->m_data[vi].getContent();
 800                 s16 y_start;
 801
 802                 if (c_full_max == CONTENT_AIR) {
 803                         y_start = full_node_max.Y - 1;
 804                 } else if (c_full_max == CONTENT_IGNORE) {
 805                         vi = vm->m_area.index(x, node_max.Y + 1, z);
 806                         content_t c_max = vm->m_data[vi].getContent();
 807
 808                         if (c_max == CONTENT_AIR)
 809                                 y_start = node_max.Y;
 810                         else
 811                                 continue;
 812                 } else {
 813                         continue;
 814                 }
 815
 816                 vi = vm->m_area.index(x, y_start, z);
 817                 for (s16 y = y_start; y >= node_min.Y - 1; y--) {
 818                         if (vm->m_data[vi].getContent() != CONTENT_AIR)
 819                                 break;
 820
 821                         VoxelArea::add_y(em, vi, -1);
 822                 }
 823
 824                 content_t c = vm->m_data[vi].getContent();
 825                 NodeDrawType dtype = ndef->get(c).drawtype;
 826                 // Only place on cubic, walkable, non-dust nodes.
 827                 // Dust check needed due to avoid double layer of dust caused by
 828                 // dropping dust from 16 nodes above mapchunk top.
 829                 if ((dtype == NDT_NORMAL ||
 830                                 dtype == NDT_ALLFACES ||
 831                                 dtype == NDT_ALLFACES_OPTIONAL ||
 832                                 dtype == NDT_GLASSLIKE ||
 833                                 dtype == NDT_GLASSLIKE_FRAMED ||
 834                                 dtype == NDT_GLASSLIKE_FRAMED_OPTIONAL) &&
 835                                 ndef->get(c).walkable && c != biome->c_dust) {
 836                         VoxelArea::add_y(em, vi, 1);
 837                         vm->m_data[vi] = MapNode(biome->c_dust);
 838                 }
 839         }
 840 }
 841
 842
 843 void MapgenBasic::generateCavesNoiseIntersection(s16 max_stone_y)
 844 {
 845         // cave_width >= 10 is used to disable generation and avoid the intensive
 846         // 3D noise calculations. Tunnels already have zero width when cave_width > 1.
 847         if (node_min.Y > max_stone_y || cave_width >= 10.0f)
 848                 return;
 849
 850         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 851                 &np_cave1, &np_cave2, seed, cave_width);
 852
 853         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 854 }
 855
 856
 857 void MapgenBasic::generateCavesRandomWalk(s16 max_stone_y, s16 large_cave_ymax)
 858 {
 859         if (node_min.Y > max_stone_y)
 860                 return;
 861
 862         PseudoRandom ps(blockseed + 21343);
 863         // Small randomwalk caves
 864         u32 num_small_caves = ps.range(small_cave_num_min, small_cave_num_max);
 865
 866         for (u32 i = 0; i < num_small_caves; i++) {
 867                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 868                         c_water_source, c_lava_source, large_cave_flooded, biomegen);
 869                 cave.makeCave(vm, node_min, node_max, &ps, false, max_stone_y, heightmap);
 870         }
 871
 872         if (node_max.Y > large_cave_ymax)
 873                 return;
 874
 875         // Large randomwalk caves below 'large_cave_ymax'.
 876         // 'large_cave_ymax' can differ from the 'large_cave_depth' mapgen parameter,
 877         // it is set to world base to disable large caves in or near caverns.
 878         u32 num_large_caves = ps.range(large_cave_num_min, large_cave_num_max);
 879
 880         for (u32 i = 0; i < num_large_caves; i++) {
 881                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 882                         c_water_source, c_lava_source, large_cave_flooded, biomegen);
 883                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
 884         }
 885 }
 886
 887
 888 bool MapgenBasic::generateCavernsNoise(s16 max_stone_y)
 889 {
 890         if (node_min.Y > max_stone_y || node_min.Y > cavern_limit)
 891                 return false;
 892
 893         CavernsNoise caverns_noise(ndef, csize, &np_cavern,
 894                 seed, cavern_limit, cavern_taper, cavern_threshold);
 895
 896         return caverns_noise.generateCaverns(vm, node_min, node_max);
 897 }
 898
 899
 900 void MapgenBasic::generateDungeons(s16 max_stone_y)
 901 {
 902         if (node_min.Y > max_stone_y || node_min.Y > dungeon_ymax ||
 903                         node_max.Y < dungeon_ymin)
 904                 return;
 905
 906         u16 num_dungeons = std::fmax(std::floor(
 907                 NoisePerlin3D(&np_dungeons, node_min.X, node_min.Y, node_min.Z, seed)), 0.0f);
 908         if (num_dungeons == 0)
 909                 return;
 910
 911         PseudoRandom ps(blockseed + 70033);
 912
 913         DungeonParams dp;
 914
 915         dp.np_alt_wall =
 916                 NoiseParams(-0.4, 1.0, v3f(40.0, 40.0, 40.0), 32474, 6, 1.1, 2.0);
 917
 918         dp.seed                = seed;
 919         dp.only_in_ground      = true;
 920         dp.num_dungeons        = num_dungeons;
 921         dp.notifytype          = GENNOTIFY_DUNGEON;
 922         dp.num_rooms           = ps.range(2, 16);
 923         dp.room_size_min       = v3s16(5, 5, 5);
 924         dp.room_size_max       = v3s16(12, 6, 12);
 925         dp.room_size_large_min = v3s16(12, 6, 12);
 926         dp.room_size_large_max = v3s16(16, 16, 16);
 927         dp.large_room_chance   = (ps.range(1, 4) == 1) ? 8 : 0;
 928         dp.diagonal_dirs       = ps.range(1, 8) == 1;
 929         // Diagonal corridors must have 'hole' width >=2 to be passable
 930         u8 holewidth           = (dp.diagonal_dirs) ? 2 : ps.range(1, 2);
 931         dp.holesize            = v3s16(holewidth, 3, holewidth);
 932         dp.corridor_len_min    = 1;
 933         dp.corridor_len_max    = 13;
 934
 935         // Get biome at mapchunk midpoint
 936         v3s16 chunk_mid = node_min + (node_max - node_min) / v3s16(2, 2, 2);
 937         Biome *biome = (Biome *)biomegen->getBiomeAtPoint(chunk_mid);
 938
 939         // Use biome-defined dungeon nodes if defined
 940         if (biome->c_dungeon != CONTENT_IGNORE) {
 941                 dp.c_wall = biome->c_dungeon;
 942                 // If 'node_dungeon_alt' is not defined by biome, it and dp.c_alt_wall
 943                 // become CONTENT_IGNORE which skips the alt wall node placement loop in
 944                 // dungeongen.cpp.
 945                 dp.c_alt_wall = biome->c_dungeon_alt;
 946                 // Stairs fall back to 'c_dungeon' if not defined by biome
 947                 dp.c_stair = (biome->c_dungeon_stair != CONTENT_IGNORE) ?
 948                         biome->c_dungeon_stair : biome->c_dungeon;
 949         // Fallback to using cobble mapgen alias if defined
 950         } else if (c_cobble != CONTENT_IGNORE) {
 951                 dp.c_wall     = c_cobble;
 952                 dp.c_alt_wall = CONTENT_IGNORE;
 953                 dp.c_stair    = c_cobble;
 954         // Fallback to using biome-defined stone
 955         } else {
 956                 dp.c_wall     = biome->c_stone;
 957                 dp.c_alt_wall = CONTENT_IGNORE;
 958                 dp.c_stair    = biome->c_stone;
 959         }
 960
 961         DungeonGen dgen(ndef, &gennotify, &dp);
 962         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 963 }
 964
 965
 966 ////
 967 //// GenerateNotifier
 968 ////
 969
 970 GenerateNotifier::GenerateNotifier(u32 notify_on,
 971         std::set<u32> *notify_on_deco_ids)
 972 {
 973         m_notify_on = notify_on;
 974         m_notify_on_deco_ids = notify_on_deco_ids;
 975 }
 976
 977
 978 void GenerateNotifier::setNotifyOn(u32 notify_on)
 979 {
 980         m_notify_on = notify_on;
 981 }
 982
 983
 984 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
 985 {
 986         m_notify_on_deco_ids = notify_on_deco_ids;
 987 }
 988
 989
 990 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
 991 {
 992         if (!(m_notify_on & (1 << type)))
 993                 return false;
 994
 995         if (type == GENNOTIFY_DECORATION &&
 996                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
 997                 return false;
 998
 999         GenNotifyEvent gne;
1000         gne.type = type;
1001         gne.pos  = pos;
1002         gne.id   = id;
1003         m_notify_events.push_back(gne);
1004
1005         return true;
1006 }
1007
1008
1009 void GenerateNotifier::getEvents(
1010         std::map<std::string, std::vector<v3s16> > &event_map)
1011 {
1012         std::list<GenNotifyEvent>::iterator it;
1013
1014         for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
1015                 GenNotifyEvent &gn = *it;
1016                 std::string name = (gn.type == GENNOTIFY_DECORATION) ?
1017                         "decoration#"+ itos(gn.id) :
1018                         flagdesc_gennotify[gn.type].name;
1019
1020                 event_map[name].push_back(gn.pos);
1021         }
1022 }
1023
1024
1025 void GenerateNotifier::clearEvents()
1026 {
1027         m_notify_events.clear();
1028 }
1029
1030
1031 ////
1032 //// MapgenParams
1033 ////
1034
1035
1036 MapgenParams::~MapgenParams()
1037 {
1038         delete bparams;
1039 }
1040
1041
1042 void MapgenParams::readParams(const Settings *settings)
1043 {
1044         std::string seed_str;
1045         const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";
1046
1047         if (settings->getNoEx(seed_name, seed_str)) {
1048                 if (!seed_str.empty())
1049                         seed = read_seed(seed_str.c_str());
1050                 else
1051                         myrand_bytes(&seed, sizeof(seed));
1052         }
1053
1054         std::string mg_name;
1055         if (settings->getNoEx("mg_name", mg_name)) {
1056                 mgtype = Mapgen::getMapgenType(mg_name);
1057                 if (mgtype == MAPGEN_INVALID)
1058                         mgtype = MAPGEN_DEFAULT;
1059         }
1060
1061         settings->getS16NoEx("water_level", water_level);
1062         settings->getS16NoEx("mapgen_limit", mapgen_limit);
1063         settings->getS16NoEx("chunksize", chunksize);
1064         settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
1065
1066         delete bparams;
1067         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
1068         if (bparams) {
1069                 bparams->readParams(settings);
1070                 bparams->seed = seed;
1071         }
1072 }
1073
1074
1075 void MapgenParams::writeParams(Settings *settings) const
1076 {
1077         settings->set("mg_name", Mapgen::getMapgenName(mgtype));
1078         settings->setU64("seed", seed);
1079         settings->setS16("water_level", water_level);
1080         settings->setS16("mapgen_limit", mapgen_limit);
1081         settings->setS16("chunksize", chunksize);
1082         settings->setFlagStr("mg_flags", flags, flagdesc_mapgen);
1083
1084         if (bparams)
1085                 bparams->writeParams(settings);
1086 }
1087
1088
1089 // Calculate exact edges of the outermost mapchunks that are within the
1090 // set 'mapgen_limit'.
1091 void MapgenParams::calcMapgenEdges()
1092 {
1093         // Central chunk offset, in blocks
1094         s16 ccoff_b = -chunksize / 2;
1095         // Chunksize, in nodes
1096         s32 csize_n = chunksize * MAP_BLOCKSIZE;
1097         // Minp/maxp of central chunk, in nodes
1098         s16 ccmin = ccoff_b * MAP_BLOCKSIZE;
1099         s16 ccmax = ccmin + csize_n - 1;
1100         // Fullminp/fullmaxp of central chunk, in nodes
1101         s16 ccfmin = ccmin - MAP_BLOCKSIZE;
1102         s16 ccfmax = ccmax + MAP_BLOCKSIZE;
1103         // Effective mapgen limit, in blocks
1104         // Uses same calculation as ServerMap::blockpos_over_mapgen_limit(v3s16 p)
1105         s16 mapgen_limit_b = rangelim(mapgen_limit,
1106                 0, MAX_MAP_GENERATION_LIMIT) / MAP_BLOCKSIZE;
1107         // Effective mapgen limits, in nodes
1108         s16 mapgen_limit_min = -mapgen_limit_b * MAP_BLOCKSIZE;
1109         s16 mapgen_limit_max = (mapgen_limit_b + 1) * MAP_BLOCKSIZE - 1;
1110         // Number of complete chunks from central chunk fullminp/fullmaxp
1111         // to effective mapgen limits.
1112         s16 numcmin = MYMAX((ccfmin - mapgen_limit_min) / csize_n, 0);
1113         s16 numcmax = MYMAX((mapgen_limit_max - ccfmax) / csize_n, 0);
1114         // Mapgen edges, in nodes
1115         mapgen_edge_min = ccmin - numcmin * csize_n;
1116         mapgen_edge_max = ccmax + numcmax * csize_n;
1117
1118         m_mapgen_edges_calculated = true;
1119 }
1120
1121
1122 s32 MapgenParams::getSpawnRangeMax()
1123 {
1124         if (!m_mapgen_edges_calculated)
1125                 calcMapgenEdges();
1126
1127         return MYMIN(-mapgen_edge_min, mapgen_edge_max);
1128 }