src/mapgen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2015 celeron55, Perttu Ahola <celeron55@gmail.com>
   4 Copyright (C) 2013-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
   5 Copyright (C) 2015-2017 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 "mapgen.h"
  23 #include "voxel.h"
  24 #include "noise.h"
  25 #include "gamedef.h"
  26 #include "mg_biome.h"
  27 #include "mapblock.h"
  28 #include "mapnode.h"
  29 #include "map.h"
  30 #include "content_sao.h"
  31 #include "nodedef.h"
  32 #include "emerge.h"
  33 #include "voxelalgorithms.h"
  34 #include "porting.h"
  35 #include "profiler.h"
  36 #include "settings.h"
  37 #include "treegen.h"
  38 #include "serialization.h"
  39 #include "util/serialize.h"
  40 #include "util/numeric.h"
  41 #include "filesys.h"
  42 #include "log.h"
  43 #include "mapgen_carpathian.h"
  44 #include "mapgen_flat.h"
  45 #include "mapgen_fractal.h"
  46 #include "mapgen_v5.h"
  47 #include "mapgen_v6.h"
  48 #include "mapgen_v7.h"
  49 #include "mapgen_valleys.h"
  50 #include "mapgen_singlenode.h"
  51 #include "cavegen.h"
  52 #include "dungeongen.h"
  53
  54 FlagDesc flagdesc_mapgen[] = {
  55         {"caves",       MG_CAVES},
  56         {"dungeons",    MG_DUNGEONS},
  57         {"light",       MG_LIGHT},
  58         {"decorations", MG_DECORATIONS},
  59         {NULL,       0}
  60 };
  61
  62 FlagDesc flagdesc_gennotify[] = {
  63         {"dungeon",          1 << GENNOTIFY_DUNGEON},
  64         {"temple",           1 << GENNOTIFY_TEMPLE},
  65         {"cave_begin",       1 << GENNOTIFY_CAVE_BEGIN},
  66         {"cave_end",         1 << GENNOTIFY_CAVE_END},
  67         {"large_cave_begin", 1 << GENNOTIFY_LARGECAVE_BEGIN},
  68         {"large_cave_end",   1 << GENNOTIFY_LARGECAVE_END},
  69         {"decoration",       1 << GENNOTIFY_DECORATION},
  70         {NULL,               0}
  71 };
  72
  73 struct MapgenDesc {
  74         const char *name;
  75         bool is_user_visible;
  76 };
  77
  78 ////
  79 //// Built-in mapgens
  80 ////
  81
  82 static MapgenDesc g_reg_mapgens[] = {
  83         {"v5",         true},
  84         {"v6",         true},
  85         {"v7",         true},
  86         {"flat",       true},
  87         {"fractal",    true},
  88         {"valleys",    true},
  89         {"singlenode", true},
  90         {"carpathian", true},
  91 };
  92
  93 STATIC_ASSERT(
  94         ARRLEN(g_reg_mapgens) == MAPGEN_INVALID,
  95         registered_mapgens_is_wrong_size);
  96
  97 ////
  98 //// Mapgen
  99 ////
 100
 101 Mapgen::Mapgen(int mapgenid, MapgenParams *params, EmergeManager *emerge) :
 102         gennotify(emerge->gen_notify_on, &emerge->gen_notify_on_deco_ids)
 103 {
 104         id           = mapgenid;
 105         water_level  = params->water_level;
 106         mapgen_limit = params->mapgen_limit;
 107         flags        = params->flags;
 108         csize        = v3s16(1, 1, 1) * (params->chunksize * MAP_BLOCKSIZE);
 109
 110         /*
 111                 We are losing half our entropy by doing this, but it is necessary to
 112                 preserve reverse compatibility.  If the top half of our current 64 bit
 113                 seeds ever starts getting used, existing worlds will break due to a
 114                 different hash outcome and no way to differentiate between versions.
 115
 116                 A solution could be to add a new bit to designate that the top half of
 117                 the seed value should be used, essentially a 1-bit version code, but
 118                 this would require increasing the total size of a seed to 9 bytes (yuck)
 119
 120                 It's probably okay if this never gets fixed.  4.2 billion possibilities
 121                 ought to be enough for anyone.
 122         */
 123         seed = (s32)params->seed;
 124
 125         ndef      = emerge->ndef;
 126 }
 127
 128
 129 MapgenType Mapgen::getMapgenType(const std::string &mgname)
 130 {
 131         for (size_t i = 0; i != ARRLEN(g_reg_mapgens); i++) {
 132                 if (mgname == g_reg_mapgens[i].name)
 133                         return (MapgenType)i;
 134         }
 135
 136         return MAPGEN_INVALID;
 137 }
 138
 139
 140 const char *Mapgen::getMapgenName(MapgenType mgtype)
 141 {
 142         size_t index = (size_t)mgtype;
 143         if (index == MAPGEN_INVALID || index >= ARRLEN(g_reg_mapgens))
 144                 return "invalid";
 145
 146         return g_reg_mapgens[index].name;
 147 }
 148
 149
 150 Mapgen *Mapgen::createMapgen(MapgenType mgtype, int mgid,
 151         MapgenParams *params, EmergeManager *emerge)
 152 {
 153         switch (mgtype) {
 154         case MAPGEN_CARPATHIAN:
 155                 return new MapgenCarpathian(mgid, (MapgenCarpathianParams *)params, emerge);
 156         case MAPGEN_FLAT:
 157                 return new MapgenFlat(mgid, (MapgenFlatParams *)params, emerge);
 158         case MAPGEN_FRACTAL:
 159                 return new MapgenFractal(mgid, (MapgenFractalParams *)params, emerge);
 160         case MAPGEN_SINGLENODE:
 161                 return new MapgenSinglenode(mgid, (MapgenSinglenodeParams *)params, emerge);
 162         case MAPGEN_V5:
 163                 return new MapgenV5(mgid, (MapgenV5Params *)params, emerge);
 164         case MAPGEN_V6:
 165                 return new MapgenV6(mgid, (MapgenV6Params *)params, emerge);
 166         case MAPGEN_V7:
 167                 return new MapgenV7(mgid, (MapgenV7Params *)params, emerge);
 168         case MAPGEN_VALLEYS:
 169                 return new MapgenValleys(mgid, (MapgenValleysParams *)params, emerge);
 170         default:
 171                 return NULL;
 172         }
 173 }
 174
 175
 176 MapgenParams *Mapgen::createMapgenParams(MapgenType mgtype)
 177 {
 178         switch (mgtype) {
 179         case MAPGEN_CARPATHIAN:
 180                 return new MapgenCarpathianParams;
 181         case MAPGEN_FLAT:
 182                 return new MapgenFlatParams;
 183         case MAPGEN_FRACTAL:
 184                 return new MapgenFractalParams;
 185         case MAPGEN_SINGLENODE:
 186                 return new MapgenSinglenodeParams;
 187         case MAPGEN_V5:
 188                 return new MapgenV5Params;
 189         case MAPGEN_V6:
 190                 return new MapgenV6Params;
 191         case MAPGEN_V7:
 192                 return new MapgenV7Params;
 193         case MAPGEN_VALLEYS:
 194                 return new MapgenValleysParams;
 195         default:
 196                 return NULL;
 197         }
 198 }
 199
 200
 201 void Mapgen::getMapgenNames(std::vector<const char *> *mgnames, bool include_hidden)
 202 {
 203         for (u32 i = 0; i != ARRLEN(g_reg_mapgens); i++) {
 204                 if (include_hidden || g_reg_mapgens[i].is_user_visible)
 205                         mgnames->push_back(g_reg_mapgens[i].name);
 206         }
 207 }
 208
 209
 210 u32 Mapgen::getBlockSeed(v3s16 p, s32 seed)
 211 {
 212         return (u32)seed   +
 213                 p.Z * 38134234 +
 214                 p.Y * 42123    +
 215                 p.X * 23;
 216 }
 217
 218
 219 u32 Mapgen::getBlockSeed2(v3s16 p, s32 seed)
 220 {
 221         u32 n = 1619 * p.X + 31337 * p.Y + 52591 * p.Z + 1013 * seed;
 222         n = (n >> 13) ^ n;
 223         return (n * (n * n * 60493 + 19990303) + 1376312589);
 224 }
 225
 226
 227 // Returns Y one under area minimum if not found
 228 s16 Mapgen::findGroundLevelFull(v2s16 p2d)
 229 {
 230         const v3s16 &em = vm->m_area.getExtent();
 231         s16 y_nodes_max = vm->m_area.MaxEdge.Y;
 232         s16 y_nodes_min = vm->m_area.MinEdge.Y;
 233         u32 i = vm->m_area.index(p2d.X, y_nodes_max, p2d.Y);
 234         s16 y;
 235
 236         for (y = y_nodes_max; y >= y_nodes_min; y--) {
 237                 MapNode &n = vm->m_data[i];
 238                 if (ndef->get(n).walkable)
 239                         break;
 240
 241                 vm->m_area.add_y(em, i, -1);
 242         }
 243         return (y >= y_nodes_min) ? y : y_nodes_min - 1;
 244 }
 245
 246
 247 // Returns -MAX_MAP_GENERATION_LIMIT if not found
 248 s16 Mapgen::findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax)
 249 {
 250         const v3s16 &em = vm->m_area.getExtent();
 251         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 252         s16 y;
 253
 254         for (y = ymax; y >= ymin; y--) {
 255                 MapNode &n = vm->m_data[i];
 256                 if (ndef->get(n).walkable)
 257                         break;
 258
 259                 vm->m_area.add_y(em, i, -1);
 260         }
 261         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 262 }
 263
 264
 265 // Returns -MAX_MAP_GENERATION_LIMIT if not found or if ground is found first
 266 s16 Mapgen::findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax)
 267 {
 268         const v3s16 &em = vm->m_area.getExtent();
 269         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 270         s16 y;
 271
 272         for (y = ymax; y >= ymin; y--) {
 273                 MapNode &n = vm->m_data[i];
 274                 if (ndef->get(n).walkable)
 275                         return -MAX_MAP_GENERATION_LIMIT;
 276
 277                 if (ndef->get(n).isLiquid())
 278                         break;
 279
 280                 vm->m_area.add_y(em, i, -1);
 281         }
 282         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 283 }
 284
 285
 286 void Mapgen::updateHeightmap(v3s16 nmin, v3s16 nmax)
 287 {
 288         if (!heightmap)
 289                 return;
 290
 291         //TimeTaker t("Mapgen::updateHeightmap", NULL, PRECISION_MICRO);
 292         int index = 0;
 293         for (s16 z = nmin.Z; z <= nmax.Z; z++) {
 294                 for (s16 x = nmin.X; x <= nmax.X; x++, index++) {
 295                         s16 y = findGroundLevel(v2s16(x, z), nmin.Y, nmax.Y);
 296
 297                         heightmap[index] = y;
 298                 }
 299         }
 300 }
 301
 302 inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
 303 {
 304         u32 vi_neg_x = vi;
 305         vm->m_area.add_x(em, vi_neg_x, -1);
 306         if (vm->m_data[vi_neg_x].getContent() != CONTENT_IGNORE) {
 307                 const ContentFeatures &c_nx = ndef->get(vm->m_data[vi_neg_x]);
 308                 if (c_nx.floodable && !c_nx.isLiquid())
 309                         return true;
 310         }
 311         u32 vi_pos_x = vi;
 312         vm->m_area.add_x(em, vi_pos_x, +1);
 313         if (vm->m_data[vi_pos_x].getContent() != CONTENT_IGNORE) {
 314                 const ContentFeatures &c_px = ndef->get(vm->m_data[vi_pos_x]);
 315                 if (c_px.floodable && !c_px.isLiquid())
 316                         return true;
 317         }
 318         u32 vi_neg_z = vi;
 319         vm->m_area.add_z(em, vi_neg_z, -1);
 320         if (vm->m_data[vi_neg_z].getContent() != CONTENT_IGNORE) {
 321                 const ContentFeatures &c_nz = ndef->get(vm->m_data[vi_neg_z]);
 322                 if (c_nz.floodable && !c_nz.isLiquid())
 323                         return true;
 324         }
 325         u32 vi_pos_z = vi;
 326         vm->m_area.add_z(em, vi_pos_z, +1);
 327         if (vm->m_data[vi_pos_z].getContent() != CONTENT_IGNORE) {
 328                 const ContentFeatures &c_pz = ndef->get(vm->m_data[vi_pos_z]);
 329                 if (c_pz.floodable && !c_pz.isLiquid())
 330                         return true;
 331         }
 332         return false;
 333 }
 334
 335 void Mapgen::updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax)
 336 {
 337         bool isignored, isliquid, wasignored, wasliquid, waschecked, waspushed;
 338         const v3s16 &em  = vm->m_area.getExtent();
 339
 340         for (s16 z = nmin.Z + 1; z <= nmax.Z - 1; z++)
 341         for (s16 x = nmin.X + 1; x <= nmax.X - 1; x++) {
 342                 wasignored = true;
 343                 wasliquid = false;
 344                 waschecked = false;
 345                 waspushed = false;
 346
 347                 u32 vi = vm->m_area.index(x, nmax.Y, z);
 348                 for (s16 y = nmax.Y; y >= nmin.Y; y--) {
 349                         isignored = vm->m_data[vi].getContent() == CONTENT_IGNORE;
 350                         isliquid = ndef->get(vm->m_data[vi]).isLiquid();
 351
 352                         if (isignored || wasignored || isliquid == wasliquid) {
 353                                 // Neither topmost node of liquid column nor topmost node below column
 354                                 waschecked = false;
 355                                 waspushed = false;
 356                         } else if (isliquid) {
 357                                 // This is the topmost node in the column
 358                                 bool ispushed = false;
 359                                 if (isLiquidHorizontallyFlowable(vi, em)) {
 360                                         trans_liquid->push_back(v3s16(x, y, z));
 361                                         ispushed = true;
 362                                 }
 363                                 // Remember waschecked and waspushed to avoid repeated
 364                                 // checks/pushes in case the column consists of only this node
 365                                 waschecked = true;
 366                                 waspushed = ispushed;
 367                         } else {
 368                                 // This is the topmost node below a liquid column
 369                                 u32 vi_above = vi;
 370                                 vm->m_area.add_y(em, vi_above, 1);
 371                                 if (!waspushed && (ndef->get(vm->m_data[vi]).floodable ||
 372                                                 (!waschecked && isLiquidHorizontallyFlowable(vi_above, em)))) {
 373                                         // Push back the lowest node in the column which is one
 374                                         // node above this one
 375                                         trans_liquid->push_back(v3s16(x, y + 1, z));
 376                                 }
 377                         }
 378
 379                         wasliquid = isliquid;
 380                         wasignored = isignored;
 381                         vm->m_area.add_y(em, vi, -1);
 382                 }
 383         }
 384 }
 385
 386
 387 void Mapgen::setLighting(u8 light, v3s16 nmin, v3s16 nmax)
 388 {
 389         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 390         VoxelArea a(nmin, nmax);
 391
 392         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 393                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 394                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 395                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++)
 396                                 vm->m_data[i].param1 = light;
 397                 }
 398         }
 399 }
 400
 401
 402 void Mapgen::lightSpread(VoxelArea &a, v3s16 p, u8 light)
 403 {
 404         if (light <= 1 || !a.contains(p))
 405                 return;
 406
 407         u32 vi = vm->m_area.index(p);
 408         MapNode &n = vm->m_data[vi];
 409
 410         // Decay light in each of the banks separately
 411         u8 light_day = light & 0x0F;
 412         if (light_day > 0)
 413                 light_day -= 0x01;
 414
 415         u8 light_night = light & 0xF0;
 416         if (light_night > 0)
 417                 light_night -= 0x10;
 418
 419         // Bail out only if we have no more light from either bank to propogate, or
 420         // we hit a solid block that light cannot pass through.
 421         if ((light_day  <= (n.param1 & 0x0F) &&
 422                 light_night <= (n.param1 & 0xF0)) ||
 423                 !ndef->get(n).light_propagates)
 424                 return;
 425
 426         // Since this recursive function only terminates when there is no light from
 427         // either bank left, we need to take the max of both banks into account for
 428         // the case where spreading has stopped for one light bank but not the other.
 429         light = MYMAX(light_day, n.param1 & 0x0F) |
 430                         MYMAX(light_night, n.param1 & 0xF0);
 431
 432         n.param1 = light;
 433
 434         lightSpread(a, p + v3s16(0, 0, 1), light);
 435         lightSpread(a, p + v3s16(0, 1, 0), light);
 436         lightSpread(a, p + v3s16(1, 0, 0), light);
 437         lightSpread(a, p - v3s16(0, 0, 1), light);
 438         lightSpread(a, p - v3s16(0, 1, 0), light);
 439         lightSpread(a, p - v3s16(1, 0, 0), light);
 440 }
 441
 442
 443 void Mapgen::calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
 444         bool propagate_shadow)
 445 {
 446         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 447         //TimeTaker t("updateLighting");
 448
 449         propagateSunlight(nmin, nmax, propagate_shadow);
 450         spreadLight(full_nmin, full_nmax);
 451
 452         //printf("updateLighting: %dms\n", t.stop());
 453 }
 454
 455
 456 void Mapgen::propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow)
 457 {
 458         //TimeTaker t("propagateSunlight");
 459         VoxelArea a(nmin, nmax);
 460         bool block_is_underground = (water_level >= nmax.Y);
 461         const v3s16 &em = vm->m_area.getExtent();
 462
 463         // NOTE: Direct access to the low 4 bits of param1 is okay here because,
 464         // by definition, sunlight will never be in the night lightbank.
 465
 466         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 467                 for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++) {
 468                         // see if we can get a light value from the overtop
 469                         u32 i = vm->m_area.index(x, a.MaxEdge.Y + 1, z);
 470                         if (vm->m_data[i].getContent() == CONTENT_IGNORE) {
 471                                 if (block_is_underground)
 472                                         continue;
 473                         } else if ((vm->m_data[i].param1 & 0x0F) != LIGHT_SUN &&
 474                                         propagate_shadow) {
 475                                 continue;
 476                         }
 477                         vm->m_area.add_y(em, i, -1);
 478
 479                         for (int y = a.MaxEdge.Y; y >= a.MinEdge.Y; y--) {
 480                                 MapNode &n = vm->m_data[i];
 481                                 if (!ndef->get(n).sunlight_propagates)
 482                                         break;
 483                                 n.param1 = LIGHT_SUN;
 484                                 vm->m_area.add_y(em, i, -1);
 485                         }
 486                 }
 487         }
 488         //printf("propagateSunlight: %dms\n", t.stop());
 489 }
 490
 491
 492 void Mapgen::spreadLight(v3s16 nmin, v3s16 nmax)
 493 {
 494         //TimeTaker t("spreadLight");
 495         VoxelArea a(nmin, nmax);
 496
 497         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 498                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 499                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 500                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++) {
 501                                 MapNode &n = vm->m_data[i];
 502                                 if (n.getContent() == CONTENT_IGNORE)
 503                                         continue;
 504
 505                                 const ContentFeatures &cf = ndef->get(n);
 506                                 if (!cf.light_propagates)
 507                                         continue;
 508
 509                                 // TODO(hmmmmm): Abstract away direct param1 accesses with a
 510                                 // wrapper, but something lighter than MapNode::get/setLight
 511
 512                                 u8 light_produced = cf.light_source;
 513                                 if (light_produced)
 514                                         n.param1 = light_produced | (light_produced << 4);
 515
 516                                 u8 light = n.param1;
 517                                 if (light) {
 518                                         lightSpread(a, v3s16(x,     y,     z + 1), light);
 519                                         lightSpread(a, v3s16(x,     y + 1, z    ), light);
 520                                         lightSpread(a, v3s16(x + 1, y,     z    ), light);
 521                                         lightSpread(a, v3s16(x,     y,     z - 1), light);
 522                                         lightSpread(a, v3s16(x,     y - 1, z    ), light);
 523                                         lightSpread(a, v3s16(x - 1, y,     z    ), light);
 524                                 }
 525                         }
 526                 }
 527         }
 528
 529         //printf("spreadLight: %dms\n", t.stop());
 530 }
 531
 532
 533 ////
 534 //// MapgenBasic
 535 ////
 536
 537 MapgenBasic::MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge)
 538         : Mapgen(mapgenid, params, emerge)
 539 {
 540         this->m_emerge = emerge;
 541         this->m_bmgr   = emerge->biomemgr;
 542
 543         //// Here, 'stride' refers to the number of elements needed to skip to index
 544         //// an adjacent element for that coordinate in noise/height/biome maps
 545         //// (*not* vmanip content map!)
 546
 547         // Note there is no X stride explicitly defined.  Items adjacent in the X
 548         // coordinate are assumed to be adjacent in memory as well (i.e. stride of 1).
 549
 550         // Number of elements to skip to get to the next Y coordinate
 551         this->ystride = csize.X;
 552
 553         // Number of elements to skip to get to the next Z coordinate
 554         this->zstride = csize.X * csize.Y;
 555
 556         // Z-stride value for maps oversized for 1-down overgeneration
 557         this->zstride_1d = csize.X * (csize.Y + 1);
 558
 559         // Z-stride value for maps oversized for 1-up 1-down overgeneration
 560         this->zstride_1u1d = csize.X * (csize.Y + 2);
 561
 562         //// Allocate heightmap
 563         this->heightmap = new s16[csize.X * csize.Z];
 564
 565         //// Initialize biome generator
 566         // TODO(hmmmm): should we have a way to disable biomemanager biomes?
 567         biomegen = m_bmgr->createBiomeGen(BIOMEGEN_ORIGINAL, params->bparams, csize);
 568         biomemap = biomegen->biomemap;
 569
 570         //// Look up some commonly used content
 571         c_stone              = ndef->getId("mapgen_stone");
 572         c_desert_stone       = ndef->getId("mapgen_desert_stone");
 573         c_sandstone          = ndef->getId("mapgen_sandstone");
 574         c_water_source       = ndef->getId("mapgen_water_source");
 575         c_river_water_source = ndef->getId("mapgen_river_water_source");
 576         c_lava_source        = ndef->getId("mapgen_lava_source");
 577
 578         // Fall back to more basic content if not defined
 579         // river_water_source cannot fallback to water_source because river water
 580         // needs to be non-renewable and have a short flow range.
 581         if (c_desert_stone == CONTENT_IGNORE)
 582                 c_desert_stone = c_stone;
 583         if (c_sandstone == CONTENT_IGNORE)
 584                 c_sandstone = c_stone;
 585
 586         //// Content used for dungeon generation
 587         c_cobble                = ndef->getId("mapgen_cobble");
 588         c_mossycobble           = ndef->getId("mapgen_mossycobble");
 589         c_stair_cobble          = ndef->getId("mapgen_stair_cobble");
 590         c_stair_desert_stone    = ndef->getId("mapgen_stair_desert_stone");
 591         c_sandstonebrick        = ndef->getId("mapgen_sandstonebrick");
 592         c_stair_sandstone_block = ndef->getId("mapgen_stair_sandstone_block");
 593
 594         // Fall back to more basic content if not defined
 595         if (c_mossycobble == CONTENT_IGNORE)
 596                 c_mossycobble = c_cobble;
 597         if (c_stair_cobble == CONTENT_IGNORE)
 598                 c_stair_cobble = c_cobble;
 599         if (c_stair_desert_stone == CONTENT_IGNORE)
 600                 c_stair_desert_stone = c_desert_stone;
 601         if (c_sandstonebrick == CONTENT_IGNORE)
 602                 c_sandstonebrick = c_sandstone;
 603         if (c_stair_sandstone_block == CONTENT_IGNORE)
 604                 c_stair_sandstone_block = c_sandstonebrick;
 605 }
 606
 607
 608 MapgenBasic::~MapgenBasic()
 609 {
 610         delete biomegen;
 611         delete []heightmap;
 612 }
 613
 614
 615 void MapgenBasic::generateBiomes(MgStoneType *mgstone_type,
 616         content_t *biome_stone, s16 biome_zero_level)
 617 {
 618         // can't generate biomes without a biome generator!
 619         assert(biomegen);
 620         assert(biomemap);
 621
 622         const v3s16 &em = vm->m_area.getExtent();
 623         u32 index = 0;
 624         MgStoneType stone_type = MGSTONE_OTHER;
 625         content_t c_biome_stone = c_stone;
 626
 627         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 628
 629         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 630         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 631                 Biome *biome = NULL;
 632                 u16 depth_top = 0;
 633                 u16 base_filler = 0;
 634                 u16 depth_water_top = 0;
 635                 u16 depth_riverbed = 0;
 636                 s16 biome_y_min = -MAX_MAP_GENERATION_LIMIT;
 637                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 638
 639                 // Check node at base of mapchunk above, either a node of a previously
 640                 // generated mapchunk or if not, a node of overgenerated base terrain.
 641                 content_t c_above = vm->m_data[vi + em.X].getContent();
 642                 bool air_above = c_above == CONTENT_AIR;
 643                 bool river_water_above = c_above == c_river_water_source;
 644                 bool water_above = c_above == c_water_source || river_water_above;
 645
 646                 biomemap[index] = BIOME_NONE;
 647
 648                 // If there is air or water above enable top/filler placement, otherwise force
 649                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 650                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 651
 652                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 653                         content_t c = vm->m_data[vi].getContent();
 654                         // Biome is (re)calculated:
 655                         // 1. At the surface of stone below air or water.
 656                         // 2. At the surface of water below air.
 657                         // 3. When stone or water is detected but biome has not yet been calculated.
 658                         // 4. When stone or water is detected just below a biome's lower limit.
 659                         bool is_stone_surface = (c == c_stone) &&
 660                                 (air_above || water_above || !biome || y < biome_y_min); // 1, 3, 4
 661
 662                         bool is_water_surface =
 663                                 (c == c_water_source || c == c_river_water_source) &&
 664                                 (air_above || !biome || y < biome_y_min); // 2, 3, 4
 665
 666                         if (is_stone_surface || is_water_surface) {
 667                                 // (Re)calculate biome
 668                                 // Limit to +-MAX MAP GENERATION LIMIT to work with biome y_min / y_max.
 669                                 s32 relative_y = rangelim(y - biome_zero_level,
 670                                         -MAX_MAP_GENERATION_LIMIT, MAX_MAP_GENERATION_LIMIT);
 671                                 biome = biomegen->getBiomeAtIndex(index, relative_y);
 672
 673                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 674                                         biomemap[index] = biome->index;
 675
 676                                 depth_top = biome->depth_top;
 677                                 base_filler = MYMAX(depth_top +
 678                                         biome->depth_filler +
 679                                         noise_filler_depth->result[index], 0.0f);
 680                                 depth_water_top = biome->depth_water_top;
 681                                 depth_riverbed = biome->depth_riverbed;
 682                                 biome_y_min = rangelim(biome->y_min + biome_zero_level,
 683                                         -MAX_MAP_GENERATION_LIMIT, MAX_MAP_GENERATION_LIMIT);
 684
 685                                 // Detect stone type for dungeons during every biome calculation.
 686                                 // If none detected the last selected biome stone is chosen.
 687                                 if (biome->c_stone == c_stone)
 688                                         stone_type = MGSTONE_STONE;
 689                                 else if (biome->c_stone == c_desert_stone)
 690                                         stone_type = MGSTONE_DESERT_STONE;
 691                                 else if (biome->c_stone == c_sandstone)
 692                                         stone_type = MGSTONE_SANDSTONE;
 693
 694                                 c_biome_stone = biome->c_stone;
 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                         vm->m_area.add_y(em, vi, -1);
 753                 }
 754         }
 755
 756         *mgstone_type = stone_type;
 757         *biome_stone = c_biome_stone;
 758 }
 759
 760
 761 void MapgenBasic::dustTopNodes()
 762 {
 763         if (node_max.Y < water_level)
 764                 return;
 765
 766         const v3s16 &em = vm->m_area.getExtent();
 767         u32 index = 0;
 768
 769         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 770         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 771                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 772
 773                 if (biome->c_dust == CONTENT_IGNORE)
 774                         continue;
 775
 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                         vm->m_area.add_y(em, vi, -1);
 800                 }
 801
 802                 content_t c = vm->m_data[vi].getContent();
 803                 if (!ndef->get(c).buildable_to && c != CONTENT_IGNORE && c != biome->c_dust) {
 804                         vm->m_area.add_y(em, vi, 1);
 805                         vm->m_data[vi] = MapNode(biome->c_dust);
 806                 }
 807         }
 808 }
 809
 810
 811 void MapgenBasic::generateCaves(s16 max_stone_y, s16 large_cave_depth)
 812 {
 813         if (max_stone_y < node_min.Y)
 814                 return;
 815
 816         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 817                 &np_cave1, &np_cave2, seed, cave_width);
 818
 819         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 820
 821         if (node_max.Y > large_cave_depth)
 822                 return;
 823
 824         PseudoRandom ps(blockseed + 21343);
 825         u32 bruises_count = ps.range(0, 2);
 826         for (u32 i = 0; i < bruises_count; i++) {
 827                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 828                         c_water_source, CONTENT_IGNORE, lava_depth);
 829
 830                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
 831         }
 832 }
 833
 834
 835 bool MapgenBasic::generateCaverns(s16 max_stone_y)
 836 {
 837         if (node_min.Y > max_stone_y || node_min.Y > cavern_limit)
 838                 return false;
 839
 840         CavernsNoise caverns_noise(ndef, csize, &np_cavern,
 841                 seed, cavern_limit, cavern_taper, cavern_threshold);
 842
 843         return caverns_noise.generateCaverns(vm, node_min, node_max);
 844 }
 845
 846
 847 void MapgenBasic::generateDungeons(s16 max_stone_y,
 848         MgStoneType stone_type, content_t biome_stone)
 849 {
 850         if (max_stone_y < node_min.Y)
 851                 return;
 852
 853         DungeonParams dp;
 854
 855         dp.seed             = seed;
 856         dp.c_water          = c_water_source;
 857         dp.c_river_water    = c_river_water_source;
 858
 859         dp.only_in_ground   = true;
 860         dp.corridor_len_min = 1;
 861         dp.corridor_len_max = 13;
 862         dp.rooms_min        = 2;
 863         dp.rooms_max        = 16;
 864         dp.y_min            = -MAX_MAP_GENERATION_LIMIT;
 865         dp.y_max            = MAX_MAP_GENERATION_LIMIT;
 866
 867         dp.np_density       = nparams_dungeon_density;
 868         dp.np_alt_wall      = nparams_dungeon_alt_wall;
 869
 870         switch (stone_type) {
 871         default:
 872         case MGSTONE_STONE:
 873                 dp.c_wall              = c_cobble;
 874                 dp.c_alt_wall          = c_mossycobble;
 875                 dp.c_stair             = c_stair_cobble;
 876
 877                 dp.diagonal_dirs       = false;
 878                 dp.holesize            = v3s16(1, 2, 1);
 879                 dp.room_size_min       = v3s16(4, 4, 4);
 880                 dp.room_size_max       = v3s16(8, 6, 8);
 881                 dp.room_size_large_min = v3s16(8, 8, 8);
 882                 dp.room_size_large_max = v3s16(16, 16, 16);
 883                 dp.notifytype          = GENNOTIFY_DUNGEON;
 884                 break;
 885         case MGSTONE_DESERT_STONE:
 886                 dp.c_wall              = c_desert_stone;
 887                 dp.c_alt_wall          = CONTENT_IGNORE;
 888                 dp.c_stair             = c_stair_desert_stone;
 889
 890                 dp.diagonal_dirs       = true;
 891                 dp.holesize            = v3s16(2, 3, 2);
 892                 dp.room_size_min       = v3s16(6, 9, 6);
 893                 dp.room_size_max       = v3s16(10, 11, 10);
 894                 dp.room_size_large_min = v3s16(10, 13, 10);
 895                 dp.room_size_large_max = v3s16(18, 21, 18);
 896                 dp.notifytype          = GENNOTIFY_TEMPLE;
 897                 break;
 898         case MGSTONE_SANDSTONE:
 899                 dp.c_wall              = c_sandstonebrick;
 900                 dp.c_alt_wall          = CONTENT_IGNORE;
 901                 dp.c_stair             = c_stair_sandstone_block;
 902
 903                 dp.diagonal_dirs       = false;
 904                 dp.holesize            = v3s16(2, 2, 2);
 905                 dp.room_size_min       = v3s16(6, 4, 6);
 906                 dp.room_size_max       = v3s16(10, 6, 10);
 907                 dp.room_size_large_min = v3s16(10, 8, 10);
 908                 dp.room_size_large_max = v3s16(18, 16, 18);
 909                 dp.notifytype          = GENNOTIFY_DUNGEON;
 910                 break;
 911         case MGSTONE_OTHER:
 912                 dp.c_wall              = biome_stone;
 913                 dp.c_alt_wall          = biome_stone;
 914                 dp.c_stair             = biome_stone;
 915
 916                 dp.diagonal_dirs       = false;
 917                 dp.holesize            = v3s16(1, 2, 1);
 918                 dp.room_size_min       = v3s16(4, 4, 4);
 919                 dp.room_size_max       = v3s16(8, 6, 8);
 920                 dp.room_size_large_min = v3s16(8, 8, 8);
 921                 dp.room_size_large_max = v3s16(16, 16, 16);
 922                 dp.notifytype          = GENNOTIFY_DUNGEON;
 923                 break;
 924         }
 925
 926         DungeonGen dgen(ndef, &gennotify, &dp);
 927         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 928 }
 929
 930
 931 ////
 932 //// GenerateNotifier
 933 ////
 934
 935 GenerateNotifier::GenerateNotifier(u32 notify_on,
 936         std::set<u32> *notify_on_deco_ids)
 937 {
 938         m_notify_on = notify_on;
 939         m_notify_on_deco_ids = notify_on_deco_ids;
 940 }
 941
 942
 943 void GenerateNotifier::setNotifyOn(u32 notify_on)
 944 {
 945         m_notify_on = notify_on;
 946 }
 947
 948
 949 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
 950 {
 951         m_notify_on_deco_ids = notify_on_deco_ids;
 952 }
 953
 954
 955 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
 956 {
 957         if (!(m_notify_on & (1 << type)))
 958                 return false;
 959
 960         if (type == GENNOTIFY_DECORATION &&
 961                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
 962                 return false;
 963
 964         GenNotifyEvent gne;
 965         gne.type = type;
 966         gne.pos  = pos;
 967         gne.id   = id;
 968         m_notify_events.push_back(gne);
 969
 970         return true;
 971 }
 972
 973
 974 void GenerateNotifier::getEvents(
 975         std::map<std::string, std::vector<v3s16> > &event_map,
 976         bool peek_events)
 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         if (!peek_events)
 990                 m_notify_events.clear();
 991 }
 992
 993
 994 ////
 995 //// MapgenParams
 996 ////
 997
 998
 999 MapgenParams::~MapgenParams()
