src/mapgen.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010-2011 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "mapgen.h"
  21 #include "voxel.h"
  22 #include "noise.h"
  23 #include "biome.h"
  24 #include "mapblock.h"
  25 #include "mapnode.h"
  26 #include "map.h"
  27 //#include "serverobject.h"
  28 #include "content_sao.h"
  29 #include "nodedef.h"
  30 #include "content_mapnode.h" // For content_mapnode_get_new_name
  31 #include "voxelalgorithms.h"
  32 #include "profiler.h"
  33 #include "settings.h" // For g_settings
  34 #include "main.h" // For g_profiler
  35 #include "treegen.h"
  36
  37 /////////////////// Mapgen V6 perlin noise default values
  38 NoiseParams nparams_v6_def_terrain_base =
  39         {-AVERAGE_MUD_AMOUNT, 20.0, v3f(250.0, 250.0, 250.0), 82341, 5, 0.6};
  40 NoiseParams nparams_v6_def_terrain_higher =
  41         {20.0, 16.0, v3f(500.0, 500.0, 500.0), 85039, 5, 0.6};
  42 NoiseParams nparams_v6_def_steepness =
  43         {0.85, 0.5, v3f(125.0, 125.0, 125.0), -932, 5, 0.7};
  44 NoiseParams nparams_v6_def_height_select =
  45         {0.5, 1.0, v3f(250.0, 250.0, 250.0), 4213, 5, 0.69};
  46 NoiseParams nparams_v6_def_trees =
  47         {0.0, 1.0, v3f(125.0, 125.0, 125.0), 2, 4, 0.66};
  48 NoiseParams nparams_v6_def_mud =
  49         {AVERAGE_MUD_AMOUNT, 2.0, v3f(200.0, 200.0, 200.0), 91013, 3, 0.55};
  50 NoiseParams nparams_v6_def_beach =
  51         {0.0, 1.0, v3f(250.0, 250.0, 250.0), 59420, 3, 0.50};
  52 NoiseParams nparams_v6_def_biome =
  53         {0.0, 1.0, v3f(250.0, 250.0, 250.0), 9130, 3, 0.50};
  54 NoiseParams nparams_v6_def_cave =
  55         {6.0, 6.0, v3f(250.0, 250.0, 250.0), 34329, 3, 0.50};
  56
  57
  58 ///////////////////////////////////////////////////////////////////////////////
  59 /////////////////////////////// Emerge Manager ////////////////////////////////
  60
  61
  62
  63 EmergeManager::EmergeManager(IGameDef *gamedef, BiomeDefManager *bdef,
  64                                                          MapgenParams *mgparams) {
  65         //the order of these assignments is pretty important
  66         this->biomedef = bdef ? bdef : new BiomeDefManager(gamedef);
  67         this->params   = mgparams;
  68         this->mapgen   = NULL;
  69         this->mapgen   = getMapgen();
  70 }
  71
  72
  73 EmergeManager::~EmergeManager() {
  74         delete biomedef;
  75         delete params;
  76 }
  77
  78
  79 Mapgen *EmergeManager::getMapgen() {
  80         if (!mapgen) {
  81                 switch (params->mg_version) {
  82                         case 6:
  83                                 mapgen = new MapgenV6(0, (MapgenV6Params *)params);
  84                                 break;
  85                         default:
  86                                 errorstream << "EmergeManager: Unsupported mapgen version "
  87                                         << params->mg_version << ", falling back to V6" << std::endl;
  88                                 params->mg_version = 6;
  89                                 mapgen = new MapgenV6(0, (MapgenV6Params *)params);
  90                 }
  91         }
  92         return mapgen;
  93 }
  94
  95
  96 void EmergeManager::addBlockToQueue() {
  97         //STUB
  98 }
  99
 100
 101 int EmergeManager::getGroundLevelAtPoint(v2s16 p) {
 102         if (!mapgen)
 103                 return 0;
 104         return mapgen->getGroundLevelAtPoint(p);
 105 }
 106
 107
 108 bool EmergeManager::isBlockUnderground(v3s16 blockpos) {
 109         /*
 110         v2s16 p = v2s16((blockpos.X * MAP_BLOCKSIZE) + MAP_BLOCKSIZE / 2,
 111                                         (blockpos.Y * MAP_BLOCKSIZE) + MAP_BLOCKSIZE / 2);
 112         int ground_level = getGroundLevelAtPoint(p);
 113         return blockpos.Y * (MAP_BLOCKSIZE + 1) <= min(water_level, ground_level);
 114         */
 115
 116         //yuck, but then again, should i bother being accurate?
 117         //the height of the nodes in a single block is quite variable
 118         return blockpos.Y * (MAP_BLOCKSIZE + 1) <= params->water_level;
 119 }
 120
 121
 122 u32 EmergeManager::getBlockSeed(v3s16 p) {
 123         return (u32)(params->seed & 0xFFFFFFFF) +
 124                 p.Z * 38134234 +
 125                 p.Y * 42123 +
 126                 p.Y * 23;
 127 }
 128
 129
 130 MapgenParams *MapgenParams::createMapgenParams(int mgver) {
 131         switch (mgver) {
 132                 case 6:
 133                         return new MapgenV6Params();
 134                 default: //instead of complaining, default to 6
 135                         return new MapgenV6Params();
 136         }
 137 }
 138
 139
 140 MapgenParams *MapgenParams::getParamsFromSettings(Settings *settings) {
 141         int mg_version = settings->getS16("mg_version");
 142         MapgenParams *mgparams = MapgenParams::createMapgenParams(mg_version);
 143         mgparams->mg_version  = mg_version;
 144         mgparams->seed        = settings->getU64(settings == g_settings ? "fixed_map_seed" : "seed");
 145         mgparams->water_level = settings->getS16("water_level");
 146         mgparams->chunksize   = settings->getS16("chunksize");
 147         mgparams->flags       = settings->getS32("mg_flags");
 148
 149         switch (mg_version) {
 150                 case 6:
 151                 {
 152                         MapgenV6Params *v6params = (MapgenV6Params *)mgparams;
 153
 154                         v6params->freq_desert = settings->getFloat("mgv6_freq_desert");
 155                         v6params->freq_beach  = settings->getFloat("mgv6_freq_beach");
 156                         v6params->np_terrain_base   = settings->getNoiseParams("mgv6_np_terrain_base");
 157                         v6params->np_terrain_higher = settings->getNoiseParams("mgv6_np_terrain_higher");
 158                         v6params->np_steepness      = settings->getNoiseParams("mgv6_np_steepness");
 159                         v6params->np_height_select  = settings->getNoiseParams("mgv6_np_height_select");
 160                         v6params->np_trees          = settings->getNoiseParams("mgv6_np_trees");
 161                         v6params->np_mud            = settings->getNoiseParams("mgv6_np_mud");
 162                         v6params->np_beach          = settings->getNoiseParams("mgv6_np_beach");
 163                         v6params->np_biome          = settings->getNoiseParams("mgv6_np_biome");
 164                         v6params->np_cave           = settings->getNoiseParams("mgv6_np_cave");
 165
 166                         if (!v6params->np_terrain_base || !v6params->np_terrain_higher ||
 167                                 !v6params->np_steepness    || !v6params->np_height_select  ||
 168                                 !v6params->np_trees        || !v6params->np_mud            ||
 169                                 !v6params->np_beach || !v6params->np_biome || !v6params->np_cave) {
 170                                 delete mgparams;
 171                                 return NULL;
 172                         }
 173
 174                         break;
 175                 }
 176                 default:
 177                         delete mgparams;
 178                         return NULL;
 179         }
 180
 181         return mgparams;
 182
 183 }
 184
 185
 186 /////////////////////////////////// legacy static functions for farmesh
 187
 188
 189 s16 Mapgen::find_ground_level_from_noise(u64 seed, v2s16 p2d, s16 precision) {
 190         //just need to return something
 191         s16 level = 5;
 192         return level;
 193 }
 194
 195
 196 bool Mapgen::get_have_beach(u64 seed, v2s16 p2d) {
 197         double sandnoise = noise2d_perlin(
 198                         0.2+(float)p2d.X/250, 0.7+(float)p2d.Y/250,
 199                         seed+59420, 3, 0.50);
 200
 201         return (sandnoise > 0.15);
 202 }
 203
 204
 205 double Mapgen::tree_amount_2d(u64 seed, v2s16 p) {
 206         double noise = noise2d_perlin(
 207                         0.5+(float)p.X/125, 0.5+(float)p.Y/125,
 208                         seed+2, 4, 0.66);
 209         double zeroval = -0.39;
 210         if(noise < zeroval)
 211                 return 0;
 212         else
 213                 return 0.04 * (noise-zeroval) / (1.0-zeroval);
 214 }
 215
 216
 217 #if 0 /// BIG COMMENT
 218 namespace mapgen
 219 {
 220
 221 /*
 222         Some helper functions for the map generator
 223 */
 224
 225 #if 1
 226 // Returns Y one under area minimum if not found
 227 static s16 find_ground_level(VoxelManipulator &vmanip, v2s16 p2d,
 228                 INodeDefManager *ndef)
 229 {
 230         v3s16 em = vmanip.m_area.getExtent();
 231         s16 y_nodes_max = vmanip.m_area.MaxEdge.Y;
 232         s16 y_nodes_min = vmanip.m_area.MinEdge.Y;
 233         u32 i = vmanip.m_area.index(v3s16(p2d.X, y_nodes_max, p2d.Y));
 234         s16 y;
 235         for(y=y_nodes_max; y>=y_nodes_min; y--)
 236         {
 237                 MapNode &n = vmanip.m_data[i];
 238                 if(ndef->get(n).walkable)
 239                         break;
 240
 241                 vmanip.m_area.add_y(em, i, -1);
 242         }
 243         if(y >= y_nodes_min)
 244                 return y;
 245         else
 246                 return y_nodes_min - 1;
 247 }
 248
 249 #if 0
 250 // Returns Y one under area minimum if not found
 251 static s16 find_ground_level_clever(VoxelManipulator &vmanip, v2s16 p2d,
 252                 INodeDefManager *ndef)
 253 {
 254         if(!vmanip.m_area.contains(v3s16(p2d.X, vmanip.m_area.MaxEdge.Y, p2d.Y)))
 255                 return vmanip.m_area.MinEdge.Y-1;
 256         v3s16 em = vmanip.m_area.getExtent();
 257         s16 y_nodes_max = vmanip.m_area.MaxEdge.Y;
 258         s16 y_nodes_min = vmanip.m_area.MinEdge.Y;
 259         u32 i = vmanip.m_area.index(v3s16(p2d.X, y_nodes_max, p2d.Y));
 260         s16 y;
 261         content_t c_tree = ndef->getId("mapgen_tree");
 262         content_t c_leaves = ndef->getId("mapgen_leaves");
 263         for(y=y_nodes_max; y>=y_nodes_min; y--)
 264         {
 265                 MapNode &n = vmanip.m_data[i];
 266                 if(ndef->get(n).walkable
 267                                 && n.getContent() != c_tree
 268                                 && n.getContent() != c_leaves)
 269                         break;
 270
 271                 vmanip.m_area.add_y(em, i, -1);
 272         }
 273         if(y >= y_nodes_min)
 274                 return y;
 275         else
 276                 return y_nodes_min - 1;
 277 }
 278 #endif
 279
 280 // Returns Y one under area minimum if not found
 281 static s16 find_stone_level(VoxelManipulator &vmanip, v2s16 p2d,
 282                 INodeDefManager *ndef)
 283 {
 284         v3s16 em = vmanip.m_area.getExtent();
 285         s16 y_nodes_max = vmanip.m_area.MaxEdge.Y;
 286         s16 y_nodes_min = vmanip.m_area.MinEdge.Y;
 287         u32 i = vmanip.m_area.index(v3s16(p2d.X, y_nodes_max, p2d.Y));
 288         s16 y;
 289         content_t c_stone = ndef->getId("mapgen_stone");
 290         content_t c_desert_stone = ndef->getId("mapgen_desert_stone");
 291         for(y=y_nodes_max; y>=y_nodes_min; y--)
 292         {
 293                 MapNode &n = vmanip.m_data[i];
 294                 content_t c = n.getContent();
 295                 if(c != CONTENT_IGNORE && (
 296                                 c == c_stone || c == c_desert_stone))
 297                         break;
 298
 299                 vmanip.m_area.add_y(em, i, -1);
 300         }
 301         if(y >= y_nodes_min)
 302                 return y;
 303         else
 304                 return y_nodes_min - 1;
 305 }
 306 #endif
 307
 308
 309 #if 0
 310
 311 static void make_papyrus(VoxelManipulator &vmanip, v3s16 p0,
 312                 INodeDefManager *ndef)
 313 {
 314         MapNode papyrusnode(ndef->getId("mapgen_papyrus"));
 315
 316         s16 trunk_h = myrand_range(2, 3);
 317         v3s16 p1 = p0;
 318         for(s16 ii=0; ii<trunk_h; ii++)
 319         {
 320                 if(vmanip.m_area.contains(p1))
 321                         vmanip.m_data[vmanip.m_area.index(p1)] = papyrusnode;
 322                 p1.Y++;
 323         }
 324 }
 325
 326 static void make_cactus(VoxelManipulator &vmanip, v3s16 p0,
 327                 INodeDefManager *ndef)
 328 {
 329         MapNode cactusnode(ndef->getId("mapgen_cactus"));
 330
 331         s16 trunk_h = 3;
 332         v3s16 p1 = p0;
 333         for(s16 ii=0; ii<trunk_h; ii++)
 334         {
 335                 if(vmanip.m_area.contains(p1))
 336                         vmanip.m_data[vmanip.m_area.index(p1)] = cactusnode;
 337                 p1.Y++;
 338         }
 339 }
 340 #endif
 341
 342 #if 0
 343 /*
 344         Dungeon making routines
 345 */
 346
 347 #define VMANIP_FLAG_DUNGEON_INSIDE VOXELFLAG_CHECKED1
 348 #define VMANIP_FLAG_DUNGEON_PRESERVE VOXELFLAG_CHECKED2
 349 #define VMANIP_FLAG_DUNGEON_UNTOUCHABLE (\
 350                 VMANIP_FLAG_DUNGEON_INSIDE|VMANIP_FLAG_DUNGEON_PRESERVE)
 351
 352 static void make_room1(VoxelManipulator &vmanip, v3s16 roomsize, v3s16 roomplace,
 353                 INodeDefManager *ndef)
 354 {
 355         // Make +-X walls
 356         for(s16 z=0; z<roomsize.Z; z++)
 357         for(s16 y=0; y<roomsize.Y; y++)
 358         {
 359                 {
 360                         v3s16 p = roomplace + v3s16(0,y,z);
 361                         if(vmanip.m_area.contains(p) == false)
 362                                 continue;
 363                         u32 vi = vmanip.m_area.index(p);
 364                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 365                                 continue;
 366                         vmanip.m_data[vi] = MapNode(ndef->getId("mapgen_cobble"));
 367                 }
 368                 {
 369                         v3s16 p = roomplace + v3s16(roomsize.X-1,y,z);
 370                         if(vmanip.m_area.contains(p) == false)
 371                                 continue;
 372                         u32 vi = vmanip.m_area.index(p);
 373                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 374                                 continue;
 375                         vmanip.m_data[vi] = MapNode(ndef->getId("mapgen_cobble"));
 376                 }
 377         }
 378
 379         // Make +-Z walls
 380         for(s16 x=0; x<roomsize.X; x++)
 381         for(s16 y=0; y<roomsize.Y; y++)
 382         {
 383                 {
 384                         v3s16 p = roomplace + v3s16(x,y,0);
 385                         if(vmanip.m_area.contains(p) == false)
 386                                 continue;
 387                         u32 vi = vmanip.m_area.index(p);
 388                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 389                                 continue;
 390                         vmanip.m_data[vi] = MapNode(ndef->getId("mapgen_cobble"));
 391                 }
 392                 {
 393                         v3s16 p = roomplace + v3s16(x,y,roomsize.Z-1);
 394                         if(vmanip.m_area.contains(p) == false)
 395                                 continue;
 396                         u32 vi = vmanip.m_area.index(p);
 397                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 398                                 continue;
 399                         vmanip.m_data[vi] = MapNode(ndef->getId("mapgen_cobble"));
 400                 }
 401         }
 402
 403         // Make +-Y walls (floor and ceiling)
 404         for(s16 z=0; z<roomsize.Z; z++)
 405         for(s16 x=0; x<roomsize.X; x++)
 406         {
 407                 {
 408                         v3s16 p = roomplace + v3s16(x,0,z);
 409                         if(vmanip.m_area.contains(p) == false)
 410                                 continue;
 411                         u32 vi = vmanip.m_area.index(p);
 412                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 413                                 continue;
 414                         vmanip.m_data[vi] = MapNode(ndef->getId("mapgen_cobble"));
 415                 }
 416                 {
 417                         v3s16 p = roomplace + v3s16(x,roomsize.Y-1,z);
 418                         if(vmanip.m_area.contains(p) == false)
 419                                 continue;
 420                         u32 vi = vmanip.m_area.index(p);
 421                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 422                                 continue;
 423                         vmanip.m_data[vi] = MapNode(ndef->getId("mapgen_cobble"));
 424                 }
 425         }
 426
 427         // Fill with air
 428         for(s16 z=1; z<roomsize.Z-1; z++)
 429         for(s16 y=1; y<roomsize.Y-1; y++)
 430         for(s16 x=1; x<roomsize.X-1; x++)
 431         {
 432                 v3s16 p = roomplace + v3s16(x,y,z);
 433                 if(vmanip.m_area.contains(p) == false)
 434                         continue;
 435                 u32 vi = vmanip.m_area.index(p);
 436                 vmanip.m_flags[vi] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE;
 437                 vmanip.m_data[vi] = MapNode(CONTENT_AIR);
 438         }
 439 }
 440
 441 static void make_fill(VoxelManipulator &vmanip, v3s16 place, v3s16 size,
 442                 u8 avoid_flags, MapNode n, u8 or_flags)
 443 {
 444         for(s16 z=0; z<size.Z; z++)
 445         for(s16 y=0; y<size.Y; y++)
 446         for(s16 x=0; x<size.X; x++)
 447         {
 448                 v3s16 p = place + v3s16(x,y,z);
 449                 if(vmanip.m_area.contains(p) == false)
 450                         continue;
 451                 u32 vi = vmanip.m_area.index(p);
 452                 if(vmanip.m_flags[vi] & avoid_flags)
 453                         continue;
 454                 vmanip.m_flags[vi] |= or_flags;
 455                 vmanip.m_data[vi] = n;
 456         }
 457 }
 458
 459 static void make_hole1(VoxelManipulator &vmanip, v3s16 place,
 460                 INodeDefManager *ndef)
 461 {
 462         make_fill(vmanip, place, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 463                         VMANIP_FLAG_DUNGEON_INSIDE);
 464 }
 465
 466 static void make_door1(VoxelManipulator &vmanip, v3s16 doorplace, v3s16 doordir,
 467                 INodeDefManager *ndef)
 468 {
 469         make_hole1(vmanip, doorplace, ndef);
 470         // Place torch (for testing)
 471         //vmanip.m_data[vmanip.m_area.index(doorplace)] = MapNode(ndef->getId("mapgen_torch"));
 472 }
 473
 474 static v3s16 rand_ortho_dir(PseudoRandom &random)
 475 {
 476         if(random.next()%2==0)
 477                 return random.next()%2 ? v3s16(-1,0,0) : v3s16(1,0,0);
 478         else
 479                 return random.next()%2 ? v3s16(0,0,-1) : v3s16(0,0,1);
 480 }
 481
 482 static v3s16 turn_xz(v3s16 olddir, int t)
 483 {
 484         v3s16 dir;
 485         if(t == 0)
 486         {
 487                 // Turn right
 488                 dir.X = olddir.Z;
 489                 dir.Z = -olddir.X;
 490                 dir.Y = olddir.Y;
 491         }
 492         else
 493         {
 494                 // Turn left
 495                 dir.X = -olddir.Z;
 496                 dir.Z = olddir.X;
 497                 dir.Y = olddir.Y;
 498         }
 499         return dir;
 500 }
 501
 502 static v3s16 random_turn(PseudoRandom &random, v3s16 olddir)
 503 {
 504         int turn = random.range(0,2);
 505         v3s16 dir;
 506         if(turn == 0)
 507         {
 508                 // Go straight
 509                 dir = olddir;
 510         }
 511         else if(turn == 1)
 512                 // Turn right
 513                 dir = turn_xz(olddir, 0);
 514         else
 515                 // Turn left
 516                 dir = turn_xz(olddir, 1);
 517         return dir;
 518 }
 519
 520 static void make_corridor(VoxelManipulator &vmanip, v3s16 doorplace,
 521                 v3s16 doordir, v3s16 &result_place, v3s16 &result_dir,
 522                 PseudoRandom &random, INodeDefManager *ndef)
 523 {
 524         make_hole1(vmanip, doorplace, ndef);
 525         v3s16 p0 = doorplace;
 526         v3s16 dir = doordir;
 527         u32 length;
 528         if(random.next()%2)
 529                 length = random.range(1,13);
 530         else
 531                 length = random.range(1,6);
 532         length = random.range(1,13);
 533         u32 partlength = random.range(1,13);
 534         u32 partcount = 0;
 535         s16 make_stairs = 0;
 536         if(random.next()%2 == 0 && partlength >= 3)
 537                 make_stairs = random.next()%2 ? 1 : -1;
 538         for(u32 i=0; i<length; i++)
 539         {
 540                 v3s16 p = p0 + dir;
 541                 if(partcount != 0)
 542                         p.Y += make_stairs;
 543
 544                 /*// If already empty
 545                 if(vmanip.getNodeNoExNoEmerge(p).getContent()
 546                                 == CONTENT_AIR
 547                 && vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 548                                 == CONTENT_AIR)
 549                 {
 550                 }*/
 551
 552                 if(vmanip.m_area.contains(p) == true
 553                                 && vmanip.m_area.contains(p+v3s16(0,1,0)) == true)
 554                 {
 555                         if(make_stairs)
 556                         {
 557                                 make_fill(vmanip, p+v3s16(-1,-1,-1), v3s16(3,5,3),
 558                                                 VMANIP_FLAG_DUNGEON_UNTOUCHABLE, MapNode(ndef->getId("mapgen_cobble")), 0);
 559                                 make_fill(vmanip, p, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 560                                                 VMANIP_FLAG_DUNGEON_INSIDE);
 561                                 make_fill(vmanip, p-dir, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 562                                                 VMANIP_FLAG_DUNGEON_INSIDE);
 563                         }
 564                         else
 565                         {
 566                                 make_fill(vmanip, p+v3s16(-1,-1,-1), v3s16(3,4,3),
 567                                                 VMANIP_FLAG_DUNGEON_UNTOUCHABLE, MapNode(ndef->getId("mapgen_cobble")), 0);
 568                                 make_hole1(vmanip, p, ndef);
 569                                 /*make_fill(vmanip, p, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 570                                                 VMANIP_FLAG_DUNGEON_INSIDE);*/
 571                         }
 572
 573                         p0 = p;
 574                 }
 575                 else
 576                 {
 577                         // Can't go here, turn away
 578                         dir = turn_xz(dir, random.range(0,1));
 579                         make_stairs = -make_stairs;
 580                         partcount = 0;
 581                         partlength = random.range(1,length);
 582                         continue;
 583                 }
 584
 585                 partcount++;
 586                 if(partcount >= partlength)
 587                 {
 588                         partcount = 0;
 589
 590                         dir = random_turn(random, dir);
 591
 592                         partlength = random.range(1,length);
 593
 594                         make_stairs = 0;
 595                         if(random.next()%2 == 0 && partlength >= 3)
 596                                 make_stairs = random.next()%2 ? 1 : -1;
 597                 }
 598         }
 599         result_place = p0;
 600         result_dir = dir;
 601 }
 602
 603 class RoomWalker
 604 {
 605 public:
 606
 607         RoomWalker(VoxelManipulator &vmanip_, v3s16 pos, PseudoRandom &random,
 608                         INodeDefManager *ndef):
 609                         vmanip(vmanip_),
 610                         m_pos(pos),
 611                         m_random(random),
 612                         m_ndef(ndef)
 613         {
 614                 randomizeDir();
 615         }
 616
 617         void randomizeDir()
 618         {
 619                 m_dir = rand_ortho_dir(m_random);
 620         }
 621
 622         void setPos(v3s16 pos)
 623         {
 624                 m_pos = pos;
 625         }
 626
 627         void setDir(v3s16 dir)
 628         {
 629                 m_dir = dir;
 630         }
 631
 632         bool findPlaceForDoor(v3s16 &result_place, v3s16 &result_dir)
 633         {
 634                 for(u32 i=0; i<100; i++)
 635                 {
 636                         v3s16 p = m_pos + m_dir;
 637                         v3s16 p1 = p + v3s16(0,1,0);
 638                         if(vmanip.m_area.contains(p) == false
 639                                         || vmanip.m_area.contains(p1) == false
 640                                         || i % 4 == 0)
 641                         {
 642                                 randomizeDir();
 643                                 continue;
 644                         }
 645                         if(vmanip.getNodeNoExNoEmerge(p).getContent()
 646                                         == m_ndef->getId("mapgen_cobble")
 647                         && vmanip.getNodeNoExNoEmerge(p1).getContent()
 648                                         == m_ndef->getId("mapgen_cobble"))
 649                         {
 650                                 // Found wall, this is a good place!
 651                                 result_place = p;
 652                                 result_dir = m_dir;
 653                                 // Randomize next direction
 654                                 randomizeDir();
 655                                 return true;
 656                         }
 657                         /*
 658                                 Determine where to move next
 659                         */
 660                         // Jump one up if the actual space is there
 661                         if(vmanip.getNodeNoExNoEmerge(p+v3s16(0,0,0)).getContent()
 662                                         == m_ndef->getId("mapgen_cobble")
 663                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 664                                         == CONTENT_AIR
 665                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,2,0)).getContent()
 666                                         == CONTENT_AIR)
 667                                 p += v3s16(0,1,0);
 668                         // Jump one down if the actual space is there
 669                         if(vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 670                                         == m_ndef->getId("mapgen_cobble")
 671                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,0,0)).getContent()
 672                                         == CONTENT_AIR
 673                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,-1,0)).getContent()
 674                                         == CONTENT_AIR)
 675                                 p += v3s16(0,-1,0);
 676                         // Check if walking is now possible
 677                         if(vmanip.getNodeNoExNoEmerge(p).getContent()
 678                                         != CONTENT_AIR
 679                         || vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 680                                         != CONTENT_AIR)
 681                         {
 682                                 // Cannot continue walking here
 683                                 randomizeDir();
 684                                 continue;
 685                         }
 686                         // Move there
 687                         m_pos = p;
 688                 }
 689                 return false;
 690         }
 691
 692         bool findPlaceForRoomDoor(v3s16 roomsize, v3s16 &result_doorplace,
 693                         v3s16 &result_doordir, v3s16 &result_roomplace)
 694         {
 695                 for(s16 trycount=0; trycount<30; trycount++)
 696                 {
 697                         v3s16 doorplace;
 698                         v3s16 doordir;
 699                         bool r = findPlaceForDoor(doorplace, doordir);
 700                         if(r == false)
 701                                 continue;
 702                         v3s16 roomplace;
 703                         // X east, Z north, Y up
 704 #if 1
 705                         if(doordir == v3s16(1,0,0)) // X+
 706                                 roomplace = doorplace +
 707                                                 v3s16(0,-1,m_random.range(-roomsize.Z+2,-2));
 708                         if(doordir == v3s16(-1,0,0)) // X-
 709                                 roomplace = doorplace +
 710                                                 v3s16(-roomsize.X+1,-1,m_random.range(-roomsize.Z+2,-2));
 711                         if(doordir == v3s16(0,0,1)) // Z+
 712                                 roomplace = doorplace +
 713                                                 v3s16(m_random.range(-roomsize.X+2,-2),-1,0);
 714                         if(doordir == v3s16(0,0,-1)) // Z-
 715                                 roomplace = doorplace +
 716                                                 v3s16(m_random.range(-roomsize.X+2,-2),-1,-roomsize.Z+1);
 717 #endif
 718 #if 0
 719                         if(doordir == v3s16(1,0,0)) // X+
 720                                 roomplace = doorplace + v3s16(0,-1,-roomsize.Z/2);
 721                         if(doordir == v3s16(-1,0,0)) // X-
 722                                 roomplace = doorplace + v3s16(-roomsize.X+1,-1,-roomsize.Z/2);
 723                         if(doordir == v3s16(0,0,1)) // Z+
 724                                 roomplace = doorplace + v3s16(-roomsize.X/2,-1,0);
 725                         if(doordir == v3s16(0,0,-1)) // Z-
 726                                 roomplace = doorplace + v3s16(-roomsize.X/2,-1,-roomsize.Z+1);
 727 #endif
 728
 729                         // Check fit
 730                         bool fits = true;
 731                         for(s16 z=1; z<roomsize.Z-1; z++)
 732                         for(s16 y=1; y<roomsize.Y-1; y++)
 733                         for(s16 x=1; x<roomsize.X-1; x++)
 734                         {
 735                                 v3s16 p = roomplace + v3s16(x,y,z);
 736                                 if(vmanip.m_area.contains(p) == false)
 737                                 {
 738                                         fits = false;
 739                                         break;
 740                                 }
 741                                 if(vmanip.m_flags[vmanip.m_area.index(p)]
 742                                                 & VMANIP_FLAG_DUNGEON_INSIDE)
 743                                 {
 744                                         fits = false;
 745                                         break;
 746                                 }
 747                         }
 748                         if(fits == false)
 749                         {
 750                                 // Find new place
 751                                 continue;
 752                         }
 753                         result_doorplace = doorplace;
 754                         result_doordir = doordir;
 755                         result_roomplace = roomplace;
 756                         return true;
 757                 }
 758                 return false;
 759         }
 760
 761 private:
 762         VoxelManipulator &vmanip;
 763         v3s16 m_pos;
 764         v3s16 m_dir;
 765         PseudoRandom &m_random;
 766         INodeDefManager *m_ndef;
 767 };
 768
 769 static void make_dungeon1(VoxelManipulator &vmanip, PseudoRandom &random,
 770                 INodeDefManager *ndef)
 771 {
 772         v3s16 areasize = vmanip.m_area.getExtent();
 773         v3s16 roomsize;
 774         v3s16 roomplace;
 775
 776         /*
 777                 Find place for first room
 778         */
 779         bool fits = false;
 780         for(u32 i=0; i<100; i++)
 781         {
 782                 roomsize = v3s16(random.range(4,8),random.range(4,6),random.range(4,8));
 783                 roomplace = vmanip.m_area.MinEdge + v3s16(
 784                                 random.range(0,areasize.X-roomsize.X-1),
 785                                 random.range(0,areasize.Y-roomsize.Y-1),
 786                                 random.range(0,areasize.Z-roomsize.Z-1));
 787                 /*
 788                         Check that we're not putting the room to an unknown place,
 789                         otherwise it might end up floating in the air
 790                 */
 791                 fits = true;
 792                 for(s16 z=1; z<roomsize.Z-1; z++)
 793                 for(s16 y=1; y<roomsize.Y-1; y++)
 794                 for(s16 x=1; x<roomsize.X-1; x++)
 795                 {
 796                         v3s16 p = roomplace + v3s16(x,y,z);
 797                         u32 vi = vmanip.m_area.index(p);
 798                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_INSIDE)
 799                         {
 800                                 fits = false;
 801                                 break;
 802                         }
 803                         if(vmanip.m_data[vi].getContent() == CONTENT_IGNORE)
 804                         {
 805                                 fits = false;
 806                                 break;
 807                         }
 808                 }
 809                 if(fits)
 810                         break;
 811         }
 812         // No place found
 813         if(fits == false)
 814                 return;
 815
 816         /*
 817                 Stores the center position of the last room made, so that
 818                 a new corridor can be started from the last room instead of
 819                 the new room, if chosen so.
 820         */
 821         v3s16 last_room_center = roomplace+v3s16(roomsize.X/2,1,roomsize.Z/2);
 822
 823         u32 room_count = random.range(2,7);
 824         for(u32 i=0; i<room_count; i++)
 825         {
 826                 // Make a room to the determined place
 827                 make_room1(vmanip, roomsize, roomplace, ndef);
 828
 829                 v3s16 room_center = roomplace + v3s16(roomsize.X/2,1,roomsize.Z/2);
 830
 831                 // Place torch at room center (for testing)
 832                 //vmanip.m_data[vmanip.m_area.index(room_center)] = MapNode(ndef->getId("mapgen_torch"));
 833
 834                 // Quit if last room
 835                 if(i == room_count-1)
 836                         break;
 837
 838                 // Determine walker start position
 839
 840                 bool start_in_last_room = (random.range(0,2)!=0);
 841                 //bool start_in_last_room = true;
 842
 843                 v3s16 walker_start_place;
 844
 845                 if(start_in_last_room)
 846                 {
 847                         walker_start_place = last_room_center;
 848                 }
 849                 else
 850                 {
 851                         walker_start_place = room_center;
 852                         // Store center of current room as the last one
 853                         last_room_center = room_center;
 854                 }
 855
 856                 // Create walker and find a place for a door
 857                 RoomWalker walker(vmanip, walker_start_place, random, ndef);
 858                 v3s16 doorplace;
 859                 v3s16 doordir;
 860                 bool r = walker.findPlaceForDoor(doorplace, doordir);
 861                 if(r == false)
 862                         return;
 863
 864                 if(random.range(0,1)==0)
 865                         // Make the door
 866                         make_door1(vmanip, doorplace, doordir, ndef);
 867                 else
 868                         // Don't actually make a door
 869                         doorplace -= doordir;
 870
 871                 // Make a random corridor starting from the door
 872                 v3s16 corridor_end;
 873                 v3s16 corridor_end_dir;
 874                 make_corridor(vmanip, doorplace, doordir, corridor_end,
 875                                 corridor_end_dir, random, ndef);
 876
 877                 // Find a place for a random sized room
 878                 roomsize = v3s16(random.range(4,8),random.range(4,6),random.range(4,8));
 879                 walker.setPos(corridor_end);
 880                 walker.setDir(corridor_end_dir);
 881                 r = walker.findPlaceForRoomDoor(roomsize, doorplace, doordir, roomplace);
 882                 if(r == false)
 883                         return;
 884
 885                 if(random.range(0,1)==0)
 886                         // Make the door
 887                         make_door1(vmanip, doorplace, doordir, ndef);
 888                 else
 889                         // Don't actually make a door
 890                         roomplace -= doordir;
 891
 892         }
 893 }
 894 #endif
 895
 896 #if 0
 897 static void make_nc(VoxelManipulator &vmanip, PseudoRandom &random,
 898                 INodeDefManager *ndef)
 899 {
 900         v3s16 dir;
 901         u8 facedir_i = 0;
 902         s32 r = random.range(0, 3);
 903         if(r == 0){
 904                 dir = v3s16( 1, 0, 0);
 905                 facedir_i = 3;
 906         }
 907         if(r == 1){
 908                 dir = v3s16(-1, 0, 0);
 909                 facedir_i = 1;
 910         }
 911         if(r == 2){
 912                 dir = v3s16( 0, 0, 1);
 913                 facedir_i = 2;
 914         }
 915         if(r == 3){
 916                 dir = v3s16( 0, 0,-1);
 917                 facedir_i = 0;
 918         }
 919         v3s16 p = vmanip.m_area.MinEdge + v3s16(
 920                         16+random.range(0,15),
 921                         16+random.range(0,15),
 922                         16+random.range(0,15));
 923         vmanip.m_data[vmanip.m_area.index(p)] = MapNode(ndef->getId("mapgen_nyancat"), facedir_i);
 924         u32 length = random.range(3,15);
 925         for(u32 j=0; j<length; j++)
 926         {
 927                 p -= dir;
 928                 vmanip.m_data[vmanip.m_area.index(p)] = MapNode(ndef->getId("mapgen_nyancat_rainbow"));
 929         }
 930 }
 931 #endif
 932
 933 /*
 934         Noise functions. Make sure seed is mangled differently in each one.
 935 */
 936
 937 #if 0
 938 /*
 939         Scaling the output of the noise function affects the overdrive of the
 940         contour function, which affects the shape of the output considerably.
 941 */
 942 #define CAVE_NOISE_SCALE 12.0
 943 //#define CAVE_NOISE_SCALE 10.0
 944 //#define CAVE_NOISE_SCALE 7.5
 945 //#define CAVE_NOISE_SCALE 5.0
 946 //#define CAVE_NOISE_SCALE 1.0
 947
 948 //#define CAVE_NOISE_THRESHOLD (2.5/CAVE_NOISE_SCALE)
 949 #define CAVE_NOISE_THRESHOLD (1.5/CAVE_NOISE_SCALE)
 950
 951 NoiseParams get_cave_noise1_params(u64 seed)
 952 {
 953         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 5, 0.7,
 954                         200, CAVE_NOISE_SCALE);*/
 955         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 4, 0.7,
 956                         100, CAVE_NOISE_SCALE);*/
 957         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 5, 0.6,
 958                         100, CAVE_NOISE_SCALE);*/
 959         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 5, 0.3,
 960                         100, CAVE_NOISE_SCALE);*/
 961         return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 4, 0.5,
 962                         50, CAVE_NOISE_SCALE);
 963         //return NoiseParams(NOISE_CONSTANT_ONE);
 964 }
 965
 966 NoiseParams get_cave_noise2_params(u64 seed)
 967 {
 968         /*return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 5, 0.7,
 969                         200, CAVE_NOISE_SCALE);*/
 970         /*return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 4, 0.7,
 971                         100, CAVE_NOISE_SCALE);*/
 972         /*return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 5, 0.3,
 973                         100, CAVE_NOISE_SCALE);*/
 974         return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 4, 0.5,
 975                         50, CAVE_NOISE_SCALE);
 976         //return NoiseParams(NOISE_CONSTANT_ONE);
 977 }
 978
 979 NoiseParams get_ground_noise1_params(u64 seed)
 980 {
 981         return NoiseParams(NOISE_PERLIN, seed+983240, 4,
 982                         0.55, 80.0, 40.0);
 983 }
 984
 985 NoiseParams get_ground_crumbleness_params(u64 seed)
 986 {
 987         return NoiseParams(NOISE_PERLIN, seed+34413, 3,
 988                         1.3, 20.0, 1.0);
 989 }
 990
 991 NoiseParams get_ground_wetness_params(u64 seed)
 992 {
 993         return NoiseParams(NOISE_PERLIN, seed+32474, 4,
 994                         1.1, 40.0, 1.0);
 995 }
 996
 997 bool is_cave(u64 seed, v3s16 p)
 998 {
 999         double d1 = noise3d_param(get_cave_noise1_params(seed), p.X,p.Y,p.Z);
1000         double d2 = noise3d_param(get_cave_noise2_params(seed), p.X,p.Y,p.Z);
1001         return d1*d2 > CAVE_NOISE_THRESHOLD;
1002 }
1003
1004 /*
1005         Ground density noise shall be interpreted by using this.
1006
1007         TODO: No perlin noises here, they should be outsourced
1008               and buffered
1009                   NOTE: The speed of these actually isn't terrible
1010 */
1011 bool val_is_ground(double ground_noise1_val, v3s16 p, u64 seed)
1012 {
1013         //return ((double)p.Y < ground_noise1_val);
1014
1015         double f = 0.55 + noise2d_perlin(
1016                         0.5+(float)p.X/250, 0.5+(float)p.Z/250,
1017                         seed+920381, 3, 0.45);
1018         if(f < 0.01)
1019                 f = 0.01;
1020         else if(f >= 1.0)
1021                 f *= 1.6;
1022         double h = WATER_LEVEL + 10 * noise2d_perlin(
1023                         0.5+(float)p.X/250, 0.5+(float)p.Z/250,
1024                         seed+84174, 4, 0.5);
1025         /*double f = 1;
1026         double h = 0;*/
1027         return ((double)p.Y - h < ground_noise1_val * f);
1028 }
1029
1030 /*
1031         Queries whether a position is ground or not.
1032 */
1033 bool is_ground(u64 seed, v3s16 p)
1034 {
1035         double val1 = noise3d_param(get_ground_noise1_params(seed), p.X,p.Y,p.Z);
1036         return val_is_ground(val1, p, seed);
1037 }
1038 #endif
1039
1040 // Amount of trees per area in nodes
1041 double tree_amount_2d(u64 seed, v2s16 p)
1042 {
1043         /*double noise = noise2d_perlin(
1044                         0.5+(float)p.X/250, 0.5+(float)p.Y/250,
1045                         seed+2, 5, 0.66);*/
1046         double noise = noise2d_perlin(
1047                         0.5+(float)p.X/125, 0.5+(float)p.Y/125,
1048                         seed+2, 4, 0.66);
1049         double zeroval = -0.39;
1050         if(noise < zeroval)
1051                 return 0;
1052         else
1053                 return 0.04 * (noise-zeroval) / (1.0-zeroval);
1054 }
1055
1056 #if 0
1057 double surface_humidity_2d(u64 seed, v2s16 p)
1058 {
1059         double noise = noise2d_perlin(
1060                         0.5+(float)p.X/500, 0.5+(float)p.Y/500,
1061                         seed+72384, 4, 0.66);
1062         noise = (noise + 1.0)/2.0;
1063         if(noise < 0.0)
1064                 noise = 0.0;
1065         if(noise > 1.0)
1066                 noise = 1.0;
1067         return noise;
1068 }
1069
1070 /*
1071         Incrementally find ground level from 3d noise
1072 */
1073 s16 find_ground_level_from_noise(u64 seed, v2s16 p2d, s16 precision)
1074 {
1075         // Start a bit fuzzy to make averaging lower precision values
1076         // more useful
1077         s16 level = myrand_range(-precision/2, precision/2);
1078         s16 dec[] = {31000, 100, 20, 4, 1, 0};
1079         s16 i;
1080         for(i = 1; dec[i] != 0 && precision <= dec[i]; i++)
1081         {
1082                 // First find non-ground by going upwards
1083                 // Don't stop in caves.
1084                 {
1085                         s16 max = level+dec[i-1]*2;
1086                         v3s16 p(p2d.X, level, p2d.Y);
1087                         for(; p.Y < max; p.Y += dec[i])
1088                         {
1089                                 if(!is_ground(seed, p))
1090                                 {
1091                                         level = p.Y;
1092                                         break;
1093                                 }
1094                         }
1095                 }
1096                 // Then find ground by going downwards from there.
1097                 // Go in caves, too, when precision is 1.
1098                 {
1099                         s16 min = level-dec[i-1]*2;
1100                         v3s16 p(p2d.X, level, p2d.Y);
1101                         for(; p.Y>min; p.Y-=dec[i])
1102                         {
1103                                 bool ground = is_ground(seed, p);
1104                                 /*if(dec[i] == 1 && is_cave(seed, p))
1105                                         ground = false;*/
1106                                 if(ground)
1107                                 {
1108                                         level = p.Y;
1109                                         break;
1110                                 }
1111                         }
1112                 }
1113         }
1114
1115         // This is more like the actual ground level
1116         level += dec[i-1]/2;
1117
1118         return level;
1119 }
1120
1121 double get_sector_average_ground_level(u64 seed, v2s16 sectorpos, double p=4);
1122
1123 double get_sector_average_ground_level(u64 seed, v2s16 sectorpos, double p)
1124 {
1125         v2s16 node_min = sectorpos*MAP_BLOCKSIZE;
1126         v2s16 node_max = (sectorpos+v2s16(1,1))*MAP_BLOCKSIZE-v2s16(1,1);
1127         double a = 0;
1128         a += find_ground_level_from_noise(seed,
1129                         v2s16(node_min.X, node_min.Y), p);
1130         a += find_ground_level_from_noise(seed,
1131                         v2s16(node_min.X, node_max.Y), p);
1132         a += find_ground_level_from_noise(seed,
1133                         v2s16(node_max.X, node_max.Y), p);
1134         a += find_ground_level_from_noise(seed,
1135                         v2s16(node_max.X, node_min.Y), p);
1136         a += find_ground_level_from_noise(seed,
1137                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y+MAP_BLOCKSIZE/2), p);
1138         a /= 5;
1139         return a;
1140 }
1141
1142 double get_sector_maximum_ground_level(u64 seed, v2s16 sectorpos, double p=4);
1143
1144 double get_sector_maximum_ground_level(u64 seed, v2s16 sectorpos, double p)
1145 {
1146         v2s16 node_min = sectorpos*MAP_BLOCKSIZE;
1147         v2s16 node_max = (sectorpos+v2s16(1,1))*MAP_BLOCKSIZE-v2s16(1,1);
1148         double a = -31000;
1149         // Corners
1150         a = MYMAX(a, find_ground_level_from_noise(seed,
1151                         v2s16(node_min.X, node_min.Y), p));
1152         a = MYMAX(a, find_ground_level_from_noise(seed,
1153                         v2s16(node_min.X, node_max.Y), p));
1154         a = MYMAX(a, find_ground_level_from_noise(seed,
1155                         v2s16(node_max.X, node_max.Y), p));
1156         a = MYMAX(a, find_ground_level_from_noise(seed,
1157                         v2s16(node_min.X, node_min.Y), p));
1158         // Center
1159         a = MYMAX(a, find_ground_level_from_noise(seed,
1160                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y+MAP_BLOCKSIZE/2), p));
1161         // Side middle points
1162         a = MYMAX(a, find_ground_level_from_noise(seed,
1163                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y), p));
1164         a = MYMAX(a, find_ground_level_from_noise(seed,
1165                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_max.Y), p));
1166         a = MYMAX(a, find_ground_level_from_noise(seed,
1167                         v2s16(node_min.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1168         a = MYMAX(a, find_ground_level_from_noise(seed,
1169                         v2s16(node_max.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1170         return a;
1171 }
1172
1173 double get_sector_minimum_ground_level(u64 seed, v2s16 sectorpos, double p=4);
1174
1175 double get_sector_minimum_ground_level(u64 seed, v2s16 sectorpos, double p)
1176 {
1177         v2s16 node_min = sectorpos*MAP_BLOCKSIZE;
1178         v2s16 node_max = (sectorpos+v2s16(1,1))*MAP_BLOCKSIZE-v2s16(1,1);
1179         double a = 31000;
1180         // Corners
1181         a = MYMIN(a, find_ground_level_from_noise(seed,
1182                         v2s16(node_min.X, node_min.Y), p));
1183         a = MYMIN(a, find_ground_level_from_noise(seed,
1184                         v2s16(node_min.X, node_max.Y), p));
1185         a = MYMIN(a, find_ground_level_from_noise(seed,
1186                         v2s16(node_max.X, node_max.Y), p));
1187         a = MYMIN(a, find_ground_level_from_noise(seed,
1188                         v2s16(node_min.X, node_min.Y), p));
1189         // Center
1190         a = MYMIN(a, find_ground_level_from_noise(seed,
1191                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y+MAP_BLOCKSIZE/2), p));
1192         // Side middle points
1193         a = MYMIN(a, find_ground_level_from_noise(seed,
1194                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y), p));
1195         a = MYMIN(a, find_ground_level_from_noise(seed,
1196                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_max.Y), p));
1197         a = MYMIN(a, find_ground_level_from_noise(seed,
1198                         v2s16(node_min.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1199         a = MYMIN(a, find_ground_level_from_noise(seed,
1200                         v2s16(node_max.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1201         return a;
1202 }
1203 #endif
1204
1205 // Required by mapgen.h
1206 bool block_is_underground(u64 seed, v3s16 blockpos)
1207 {
1208         /*s16 minimum_groundlevel = (s16)get_sector_minimum_ground_level(
1209                         seed, v2s16(blockpos.X, blockpos.Z));*/
1210         // Nah, this is just a heuristic, just return something
1211         s16 minimum_groundlevel = WATER_LEVEL;
1212
1213         if(blockpos.Y*MAP_BLOCKSIZE + MAP_BLOCKSIZE <= minimum_groundlevel)
1214                 return true;
1215         else
1216                 return false;
1217 }
1218
1219 #define AVERAGE_MUD_AMOUNT 4
1220
1221 double base_rock_level_2d(u64 seed, v2s16 p)
1222 {
1223         // The base ground level
1224         double base = (double)WATER_LEVEL - (double)AVERAGE_MUD_AMOUNT
1225                         + 20. * noise2d_perlin(
1226                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1227                         seed+82341, 5, 0.6);
1228
1229         /*// A bit hillier one
1230         double base2 = WATER_LEVEL - 4.0 + 40. * noise2d_perlin(
1231                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1232                         seed+93413, 6, 0.69);
1233         if(base2 > base)
1234                 base = base2;*/
1235 #if 1
1236         // Higher ground level
1237         double higher = (double)WATER_LEVEL + 20. + 16. * noise2d_perlin(
1238                         0.5+(float)p.X/500., 0.5+(float)p.Y/500.,
1239                         seed+85039, 5, 0.6);
1240         //higher = 30; // For debugging
1241
1242         // Limit higher to at least base
1243         if(higher < base)
1244                 higher = base;
1245
1246         // Steepness factor of cliffs
1247         double b = 0.85 + 0.5 * noise2d_perlin(
1248                         0.5+(float)p.X/125., 0.5+(float)p.Y/125.,
1249                         seed-932, 5, 0.7);
1250         b = rangelim(b, 0.0, 1000.0);
1251         b = b*b*b*b*b*b*b;
1252         b *= 5;
1253         b = rangelim(b, 0.5, 1000.0);
1254         // Values 1.5...100 give quite horrible looking slopes
1255         if(b > 1.5 && b < 100.0){
1256                 if(b < 10.0)
1257                         b = 1.5;
1258                 else
1259                         b = 100.0;
1260         }
1261         //dstream<<"b="<<b<<std::endl;
1262         //double b = 20;
1263         //b = 0.25;
1264
1265         // Offset to more low
1266         double a_off = -0.20;
1267         // High/low selector
1268         /*double a = 0.5 + b * (a_off + noise2d_perlin(
1269                         0.5+(float)p.X/500., 0.5+(float)p.Y/500.,
1270                         seed+4213, 6, 0.7));*/
1271         double a = (double)0.5 + b * (a_off + noise2d_perlin(
1272                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1273                         seed+4213, 5, 0.69));
1274         // Limit
1275         a = rangelim(a, 0.0, 1.0);
1276
1277         //dstream<<"a="<<a<<std::endl;
1278
1279         double h = base*(1.0-a) + higher*a;
1280 #else
1281         double h = base;
1282 #endif
1283         return h;
1284 }
1285
1286 s16 find_ground_level_from_noise(u64 seed, v2s16 p2d, s16 precision)
1287 {
1288         return base_rock_level_2d(seed, p2d) + AVERAGE_MUD_AMOUNT;
1289 }
1290
1291 double get_mud_add_amount(u64 seed, v2s16 p)
1292 {
1293         return ((float)AVERAGE_MUD_AMOUNT + 2.0 * noise2d_perlin(
1294                         0.5+(float)p.X/200, 0.5+(float)p.Y/200,
1295                         seed+91013, 3, 0.55));
1296 }
1297
1298 bool get_have_beach(u64 seed, v2s16 p2d)
1299 {
1300         // Determine whether to have sand here
1301         double sandnoise = noise2d_perlin(
1302                         0.2+(float)p2d.X/250, 0.7+(float)p2d.Y/250,
1303                         seed+59420, 3, 0.50);
1304
1305         return (sandnoise > 0.15);
1306 }
1307
1308 enum BiomeType
1309 {
1310         BT_NORMAL,
1311         BT_DESERT
1312 };
1313
1314 BiomeType get_biome(u64 seed, v2s16 p2d)
1315 {
1316         // Just do something very simple as for now
1317         double d = noise2d_perlin(
1318                         0.6+(float)p2d.X/250, 0.2+(float)p2d.Y/250,
1319                         seed+9130, 3, 0.50);
1320         if(d > 0.45)
1321                 return BT_DESERT;
1322         if(d > 0.35 && (noise2d( p2d.X, p2d.Y, int(seed) ) + 1.0) > ( 0.45 - d ) * 20.0  )
1323                 return BT_DESERT;
1324         return BT_NORMAL;
1325 };
1326
1327 u32 get_blockseed(u64 seed, v3s16 p)
1328 {
1329         s32 x=p.X, y=p.Y, z=p.Z;
1330         return (u32)(seed%0x100000000ULL) + z*38134234 + y*42123 + x*23;
1331 }
1332
1333 #define VMANIP_FLAG_CAVE VOXELFLAG_CHECKED1
1334
1335 void make_block(BlockMakeData *data)
1336 {
1337         if(data->no_op)
1338         {
1339                 //dstream<<"makeBlock: no-op"<<std::endl;
1340                 return;
1341         }
1342
1343         assert(data->vmanip);
1344         assert(data->nodedef);
1345         assert(data->blockpos_requested.X >= data->blockpos_min.X &&
1346                         data->blockpos_requested.Y >= data->blockpos_min.Y &&
1347                         data->blockpos_requested.Z >= data->blockpos_min.Z);
1348         assert(data->blockpos_requested.X <= data->blockpos_max.X &&
1349                         data->blockpos_requested.Y <= data->blockpos_max.Y &&
1350                         data->blockpos_requested.Z <= data->blockpos_max.Z);
1351
1352         INodeDefManager *ndef = data->nodedef;
1353
1354         // Hack: use minimum block coordinates for old code that assumes
1355         // a single block
1356         v3s16 blockpos = data->blockpos_requested;
1357
1358         /*dstream<<"makeBlock(): ("<<blockpos.X<<","<<blockpos.Y<<","
1359                         <<blockpos.Z<<")"<<std::endl;*/
1360
1361         v3s16 blockpos_min = data->blockpos_min;
1362         v3s16 blockpos_max = data->blockpos_max;
1363         v3s16 blockpos_full_min = blockpos_min - v3s16(1,1,1);
1364         v3s16 blockpos_full_max = blockpos_max + v3s16(1,1,1);
1365
1366         ManualMapVoxelManipulator &vmanip = *(data->vmanip);
1367         // Area of central chunk
1368         v3s16 node_min = blockpos_min*MAP_BLOCKSIZE;
1369         v3s16 node_max = (blockpos_max+v3s16(1,1,1))*MAP_BLOCKSIZE-v3s16(1,1,1);
1370         // Full allocated area
1371         v3s16 full_node_min = (blockpos_min-1)*MAP_BLOCKSIZE;
1372         v3s16 full_node_max = (blockpos_max+2)*MAP_BLOCKSIZE-v3s16(1,1,1);
1373
1374         v3s16 central_area_size = node_max - node_min + v3s16(1,1,1);
1375
1376         const s16 max_spread_amount = MAP_BLOCKSIZE;
1377
1378         int volume_blocks = (blockpos_max.X - blockpos_min.X + 1)
1379                         * (blockpos_max.Y - blockpos_min.Y + 1)
1380                         * (blockpos_max.Z - blockpos_max.Z + 1);
1381
1382         int volume_nodes = volume_blocks *
1383                         MAP_BLOCKSIZE*MAP_BLOCKSIZE*MAP_BLOCKSIZE;
1384
1385         // Generated surface area
1386         //double gen_area_nodes = MAP_BLOCKSIZE*MAP_BLOCKSIZE * rel_volume;
1387
1388         // Horribly wrong heuristic, but better than nothing
1389         bool block_is_underground = (WATER_LEVEL > node_max.Y);
1390
1391         /*
1392                 Create a block-specific seed
1393         */
1394         u32 blockseed = get_blockseed(data->seed, full_node_min);
1395
1396         /*
1397                 Cache some ground type values for speed
1398         */
1399
1400 // Creates variables c_name=id and n_name=node
1401 #define CONTENT_VARIABLE(ndef, name)\
1402         content_t c_##name = ndef->getId("mapgen_" #name);\
1403         MapNode n_##name(c_##name);
1404 // Default to something else if was CONTENT_IGNORE
1405 #define CONTENT_VARIABLE_FALLBACK(name, dname)\
1406         if(c_##name == CONTENT_IGNORE){\
1407                 c_##name = c_##dname;\
1408                 n_##name = n_##dname;\
1409         }
1410
1411         CONTENT_VARIABLE(ndef, stone);
1412         CONTENT_VARIABLE(ndef, air);
1413         CONTENT_VARIABLE(ndef, water_source);
1414         CONTENT_VARIABLE(ndef, dirt);
1415         CONTENT_VARIABLE(ndef, sand);
1416         CONTENT_VARIABLE(ndef, gravel);
1417         CONTENT_VARIABLE(ndef, clay);
1418         CONTENT_VARIABLE(ndef, lava_source);
1419         CONTENT_VARIABLE(ndef, cobble);
1420         CONTENT_VARIABLE(ndef, mossycobble);
1421         CONTENT_VARIABLE(ndef, dirt_with_grass);
1422         CONTENT_VARIABLE(ndef, junglegrass);
1423         CONTENT_VARIABLE(ndef, stone_with_coal);
1424         CONTENT_VARIABLE(ndef, stone_with_iron);
1425         CONTENT_VARIABLE(ndef, mese);
1426         CONTENT_VARIABLE(ndef, desert_sand);
1427         CONTENT_VARIABLE_FALLBACK(desert_sand, sand);
1428         CONTENT_VARIABLE(ndef, desert_stone);
1429         CONTENT_VARIABLE_FALLBACK(desert_stone, stone);
1430
1431         // Maximum height of the stone surface and obstacles.
1432         // This is used to guide the cave generation
1433         s16 stone_surface_max_y = 0;
1434
1435         /*
1436                 Generate general ground level to full area
1437         */
1438         {
1439 #if 1
1440         TimeTaker timer1("Generating ground level");
1441
1442         for(s16 x=node_min.X; x<=node_max.X; x++)
1443         for(s16 z=node_min.Z; z<=node_max.Z; z++)
1444         {
1445                 // Node position
1446                 v2s16 p2d = v2s16(x,z);
1447
1448                 /*
1449                         Skip of already generated
1450                 */
1451                 /*{
1452                         v3s16 p(p2d.X, node_min.Y, p2d.Y);
1453                         if(vmanip.m_data[vmanip.m_area.index(p)].d != CONTENT_AIR)
1454                                 continue;
1455                 }*/
1456
1457                 // Ground height at this point
1458                 float surface_y_f = 0.0;
1459
1460                 // Use perlin noise for ground height
1461                 surface_y_f = base_rock_level_2d(data->seed, p2d);
1462
1463                 /*// Experimental stuff
1464                 {
1465                         float a = highlands_level_2d(data->seed, p2d);
1466                         if(a > surface_y_f)
1467                                 surface_y_f = a;
1468                 }*/
1469
1470                 // Convert to integer
1471                 s16 surface_y = (s16)surface_y_f;
1472
1473                 // Log it
1474                 if(surface_y > stone_surface_max_y)
1475                         stone_surface_max_y = surface_y;
1476
1477                 BiomeType bt = get_biome(data->seed, p2d);
1478                 /*
1479                         Fill ground with stone
1480                 */
1481                 {
1482                         // Use fast index incrementing
1483                         v3s16 em = vmanip.m_area.getExtent();
1484                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_min.Y, p2d.Y));
1485                         for(s16 y=node_min.Y; y<=node_max.Y; y++)
1486                         {
1487                                 if(vmanip.m_data[i].getContent() == CONTENT_IGNORE){
1488                                         if(y <= surface_y){
1489                                                 if(y > WATER_LEVEL && bt == BT_DESERT)
1490                                                         vmanip.m_data[i] = n_desert_stone;
1491                                                 else
1492                                                         vmanip.m_data[i] = n_stone;
1493                                         } else if(y <= WATER_LEVEL){
1494                                                 vmanip.m_data[i] = MapNode(c_water_source);
1495                                         } else {
1496                                                 vmanip.m_data[i] = MapNode(c_air);
1497                                         }
1498                                 }
1499                                 vmanip.m_area.add_y(em, i, 1);
1500                         }
1501                 }
1502         }
1503 #endif
1504
1505         }//timer1
1506
1507         // Limit dirt flow area by 1 because mud is flown into neighbors.
1508         assert(central_area_size.X == central_area_size.Z);
1509         s16 mudflow_minpos = 0-max_spread_amount+1;
1510         s16 mudflow_maxpos = central_area_size.X+max_spread_amount-2;
1511
1512         /*
1513                 Loop this part, it will make stuff look older and newer nicely
1514         */
1515
1516         const u32 age_loops = 2;
1517         for(u32 i_age=0; i_age<age_loops; i_age++)
1518         { // Aging loop
1519         /******************************
1520                 BEGINNING OF AGING LOOP
1521         ******************************/
1522
1523 #if 1
1524         {
1525         // 24ms @cs=8
1526         //TimeTaker timer1("caves");
1527
1528         /*
1529                 Make caves (this code is relatively horrible)
1530         */
1531         double cave_amount = 6.0 + 6.0 * noise2d_perlin(
1532                         0.5+(double)node_min.X/250, 0.5+(double)node_min.Y/250,
1533                         data->seed+34329, 3, 0.50);
1534         cave_amount = MYMAX(0.0, cave_amount);
1535         u32 caves_count = cave_amount * volume_nodes / 50000;
1536         u32 bruises_count = 1;
1537         PseudoRandom ps(blockseed+21343);
1538         PseudoRandom ps2(blockseed+1032);
1539         if(ps.range(1, 6) == 1)
1540                 bruises_count = ps.range(0, ps.range(0, 2));
1541         if(get_biome(data->seed, v2s16(node_min.X, node_min.Y)) == BT_DESERT){
1542                 caves_count /= 3;
1543                 bruises_count /= 3;
1544         }
1545         for(u32 jj=0; jj<caves_count+bruises_count; jj++)
1546         {
1547                 bool large_cave = (jj >= caves_count);
1548                 s16 min_tunnel_diameter = 2;
1549                 s16 max_tunnel_diameter = ps.range(2,6);
1550                 int dswitchint = ps.range(1,14);
1551                 u16 tunnel_routepoints = 0;
1552                 int part_max_length_rs = 0;
1553                 if(large_cave){
1554                         part_max_length_rs = ps.range(2,4);
1555                         tunnel_routepoints = ps.range(5, ps.range(15,30));
1556                         min_tunnel_diameter = 5;
1557                         max_tunnel_diameter = ps.range(7, ps.range(8,24));
1558                 } else {
1559                         part_max_length_rs = ps.range(2,9);
1560                         tunnel_routepoints = ps.range(10, ps.range(15,30));
1561                 }
1562                 bool large_cave_is_flat = (ps.range(0,1) == 0);
1563
1564                 v3f main_direction(0,0,0);
1565
1566                 // Allowed route area size in nodes
1567                 v3s16 ar = central_area_size;
1568
1569                 // Area starting point in nodes
1570                 v3s16 of = node_min;
1571
1572                 // Allow a bit more
1573                 //(this should be more than the maximum radius of the tunnel)
1574                 //s16 insure = 5; // Didn't work with max_d = 20
1575                 s16 insure = 10;
1576                 s16 more = max_spread_amount - max_tunnel_diameter/2 - insure;
1577                 ar += v3s16(1,0,1) * more * 2;
1578                 of -= v3s16(1,0,1) * more;
1579
1580                 s16 route_y_min = 0;
1581                 // Allow half a diameter + 7 over stone surface
1582                 s16 route_y_max = -of.Y + stone_surface_max_y + max_tunnel_diameter/2 + 7;
1583
1584                 /*// If caves, don't go through surface too often
1585                 if(large_cave == false)
1586                         route_y_max -= ps.range(0, max_tunnel_diameter*2);*/
1587
1588                 // Limit maximum to area
1589                 route_y_max = rangelim(route_y_max, 0, ar.Y-1);
1590
1591                 if(large_cave)
1592                 {
1593                         /*// Minimum is at y=0
1594                         route_y_min = -of.Y - 0;*/
1595                         // Minimum is at y=max_tunnel_diameter/4
1596                         //route_y_min = -of.Y + max_tunnel_diameter/4;
1597                         //s16 min = -of.Y + max_tunnel_diameter/4;
1598                         //s16 min = -of.Y + 0;
1599                         s16 min = 0;
1600                         if(node_min.Y < WATER_LEVEL && node_max.Y > WATER_LEVEL)
1601                         {
1602                                 min = WATER_LEVEL - max_tunnel_diameter/3 - of.Y;
1603                                 route_y_max = WATER_LEVEL + max_tunnel_diameter/3 - of.Y;
1604                         }
1605                         route_y_min = ps.range(min, min + max_tunnel_diameter);
1606                         route_y_min = rangelim(route_y_min, 0, route_y_max);
1607                 }
1608
1609                 /*dstream<<"route_y_min = "<<route_y_min
1610                                 <<", route_y_max = "<<route_y_max<<std::endl;*/
1611
1612                 s16 route_start_y_min = route_y_min;
1613                 s16 route_start_y_max = route_y_max;
1614
1615                 // Start every 4th cave from surface when applicable
1616                 /*bool coming_from_surface = false;
1617                 if(node_min.Y <= 0 && node_max.Y >= 0){
1618                         coming_from_surface = (jj % 4 == 0 && large_cave == false);
1619                         if(coming_from_surface)
1620                                 route_start_y_min = -of.Y + stone_surface_max_y + 10;
1621                 }*/
1622
1623                 route_start_y_min = rangelim(route_start_y_min, 0, ar.Y-1);
1624                 route_start_y_max = rangelim(route_start_y_max, route_start_y_min, ar.Y-1);
1625
1626                 // Randomize starting position
1627                 v3f orp(
1628                         (float)(ps.next()%ar.X)+0.5,
1629                         (float)(ps.range(route_start_y_min, route_start_y_max))+0.5,
1630                         (float)(ps.next()%ar.Z)+0.5
1631                 );
1632
1633                 v3s16 startp(orp.X, orp.Y, orp.Z);
1634                 startp += of;
1635
1636                 MapNode airnode(CONTENT_AIR);
1637                 MapNode waternode(c_water_source);
1638                 MapNode lavanode(c_lava_source);
1639
1640                 /*
1641                         Generate some tunnel starting from orp
1642                 */
1643
1644                 for(u16 j=0; j<tunnel_routepoints; j++)
1645                 {
1646                         if(j%dswitchint==0 && large_cave == false)
1647                         {
1648                                 main_direction = v3f(
1649                                         ((float)(ps.next()%20)-(float)10)/10,
1650                                         ((float)(ps.next()%20)-(float)10)/30,
1651                                         ((float)(ps.next()%20)-(float)10)/10
1652                                 );
1653                                 main_direction *= (float)ps.range(0, 10)/10;
1654                         }
1655
1656                         // Randomize size
1657                         s16 min_d = min_tunnel_diameter;
1658                         s16 max_d = max_tunnel_diameter;
1659                         s16 rs = ps.range(min_d, max_d);
1660
1661                         // Every second section is rough
1662                         bool randomize_xz = (ps2.range(1,2) == 1);
1663
1664                         v3s16 maxlen;
1665                         if(large_cave)
1666                         {
1667                                 maxlen = v3s16(
1668                                         rs*part_max_length_rs,
1669                                         rs*part_max_length_rs/2,
1670                                         rs*part_max_length_rs
1671                                 );
1672                         }
1673                         else
1674                         {
1675                                 maxlen = v3s16(
1676                                         rs*part_max_length_rs,
1677                                         ps.range(1, rs*part_max_length_rs),
1678                                         rs*part_max_length_rs
1679                                 );
1680                         }
1681
1682                         v3f vec;
1683
1684                         vec = v3f(
1685                                 (float)(ps.next()%(maxlen.X*1))-(float)maxlen.X/2,
1686                                 (float)(ps.next()%(maxlen.Y*1))-(float)maxlen.Y/2,
1687                                 (float)(ps.next()%(maxlen.Z*1))-(float)maxlen.Z/2
1688                         );
1689
1690                         // Jump downward sometimes
1691                         if(!large_cave && ps.range(0,12) == 0)
1692                         {
1693                                 vec = v3f(
1694                                         (float)(ps.next()%(maxlen.X*1))-(float)maxlen.X/2,
1695                                         (float)(ps.next()%(maxlen.Y*2))-(float)maxlen.Y*2/2,
1696                                         (float)(ps.next()%(maxlen.Z*1))-(float)maxlen.Z/2
1697                                 );
1698                         }
1699
1700                         /*if(large_cave){
1701                                 v3f p = orp + vec;
1702                                 s16 h = find_ground_level_clever(vmanip,
1703                                                 v2s16(p.X, p.Z), ndef);
1704                                 route_y_min = h - rs/3;
1705                                 route_y_max = h + rs;
1706                         }*/
1707
1708                         vec += main_direction;
1709
1710                         v3f rp = orp + vec;
1711                         if(rp.X < 0)
1712                                 rp.X = 0;
1713                         else if(rp.X >= ar.X)
1714                                 rp.X = ar.X-1;
1715                         if(rp.Y < route_y_min)
1716                                 rp.Y = route_y_min;
1717                         else if(rp.Y >= route_y_max)
1718                                 rp.Y = route_y_max-1;
1719                         if(rp.Z < 0)
1720                                 rp.Z = 0;
1721                         else if(rp.Z >= ar.Z)
1722                                 rp.Z = ar.Z-1;
1723                         vec = rp - orp;
1724
1725                         for(float f=0; f<1.0; f+=1.0/vec.getLength())
1726                         {
1727                                 v3f fp = orp + vec * f;
1728                                 fp.X += 0.1*ps.range(-10,10);
1729                                 fp.Z += 0.1*ps.range(-10,10);
1730                                 v3s16 cp(fp.X, fp.Y, fp.Z);
1731
1732                                 s16 d0 = -rs/2;
1733                                 s16 d1 = d0 + rs;
1734                                 if(randomize_xz){
1735                                         d0 += ps.range(-1,1);
1736                                         d1 += ps.range(-1,1);
1737                                 }
1738                                 for(s16 z0=d0; z0<=d1; z0++)
1739                                 {
1740                                         s16 si = rs/2 - MYMAX(0, abs(z0)-rs/7-1);
1741                                         for(s16 x0=-si-ps.range(0,1); x0<=si-1+ps.range(0,1); x0++)
1742                                         {
1743                                                 s16 maxabsxz = MYMAX(abs(x0), abs(z0));
1744                                                 s16 si2 = rs/2 - MYMAX(0, maxabsxz-rs/7-1);
1745                                                 for(s16 y0=-si2; y0<=si2; y0++)
1746                                                 {
1747                                                         /*// Make better floors in small caves
1748                                                         if(y0 <= -rs/2 && rs<=7)
1749                                                                 continue;*/
1750                                                         if(large_cave_is_flat){
1751                                                                 // Make large caves not so tall
1752                                                                 if(rs > 7 && abs(y0) >= rs/3)
1753                                                                         continue;
1754                                                         }
1755
1756                                                         s16 z = cp.Z + z0;
1757                                                         s16 y = cp.Y + y0;
1758                                                         s16 x = cp.X + x0;
1759                                                         v3s16 p(x,y,z);
1760                                                         p += of;
1761
1762                                                         if(vmanip.m_area.contains(p) == false)
1763                                                                 continue;
1764
1765                                                         u32 i = vmanip.m_area.index(p);
1766
1767                                                         if(large_cave)
1768                                                         {
1769                                                                 if(full_node_min.Y < WATER_LEVEL &&
1770                                                                         full_node_max.Y > WATER_LEVEL){
1771                                                                         if(p.Y <= WATER_LEVEL)
1772                                                                                 vmanip.m_data[i] = waternode;
1773                                                                         else
1774                                                                                 vmanip.m_data[i] = airnode;
1775                                                                 } else if(full_node_max.Y < WATER_LEVEL){
1776                                                                         if(p.Y < startp.Y - 2)
1777                                                                                 vmanip.m_data[i] = lavanode;
1778                                                                         else
1779                                                                                 vmanip.m_data[i] = airnode;
1780                                                                 } else {
1781                                                                         vmanip.m_data[i] = airnode;
1782                                                                 }
1783                                                         } else {
1784                                                                 // Don't replace air or water or lava or ignore
1785                                                                 if(vmanip.m_data[i].getContent() == CONTENT_IGNORE ||
1786                                                                 vmanip.m_data[i].getContent() == CONTENT_AIR ||
1787                                                                 vmanip.m_data[i].getContent() == c_water_source ||
1788                                                                 vmanip.m_data[i].getContent() == c_lava_source)
1789                                                                         continue;
1790
1791                                                                 vmanip.m_data[i] = airnode;
1792
1793                                                                 // Set tunnel flag
1794                                                                 vmanip.m_flags[i] |= VMANIP_FLAG_CAVE;
1795                                                         }
1796                                                 }
1797                                         }
1798                                 }
1799                         }
1800
1801                         orp = rp;
1802                 }
1803
1804         }
1805
1806         }//timer1
1807 #endif
1808
1809 #if 1
1810         {
1811         // 15ms @cs=8
1812         TimeTaker timer1("add mud");
1813
1814         /*
1815                 Add mud to the central chunk
1816         */
1817
1818         for(s16 x=node_min.X; x<=node_max.X; x++)
1819         for(s16 z=node_min.Z; z<=node_max.Z; z++)
1820         {
1821                 // Node position in 2d
1822                 v2s16 p2d = v2s16(x,z);
1823
1824                 // Randomize mud amount
1825                 s16 mud_add_amount = get_mud_add_amount(data->seed, p2d) / 2.0 + 0.5;
1826
1827                 // Find ground level
1828                 s16 surface_y = find_stone_level(vmanip, p2d, ndef);
1829                 // Handle area not found
1830                 if(surface_y == vmanip.m_area.MinEdge.Y - 1)
1831                         continue;
1832
1833                 MapNode addnode(c_dirt);
1834                 BiomeType bt = get_biome(data->seed, p2d);
1835
1836                 if(bt == BT_DESERT)
1837                         addnode = MapNode(c_desert_sand);
1838
1839                 if(bt == BT_DESERT && surface_y + mud_add_amount <= WATER_LEVEL+1){
1840                         addnode = MapNode(c_sand);
1841                 } else if(mud_add_amount <= 0){
1842                         mud_add_amount = 1 - mud_add_amount;
1843                         addnode = MapNode(c_gravel);
1844                 } else if(bt == BT_NORMAL && get_have_beach(data->seed, p2d) &&
1845                                 surface_y + mud_add_amount <= WATER_LEVEL+2){
1846                         addnode = MapNode(c_sand);
1847                 }
1848
1849                 if(bt == BT_DESERT){
1850                         if(surface_y > 20){
1851                                 mud_add_amount = MYMAX(0, mud_add_amount - (surface_y - 20)/5);
1852                         }
1853                 }
1854
1855                 /*
1856                         If topmost node is grass, change it to mud.
1857                         It might be if it was flown to there from a neighboring
1858                         chunk and then converted.
1859                 */
1860                 {
1861                         u32 i = vmanip.m_area.index(v3s16(p2d.X, surface_y, p2d.Y));
1862                         MapNode *n = &vmanip.m_data[i];
1863                         if(n->getContent() == c_dirt_with_grass)
1864                                 *n = MapNode(c_dirt);
1865                 }
1866
1867                 /*
1868                         Add mud on ground
1869                 */
1870                 {
1871                         s16 mudcount = 0;
1872                         v3s16 em = vmanip.m_area.getExtent();
1873                         s16 y_start = surface_y+1;
1874                         u32 i = vmanip.m_area.index(v3s16(p2d.X, y_start, p2d.Y));
1875                         for(s16 y=y_start; y<=node_max.Y; y++)
1876                         {
1877                                 if(mudcount >= mud_add_amount)
1878                                         break;
1879
1880                                 MapNode &n = vmanip.m_data[i];
1881                                 n = addnode;
1882                                 mudcount++;
1883
1884                                 vmanip.m_area.add_y(em, i, 1);
1885                         }
1886                 }
1887
1888         }
1889
1890         }//timer1
1891 #endif
1892
1893         /*
1894                 Add blobs of dirt and gravel underground
1895         */
1896         if(get_biome(data->seed, v2s16(node_min.X, node_min.Y)) == BT_NORMAL)
1897         {
1898         PseudoRandom pr(blockseed+983);
1899         for(int i=0; i<volume_nodes/10/10/10; i++)
1900         {
1901                 bool only_fill_cave = (myrand_range(0,1) != 0);
1902                 v3s16 size(
1903                         pr.range(1, 8),
1904                         pr.range(1, 8),
1905                         pr.range(1, 8)
1906                 );
1907                 v3s16 p0(
1908                         pr.range(node_min.X, node_max.X)-size.X/2,
1909                         pr.range(node_min.Y, node_max.Y)-size.Y/2,
1910                         pr.range(node_min.Z, node_max.Z)-size.Z/2
1911                 );
1912                 MapNode n1;
1913                 if(p0.Y > -32 && pr.range(0,1) == 0)
1914                         n1 = MapNode(c_dirt);
1915                 else
1916                         n1 = MapNode(c_gravel);
1917                 for(int x1=0; x1<size.X; x1++)
1918                 for(int y1=0; y1<size.Y; y1++)
1919                 for(int z1=0; z1<size.Z; z1++)
1920                 {
1921                         v3s16 p = p0 + v3s16(x1,y1,z1);
1922                         u32 i = vmanip.m_area.index(p);
1923                         if(!vmanip.m_area.contains(i))
1924                                 continue;
1925                         // Cancel if not stone and not cave air
1926                         if(vmanip.m_data[i].getContent() != c_stone &&
1927                                         !(vmanip.m_flags[i] & VMANIP_FLAG_CAVE))
1928                                 continue;
1929                         if(only_fill_cave && !(vmanip.m_flags[i] & VMANIP_FLAG_CAVE))
1930                                 continue;
1931                         vmanip.m_data[i] = n1;
1932                 }
1933         }
1934         }
1935
1936 #if 1
1937         {
1938         // 340ms @cs=8
1939         TimeTaker timer1("flow mud");
1940
1941         /*
1942                 Flow mud away from steep edges
1943         */
1944
1945         // Iterate a few times
1946         for(s16 k=0; k<3; k++)
1947         {
1948
1949         for(s16 x=mudflow_minpos; x<=mudflow_maxpos; x++)
1950         for(s16 z=mudflow_minpos; z<=mudflow_maxpos; z++)
1951         {
1952                 // Invert coordinates every 2nd iteration
1953                 if(k%2 == 0)
1954                 {
1955                         x = mudflow_maxpos - (x-mudflow_minpos);
1956                         z = mudflow_maxpos - (z-mudflow_minpos);
1957                 }
1958
1959                 // Node position in 2d
1960                 v2s16 p2d = v2s16(node_min.X, node_min.Z) + v2s16(x,z);
1961
1962                 v3s16 em = vmanip.m_area.getExtent();
1963                 u32 i = vmanip.m_area.index(v3s16(p2d.X, node_max.Y, p2d.Y));
1964                 s16 y=node_max.Y;
1965
1966                 while(y >= node_min.Y)
1967                 {
1968
1969                 for(;; y--)
1970                 {
1971                         MapNode *n = NULL;
1972                         // Find mud
1973                         for(; y>=node_min.Y; y--)
1974                         {
1975                                 n = &vmanip.m_data[i];
1976                                 //if(content_walkable(n->d))
1977                                 //      break;
1978                                 if(n->getContent() == c_dirt ||
1979                                                 n->getContent() == c_dirt_with_grass ||
1980                                                 n->getContent() == c_gravel)
1981                                         break;
1982
1983                                 vmanip.m_area.add_y(em, i, -1);
1984                         }
1985
1986                         // Stop if out of area
1987                         //if(vmanip.m_area.contains(i) == false)
1988                         if(y < node_min.Y)
1989                                 break;
1990
1991                         /*// If not mud, do nothing to it
1992                         MapNode *n = &vmanip.m_data[i];
1993                         if(n->d != CONTENT_MUD && n->d != CONTENT_GRASS)
1994                                 continue;*/
1995
1996                         if(n->getContent() == c_dirt ||
1997                                         n->getContent() == c_dirt_with_grass)
1998                         {
1999                                 // Make it exactly mud
2000                                 n->setContent(c_dirt);
2001
2002                                 /*
2003                                         Don't flow it if the stuff under it is not mud
2004                                 */
2005                                 {
2006                                         u32 i2 = i;
2007                                         vmanip.m_area.add_y(em, i2, -1);
2008                                         // Cancel if out of area
2009                                         if(vmanip.m_area.contains(i2) == false)
2010                                                 continue;
2011                                         MapNode *n2 = &vmanip.m_data[i2];
2012                                         if(n2->getContent() != c_dirt &&
2013                                                         n2->getContent() != c_dirt_with_grass)
2014                                                 continue;
2015                                 }
2016                         }
2017
2018                         /*s16 recurse_count = 0;
2019         mudflow_recurse:*/
2020
2021                         v3s16 dirs4[4] = {
2022                                 v3s16(0,0,1), // back
2023                                 v3s16(1,0,0), // right
2024                                 v3s16(0,0,-1), // front
2025                                 v3s16(-1,0,0), // left
2026                         };
2027
2028                         // Theck that upper is air or doesn't exist.
2029                         // Cancel dropping if upper keeps it in place
2030                         u32 i3 = i;
2031                         vmanip.m_area.add_y(em, i3, 1);
2032                         if(vmanip.m_area.contains(i3) == true
2033                                         && ndef->get(vmanip.m_data[i3]).walkable)
2034                         {
2035                                 continue;
2036                         }
2037
2038                         // Drop mud on side
2039
2040                         for(u32 di=0; di<4; di++)
2041                         {
2042                                 v3s16 dirp = dirs4[di];
2043                                 u32 i2 = i;
2044                                 // Move to side
2045                                 vmanip.m_area.add_p(em, i2, dirp);
2046                                 // Fail if out of area
2047                                 if(vmanip.m_area.contains(i2) == false)
2048                                         continue;
2049                                 // Check that side is air
2050                                 MapNode *n2 = &vmanip.m_data[i2];
2051                                 if(ndef->get(*n2).walkable)
2052                                         continue;
2053                                 // Check that under side is air
2054                                 vmanip.m_area.add_y(em, i2, -1);
2055                                 if(vmanip.m_area.contains(i2) == false)
2056                                         continue;
2057                                 n2 = &vmanip.m_data[i2];
2058                                 if(ndef->get(*n2).walkable)
2059                                         continue;
2060                                 /*// Check that under that is air (need a drop of 2)
2061                                 vmanip.m_area.add_y(em, i2, -1);
2062                                 if(vmanip.m_area.contains(i2) == false)
2063                                         continue;
2064                                 n2 = &vmanip.m_data[i2];
2065                                 if(content_walkable(n2->d))
2066                                         continue;*/
2067                                 // Loop further down until not air
2068                                 bool dropped_to_unknown = false;
2069                                 do{
2070                                         vmanip.m_area.add_y(em, i2, -1);
2071                                         n2 = &vmanip.m_data[i2];
2072                                         // if out of known area
2073                                         if(vmanip.m_area.contains(i2) == false
2074                                                         || n2->getContent() == CONTENT_IGNORE){
2075                                                 dropped_to_unknown = true;
2076                                                 break;
2077                                         }
2078                                 }while(ndef->get(*n2).walkable == false);
2079                                 // Loop one up so that we're in air
2080                                 vmanip.m_area.add_y(em, i2, 1);
2081                                 n2 = &vmanip.m_data[i2];
2082
2083                                 bool old_is_water = (n->getContent() == c_water_source);
2084                                 // Move mud to new place
2085                                 if(!dropped_to_unknown) {
2086                                         *n2 = *n;
2087                                         // Set old place to be air (or water)
2088                                         if(old_is_water)
2089                                                 *n = MapNode(c_water_source);
2090                                         else
2091                                                 *n = MapNode(CONTENT_AIR);
2092                                 }
2093
2094                                 // Done
2095                                 break;
2096                         }
2097                 }
2098                 }
2099         }
2100
2101         }
2102
2103         }//timer1
2104 #endif
2105
2106         } // Aging loop
2107         /***********************
2108                 END OF AGING LOOP
2109         ************************/
2110
2111         /*
2112                 Add top and bottom side of water to transforming_liquid queue
2113         */
2114
2115         for(s16 x=full_node_min.X; x<=full_node_max.X; x++)
2116         for(s16 z=full_node_min.Z; z<=full_node_max.Z; z++)
2117         {
2118                 // Node position
2119                 v2s16 p2d(x,z);
2120                 {
2121                         bool water_found = false;
2122                         // Use fast index incrementing
2123                         v3s16 em = vmanip.m_area.getExtent();
2124                         u32 i = vmanip.m_area.index(v3s16(p2d.X, full_node_max.Y, p2d.Y));
2125                         for(s16 y=full_node_max.Y; y>=full_node_min.Y; y--)
2126                         {
2127                                 if(y == full_node_max.Y){
2128                                         water_found =
2129                                                 (vmanip.m_data[i].getContent() == c_water_source ||
2130                                                 vmanip.m_data[i].getContent() == c_lava_source);
2131                                 }
2132                                 else if(water_found == false)
2133                                 {
2134                                         if(vmanip.m_data[i].getContent() == c_water_source ||
2135                                                         vmanip.m_data[i].getContent() == c_lava_source)
2136                                         {
2137                                                 v3s16 p = v3s16(p2d.X, y, p2d.Y);
2138                                                 data->transforming_liquid.push_back(p);
2139                                                 water_found = true;
2140                                         }
2141                                 }
2142                                 else
2143                                 {
2144                                         // This can be done because water_found can only
2145                                         // turn to true and end up here after going through
2146                                         // a single block.
2147                                         if(vmanip.m_data[i+1].getContent() != c_water_source ||
2148                                                         vmanip.m_data[i+1].getContent() != c_lava_source)
2149                                         {
2150                                                 v3s16 p = v3s16(p2d.X, y+1, p2d.Y);
2151                                                 data->transforming_liquid.push_back(p);
2152                                                 water_found = false;
2153                                         }
2154                                 }
2155
2156                                 vmanip.m_area.add_y(em, i, -1);
2157                         }
2158                 }
2159         }
2160
2161         /*
2162                 Grow grass
2163         */
2164
2165         for(s16 x=full_node_min.X; x<=full_node_max.X; x++)
2166         for(s16 z=full_node_min.Z; z<=full_node_max.Z; z++)
2167         {
2168                 // Node position in 2d
2169                 v2s16 p2d = v2s16(x,z);
2170
2171                 /*
2172                         Find the lowest surface to which enough light ends up
2173                         to make grass grow.
2174
2175                         Basically just wait until not air and not leaves.
2176                 */
2177                 s16 surface_y = 0;
2178                 {
2179                         v3s16 em = vmanip.m_area.getExtent();
2180                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_max.Y, p2d.Y));
2181                         s16 y;
2182                         // Go to ground level
2183                         for(y=node_max.Y; y>=full_node_min.Y; y--)
2184                         {
2185                                 MapNode &n = vmanip.m_data[i];
2186                                 if(ndef->get(n).param_type != CPT_LIGHT
2187                                                 || ndef->get(n).liquid_type != LIQUID_NONE)
2188                                         break;
2189                                 vmanip.m_area.add_y(em, i, -1);
2190                         }
2191                         if(y >= full_node_min.Y)
2192                                 surface_y = y;
2193                         else
2194                                 surface_y = full_node_min.Y;
2195                 }
2196
2197                 u32 i = vmanip.m_area.index(p2d.X, surface_y, p2d.Y);
2198                 MapNode *n = &vmanip.m_data[i];
2199                 if(n->getContent() == c_dirt){
2200                         // Well yeah, this can't be overground...
2201                         if(surface_y < WATER_LEVEL - 20)
2202                                 continue;
2203                         n->setContent(c_dirt_with_grass);
2204                 }
2205         }
2206
2207         /*
2208                 Generate some trees
2209         */
2210         assert(central_area_size.X == central_area_size.Z);
2211         {
2212                 // Divide area into parts
2213                 s16 div = 8;
2214                 s16 sidelen = central_area_size.X / div;
2215                 double area = sidelen * sidelen;
2216                 for(s16 x0=0; x0<div; x0++)
2217                 for(s16 z0=0; z0<div; z0++)
2218                 {
2219                         // Center position of part of division
2220                         v2s16 p2d_center(
2221                                 node_min.X + sidelen/2 + sidelen*x0,
2222                                 node_min.Z + sidelen/2 + sidelen*z0
2223                         );
2224                         // Minimum edge of part of division
2225                         v2s16 p2d_min(
2226                                 node_min.X + sidelen*x0,
2227                                 node_min.Z + sidelen*z0
2228                         );
2229                         // Maximum edge of part of division
2230                         v2s16 p2d_max(
2231                                 node_min.X + sidelen + sidelen*x0 - 1,
2232                                 node_min.Z + sidelen + sidelen*z0 - 1
2233                         );
2234                         // Amount of trees
2235                         u32 tree_count = area * tree_amount_2d(data->seed, p2d_center);
2236                         // Put trees in random places on part of division
2237                         for(u32 i=0; i<tree_count; i++)
2238                         {
2239                                 s16 x = myrand_range(p2d_min.X, p2d_max.X);
2240                                 s16 z = myrand_range(p2d_min.Y, p2d_max.Y);
2241                                 s16 y = find_ground_level(vmanip, v2s16(x,z), ndef);
2242                                 // Don't make a tree under water level
2243                                 if(y < WATER_LEVEL)
2244                                         continue;
2245                                 // Don't make a tree so high that it doesn't fit
2246                                 if(y > node_max.Y - 6)
2247                                         continue;
2248                                 v3s16 p(x,y,z);
2249                                 /*
2250                                         Trees grow only on mud and grass
2251                                 */
2252                                 {
2253                                         u32 i = vmanip.m_area.index(v3s16(p));
2254                                         MapNode *n = &vmanip.m_data[i];
2255                                         if(n->getContent() != c_dirt
2256                                                         && n->getContent() != c_dirt_with_grass)
2257                                                 continue;
2258                                 }
2259                                 p.Y++;
2260                                 // Make a tree
2261                                 treegen::make_tree(vmanip, p, false, ndef);
2262                         }
2263                 }
2264         }
2265
2266 #if 0
2267         /*
2268                 Make base ground level
2269         */
2270
2271         for(s16 x=node_min.X; x<=node_max.X; x++)
2272         for(s16 z=node_min.Z; z<=node_max.Z; z++)
2273         {
2274                 // Node position
2275                 v2s16 p2d(x,z);
2276                 {
2277                         // Use fast index incrementing
2278                         v3s16 em = vmanip.m_area.getExtent();
2279                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_min.Y, p2d.Y));
2280                         for(s16 y=node_min.Y; y<=node_max.Y; y++)
2281                         {
2282                                 // Only modify places that have no content
2283                                 if(vmanip.m_data[i].getContent() == CONTENT_IGNORE)
2284                                 {
2285                                         // First priority: make air and water.
2286                                         // This avoids caves inside water.
2287                                         if(all_is_ground_except_caves == false
2288                                                         && val_is_ground(noisebuf_ground.get(x,y,z),
2289                                                         v3s16(x,y,z), data->seed) == false)
2290                                         {
2291                                                 if(y <= WATER_LEVEL)
2292                                                         vmanip.m_data[i] = n_water_source;
2293                                                 else
2294                                                         vmanip.m_data[i] = n_air;
2295                                         }
2296                                         else if(noisebuf_cave.get(x,y,z) > CAVE_NOISE_THRESHOLD)
2297                                                 vmanip.m_data[i] = n_air;
2298                                         else
2299                                                 vmanip.m_data[i] = n_stone;
2300                                 }
2301
2302                                 vmanip->m_area.add_y(em, i, 1);
2303                         }
2304                 }
2305         }
2306
2307         /*
2308                 Add mud and sand and others underground (in place of stone)
2309         */
2310
2311         for(s16 x=node_min.X; x<=node_max.X; x++)
2312         for(s16 z=node_min.Z; z<=node_max.Z; z++)
2313         {
2314                 // Node position
2315                 v2s16 p2d(x,z);
2316                 {
2317                         // Use fast index incrementing
2318                         v3s16 em = vmanip.m_area.getExtent();
2319                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_max.Y, p2d.Y));
2320                         for(s16 y=node_max.Y; y>=node_min.Y; y--)
2321                         {
2322                                 if(vmanip.m_data[i].getContent() == c_stone)
2323                                 {
2324                                         if(noisebuf_ground_crumbleness.get(x,y,z) > 1.3)
2325                                         {
2326                                                 if(noisebuf_ground_wetness.get(x,y,z) > 0.0)
2327                                                         vmanip.m_data[i] = n_dirt;
2328                                                 else
2329                                                         vmanip.m_data[i] = n_sand;
2330                                         }
2331                                         else if(noisebuf_ground_crumbleness.get(x,y,z) > 0.7)
2332                                         {
2333                                                 if(noisebuf_ground_wetness.get(x,y,z) < -0.6)
2334                                                         vmanip.m_data[i] = n_gravel;
2335                                         }
2336                                         else if(noisebuf_ground_crumbleness.get(x,y,z) <
2337                                                         -3.0 + MYMIN(0.1 * sqrt((float)MYMAX(0, -y)), 1.5))
2338                                         {
2339                                                 vmanip.m_data[i] = n_lava_source;
2340                                                 for(s16 x1=-1; x1<=1; x1++)
2341                                                 for(s16 y1=-1; y1<=1; y1++)
2342                                                 for(s16 z1=-1; z1<=1; z1++)
2343                                                         data->transforming_liquid.push_back(
2344                                                                         v3s16(p2d.X+x1, y+y1, p2d.Y+z1));
2345                                         }
2346                                 }
2347
2348                                 vmanip->m_area.add_y(em, i, -1);
2349                         }
2350                 }
2351         }
2352
2353         /*
2354                 Add dungeons
2355         */
2356
2357         //if(node_min.Y < approx_groundlevel)
2358         //if(myrand() % 3 == 0)
2359         //if(myrand() % 3 == 0 && node_min.Y < approx_groundlevel)
2360         //if(myrand() % 100 == 0 && node_min.Y < approx_groundlevel)
2361         //float dungeon_rarity = g_settings.getFloat("dungeon_rarity");
2362         float dungeon_rarity = 0.02;
2363         if(((noise3d(blockpos.X,blockpos.Y,blockpos.Z,data->seed)+1.0)/2.0)
2364                         < dungeon_rarity
2365                         && node_min.Y < approx_groundlevel)
2366         {
2367                 // Dungeon generator doesn't modify places which have this set
2368                 vmanip->clearFlag(VMANIP_FLAG_DUNGEON_INSIDE
2369                                 | VMANIP_FLAG_DUNGEON_PRESERVE);
2370
2371                 // Set all air and water to be untouchable to make dungeons open
2372                 // to caves and open air
2373                 for(s16 x=full_node_min.X; x<=full_node_max.X; x++)
2374                 for(s16 z=full_node_min.Z; z<=full_node_max.Z; z++)
2375                 {
2376                         // Node position
2377                         v2s16 p2d(x,z);
2378                         {
2379                                 // Use fast index incrementing
2380                                 v3s16 em = vmanip.m_area.getExtent();
2381                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, full_node_max.Y, p2d.Y));
2382                                 for(s16 y=full_node_max.Y; y>=full_node_min.Y; y--)
2383                                 {
2384                                         if(vmanip.m_data[i].getContent() == CONTENT_AIR)
2385                                                 vmanip.m_flags[i] |= VMANIP_FLAG_DUNGEON_PRESERVE;
2386                                         else if(vmanip.m_data[i].getContent() == c_water_source)
2387                                                 vmanip.m_flags[i] |= VMANIP_FLAG_DUNGEON_PRESERVE;
2388                                         vmanip->m_area.add_y(em, i, -1);
2389                                 }
2390                         }
2391                 }
2392
2393                 PseudoRandom random(blockseed+2);
2394
2395                 // Add it
2396                 make_dungeon1(vmanip, random, ndef);
2397
2398                 // Convert some cobble to mossy cobble
2399                 for(s16 x=full_node_min.X; x<=full_node_max.X; x++)
2400                 for(s16 z=full_node_min.Z; z<=full_node_max.Z; z++)
2401                 {
2402                         // Node position
2403                         v2s16 p2d(x,z);
2404                         {
2405                                 // Use fast index incrementing
2406                                 v3s16 em = vmanip.m_area.getExtent();
2407                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, full_node_max.Y, p2d.Y));
2408                                 for(s16 y=full_node_max.Y; y>=full_node_min.Y; y--)
2409                                 {
2410                                         // (noisebuf not used because it doesn't contain the
2411                                         //  full area)
2412                                         double wetness = noise3d_param(
2413                                                         get_ground_wetness_params(data->seed), x,y,z);
2414                                         double d = noise3d_perlin((float)x/2.5,
2415                                                         (float)y/2.5,(float)z/2.5,
2416                                                         blockseed, 2, 1.4);
2417                                         if(vmanip.m_data[i].getContent() == c_cobble)
2418                                         {
2419                                                 if(d < wetness/3.0)
2420                                                 {
2421                                                         vmanip.m_data[i].setContent(c_mossycobble);
2422                                                 }
2423                                         }
2424                                         /*else if(vmanip.m_flags[i] & VMANIP_FLAG_DUNGEON_INSIDE)
2425                                         {
2426                                                 if(wetness > 1.2)
2427                                                         vmanip.m_data[i].setContent(c_dirt);
2428                                         }*/
2429                                         vmanip->m_area.add_y(em, i, -1);
2430                                 }
2431                         }
2432                 }
2433         }
2434
2435         /*
2436                 Add NC
2437         */
2438         {
2439                 PseudoRandom ncrandom(blockseed+9324342);
2440                 if(ncrandom.range(0, 1000) == 0 && blockpos.Y <= -3)
2441                 {
2442                         make_nc(vmanip, ncrandom, ndef);
2443                 }
2444         }
2445
2446         /*
2447                 Add top and bottom side of water to transforming_liquid queue
2448         */
2449
2450         for(s16 x=node_min.X; x<=node_max.X; x++)
2451         for(s16 z=node_min.Z; z<=node_max.Z; z++)
2452         {
2453                 // Node position
2454                 v2s16 p2d(x,z);
2455                 {
2456                         bool water_found = false;
2457                         // Use fast index incrementing
2458                         v3s16 em = vmanip.m_area.getExtent();
2459                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_max.Y, p2d.Y));
2460                         for(s16 y=node_max.Y; y>=node_min.Y; y--)
2461                         {
2462                                 if(water_found == false)
2463                                 {
2464                                         if(vmanip.m_data[i].getContent() == c_water_source)
2465                                         {
2466                                                 v3s16 p = v3s16(p2d.X, y, p2d.Y);
2467                                                 data->transforming_liquid.push_back(p);
2468                                                 water_found = true;
2469                                         }
2470                                 }
2471                                 else
2472                                 {
2473                                         // This can be done because water_found can only
2474                                         // turn to true and end up here after going through
2475                                         // a single block.
2476                                         if(vmanip.m_data[i+1].getContent() != c_water_source)
2477                                         {
2478                                                 v3s16 p = v3s16(p2d.X, y+1, p2d.Y);
2479                                                 data->transforming_liquid.push_back(p);
2480                                                 water_found = false;
2481                                         }
2482                                 }
2483
2484                                 vmanip->m_area.add_y(em, i, -1);
2485                         }
2486                 }
2487         }
2488
2489         /*
2490                 If close to ground level
2491         */
2492
2493         //if(abs(approx_ground_depth) < 30)
2494         if(minimum_ground_depth < 5 && maximum_ground_depth > -5)
2495         {
2496                 /*
2497                         Add grass and mud
2498                 */
2499
2500                 for(s16 x=node_min.X; x<=node_max.X; x++)
2501                 for(s16 z=node_min.Z; z<=node_max.Z; z++)
2502                 {
2503                         // Node position
2504                         v2s16 p2d(x,z);
2505                         {
2506                                 bool possibly_have_sand = get_have_beach(data->seed, p2d);
2507                                 bool have_sand = false;
2508                                 u32 current_depth = 0;
2509                                 bool air_detected = false;
2510                                 bool water_detected = false;
2511                                 bool have_clay = false;
2512
2513                                 // Use fast index incrementing
2514                                 s16 start_y = node_max.Y+2;
2515                                 v3s16 em = vmanip.m_area.getExtent();
2516                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, start_y, p2d.Y));
2517                                 for(s16 y=start_y; y>=node_min.Y-3; y--)
2518                                 {
2519                                         if(vmanip.m_data[i].getContent() == c_water_source)
2520                                                 water_detected = true;
2521                                         if(vmanip.m_data[i].getContent() == CONTENT_AIR)
2522                                                 air_detected = true;
2523
2524                                         if((vmanip.m_data[i].getContent() == c_stone
2525                                                         || vmanip.m_data[i].getContent() == c_dirt_with_grass
2526                                                         || vmanip.m_data[i].getContent() == c_dirt
2527                                                         || vmanip.m_data[i].getContent() == c_sand
2528                                                         || vmanip.m_data[i].getContent() == c_gravel
2529                                                         ) && (air_detected || water_detected))
2530                                         {
2531                                                 if(current_depth == 0 && y <= WATER_LEVEL+2
2532                                                                 && possibly_have_sand)
2533                                                         have_sand = true;
2534
2535                                                 if(current_depth < 4)
2536                                                 {
2537                                                         if(have_sand)
2538                                                         {
2539                                                                 vmanip.m_data[i] = MapNode(c_sand);
2540                                                         }
2541                                                         #if 1
2542                                                         else if(current_depth==0 && !water_detected
2543                                                                         && y >= WATER_LEVEL && air_detected)
2544                                                                 vmanip.m_data[i] = MapNode(c_dirt_with_grass);
2545                                                         #endif
2546                                                         else
2547                                                                 vmanip.m_data[i] = MapNode(c_dirt);
2548                                                 }
2549                                                 else
2550                                                 {
2551                                                         if(vmanip.m_data[i].getContent() == c_dirt
2552                                                                 || vmanip.m_data[i].getContent() == c_dirt_with_grass)
2553                                                                 vmanip.m_data[i] = MapNode(c_stone);
2554                                                 }
2555
2556                                                 current_depth++;
2557
2558                                                 if(current_depth >= 8)
2559                                                         break;
2560                                         }
2561                                         else if(current_depth != 0)
2562                                                 break;
2563
2564                                         vmanip->m_area.add_y(em, i, -1);
2565                                 }
2566                         }
2567                 }
2568
2569                 /*
2570                         Calculate some stuff
2571                 */
2572
2573                 float surface_humidity = surface_humidity_2d(data->seed, p2d_center);
2574                 bool is_jungle = surface_humidity > 0.75;
2575                 // Amount of trees
2576                 u32 tree_count = gen_area_nodes * tree_amount_2d(data->seed, p2d_center);
2577                 if(is_jungle)
2578                         tree_count *= 5;
2579
2580                 /*
2581                         Add trees
2582                 */
2583                 PseudoRandom treerandom(blockseed);
2584                 // Put trees in random places on part of division
2585                 for(u32 i=0; i<tree_count; i++)
2586                 {
2587                         s16 x = treerandom.range(node_min.X, node_max.X);
2588                         s16 z = treerandom.range(node_min.Z, node_max.Z);
2589                         //s16 y = find_ground_level(vmanip, v2s16(x,z));
2590                         s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 4);
2591                         // Don't make a tree under water level
2592                         if(y < WATER_LEVEL)
2593                                 continue;
2594                         // Make sure tree fits (only trees whose starting point is
2595                         // at this block are added)
2596                         if(y < node_min.Y || y > node_max.Y)
2597                                 continue;
2598                         /*
2599                                 Find exact ground level
2600                         */
2601                         v3s16 p(x,y+6,z);
2602                         bool found = false;
2603                         for(; p.Y >= y-6; p.Y--)
2604                         {
2605                                 u32 i = vmanip->m_area.index(p);
2606                                 MapNode *n = &vmanip->m_data[i];
2607                                 if(n->getContent() != CONTENT_AIR && n->getContent() != c_water_source && n->getContent() != CONTENT_IGNORE)
2608                                 {
2609                                         found = true;
2610                                         break;
2611                                 }
2612                         }
2613                         // If not found, handle next one
2614                         if(found == false)
2615                                 continue;
2616
2617                         {
2618                                 u32 i = vmanip->m_area.index(p);
2619                                 MapNode *n = &vmanip->m_data[i];
2620
2621                                 if(n->getContent() != c_dirt && n->getContent() != c_dirt_with_grass && n->getContent() != c_sand)
2622                                                 continue;
2623
2624                                 // Papyrus grows only on mud and in water
2625                                 if(n->getContent() == c_dirt && y <= WATER_LEVEL)
2626                                 {
2627                                         p.Y++;
2628                                         make_papyrus(vmanip, p, ndef);
2629                                 }
2630                                 // Trees grow only on mud and grass, on land
2631                                 else if((n->getContent() == c_dirt || n->getContent() == c_dirt_with_grass) && y > WATER_LEVEL + 2)
2632                                 {
2633                                         p.Y++;
2634                                         //if(surface_humidity_2d(data->seed, v2s16(x, y)) < 0.5)
2635                                         if(is_jungle == false)
2636                                         {
2637                                                 bool is_apple_tree;
2638                                                 if(myrand_range(0,4) != 0)
2639                                                         is_apple_tree = false;
2640                                                 else
2641                                                         is_apple_tree = noise2d_perlin(
2642                                                                         0.5+(float)p.X/100, 0.5+(float)p.Z/100,
2643                                                                         data->seed+342902, 3, 0.45) > 0.2;
2644                                                 make_tree(vmanip, p, is_apple_tree, ndef);
2645                                         }
2646                                         else
2647                                                 make_jungletree(vmanip, p, ndef);
2648                                 }
2649                                 // Cactii grow only on sand, on land
2650                                 else if(n->getContent() == c_sand && y > WATER_LEVEL + 2)
2651                                 {
2652                                         p.Y++;
2653                                         make_cactus(vmanip, p, ndef);
2654                                 }
2655                         }
2656                 }
2657
2658                 /*
2659                         Add jungle grass
2660                 */
2661                 if(is_jungle)
2662                 {
2663                         PseudoRandom grassrandom(blockseed);
2664                         for(u32 i=0; i<surface_humidity*5*tree_count; i++)
2665                         {
2666                                 s16 x = grassrandom.range(node_min.X, node_max.X);
2667                                 s16 z = grassrandom.range(node_min.Z, node_max.Z);
2668                                 s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 4);
2669                                 if(y < WATER_LEVEL)
2670                                         continue;
2671                                 if(y < node_min.Y || y > node_max.Y)
2672                                         continue;
2673                                 /*
2674                                         Find exact ground level
2675                                 */
2676                                 v3s16 p(x,y+6,z);
2677                                 bool found = false;
2678                                 for(; p.Y >= y-6; p.Y--)
2679                                 {
2680                                         u32 i = vmanip->m_area.index(p);
2681                                         MapNode *n = &vmanip->m_data[i];
2682                                         if(data->nodedef->get(*n).is_ground_content)
2683                                         {
2684                                                 found = true;
2685                                                 break;
2686                                         }
2687                                 }
2688                                 // If not found, handle next one
2689                                 if(found == false)
2690                                         continue;
2691                                 p.Y++;
2692                                 if(vmanip.m_area.contains(p) == false)
2693                                         continue;
2694                                 if(vmanip.m_data[vmanip.m_area.index(p)].getContent() != CONTENT_AIR)
2695                                         continue;
2696                                 /*p.Y--;
2697                                 if(vmanip.m_area.contains(p))
2698                                         vmanip.m_data[vmanip.m_area.index(p)] = c_dirt;
2699                                 p.Y++;*/
2700                                 if(vmanip.m_area.contains(p))
2701                                         vmanip.m_data[vmanip.m_area.index(p)] = c_junglegrass;
2702                         }
2703                 }
2704
2705 #if 0
2706                 /*
2707                         Add some kind of random stones
2708                 */
2709
2710                 u32 random_stone_count = gen_area_nodes *
2711                                 randomstone_amount_2d(data->seed, p2d_center);
2712                 // Put in random places on part of division
2713                 for(u32 i=0; i<random_stone_count; i++)
2714                 {
2715                         s16 x = myrand_range(node_min.X, node_max.X);
2716                         s16 z = myrand_range(node_min.Z, node_max.Z);
2717                         s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 1);
2718                         // Don't add under water level
2719                         /*if(y < WATER_LEVEL)
2720                                 continue;*/
2721                         // Don't add if doesn't belong to this block
2722                         if(y < node_min.Y || y > node_max.Y)
2723                                 continue;
2724                         v3s16 p(x,y,z);
2725                         // Filter placement
2726                         /*{
2727                                 u32 i = vmanip->m_area.index(v3s16(p));
2728                                 MapNode *n = &vmanip->m_data[i];
2729                                 if(n->getContent() != c_dirt && n->getContent() != c_dirt_with_grass)
2730                                         continue;
2731                         }*/
2732                         // Will be placed one higher
2733                         p.Y++;
2734                         // Add it
2735                         make_randomstone(vmanip, p);
2736                 }
2737 #endif
2738
2739 #if 0
2740                 /*
2741                         Add larger stones
2742                 */
2743
2744                 u32 large_stone_count = gen_area_nodes *
2745                                 largestone_amount_2d(data->seed, p2d_center);
2746                 //u32 large_stone_count = 1;
2747                 // Put in random places on part of division
2748                 for(u32 i=0; i<large_stone_count; i++)
2749                 {
2750                         s16 x = myrand_range(node_min.X, node_max.X);
2751                         s16 z = myrand_range(node_min.Z, node_max.Z);
2752                         s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 1);
2753                         // Don't add under water level
2754                         /*if(y < WATER_LEVEL)
2755                                 continue;*/
2756                         // Don't add if doesn't belong to this block
2757                         if(y < node_min.Y || y > node_max.Y)
2758                                 continue;
2759                         v3s16 p(x,y,z);
2760                         // Filter placement
2761                         /*{
2762                                 u32 i = vmanip->m_area.index(v3s16(p));
2763                                 MapNode *n = &vmanip->m_data[i];
2764                                 if(n->getContent() != c_dirt && n->getContent() != c_dirt_with_grass)
2765                                         continue;
2766                         }*/
2767                         // Will be placed one lower
2768                         p.Y--;
2769                         // Add it
2770                         make_largestone(vmanip, p);
2771                 }
2772 #endif
2773         }
2774
2775         /*
2776                 Add minerals
2777         */
2778
2779         {
2780                 PseudoRandom mineralrandom(blockseed);
2781
2782                 /*
2783                         Add meseblocks
2784                 */
2785                 for(s16 i=0; i<approx_ground_depth/4; i++)
2786                 {
2787                         if(mineralrandom.next()%50 == 0)
2788                         {
2789                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
2790                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
2791                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
2792                                 for(u16 i=0; i<27; i++)
2793                                 {
2794                                         v3s16 p = v3s16(x,y,z) + g_27dirs[i];
2795                                         u32 vi = vmanip.m_area.index(p);
2796                                         if(vmanip.m_data[vi].getContent() == c_stone)
2797                                                 if(mineralrandom.next()%8 == 0)
2798                                                         vmanip.m_data[vi] = MapNode(c_mese);
2799                                 }
2800
2801                         }
2802                 }
2803                 /*
2804                         Add others
2805                 */
2806                 {
2807                         u16 a = mineralrandom.range(0,15);
2808                         a = a*a*a;
2809                         u16 amount = 20 * a/1000;
2810                         for(s16 i=0; i<amount; i++)
2811                         {
2812                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
2813                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
2814                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
2815
2816                                 u8 base_content = c_stone;
2817                                 MapNode new_content(CONTENT_IGNORE);
2818                                 u32 sparseness = 6;
2819
2820                                 if(noisebuf_ground_crumbleness.get(x,y+5,z) < -0.1)
2821                                 {
2822                                         new_content = MapNode(c_stone_with_coal);
2823                                 }
2824                                 else
2825                                 {
2826                                         if(noisebuf_ground_wetness.get(x,y+5,z) > 0.0)
2827                                                 new_content = MapNode(c_stone_with_iron);
2828                                         /*if(noisebuf_ground_wetness.get(x,y,z) > 0.0)
2829                                                 vmanip.m_data[i] = MapNode(c_dirt);
2830                                         else
2831                                                 vmanip.m_data[i] = MapNode(c_sand);*/
2832                                 }
2833                                 /*else if(noisebuf_ground_crumbleness.get(x,y,z) > 0.1)
2834                                 {
2835                                 }*/
2836
2837                                 if(new_content.getContent() != CONTENT_IGNORE)
2838                                 {
2839                                         for(u16 i=0; i<27; i++)
2840                                         {
2841                                                 v3s16 p = v3s16(x,y,z) + g_27dirs[i];
2842                                                 u32 vi = vmanip.m_area.index(p);
2843                                                 if(vmanip.m_data[vi].getContent() == base_content)
2844                                                 {
2845                                                         if(mineralrandom.next()%sparseness == 0)
2846                                                                 vmanip.m_data[vi] = new_content;
2847                                                 }
2848                                         }
2849                                 }
2850                         }
2851                 }
2852                 /*
2853                         Add coal
2854                 */
2855                 //for(s16 i=0; i < MYMAX(0, 50 - abs(node_min.Y+8 - (-30))); i++)
2856                 //for(s16 i=0; i<50; i++)
2857                 u16 coal_amount = 30;
2858                 u16 coal_rareness = 60 / coal_amount;
2859                 if(coal_rareness == 0)
2860                         coal_rareness = 1;
2861                 if(mineralrandom.next()%coal_rareness == 0)
2862                 {
2863                         u16 a = mineralrandom.next() % 16;
2864                         u16 amount = coal_amount * a*a*a / 1000;
2865                         for(s16 i=0; i<amount; i++)
2866                         {
2867                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
2868                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
2869                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
2870                                 for(u16 i=0; i<27; i++)
2871                                 {
2872                                         v3s16 p = v3s16(x,y,z) + g_27dirs[i];
2873                                         u32 vi = vmanip.m_area.index(p);
2874                                         if(vmanip.m_data[vi].getContent() == c_stone)
2875                                                 if(mineralrandom.next()%8 == 0)
2876                                                         vmanip.m_data[vi] = MapNode(c_stone_with_coal);
2877                                 }
2878                         }
2879                 }
2880                 /*
2881                         Add iron
2882                 */
2883                 u16 iron_amount = 8;
2884                 u16 iron_rareness = 60 / iron_amount;
2885                 if(iron_rareness == 0)
2886                         iron_rareness = 1;
2887                 if(mineralrandom.next()%iron_rareness == 0)
2888                 {
2889                         u16 a = mineralrandom.next() % 16;
2890                         u16 amount = iron_amount * a*a*a / 1000;
2891                         for(s16 i=0; i<amount; i++)
2892                         {
2893                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
2894                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
2895                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
2896                                 for(u16 i=0; i<27; i++)
2897                                 {
2898                                         v3s16 p = v3s16(x,y,z) + g_27dirs[i];
2899                                         u32 vi = vmanip.m_area.index(p);
2900                                         if(vmanip.m_data[vi].getContent() == c_stone)
2901                                                 if(mineralrandom.next()%8 == 0)
2902                                                         vmanip.m_data[vi] = MapNode(c_stone_with_iron);
2903                                 }
2904                         }
2905                 }
2906         }
2907 #endif
2908
2909         /*
2910                 Calculate lighting
2911         */
2912         {
2913         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update",
2914                         SPT_AVG);
2915         //VoxelArea a(node_min, node_max);
2916         VoxelArea a(node_min-v3s16(1,0,1)*MAP_BLOCKSIZE,
2917                         node_max+v3s16(1,0,1)*MAP_BLOCKSIZE);
2918         /*VoxelArea a(node_min-v3s16(1,0,1)*MAP_BLOCKSIZE/2,
2919                         node_max+v3s16(1,0,1)*MAP_BLOCKSIZE/2);*/
2920         enum LightBank banks[2] = {LIGHTBANK_DAY, LIGHTBANK_NIGHT};
2921         for(int i=0; i<2; i++)
2922         {
2923                 enum LightBank bank = banks[i];
2924
2925                 core::map<v3s16, bool> light_sources;
2926                 core::map<v3s16, u8> unlight_from;
2927
2928                 voxalgo::clearLightAndCollectSources(vmanip, a, bank, ndef,
2929                                 light_sources, unlight_from);
2930
2931                 bool inexistent_top_provides_sunlight = !block_is_underground;
2932                 voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
2933                                 vmanip, a, inexistent_top_provides_sunlight,
2934                                 light_sources, ndef);
2935                 // TODO: Do stuff according to bottom_sunlight_valid
2936
2937                 vmanip.unspreadLight(bank, unlight_from, light_sources, ndef);
2938
2939                 vmanip.spreadLight(bank, light_sources, ndef);
2940         }
2941         }
2942 }
2943
2944 #endif ///BIG COMMENT
2945
2946 BlockMakeData::BlockMakeData():
2947         no_op(false),
2948         vmanip(NULL),
2949         seed(0),
2950         nodedef(NULL)
2951 {}
2952
2953 BlockMakeData::~BlockMakeData()
2954 {
2955         delete vmanip;
2956 }
2957
2958 //}; // namespace mapgen
2959
2960