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