1000 {
1001         delete bparams;
1002 }
1003
1004
1005 void MapgenParams::readParams(const Settings *settings)
1006 {
1007         std::string seed_str;
1008         const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";
1009
1010         if (settings->getNoEx(seed_name, seed_str)) {
1011                 if (!seed_str.empty())
1012                         seed = read_seed(seed_str.c_str());
1013                 else
1014                         myrand_bytes(&seed, sizeof(seed));
1015         }
1016
1017         std::string mg_name;
1018         if (settings->getNoEx("mg_name", mg_name)) {
1019                 mgtype = Mapgen::getMapgenType(mg_name);
1020                 if (mgtype == MAPGEN_INVALID)
1021                         mgtype = MAPGEN_DEFAULT;
1022         }
1023
1024         settings->getS16NoEx("water_level", water_level);
1025         settings->getS16NoEx("mapgen_limit", mapgen_limit);
1026         settings->getS16NoEx("chunksize", chunksize);
1027         settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
1028
1029         delete bparams;
1030         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
1031         if (bparams) {
1032                 bparams->readParams(settings);
1033                 bparams->seed = seed;
1034         }
1035 }
1036
1037
1038 void MapgenParams::writeParams(Settings *settings) const
1039 {
1040         settings->set("mg_name", Mapgen::getMapgenName(mgtype));
1041         settings->setU64("seed", seed);
1042         settings->setS16("water_level", water_level);
1043         settings->setS16("mapgen_limit", mapgen_limit);
1044         settings->setS16("chunksize", chunksize);
1045         settings->setFlagStr("mg_flags", flags, flagdesc_mapgen, U32_MAX);
1046
1047         if (bparams)
1048                 bparams->writeParams(settings);
1049 }
1050
1051 // Calculate edges of outermost generated mapchunks (less than
1052 // 'mapgen_limit'), and corresponding exact limits for SAO entities.
1053 void MapgenParams::calcMapgenEdges()
1054 {
1055         if (m_mapgen_edges_calculated)
1056                 return;
1057
1058         // Central chunk offset, in blocks
1059         s16 ccoff_b = -chunksize / 2;
1060         // Chunksize, in nodes
1061         s32 csize_n = chunksize * MAP_BLOCKSIZE;
1062         // Minp/maxp of central chunk, in nodes
1063         s16 ccmin = ccoff_b * MAP_BLOCKSIZE;
1064         s16 ccmax = ccmin + csize_n - 1;
1065         // Fullminp/fullmaxp of central chunk, in nodes
1066         s16 ccfmin = ccmin - MAP_BLOCKSIZE;
1067         s16 ccfmax = ccmax + MAP_BLOCKSIZE;
1068         // Effective mapgen limit, in blocks
1069         // Uses same calculation as ServerMap::blockpos_over_mapgen_limit(v3s16 p)
1070         s16 mapgen_limit_b = rangelim(mapgen_limit,
1071                 0, MAX_MAP_GENERATION_LIMIT) / MAP_BLOCKSIZE;
1072         // Effective mapgen limits, in nodes
1073         s16 mapgen_limit_min = -mapgen_limit_b * MAP_BLOCKSIZE;
1074         s16 mapgen_limit_max = (mapgen_limit_b + 1) * MAP_BLOCKSIZE - 1;
1075         // Number of complete chunks from central chunk fullminp/fullmaxp
1076         // to effective mapgen limits.
1077         s16 numcmin = MYMAX((ccfmin - mapgen_limit_min) / csize_n, 0);
1078         s16 numcmax = MYMAX((mapgen_limit_max - ccfmax) / csize_n, 0);
1079         // Mapgen edges, in nodes
1080         mapgen_edge_min = ccmin - numcmin * csize_n;
1081         mapgen_edge_max = ccmax + numcmax * csize_n;
1082         // SAO position limits, in Irrlicht units
1083         m_sao_limit_min = mapgen_edge_min * BS - 3.0f;
1084         m_sao_limit_max = mapgen_edge_max * BS + 3.0f;
1085
1086         m_mapgen_edges_calculated = true;
1087 }
1088
1089
1090 bool MapgenParams::saoPosOverLimit(const v3f &p)
1091 {
1092         if (!m_mapgen_edges_calculated)
1093                 calcMapgenEdges();
1094
1095         return p.X < m_sao_limit_min ||
1096                 p.X > m_sao_limit_max ||
1097                 p.Y < m_sao_limit_min ||
1098                 p.Y > m_sao_limit_max ||
1099                 p.Z < m_sao_limit_min ||
1100                 p.Z > m_sao_limit_max;
1101 }
1102
1103
1104 s32 MapgenParams::getSpawnRangeMax()
1105 {
1106         calcMapgenEdges();
1107
1108         return MYMIN(-mapgen_edge_min, mapgen_edge_max);
1109 }