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