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