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