src/mapgen/mapgen.cpp

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