src/mapgen/mapgen.cpp

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