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