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