src/mapgen.cpp

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