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
 303 void Mapgen::getSurfaces(v2s16 p2d, s16 ymin, s16 ymax,
 304         s16 *floors, s16 *ceilings, u16 *num_floors, u16 *num_ceilings)
 305 {
 306         u16 floor_i = 0;
 307         u16 ceiling_i = 0;
 308         const v3s16 &em = vm->m_area.getExtent();
 309
 310         bool is_walkable = false;
 311         u32 vi = vm->m_area.index(p2d.X, ymax, p2d.Y);
 312         MapNode mn_max = vm->m_data[vi];
 313         bool walkable_above = ndef->get(mn_max).walkable;
 314         vm->m_area.add_y(em, vi, -1);
 315
 316         for (s16 y = ymax - 1; y >= ymin; y--) {
 317                 MapNode mn = vm->m_data[vi];
 318                 is_walkable = ndef->get(mn).walkable;
 319
 320                 if (is_walkable && !walkable_above) {
 321                         floors[floor_i] = y;
 322                         floor_i++;
 323                 } else if (!is_walkable && walkable_above) {
 324                         ceilings[ceiling_i] = y + 1;
 325                         ceiling_i++;
 326                 }
 327
 328                 vm->m_area.add_y(em, vi, -1);
 329                 walkable_above = is_walkable;
 330         }
 331
 332         *num_floors = floor_i;
 333         *num_ceilings = ceiling_i;
 334 }
 335
 336
 337 inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
 338 {
 339         u32 vi_neg_x = vi;
 340         vm->m_area.add_x(em, vi_neg_x, -1);
 341         if (vm->m_data[vi_neg_x].getContent() != CONTENT_IGNORE) {
 342                 const ContentFeatures &c_nx = ndef->get(vm->m_data[vi_neg_x]);
 343                 if (c_nx.floodable && !c_nx.isLiquid())
 344                         return true;
 345         }
 346         u32 vi_pos_x = vi;
 347         vm->m_area.add_x(em, vi_pos_x, +1);
 348         if (vm->m_data[vi_pos_x].getContent() != CONTENT_IGNORE) {
 349                 const ContentFeatures &c_px = ndef->get(vm->m_data[vi_pos_x]);
 350                 if (c_px.floodable && !c_px.isLiquid())
 351                         return true;
 352         }
 353         u32 vi_neg_z = vi;
 354         vm->m_area.add_z(em, vi_neg_z, -1);
 355         if (vm->m_data[vi_neg_z].getContent() != CONTENT_IGNORE) {
 356                 const ContentFeatures &c_nz = ndef->get(vm->m_data[vi_neg_z]);
 357                 if (c_nz.floodable && !c_nz.isLiquid())
 358                         return true;
 359         }
 360         u32 vi_pos_z = vi;
 361         vm->m_area.add_z(em, vi_pos_z, +1);
 362         if (vm->m_data[vi_pos_z].getContent() != CONTENT_IGNORE) {
 363                 const ContentFeatures &c_pz = ndef->get(vm->m_data[vi_pos_z]);
 364                 if (c_pz.floodable && !c_pz.isLiquid())
 365                         return true;
 366         }
 367         return false;
 368 }
 369
 370 void Mapgen::updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax)
 371 {
 372         bool isignored, isliquid, wasignored, wasliquid, waschecked, waspushed;
 373         const v3s16 &em  = vm->m_area.getExtent();
 374
 375         for (s16 z = nmin.Z + 1; z <= nmax.Z - 1; z++)
 376         for (s16 x = nmin.X + 1; x <= nmax.X - 1; x++) {
 377                 wasignored = true;
 378                 wasliquid = false;
 379                 waschecked = false;
 380                 waspushed = false;
 381
 382                 u32 vi = vm->m_area.index(x, nmax.Y, z);
 383                 for (s16 y = nmax.Y; y >= nmin.Y; y--) {
 384                         isignored = vm->m_data[vi].getContent() == CONTENT_IGNORE;
 385                         isliquid = ndef->get(vm->m_data[vi]).isLiquid();
 386
 387                         if (isignored || wasignored || isliquid == wasliquid) {
 388                                 // Neither topmost node of liquid column nor topmost node below column
 389                                 waschecked = false;
 390                                 waspushed = false;
 391                         } else if (isliquid) {
 392                                 // This is the topmost node in the column
 393                                 bool ispushed = false;
 394                                 if (isLiquidHorizontallyFlowable(vi, em)) {
 395                                         trans_liquid->push_back(v3s16(x, y, z));
 396                                         ispushed = true;
 397                                 }
 398                                 // Remember waschecked and waspushed to avoid repeated
 399                                 // checks/pushes in case the column consists of only this node
 400                                 waschecked = true;
 401                                 waspushed = ispushed;
 402                         } else {
 403                                 // This is the topmost node below a liquid column
 404                                 u32 vi_above = vi;
 405                                 vm->m_area.add_y(em, vi_above, 1);
 406                                 if (!waspushed && (ndef->get(vm->m_data[vi]).floodable ||
 407                                                 (!waschecked && isLiquidHorizontallyFlowable(vi_above, em)))) {
 408                                         // Push back the lowest node in the column which is one
 409                                         // node above this one
 410                                         trans_liquid->push_back(v3s16(x, y + 1, z));
 411                                 }
 412                         }
 413
 414                         wasliquid = isliquid;
 415                         wasignored = isignored;
 416                         vm->m_area.add_y(em, vi, -1);
 417                 }
 418         }
 419 }
 420
 421
 422 void Mapgen::setLighting(u8 light, v3s16 nmin, v3s16 nmax)
 423 {
 424         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 425         VoxelArea a(nmin, nmax);
 426
 427         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 428                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 429                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 430                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++)
 431                                 vm->m_data[i].param1 = light;
 432                 }
 433         }
 434 }
 435
 436
 437 void Mapgen::lightSpread(VoxelArea &a, v3s16 p, u8 light)
 438 {
 439         if (light <= 1 || !a.contains(p))
 440                 return;
 441
 442         u32 vi = vm->m_area.index(p);
 443         MapNode &n = vm->m_data[vi];
 444
 445         // Decay light in each of the banks separately
 446         u8 light_day = light & 0x0F;
 447         if (light_day > 0)
 448                 light_day -= 0x01;
 449
 450         u8 light_night = light & 0xF0;
 451         if (light_night > 0)
 452                 light_night -= 0x10;
 453
 454         // Bail out only if we have no more light from either bank to propogate, or
 455         // we hit a solid block that light cannot pass through.
 456         if ((light_day  <= (n.param1 & 0x0F) &&
 457                 light_night <= (n.param1 & 0xF0)) ||
 458                 !ndef->get(n).light_propagates)
 459                 return;
 460
 461         // Since this recursive function only terminates when there is no light from
 462         // either bank left, we need to take the max of both banks into account for
 463         // the case where spreading has stopped for one light bank but not the other.
 464         light = MYMAX(light_day, n.param1 & 0x0F) |
 465                         MYMAX(light_night, n.param1 & 0xF0);
 466
 467         n.param1 = light;
 468
 469         lightSpread(a, p + v3s16(0, 0, 1), light);
 470         lightSpread(a, p + v3s16(0, 1, 0), light);
 471         lightSpread(a, p + v3s16(1, 0, 0), light);
 472         lightSpread(a, p - v3s16(0, 0, 1), light);
 473         lightSpread(a, p - v3s16(0, 1, 0), light);
 474         lightSpread(a, p - v3s16(1, 0, 0), light);
 475 }
 476
 477
 478 void Mapgen::calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
 479         bool propagate_shadow)
 480 {
 481         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 482         //TimeTaker t("updateLighting");
 483
 484         propagateSunlight(nmin, nmax, propagate_shadow);
 485         spreadLight(full_nmin, full_nmax);
 486
 487         //printf("updateLighting: %dms\n", t.stop());
 488 }
 489
 490
 491 void Mapgen::propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow)
 492 {
 493         //TimeTaker t("propagateSunlight");
 494         VoxelArea a(nmin, nmax);
 495         bool block_is_underground = (water_level >= nmax.Y);
 496         const v3s16 &em = vm->m_area.getExtent();
 497
 498         // NOTE: Direct access to the low 4 bits of param1 is okay here because,
 499         // by definition, sunlight will never be in the night lightbank.
 500
 501         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 502                 for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++) {
 503                         // see if we can get a light value from the overtop
 504                         u32 i = vm->m_area.index(x, a.MaxEdge.Y + 1, z);
 505                         if (vm->m_data[i].getContent() == CONTENT_IGNORE) {
 506                                 if (block_is_underground)
 507                                         continue;
 508                         } else if ((vm->m_data[i].param1 & 0x0F) != LIGHT_SUN &&
 509                                         propagate_shadow) {
 510                                 continue;
 511                         }
 512                         vm->m_area.add_y(em, i, -1);
 513
 514                         for (int y = a.MaxEdge.Y; y >= a.MinEdge.Y; y--) {
 515                                 MapNode &n = vm->m_data[i];
 516                                 if (!ndef->get(n).sunlight_propagates)
 517                                         break;
 518                                 n.param1 = LIGHT_SUN;
 519                                 vm->m_area.add_y(em, i, -1);
 520                         }
 521                 }
 522         }
 523         //printf("propagateSunlight: %dms\n", t.stop());
 524 }
 525
 526
 527 void Mapgen::spreadLight(v3s16 nmin, v3s16 nmax)
 528 {
 529         //TimeTaker t("spreadLight");
 530         VoxelArea a(nmin, nmax);
 531
 532         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 533                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 534                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 535                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++) {
 536                                 MapNode &n = vm->m_data[i];
 537                                 if (n.getContent() == CONTENT_IGNORE)
 538                                         continue;
 539
 540                                 const ContentFeatures &cf = ndef->get(n);
 541                                 if (!cf.light_propagates)
 542                                         continue;
 543
 544                                 // TODO(hmmmmm): Abstract away direct param1 accesses with a
 545                                 // wrapper, but something lighter than MapNode::get/setLight
 546
 547                                 u8 light_produced = cf.light_source;
 548                                 if (light_produced)
 549                                         n.param1 = light_produced | (light_produced << 4);
 550
 551                                 u8 light = n.param1;
 552                                 if (light) {
 553                                         lightSpread(a, v3s16(x,     y,     z + 1), light);
 554                                         lightSpread(a, v3s16(x,     y + 1, z    ), light);
 555                                         lightSpread(a, v3s16(x + 1, y,     z    ), light);
 556                                         lightSpread(a, v3s16(x,     y,     z - 1), light);
 557                                         lightSpread(a, v3s16(x,     y - 1, z    ), light);
 558                                         lightSpread(a, v3s16(x - 1, y,     z    ), light);
 559                                 }
 560                         }
 561                 }
 562         }
 563
 564         //printf("spreadLight: %dms\n", t.stop());
 565 }
 566
 567
 568 ////
 569 //// MapgenBasic
 570 ////
 571
 572 MapgenBasic::MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge)
 573         : Mapgen(mapgenid, params, emerge)
 574 {
 575         this->m_emerge = emerge;
 576         this->m_bmgr   = emerge->biomemgr;
 577
 578         //// Here, 'stride' refers to the number of elements needed to skip to index
 579         //// an adjacent element for that coordinate in noise/height/biome maps
 580         //// (*not* vmanip content map!)
 581
 582         // Note there is no X stride explicitly defined.  Items adjacent in the X
 583         // coordinate are assumed to be adjacent in memory as well (i.e. stride of 1).
 584
 585         // Number of elements to skip to get to the next Y coordinate
 586         this->ystride = csize.X;
 587
 588         // Number of elements to skip to get to the next Z coordinate
 589         this->zstride = csize.X * csize.Y;
 590
 591         // Z-stride value for maps oversized for 1-down overgeneration
 592         this->zstride_1d = csize.X * (csize.Y + 1);
 593
 594         // Z-stride value for maps oversized for 1-up 1-down overgeneration
 595         this->zstride_1u1d = csize.X * (csize.Y + 2);
 596
 597         //// Allocate heightmap
 598         this->heightmap = new s16[csize.X * csize.Z];
 599
 600         //// Initialize biome generator
 601         // TODO(hmmmm): should we have a way to disable biomemanager biomes?
 602         biomegen = m_bmgr->createBiomeGen(BIOMEGEN_ORIGINAL, params->bparams, csize);
 603         biomemap = biomegen->biomemap;
 604
 605         //// Look up some commonly used content
 606         c_stone              = ndef->getId("mapgen_stone");
 607         c_desert_stone       = ndef->getId("mapgen_desert_stone");
 608         c_sandstone          = ndef->getId("mapgen_sandstone");
 609         c_water_source       = ndef->getId("mapgen_water_source");
 610         c_river_water_source = ndef->getId("mapgen_river_water_source");
 611         c_lava_source        = ndef->getId("mapgen_lava_source");
 612
 613         // Fall back to more basic content if not defined
 614         // river_water_source cannot fallback to water_source because river water
 615         // needs to be non-renewable and have a short flow range.
 616         if (c_desert_stone == CONTENT_IGNORE)
 617                 c_desert_stone = c_stone;
 618         if (c_sandstone == CONTENT_IGNORE)
 619                 c_sandstone = c_stone;
 620
 621         //// Content used for dungeon generation
 622         c_cobble                = ndef->getId("mapgen_cobble");
 623         c_mossycobble           = ndef->getId("mapgen_mossycobble");
 624         c_stair_cobble          = ndef->getId("mapgen_stair_cobble");
 625         c_stair_desert_stone    = ndef->getId("mapgen_stair_desert_stone");
 626         c_sandstonebrick        = ndef->getId("mapgen_sandstonebrick");
 627         c_stair_sandstone_block = ndef->getId("mapgen_stair_sandstone_block");
 628
 629         // Fall back to more basic content if not defined
 630         if (c_mossycobble == CONTENT_IGNORE)
 631                 c_mossycobble = c_cobble;
 632         if (c_stair_cobble == CONTENT_IGNORE)
 633                 c_stair_cobble = c_cobble;
 634         if (c_stair_desert_stone == CONTENT_IGNORE)
 635                 c_stair_desert_stone = c_desert_stone;
 636         if (c_sandstonebrick == CONTENT_IGNORE)
 637                 c_sandstonebrick = c_sandstone;
 638         if (c_stair_sandstone_block == CONTENT_IGNORE)
 639                 c_stair_sandstone_block = c_sandstonebrick;
 640 }
 641
 642
 643 MapgenBasic::~MapgenBasic()
 644 {
 645         delete biomegen;
 646         delete []heightmap;
 647 }
 648
 649
 650 void MapgenBasic::generateBiomes(MgStoneType *mgstone_type,
 651         content_t *biome_stone)
 652 {
 653         // can't generate biomes without a biome generator!
 654         assert(biomegen);
 655         assert(biomemap);
 656
 657         const v3s16 &em = vm->m_area.getExtent();
 658         u32 index = 0;
 659         MgStoneType stone_type = MGSTONE_OTHER;
 660         content_t c_biome_stone = c_stone;
 661
 662         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 663
 664         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 665         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 666                 Biome *biome = NULL;
 667                 u16 depth_top = 0;
 668                 u16 base_filler = 0;
 669                 u16 depth_water_top = 0;
 670                 u16 depth_riverbed = 0;
 671                 s16 biome_y_min = -MAX_MAP_GENERATION_LIMIT;
 672                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 673
 674                 // Check node at base of mapchunk above, either a node of a previously
 675                 // generated mapchunk or if not, a node of overgenerated base terrain.
 676                 content_t c_above = vm->m_data[vi + em.X].getContent();
 677                 bool air_above = c_above == CONTENT_AIR;
 678                 bool river_water_above = c_above == c_river_water_source;
 679                 bool water_above = c_above == c_water_source || river_water_above;
 680
 681                 biomemap[index] = BIOME_NONE;
 682
 683                 // If there is air or water above enable top/filler placement, otherwise force
 684                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 685                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 686
 687                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 688                         content_t c = vm->m_data[vi].getContent();
 689                         // Biome is (re)calculated:
 690                         // 1. At the surface of stone below air or water.
 691                         // 2. At the surface of water below air.
 692                         // 3. When stone or water is detected but biome has not yet been calculated.
 693                         // 4. When stone or water is detected just below a biome's lower limit.
 694                         bool is_stone_surface = (c == c_stone) &&
 695                                 (air_above || water_above || !biome || y < biome_y_min); // 1, 3, 4
 696
 697                         bool is_water_surface =
 698                                 (c == c_water_source || c == c_river_water_source) &&
 699                                 (air_above || !biome || y < biome_y_min); // 2, 3, 4
 700
 701                         if (is_stone_surface || is_water_surface) {
 702                                 // (Re)calculate biome
 703                                 biome = biomegen->getBiomeAtIndex(index, y);
 704
 705                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 706                                         biomemap[index] = biome->index;
 707
 708                                 depth_top = biome->depth_top;
 709                                 base_filler = MYMAX(depth_top +
 710                                         biome->depth_filler +
 711                                         noise_filler_depth->result[index], 0.0f);
 712                                 depth_water_top = biome->depth_water_top;
 713                                 depth_riverbed = biome->depth_riverbed;
 714                                 biome_y_min = biome->y_min;
 715
 716                                 // Detect stone type for dungeons during every biome calculation.
 717                                 // If none detected the last selected biome stone is chosen.
 718                                 if (biome->c_stone == c_stone)
 719                                         stone_type = MGSTONE_STONE;
 720                                 else if (biome->c_stone == c_desert_stone)
 721                                         stone_type = MGSTONE_DESERT_STONE;
 722                                 else if (biome->c_stone == c_sandstone)
 723                                         stone_type = MGSTONE_SANDSTONE;
 724
 725                                 c_biome_stone = biome->c_stone;
 726                         }
 727
 728                         if (c == c_stone) {
 729                                 content_t c_below = vm->m_data[vi - em.X].getContent();
 730
 731                                 // If the node below isn't solid, make this node stone, so that
 732                                 // any top/filler nodes above are structurally supported.
 733                                 // This is done by aborting the cycle of top/filler placement
 734                                 // immediately by forcing nplaced to stone level.
 735                                 if (c_below == CONTENT_AIR
 736                                                 || c_below == c_water_source
 737                                                 || c_below == c_river_water_source)
 738                                         nplaced = U16_MAX;
 739
 740                                 if (river_water_above) {
 741                                         if (nplaced < depth_riverbed) {
 742                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 743                                                 nplaced++;
 744                                         } else {
 745                                                 nplaced = U16_MAX;  // Disable top/filler placement
 746                                                 river_water_above = false;
 747                                         }
 748                                 } else if (nplaced < depth_top) {
 749                                         vm->m_data[vi] = MapNode(biome->c_top);
 750                                         nplaced++;
 751                                 } else if (nplaced < base_filler) {
 752                                         vm->m_data[vi] = MapNode(biome->c_filler);
 753                                         nplaced++;
 754                                 } else {
 755                                         vm->m_data[vi] = MapNode(biome->c_stone);
 756                                         nplaced = U16_MAX;  // Disable top/filler placement
 757                                 }
 758
 759                                 air_above = false;
 760                                 water_above = false;
 761                         } else if (c == c_water_source) {
 762                                 vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
 763                                                 ? biome->c_water_top : biome->c_water);
 764                                 nplaced = 0;  // Enable top/filler placement for next surface
 765                                 air_above = false;
 766                                 water_above = true;
 767                         } else if (c == c_river_water_source) {
 768                                 vm->m_data[vi] = MapNode(biome->c_river_water);
 769                                 nplaced = 0;  // Enable riverbed placement for next surface
 770                                 air_above = false;
 771                                 water_above = true;
 772                                 river_water_above = true;
 773                         } else if (c == CONTENT_AIR) {
 774                                 nplaced = 0;  // Enable top/filler placement for next surface
 775                                 air_above = true;
 776                                 water_above = false;
 777                         } else {  // Possible various nodes overgenerated from neighbouring mapchunks
 778                                 nplaced = U16_MAX;  // Disable top/filler placement
 779                                 air_above = false;
 780                                 water_above = false;
 781                         }
 782
 783                         vm->m_area.add_y(em, vi, -1);
 784                 }
 785         }
 786
 787         *mgstone_type = stone_type;
 788         *biome_stone = c_biome_stone;
 789 }
 790
 791
 792 void MapgenBasic::dustTopNodes()
 793 {
 794         if (node_max.Y < water_level)
 795                 return;
 796
 797         const v3s16 &em = vm->m_area.getExtent();
 798         u32 index = 0;
 799
 800         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 801         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 802                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 803
 804                 if (biome->c_dust == CONTENT_IGNORE)
 805                         continue;
 806
 807                 u32 vi = vm->m_area.index(x, full_node_max.Y, z);
 808                 content_t c_full_max = vm->m_data[vi].getContent();
 809                 s16 y_start;
 810
 811                 if (c_full_max == CONTENT_AIR) {
 812                         y_start = full_node_max.Y - 1;
 813                 } else if (c_full_max == CONTENT_IGNORE) {
 814                         vi = vm->m_area.index(x, node_max.Y + 1, z);
 815                         content_t c_max = vm->m_data[vi].getContent();
 816
 817                         if (c_max == CONTENT_AIR)
 818                                 y_start = node_max.Y;
 819                         else
 820                                 continue;
 821                 } else {
 822                         continue;
 823                 }
 824
 825                 vi = vm->m_area.index(x, y_start, z);
 826                 for (s16 y = y_start; y >= node_min.Y - 1; y--) {
 827                         if (vm->m_data[vi].getContent() != CONTENT_AIR)
 828                                 break;
 829
 830                         vm->m_area.add_y(em, vi, -1);
 831                 }
 832
 833                 content_t c = vm->m_data[vi].getContent();
 834                 if (!ndef->get(c).buildable_to && c != CONTENT_IGNORE && c != biome->c_dust) {
 835                         vm->m_area.add_y(em, vi, 1);
 836                         vm->m_data[vi] = MapNode(biome->c_dust);
 837                 }
 838         }
 839 }
 840
 841
 842 void MapgenBasic::generateCaves(s16 max_stone_y, s16 large_cave_depth)
 843 {
 844         if (max_stone_y < node_min.Y)
 845                 return;
 846
 847         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 848                 &np_cave1, &np_cave2, seed, cave_width);
 849
 850         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 851
 852         if (node_max.Y > large_cave_depth)
 853                 return;
 854
 855         PseudoRandom ps(blockseed + 21343);
 856         u32 bruises_count = ps.range(0, 2);
 857         for (u32 i = 0; i < bruises_count; i++) {
 858                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 859                         c_water_source, CONTENT_IGNORE, lava_depth);
 860
 861                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y, heightmap);
 862         }
 863 }
 864
 865
 866 bool MapgenBasic::generateCaverns(s16 max_stone_y)
 867 {
 868         if (node_min.Y > max_stone_y || node_min.Y > cavern_limit)
 869                 return false;
 870
 871         CavernsNoise caverns_noise(ndef, csize, &np_cavern,
 872                 seed, cavern_limit, cavern_taper, cavern_threshold);
 873
 874         return caverns_noise.generateCaverns(vm, node_min, node_max);
 875 }
 876
 877
 878 void MapgenBasic::generateDungeons(s16 max_stone_y,
 879         MgStoneType stone_type, content_t biome_stone)
 880 {
 881         if (max_stone_y < node_min.Y)
 882                 return;
 883
 884         DungeonParams dp;
 885
 886         dp.seed             = seed;
 887         dp.c_water          = c_water_source;
 888         dp.c_river_water    = c_river_water_source;
 889
 890         dp.only_in_ground   = true;
 891         dp.corridor_len_min = 1;
 892         dp.corridor_len_max = 13;
 893         dp.rooms_min        = 2;
 894         dp.rooms_max        = 16;
 895         dp.y_min            = -MAX_MAP_GENERATION_LIMIT;
 896         dp.y_max            = MAX_MAP_GENERATION_LIMIT;
 897
 898         dp.np_density       = nparams_dungeon_density;
 899         dp.np_alt_wall      = nparams_dungeon_alt_wall;
 900
 901         switch (stone_type) {
 902         default:
 903         case MGSTONE_STONE:
 904                 dp.c_wall              = c_cobble;
 905                 dp.c_alt_wall          = c_mossycobble;
 906                 dp.c_stair             = c_stair_cobble;
 907
 908                 dp.diagonal_dirs       = false;
 909                 dp.holesize            = v3s16(1, 2, 1);
 910                 dp.room_size_min       = v3s16(4, 4, 4);
 911                 dp.room_size_max       = v3s16(8, 6, 8);
 912                 dp.room_size_large_min = v3s16(8, 8, 8);
 913                 dp.room_size_large_max = v3s16(16, 16, 16);
 914                 dp.notifytype          = GENNOTIFY_DUNGEON;
 915                 break;
 916         case MGSTONE_DESERT_STONE:
 917                 dp.c_wall              = c_desert_stone;
 918                 dp.c_alt_wall          = CONTENT_IGNORE;
 919                 dp.c_stair             = c_stair_desert_stone;
 920
 921                 dp.diagonal_dirs       = true;
 922                 dp.holesize            = v3s16(2, 3, 2);
 923                 dp.room_size_min       = v3s16(6, 9, 6);
 924                 dp.room_size_max       = v3s16(10, 11, 10);
 925                 dp.room_size_large_min = v3s16(10, 13, 10);
 926                 dp.room_size_large_max = v3s16(18, 21, 18);
 927                 dp.notifytype          = GENNOTIFY_TEMPLE;
 928                 break;
 929         case MGSTONE_SANDSTONE:
 930                 dp.c_wall              = c_sandstonebrick;
 931                 dp.c_alt_wall          = CONTENT_IGNORE;
 932                 dp.c_stair             = c_stair_sandstone_block;
 933
 934                 dp.diagonal_dirs       = false;
 935                 dp.holesize            = v3s16(2, 2, 2);
 936                 dp.room_size_min       = v3s16(6, 4, 6);
 937                 dp.room_size_max       = v3s16(10, 6, 10);
 938                 dp.room_size_large_min = v3s16(10, 8, 10);
 939                 dp.room_size_large_max = v3s16(18, 16, 18);
 940                 dp.notifytype          = GENNOTIFY_DUNGEON;
 941                 break;
 942         case MGSTONE_OTHER:
 943                 dp.c_wall              = biome_stone;
 944                 dp.c_alt_wall          = biome_stone;
 945                 dp.c_stair             = biome_stone;
 946
 947                 dp.diagonal_dirs       = false;
 948                 dp.holesize            = v3s16(1, 2, 1);
 949                 dp.room_size_min       = v3s16(4, 4, 4);
 950                 dp.room_size_max       = v3s16(8, 6, 8);
 951                 dp.room_size_large_min = v3s16(8, 8, 8);
 952                 dp.room_size_large_max = v3s16(16, 16, 16);
 953                 dp.notifytype          = GENNOTIFY_DUNGEON;
 954                 break;
 955         }
 956
 957         DungeonGen dgen(ndef, &gennotify, &dp);
 958         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 959 }
 960
 961
 962 ////
 963 //// GenerateNotifier
 964 ////
 965
 966 GenerateNotifier::GenerateNotifier(u32 notify_on,
 967         std::set<u32> *notify_on_deco_ids)
 968 {
 969         m_notify_on = notify_on;
 970         m_notify_on_deco_ids = notify_on_deco_ids;
 971 }
 972
 973
 974 void GenerateNotifier::setNotifyOn(u32 notify_on)
 975 {
 976         m_notify_on = notify_on;
 977 }
 978
 979
 980 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
 981 {
 982         m_notify_on_deco_ids = notify_on_deco_ids;
 983 }
 984
 985
 986 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
 987 {
 988         if (!(m_notify_on & (1 << type)))
 989                 return false;
 990
 991         if (type == GENNOTIFY_DECORATION &&
 992                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
 993                 return false;
 994
 995         GenNotifyEvent gne;
 996         gne.type = type;
 997         gne.pos  = pos;
 998         gne.id   = id;
 999         m_notify_events.push_back(gne);
1000
1001         return true;
1002 }
1003
1004
1005 void GenerateNotifier::getEvents(
1006         std::map<std::string, std::vector<v3s16> > &event_map,
1007         bool peek_events)
1008 {
1009         std::list<GenNotifyEvent>::iterator it;
1010
1011         for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
1012                 GenNotifyEvent &gn = *it;
1013                 std::string name = (gn.type == GENNOTIFY_DECORATION) ?
1014                         "decoration#"+ itos(gn.id) :
1015                         flagdesc_gennotify[gn.type].name;
1016
1017                 event_map[name].push_back(gn.pos);
1018         }
1019
1020         if (!peek_events)
1021                 m_notify_events.clear();
1022 }
1023
1024
1025 ////
1026 //// MapgenParams
1027 ////
1028
1029
1030 MapgenParams::~MapgenParams()
1031 {
1032         delete bparams;
1033 }
1034
1035
1036 void MapgenParams::readParams(const Settings *settings)
1037 {
1038         std::string seed_str;
1039         const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";
1040
1041         if (settings->getNoEx(seed_name, seed_str)) {
1042                 if (!seed_str.empty())
1043                         seed = read_seed(seed_str.c_str());
1044                 else
1045                         myrand_bytes(&seed, sizeof(seed));
1046         }
1047
1048         std::string mg_name;
1049         if (settings->getNoEx("mg_name", mg_name)) {
1050                 mgtype = Mapgen::getMapgenType(mg_name);
1051                 if (mgtype == MAPGEN_INVALID)
1052                         mgtype = MAPGEN_DEFAULT;
1053         }
1054
1055         settings->getS16NoEx("water_level", water_level);
1056         settings->getS16NoEx("mapgen_limit", mapgen_limit);
1057         settings->getS16NoEx("chunksize", chunksize);
1058         settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
1059
1060         delete bparams;
1061         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
1062         if (bparams) {
1063                 bparams->readParams(settings);
1064                 bparams->seed = seed;
1065         }
1066 }
1067
1068
1069 void MapgenParams::writeParams(Settings *settings) const
1070 {
1071         settings->set("mg_name", Mapgen::getMapgenName(mgtype));
1072         settings->setU64("seed", seed);
1073         settings->setS16("water_level", water_level);
1074         settings->setS16("mapgen_limit", mapgen_limit);
1075         settings->setS16("chunksize", chunksize);
1076         settings->setFlagStr("mg_flags", flags, flagdesc_mapgen, U32_MAX);
1077
1078         if (bparams)
1079                 bparams->writeParams(settings);
1080 }
1081
1082 // Calculate edges of outermost generated mapchunks (less than
1083 // 'mapgen_limit'), and corresponding exact limits for SAO entities.
1084 void MapgenParams::calcMapgenEdges()
1085 {
1086         if (m_mapgen_edges_calculated)
1087                 return;
1088
1089         // Central chunk offset, in blocks
1090         s16 ccoff_b = -chunksize / 2;
1091         // Chunksize, in nodes
1092         s32 csize_n = chunksize * MAP_BLOCKSIZE;
1093         // Minp/maxp of central chunk, in nodes
1094         s16 ccmin = ccoff_b * MAP_BLOCKSIZE;
1095         s16 ccmax = ccmin + csize_n - 1;
1096         // Fullminp/fullmaxp of central chunk, in nodes
1097         s16 ccfmin = ccmin - MAP_BLOCKSIZE;
1098         s16 ccfmax = ccmax + MAP_BLOCKSIZE;
1099         // Effective mapgen limit, in blocks
1100         // Uses same calculation as ServerMap::blockpos_over_mapgen_limit(v3s16 p)
1101         s16 mapgen_limit_b = rangelim(mapgen_limit,
1102                 0, MAX_MAP_GENERATION_LIMIT) / MAP_BLOCKSIZE;
1103         // Effective mapgen limits, in nodes
1104         s16 mapgen_limit_min = -mapgen_limit_b * MAP_BLOCKSIZE;
1105         s16 mapgen_limit_max = (mapgen_limit_b + 1) * MAP_BLOCKSIZE - 1;
1106         // Number of complete chunks from central chunk fullminp/fullmaxp
1107         // to effective mapgen limits.
1108         s16 numcmin = MYMAX((ccfmin - mapgen_limit_min) / csize_n, 0);
1109         s16 numcmax = MYMAX((mapgen_limit_max - ccfmax) / csize_n, 0);
1110         // Mapgen edges, in nodes
1111         mapgen_edge_min = ccmin - numcmin * csize_n;
1112         mapgen_edge_max = ccmax + numcmax * csize_n;
1113         // SAO position limits, in Irrlicht units
1114         m_sao_limit_min = mapgen_edge_min * BS - 3.0f;
1115         m_sao_limit_max = mapgen_edge_max * BS + 3.0f;
1116
1117         m_mapgen_edges_calculated = true;
1118 }
1119
1120
1121 bool MapgenParams::saoPosOverLimit(const v3f &p)
1122 {
1123         if (!m_mapgen_edges_calculated)
1124                 calcMapgenEdges();
1125
1126         return p.X < m_sao_limit_min ||
1127                 p.X > m_sao_limit_max ||
1128                 p.Y < m_sao_limit_min ||
1129                 p.Y > m_sao_limit_max ||
1130                 p.Z < m_sao_limit_min ||
1131                 p.Z > m_sao_limit_max;
1132 }
1133
1134
1135 s32 MapgenParams::getSpawnRangeMax()
1136 {
1137         calcMapgenEdges();
1138
1139         return MYMIN(-mapgen_edge_min, mapgen_edge_max);
1140 }