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