src/mapgen.cpp

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