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