src/mapgen.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010-2011 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "mapgen.h"
  21 #include "voxel.h"
  22 #include "content_mapnode.h"
  23 #include "noise.h"
  24 #include "mapblock.h"
  25 #include "map.h"
  26 #include "mineral.h"
  27 //#include "serverobject.h"
  28 #include "content_sao.h"
  29
  30 namespace mapgen
  31 {
  32
  33 /*
  34         Some helper functions for the map generator
  35 */
  36
  37 #if 0
  38 static s16 find_ground_level(VoxelManipulator &vmanip, v2s16 p2d)
  39 {
  40         v3s16 em = vmanip.m_area.getExtent();
  41         s16 y_nodes_max = vmanip.m_area.MaxEdge.Y;
  42         s16 y_nodes_min = vmanip.m_area.MinEdge.Y;
  43         u32 i = vmanip.m_area.index(v3s16(p2d.X, y_nodes_max, p2d.Y));
  44         s16 y;
  45         for(y=y_nodes_max; y>=y_nodes_min; y--)
  46         {
  47                 MapNode &n = vmanip.m_data[i];
  48                 if(content_walkable(n.d))
  49                         break;
  50
  51                 vmanip.m_area.add_y(em, i, -1);
  52         }
  53         if(y >= y_nodes_min)
  54                 return y;
  55         else
  56                 return y_nodes_min;
  57 }
  58
  59 static s16 find_ground_level_clever(VoxelManipulator &vmanip, v2s16 p2d)
  60 {
  61         v3s16 em = vmanip.m_area.getExtent();
  62         s16 y_nodes_max = vmanip.m_area.MaxEdge.Y;
  63         s16 y_nodes_min = vmanip.m_area.MinEdge.Y;
  64         u32 i = vmanip.m_area.index(v3s16(p2d.X, y_nodes_max, p2d.Y));
  65         s16 y;
  66         for(y=y_nodes_max; y>=y_nodes_min; y--)
  67         {
  68                 MapNode &n = vmanip.m_data[i];
  69                 if(content_walkable(n.d)
  70                                 && n.getContent() != CONTENT_TREE
  71                                 && n.getContent() != CONTENT_LEAVES)
  72                         break;
  73
  74                 vmanip.m_area.add_y(em, i, -1);
  75         }
  76         if(y >= y_nodes_min)
  77                 return y;
  78         else
  79                 return y_nodes_min;
  80 }
  81 #endif
  82
  83 static void make_tree(VoxelManipulator &vmanip, v3s16 p0, bool is_apple_tree)
  84 {
  85         MapNode treenode(CONTENT_TREE);
  86         MapNode leavesnode(CONTENT_LEAVES);
  87         MapNode applenode(CONTENT_APPLE);
  88
  89         s16 trunk_h = myrand_range(4, 5);
  90         v3s16 p1 = p0;
  91         for(s16 ii=0; ii<trunk_h; ii++)
  92         {
  93                 if(vmanip.m_area.contains(p1))
  94                         vmanip.m_data[vmanip.m_area.index(p1)] = treenode;
  95                 p1.Y++;
  96         }
  97
  98         // p1 is now the last piece of the trunk
  99         p1.Y -= 1;
 100
 101         VoxelArea leaves_a(v3s16(-2,-1,-2), v3s16(2,2,2));
 102         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
 103         Buffer<u8> leaves_d(leaves_a.getVolume());
 104         for(s32 i=0; i<leaves_a.getVolume(); i++)
 105                 leaves_d[i] = 0;
 106
 107         // Force leaves at near the end of the trunk
 108         {
 109                 s16 d = 1;
 110                 for(s16 z=-d; z<=d; z++)
 111                 for(s16 y=-d; y<=d; y++)
 112                 for(s16 x=-d; x<=d; x++)
 113                 {
 114                         leaves_d[leaves_a.index(v3s16(x,y,z))] = 1;
 115                 }
 116         }
 117
 118         // Add leaves randomly
 119         for(u32 iii=0; iii<7; iii++)
 120         {
 121                 s16 d = 1;
 122
 123                 v3s16 p(
 124                         myrand_range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X-d),
 125                         myrand_range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y-d),
 126                         myrand_range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z-d)
 127                 );
 128
 129                 for(s16 z=0; z<=d; z++)
 130                 for(s16 y=0; y<=d; y++)
 131                 for(s16 x=0; x<=d; x++)
 132                 {
 133                         leaves_d[leaves_a.index(p+v3s16(x,y,z))] = 1;
 134                 }
 135         }
 136
 137         // Blit leaves to vmanip
 138         for(s16 z=leaves_a.MinEdge.Z; z<=leaves_a.MaxEdge.Z; z++)
 139         for(s16 y=leaves_a.MinEdge.Y; y<=leaves_a.MaxEdge.Y; y++)
 140         for(s16 x=leaves_a.MinEdge.X; x<=leaves_a.MaxEdge.X; x++)
 141         {
 142                 v3s16 p(x,y,z);
 143                 p += p1;
 144                 if(vmanip.m_area.contains(p) == false)
 145                         continue;
 146                 u32 vi = vmanip.m_area.index(p);
 147                 if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 148                                 && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 149                         continue;
 150                 u32 i = leaves_a.index(x,y,z);
 151                 if(leaves_d[i] == 1) {
 152                         bool is_apple = myrand_range(0,99) < 10;
 153                         if(is_apple_tree && is_apple) {
 154                                 vmanip.m_data[vi] = applenode;
 155                         } else {
 156                                 vmanip.m_data[vi] = leavesnode;
 157                         }
 158                 }
 159         }
 160 }
 161
 162 static void make_jungletree(VoxelManipulator &vmanip, v3s16 p0)
 163 {
 164         MapNode treenode(CONTENT_JUNGLETREE);
 165         MapNode leavesnode(CONTENT_LEAVES);
 166
 167         for(s16 x=-1; x<=1; x++)
 168         for(s16 z=-1; z<=1; z++)
 169         {
 170                 if(myrand_range(0, 2) == 0)
 171                         continue;
 172                 v3s16 p1 = p0 + v3s16(x,0,z);
 173                 v3s16 p2 = p0 + v3s16(x,-1,z);
 174                 if(vmanip.m_area.contains(p2)
 175                                 && vmanip.m_data[vmanip.m_area.index(p2)] == CONTENT_AIR)
 176                         vmanip.m_data[vmanip.m_area.index(p2)] = treenode;
 177                 else if(vmanip.m_area.contains(p1))
 178                         vmanip.m_data[vmanip.m_area.index(p1)] = treenode;
 179         }
 180
 181         s16 trunk_h = myrand_range(8, 12);
 182         v3s16 p1 = p0;
 183         for(s16 ii=0; ii<trunk_h; ii++)
 184         {
 185                 if(vmanip.m_area.contains(p1))
 186                         vmanip.m_data[vmanip.m_area.index(p1)] = treenode;
 187                 p1.Y++;
 188         }
 189
 190         // p1 is now the last piece of the trunk
 191         p1.Y -= 1;
 192
 193         VoxelArea leaves_a(v3s16(-3,-2,-3), v3s16(3,2,3));
 194         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
 195         Buffer<u8> leaves_d(leaves_a.getVolume());
 196         for(s32 i=0; i<leaves_a.getVolume(); i++)
 197                 leaves_d[i] = 0;
 198
 199         // Force leaves at near the end of the trunk
 200         {
 201                 s16 d = 1;
 202                 for(s16 z=-d; z<=d; z++)
 203                 for(s16 y=-d; y<=d; y++)
 204                 for(s16 x=-d; x<=d; x++)
 205                 {
 206                         leaves_d[leaves_a.index(v3s16(x,y,z))] = 1;
 207                 }
 208         }
 209
 210         // Add leaves randomly
 211         for(u32 iii=0; iii<30; iii++)
 212         {
 213                 s16 d = 1;
 214
 215                 v3s16 p(
 216                         myrand_range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X-d),
 217                         myrand_range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y-d),
 218                         myrand_range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z-d)
 219                 );
 220
 221                 for(s16 z=0; z<=d; z++)
 222                 for(s16 y=0; y<=d; y++)
 223                 for(s16 x=0; x<=d; x++)
 224                 {
 225                         leaves_d[leaves_a.index(p+v3s16(x,y,z))] = 1;
 226                 }
 227         }
 228
 229         // Blit leaves to vmanip
 230         for(s16 z=leaves_a.MinEdge.Z; z<=leaves_a.MaxEdge.Z; z++)
 231         for(s16 y=leaves_a.MinEdge.Y; y<=leaves_a.MaxEdge.Y; y++)
 232         for(s16 x=leaves_a.MinEdge.X; x<=leaves_a.MaxEdge.X; x++)
 233         {
 234                 v3s16 p(x,y,z);
 235                 p += p1;
 236                 if(vmanip.m_area.contains(p) == false)
 237                         continue;
 238                 u32 vi = vmanip.m_area.index(p);
 239                 if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 240                                 && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 241                         continue;
 242                 u32 i = leaves_a.index(x,y,z);
 243                 if(leaves_d[i] == 1)
 244                         vmanip.m_data[vi] = leavesnode;
 245         }
 246 }
 247
 248 void make_papyrus(VoxelManipulator &vmanip, v3s16 p0)
 249 {
 250         MapNode papyrusnode(CONTENT_PAPYRUS);
 251
 252         s16 trunk_h = myrand_range(2, 3);
 253         v3s16 p1 = p0;
 254         for(s16 ii=0; ii<trunk_h; ii++)
 255         {
 256                 if(vmanip.m_area.contains(p1))
 257                         vmanip.m_data[vmanip.m_area.index(p1)] = papyrusnode;
 258                 p1.Y++;
 259         }
 260 }
 261
 262 void make_cactus(VoxelManipulator &vmanip, v3s16 p0)
 263 {
 264         MapNode cactusnode(CONTENT_CACTUS);
 265
 266         s16 trunk_h = 3;
 267         v3s16 p1 = p0;
 268         for(s16 ii=0; ii<trunk_h; ii++)
 269         {
 270                 if(vmanip.m_area.contains(p1))
 271                         vmanip.m_data[vmanip.m_area.index(p1)] = cactusnode;
 272                 p1.Y++;
 273         }
 274 }
 275
 276 #if 0
 277 static void make_randomstone(VoxelManipulator &vmanip, v3s16 p0)
 278 {
 279         MapNode stonenode(CONTENT_STONE);
 280
 281         s16 size = myrand_range(3, 6);
 282
 283         VoxelArea stone_a(v3s16(-2,0,-2), v3s16(2,size,2));
 284         Buffer<u8> stone_d(stone_a.getVolume());
 285         for(s32 i=0; i<stone_a.getVolume(); i++)
 286                 stone_d[i] = 0;
 287
 288         // Force stone at bottom to make it usually touch the ground
 289         {
 290                 for(s16 z=0; z<=0; z++)
 291                 for(s16 y=0; y<=0; y++)
 292                 for(s16 x=0; x<=0; x++)
 293                 {
 294                         stone_d[stone_a.index(v3s16(x,y,z))] = 1;
 295                 }
 296         }
 297
 298         // Generate from perlin noise
 299         for(s16 z=stone_a.MinEdge.Z; z<=stone_a.MaxEdge.Z; z++)
 300         for(s16 y=stone_a.MinEdge.Y; y<=stone_a.MaxEdge.Y; y++)
 301         for(s16 x=stone_a.MinEdge.X; x<=stone_a.MaxEdge.X; x++)
 302         {
 303                 double d = noise3d_perlin((float)x/3.,(float)z/3.,(float)y/3.,
 304                                 p0.Z*4243+p0.Y*34+p0.X, 2, 0.5);
 305                 if(z == stone_a.MinEdge.Z || z == stone_a.MaxEdge.Z)
 306                         d -= 0.3;
 307                 if(/*y == stone_a.MinEdge.Y ||*/ y == stone_a.MaxEdge.Y)
 308                         d -= 0.3;
 309                 if(x == stone_a.MinEdge.X || x == stone_a.MaxEdge.X)
 310                         d -= 0.3;
 311                 if(d > 0.0)
 312                 {
 313                         u32 vi = stone_a.index(v3s16(x,y,z));
 314                         stone_d[vi] = 1;
 315                 }
 316         }
 317
 318         /*// Add stone randomly
 319         for(u32 iii=0; iii<7; iii++)
 320         {
 321                 s16 d = 1;
 322
 323                 v3s16 p(
 324                         myrand_range(stone_a.MinEdge.X, stone_a.MaxEdge.X-d),
 325                         myrand_range(stone_a.MinEdge.Y, stone_a.MaxEdge.Y-d),
 326                         myrand_range(stone_a.MinEdge.Z, stone_a.MaxEdge.Z-d)
 327                 );
 328
 329                 for(s16 z=0; z<=d; z++)
 330                 for(s16 y=0; y<=d; y++)
 331                 for(s16 x=0; x<=d; x++)
 332                 {
 333                         stone_d[stone_a.index(p+v3s16(x,y,z))] = 1;
 334                 }
 335         }*/
 336
 337         // Blit stone to vmanip
 338         for(s16 z=stone_a.MinEdge.Z; z<=stone_a.MaxEdge.Z; z++)
 339         for(s16 y=stone_a.MinEdge.Y; y<=stone_a.MaxEdge.Y; y++)
 340         for(s16 x=stone_a.MinEdge.X; x<=stone_a.MaxEdge.X; x++)
 341         {
 342                 v3s16 p(x,y,z);
 343                 p += p0;
 344                 if(vmanip.m_area.contains(p) == false)
 345                         continue;
 346                 u32 vi = vmanip.m_area.index(p);
 347                 if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 348                                 && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 349                         continue;
 350                 u32 i = stone_a.index(x,y,z);
 351                 if(stone_d[i] == 1)
 352                         vmanip.m_data[vi] = stonenode;
 353         }
 354 }
 355 #endif
 356
 357 #if 0
 358 static void make_largestone(VoxelManipulator &vmanip, v3s16 p0)
 359 {
 360         MapNode stonenode(CONTENT_STONE);
 361
 362         s16 size = myrand_range(8, 16);
 363
 364         VoxelArea stone_a(v3s16(-size/2,0,-size/2), v3s16(size/2,size,size/2));
 365         Buffer<u8> stone_d(stone_a.getVolume());
 366         for(s32 i=0; i<stone_a.getVolume(); i++)
 367                 stone_d[i] = 0;
 368
 369         // Force stone at bottom to make it usually touch the ground
 370         {
 371                 for(s16 z=0; z<=0; z++)
 372                 for(s16 y=0; y<=0; y++)
 373                 for(s16 x=0; x<=0; x++)
 374                 {
 375                         stone_d[stone_a.index(v3s16(x,y,z))] = 1;
 376                 }
 377         }
 378
 379         // Generate from perlin noise
 380         for(s16 z=stone_a.MinEdge.Z; z<=stone_a.MaxEdge.Z; z++)
 381         for(s16 y=stone_a.MinEdge.Y; y<=stone_a.MaxEdge.Y; y++)
 382         for(s16 x=stone_a.MinEdge.X; x<=stone_a.MaxEdge.X; x++)
 383         {
 384                 double d = 1.0;
 385                 d += noise3d_perlin((float)x/10.,(float)z/10.,(float)y/10.,
 386                                 p0.Z*5123+p0.Y*2439+p0.X, 2, 0.5);
 387                 double mid_z = (stone_a.MaxEdge.Z+stone_a.MinEdge.Z)/2;
 388                 double mid_x = (stone_a.MaxEdge.X+stone_a.MinEdge.X)/2;
 389                 double mid_y = (stone_a.MaxEdge.Y+stone_a.MinEdge.Y)/2;
 390                 double dz = (double)z-mid_z;
 391                 double dx = (double)x-mid_x;
 392                 double dy = MYMAX(0, (double)y-mid_y);
 393                 double r = sqrt(dz*dz+dx*dx+dy*dy);
 394                 d /= (2*r/size)*2 + 0.01;
 395                 if(d > 1.0)
 396                 {
 397                         u32 vi = stone_a.index(v3s16(x,y,z));
 398                         stone_d[vi] = 1;
 399                 }
 400         }
 401
 402         /*// Add stone randomly
 403         for(u32 iii=0; iii<7; iii++)
 404         {
 405                 s16 d = 1;
 406
 407                 v3s16 p(
 408                         myrand_range(stone_a.MinEdge.X, stone_a.MaxEdge.X-d),
 409                         myrand_range(stone_a.MinEdge.Y, stone_a.MaxEdge.Y-d),
 410                         myrand_range(stone_a.MinEdge.Z, stone_a.MaxEdge.Z-d)
 411                 );
 412
 413                 for(s16 z=0; z<=d; z++)
 414                 for(s16 y=0; y<=d; y++)
 415                 for(s16 x=0; x<=d; x++)
 416                 {
 417                         stone_d[stone_a.index(p+v3s16(x,y,z))] = 1;
 418                 }
 419         }*/
 420
 421         // Blit stone to vmanip
 422         for(s16 z=stone_a.MinEdge.Z; z<=stone_a.MaxEdge.Z; z++)
 423         for(s16 y=stone_a.MinEdge.Y; y<=stone_a.MaxEdge.Y; y++)
 424         for(s16 x=stone_a.MinEdge.X; x<=stone_a.MaxEdge.X; x++)
 425         {
 426                 v3s16 p(x,y,z);
 427                 p += p0;
 428                 if(vmanip.m_area.contains(p) == false)
 429                         continue;
 430                 u32 vi = vmanip.m_area.index(p);
 431                 /*if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 432                                 && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 433                         continue;*/
 434                 u32 i = stone_a.index(x,y,z);
 435                 if(stone_d[i] == 1)
 436                         vmanip.m_data[vi] = stonenode;
 437         }
 438 }
 439 #endif
 440
 441 /*
 442         Dungeon making routines
 443 */
 444
 445 #define VMANIP_FLAG_DUNGEON_INSIDE VOXELFLAG_CHECKED1
 446 #define VMANIP_FLAG_DUNGEON_PRESERVE VOXELFLAG_CHECKED2
 447 #define VMANIP_FLAG_DUNGEON_UNTOUCHABLE (\
 448                 VMANIP_FLAG_DUNGEON_INSIDE|VMANIP_FLAG_DUNGEON_PRESERVE)
 449
 450 static void make_room1(VoxelManipulator &vmanip, v3s16 roomsize, v3s16 roomplace)
 451 {
 452         // Make +-X walls
 453         for(s16 z=0; z<roomsize.Z; z++)
 454         for(s16 y=0; y<roomsize.Y; y++)
 455         {
 456                 {
 457                         v3s16 p = roomplace + v3s16(0,y,z);
 458                         if(vmanip.m_area.contains(p) == false)
 459                                 continue;
 460                         u32 vi = vmanip.m_area.index(p);
 461                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 462                                 continue;
 463                         vmanip.m_data[vi] = MapNode(CONTENT_COBBLE);
 464                 }
 465                 {
 466                         v3s16 p = roomplace + v3s16(roomsize.X-1,y,z);
 467                         if(vmanip.m_area.contains(p) == false)
 468                                 continue;
 469                         u32 vi = vmanip.m_area.index(p);
 470                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 471                                 continue;
 472                         vmanip.m_data[vi] = MapNode(CONTENT_COBBLE);
 473                 }
 474         }
 475
 476         // Make +-Z walls
 477         for(s16 x=0; x<roomsize.X; x++)
 478         for(s16 y=0; y<roomsize.Y; y++)
 479         {
 480                 {
 481                         v3s16 p = roomplace + v3s16(x,y,0);
 482                         if(vmanip.m_area.contains(p) == false)
 483                                 continue;
 484                         u32 vi = vmanip.m_area.index(p);
 485                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 486                                 continue;
 487                         vmanip.m_data[vi] = MapNode(CONTENT_COBBLE);
 488                 }
 489                 {
 490                         v3s16 p = roomplace + v3s16(x,y,roomsize.Z-1);
 491                         if(vmanip.m_area.contains(p) == false)
 492                                 continue;
 493                         u32 vi = vmanip.m_area.index(p);
 494                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 495                                 continue;
 496                         vmanip.m_data[vi] = MapNode(CONTENT_COBBLE);
 497                 }
 498         }
 499
 500         // Make +-Y walls (floor and ceiling)
 501         for(s16 z=0; z<roomsize.Z; z++)
 502         for(s16 x=0; x<roomsize.X; x++)
 503         {
 504                 {
 505                         v3s16 p = roomplace + v3s16(x,0,z);
 506                         if(vmanip.m_area.contains(p) == false)
 507                                 continue;
 508                         u32 vi = vmanip.m_area.index(p);
 509                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 510                                 continue;
 511                         vmanip.m_data[vi] = MapNode(CONTENT_COBBLE);
 512                 }
 513                 {
 514                         v3s16 p = roomplace + v3s16(x,roomsize.Y-1,z);
 515                         if(vmanip.m_area.contains(p) == false)
 516                                 continue;
 517                         u32 vi = vmanip.m_area.index(p);
 518                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_UNTOUCHABLE)
 519                                 continue;
 520                         vmanip.m_data[vi] = MapNode(CONTENT_COBBLE);
 521                 }
 522         }
 523
 524         // Fill with air
 525         for(s16 z=1; z<roomsize.Z-1; z++)
 526         for(s16 y=1; y<roomsize.Y-1; y++)
 527         for(s16 x=1; x<roomsize.X-1; x++)
 528         {
 529                 v3s16 p = roomplace + v3s16(x,y,z);
 530                 if(vmanip.m_area.contains(p) == false)
 531                         continue;
 532                 u32 vi = vmanip.m_area.index(p);
 533                 vmanip.m_flags[vi] |= VMANIP_FLAG_DUNGEON_UNTOUCHABLE;
 534                 vmanip.m_data[vi] = MapNode(CONTENT_AIR);
 535         }
 536 }
 537
 538 static void make_fill(VoxelManipulator &vmanip, v3s16 place, v3s16 size,
 539                 u8 avoid_flags, MapNode n, u8 or_flags)
 540 {
 541         for(s16 z=0; z<size.Z; z++)
 542         for(s16 y=0; y<size.Y; y++)
 543         for(s16 x=0; x<size.X; x++)
 544         {
 545                 v3s16 p = place + v3s16(x,y,z);
 546                 if(vmanip.m_area.contains(p) == false)
 547                         continue;
 548                 u32 vi = vmanip.m_area.index(p);
 549                 if(vmanip.m_flags[vi] & avoid_flags)
 550                         continue;
 551                 vmanip.m_flags[vi] |= or_flags;
 552                 vmanip.m_data[vi] = n;
 553         }
 554 }
 555
 556 static void make_hole1(VoxelManipulator &vmanip, v3s16 place)
 557 {
 558         make_fill(vmanip, place, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 559                         VMANIP_FLAG_DUNGEON_INSIDE);
 560 }
 561
 562 static void make_door1(VoxelManipulator &vmanip, v3s16 doorplace, v3s16 doordir)
 563 {
 564         make_hole1(vmanip, doorplace);
 565         // Place torch (for testing)
 566         //vmanip.m_data[vmanip.m_area.index(doorplace)] = MapNode(CONTENT_TORCH);
 567 }
 568
 569 static v3s16 rand_ortho_dir(PseudoRandom &random)
 570 {
 571         if(random.next()%2==0)
 572                 return random.next()%2 ? v3s16(-1,0,0) : v3s16(1,0,0);
 573         else
 574                 return random.next()%2 ? v3s16(0,0,-1) : v3s16(0,0,1);
 575 }
 576
 577 static v3s16 turn_xz(v3s16 olddir, int t)
 578 {
 579         v3s16 dir;
 580         if(t == 0)
 581         {
 582                 // Turn right
 583                 dir.X = olddir.Z;
 584                 dir.Z = -olddir.X;
 585                 dir.Y = olddir.Y;
 586         }
 587         else
 588         {
 589                 // Turn left
 590                 dir.X = -olddir.Z;
 591                 dir.Z = olddir.X;
 592                 dir.Y = olddir.Y;
 593         }
 594         return dir;
 595 }
 596
 597 static v3s16 random_turn(PseudoRandom &random, v3s16 olddir)
 598 {
 599         int turn = random.range(0,2);
 600         v3s16 dir;
 601         if(turn == 0)
 602         {
 603                 // Go straight
 604                 dir = olddir;
 605         }
 606         else if(turn == 1)
 607                 // Turn right
 608                 dir = turn_xz(olddir, 0);
 609         else
 610                 // Turn left
 611                 dir = turn_xz(olddir, 1);
 612         return dir;
 613 }
 614
 615 static void make_corridor(VoxelManipulator &vmanip, v3s16 doorplace,
 616                 v3s16 doordir, v3s16 &result_place, v3s16 &result_dir,
 617                 PseudoRandom &random)
 618 {
 619         make_hole1(vmanip, doorplace);
 620         v3s16 p0 = doorplace;
 621         v3s16 dir = doordir;
 622         u32 length;
 623         if(random.next()%2)
 624                 length = random.range(1,13);
 625         else
 626                 length = random.range(1,6);
 627         length = random.range(1,13);
 628         u32 partlength = random.range(1,13);
 629         u32 partcount = 0;
 630         s16 make_stairs = 0;
 631         if(random.next()%2 == 0 && partlength >= 3)
 632                 make_stairs = random.next()%2 ? 1 : -1;
 633         for(u32 i=0; i<length; i++)
 634         {
 635                 v3s16 p = p0 + dir;
 636                 if(partcount != 0)
 637                         p.Y += make_stairs;
 638
 639                 /*// If already empty
 640                 if(vmanip.getNodeNoExNoEmerge(p).getContent()
 641                                 == CONTENT_AIR
 642                 && vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 643                                 == CONTENT_AIR)
 644                 {
 645                 }*/
 646
 647                 if(vmanip.m_area.contains(p) == true
 648                                 && vmanip.m_area.contains(p+v3s16(0,1,0)) == true)
 649                 {
 650                         if(make_stairs)
 651                         {
 652                                 make_fill(vmanip, p+v3s16(-1,-1,-1), v3s16(3,5,3),
 653                                                 VMANIP_FLAG_DUNGEON_UNTOUCHABLE, MapNode(CONTENT_COBBLE), 0);
 654                                 make_fill(vmanip, p, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 655                                                 VMANIP_FLAG_DUNGEON_INSIDE);
 656                                 make_fill(vmanip, p-dir, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 657                                                 VMANIP_FLAG_DUNGEON_INSIDE);
 658                         }
 659                         else
 660                         {
 661                                 make_fill(vmanip, p+v3s16(-1,-1,-1), v3s16(3,4,3),
 662                                                 VMANIP_FLAG_DUNGEON_UNTOUCHABLE, MapNode(CONTENT_COBBLE), 0);
 663                                 make_hole1(vmanip, p);
 664                                 /*make_fill(vmanip, p, v3s16(1,2,1), 0, MapNode(CONTENT_AIR),
 665                                                 VMANIP_FLAG_DUNGEON_INSIDE);*/
 666                         }
 667
 668                         p0 = p;
 669                 }
 670                 else
 671                 {
 672                         // Can't go here, turn away
 673                         dir = turn_xz(dir, random.range(0,1));
 674                         make_stairs = -make_stairs;
 675                         partcount = 0;
 676                         partlength = random.range(1,length);
 677                         continue;
 678                 }
 679
 680                 partcount++;
 681                 if(partcount >= partlength)
 682                 {
 683                         partcount = 0;
 684
 685                         dir = random_turn(random, dir);
 686
 687                         partlength = random.range(1,length);
 688
 689                         make_stairs = 0;
 690                         if(random.next()%2 == 0 && partlength >= 3)
 691                                 make_stairs = random.next()%2 ? 1 : -1;
 692                 }
 693         }
 694         result_place = p0;
 695         result_dir = dir;
 696 }
 697
 698 class RoomWalker
 699 {
 700 public:
 701
 702         RoomWalker(VoxelManipulator &vmanip_, v3s16 pos, PseudoRandom &random):
 703                         vmanip(vmanip_),
 704                         m_pos(pos),
 705                         m_random(random)
 706         {
 707                 randomizeDir();
 708         }
 709
 710         void randomizeDir()
 711         {
 712                 m_dir = rand_ortho_dir(m_random);
 713         }
 714
 715         void setPos(v3s16 pos)
 716         {
 717                 m_pos = pos;
 718         }
 719
 720         void setDir(v3s16 dir)
 721         {
 722                 m_dir = dir;
 723         }
 724
 725         bool findPlaceForDoor(v3s16 &result_place, v3s16 &result_dir)
 726         {
 727                 for(u32 i=0; i<100; i++)
 728                 {
 729                         v3s16 p = m_pos + m_dir;
 730                         v3s16 p1 = p + v3s16(0,1,0);
 731                         if(vmanip.m_area.contains(p) == false
 732                                         || vmanip.m_area.contains(p1) == false
 733                                         || i % 4 == 0)
 734                         {
 735                                 randomizeDir();
 736                                 continue;
 737                         }
 738                         if(vmanip.getNodeNoExNoEmerge(p).getContent()
 739                                         == CONTENT_COBBLE
 740                         && vmanip.getNodeNoExNoEmerge(p1).getContent()
 741                                         == CONTENT_COBBLE)
 742                         {
 743                                 // Found wall, this is a good place!
 744                                 result_place = p;
 745                                 result_dir = m_dir;
 746                                 // Randomize next direction
 747                                 randomizeDir();
 748                                 return true;
 749                         }
 750                         /*
 751                                 Determine where to move next
 752                         */
 753                         // Jump one up if the actual space is there
 754                         if(vmanip.getNodeNoExNoEmerge(p+v3s16(0,0,0)).getContent()
 755                                         == CONTENT_COBBLE
 756                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 757                                         == CONTENT_AIR
 758                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,2,0)).getContent()
 759                                         == CONTENT_AIR)
 760                                 p += v3s16(0,1,0);
 761                         // Jump one down if the actual space is there
 762                         if(vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 763                                         == CONTENT_COBBLE
 764                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,0,0)).getContent()
 765                                         == CONTENT_AIR
 766                         && vmanip.getNodeNoExNoEmerge(p+v3s16(0,-1,0)).getContent()
 767                                         == CONTENT_AIR)
 768                                 p += v3s16(0,-1,0);
 769                         // Check if walking is now possible
 770                         if(vmanip.getNodeNoExNoEmerge(p).getContent()
 771                                         != CONTENT_AIR
 772                         || vmanip.getNodeNoExNoEmerge(p+v3s16(0,1,0)).getContent()
 773                                         != CONTENT_AIR)
 774                         {
 775                                 // Cannot continue walking here
 776                                 randomizeDir();
 777                                 continue;
 778                         }
 779                         // Move there
 780                         m_pos = p;
 781                 }
 782                 return false;
 783         }
 784
 785         bool findPlaceForRoomDoor(v3s16 roomsize, v3s16 &result_doorplace,
 786                         v3s16 &result_doordir, v3s16 &result_roomplace)
 787         {
 788                 for(s16 trycount=0; trycount<30; trycount++)
 789                 {
 790                         v3s16 doorplace;
 791                         v3s16 doordir;
 792                         bool r = findPlaceForDoor(doorplace, doordir);
 793                         if(r == false)
 794                                 continue;
 795                         v3s16 roomplace;
 796                         // X east, Z north, Y up
 797 #if 1
 798                         if(doordir == v3s16(1,0,0)) // X+
 799                                 roomplace = doorplace +
 800                                                 v3s16(0,-1,m_random.range(-roomsize.Z+2,-2));
 801                         if(doordir == v3s16(-1,0,0)) // X-
 802                                 roomplace = doorplace +
 803                                                 v3s16(-roomsize.X+1,-1,m_random.range(-roomsize.Z+2,-2));
 804                         if(doordir == v3s16(0,0,1)) // Z+
 805                                 roomplace = doorplace +
 806                                                 v3s16(m_random.range(-roomsize.X+2,-2),-1,0);
 807                         if(doordir == v3s16(0,0,-1)) // Z-
 808                                 roomplace = doorplace +
 809                                                 v3s16(m_random.range(-roomsize.X+2,-2),-1,-roomsize.Z+1);
 810 #endif
 811 #if 0
 812                         if(doordir == v3s16(1,0,0)) // X+
 813                                 roomplace = doorplace + v3s16(0,-1,-roomsize.Z/2);
 814                         if(doordir == v3s16(-1,0,0)) // X-
 815                                 roomplace = doorplace + v3s16(-roomsize.X+1,-1,-roomsize.Z/2);
 816                         if(doordir == v3s16(0,0,1)) // Z+
 817                                 roomplace = doorplace + v3s16(-roomsize.X/2,-1,0);
 818                         if(doordir == v3s16(0,0,-1)) // Z-
 819                                 roomplace = doorplace + v3s16(-roomsize.X/2,-1,-roomsize.Z+1);
 820 #endif
 821
 822                         // Check fit
 823                         bool fits = true;
 824                         for(s16 z=1; z<roomsize.Z-1; z++)
 825                         for(s16 y=1; y<roomsize.Y-1; y++)
 826                         for(s16 x=1; x<roomsize.X-1; x++)
 827                         {
 828                                 v3s16 p = roomplace + v3s16(x,y,z);
 829                                 if(vmanip.m_area.contains(p) == false)
 830                                 {
 831                                         fits = false;
 832                                         break;
 833                                 }
 834                                 if(vmanip.m_flags[vmanip.m_area.index(p)]
 835                                                 & VMANIP_FLAG_DUNGEON_INSIDE)
 836                                 {
 837                                         fits = false;
 838                                         break;
 839                                 }
 840                         }
 841                         if(fits == false)
 842                         {
 843                                 // Find new place
 844                                 continue;
 845                         }
 846                         result_doorplace = doorplace;
 847                         result_doordir = doordir;
 848                         result_roomplace = roomplace;
 849                         return true;
 850                 }
 851                 return false;
 852         }
 853
 854 private:
 855         VoxelManipulator &vmanip;
 856         v3s16 m_pos;
 857         v3s16 m_dir;
 858         PseudoRandom &m_random;
 859 };
 860
 861 static void make_dungeon1(VoxelManipulator &vmanip, PseudoRandom &random)
 862 {
 863         v3s16 areasize = vmanip.m_area.getExtent();
 864         v3s16 roomsize;
 865         v3s16 roomplace;
 866
 867         /*
 868                 Find place for first room
 869         */
 870         bool fits = false;
 871         for(u32 i=0; i<100; i++)
 872         {
 873                 roomsize = v3s16(random.range(4,8),random.range(4,6),random.range(4,8));
 874                 roomplace = vmanip.m_area.MinEdge + v3s16(
 875                                 random.range(0,areasize.X-roomsize.X-1),
 876                                 random.range(0,areasize.Y-roomsize.Y-1),
 877                                 random.range(0,areasize.Z-roomsize.Z-1));
 878                 /*
 879                         Check that we're not putting the room to an unknown place,
 880                         otherwise it might end up floating in the air
 881                 */
 882                 fits = true;
 883                 for(s16 z=1; z<roomsize.Z-1; z++)
 884                 for(s16 y=1; y<roomsize.Y-1; y++)
 885                 for(s16 x=1; x<roomsize.X-1; x++)
 886                 {
 887                         v3s16 p = roomplace + v3s16(x,y,z);
 888                         u32 vi = vmanip.m_area.index(p);
 889                         if(vmanip.m_flags[vi] & VMANIP_FLAG_DUNGEON_INSIDE)
 890                         {
 891                                 fits = false;
 892                                 break;
 893                         }
 894                         if(vmanip.m_data[vi].getContent() == CONTENT_IGNORE)
 895                         {
 896                                 fits = false;
 897                                 break;
 898                         }
 899                 }
 900                 if(fits)
 901                         break;
 902         }
 903         // No place found
 904         if(fits == false)
 905                 return;
 906
 907         /*
 908                 Stores the center position of the last room made, so that
 909                 a new corridor can be started from the last room instead of
 910                 the new room, if chosen so.
 911         */
 912         v3s16 last_room_center = roomplace+v3s16(roomsize.X/2,1,roomsize.Z/2);
 913
 914         u32 room_count = random.range(2,7);
 915         for(u32 i=0; i<room_count; i++)
 916         {
 917                 // Make a room to the determined place
 918                 make_room1(vmanip, roomsize, roomplace);
 919
 920                 v3s16 room_center = roomplace + v3s16(roomsize.X/2,1,roomsize.Z/2);
 921
 922                 // Place torch at room center (for testing)
 923                 //vmanip.m_data[vmanip.m_area.index(room_center)] = MapNode(CONTENT_TORCH);
 924
 925                 // Quit if last room
 926                 if(i == room_count-1)
 927                         break;
 928
 929                 // Determine walker start position
 930
 931                 bool start_in_last_room = (random.range(0,2)!=0);
 932                 //bool start_in_last_room = true;
 933
 934                 v3s16 walker_start_place;
 935
 936                 if(start_in_last_room)
 937                 {
 938                         walker_start_place = last_room_center;
 939                 }
 940                 else
 941                 {
 942                         walker_start_place = room_center;
 943                         // Store center of current room as the last one
 944                         last_room_center = room_center;
 945                 }
 946
 947                 // Create walker and find a place for a door
 948                 RoomWalker walker(vmanip, walker_start_place, random);
 949                 v3s16 doorplace;
 950                 v3s16 doordir;
 951                 bool r = walker.findPlaceForDoor(doorplace, doordir);
 952                 if(r == false)
 953                         return;
 954
 955                 if(random.range(0,1)==0)
 956                         // Make the door
 957                         make_door1(vmanip, doorplace, doordir);
 958                 else
 959                         // Don't actually make a door
 960                         doorplace -= doordir;
 961
 962                 // Make a random corridor starting from the door
 963                 v3s16 corridor_end;
 964                 v3s16 corridor_end_dir;
 965                 make_corridor(vmanip, doorplace, doordir, corridor_end,
 966                                 corridor_end_dir, random);
 967
 968                 // Find a place for a random sized room
 969                 roomsize = v3s16(random.range(4,8),random.range(4,6),random.range(4,8));
 970                 walker.setPos(corridor_end);
 971                 walker.setDir(corridor_end_dir);
 972                 r = walker.findPlaceForRoomDoor(roomsize, doorplace, doordir, roomplace);
 973                 if(r == false)
 974                         return;
 975
 976                 if(random.range(0,1)==0)
 977                         // Make the door
 978                         make_door1(vmanip, doorplace, doordir);
 979                 else
 980                         // Don't actually make a door
 981                         roomplace -= doordir;
 982
 983         }
 984 }
 985
 986 static void make_nc(VoxelManipulator &vmanip, PseudoRandom &random)
 987 {
 988         v3s16 dir;
 989         u8 facedir_i = 0;
 990         s32 r = random.range(0, 3);
 991         if(r == 0){
 992                 dir = v3s16( 1, 0, 0);
 993                 facedir_i = 3;
 994         }
 995         if(r == 1){
 996                 dir = v3s16(-1, 0, 0);
 997                 facedir_i = 1;
 998         }
 999         if(r == 2){
1000                 dir = v3s16( 0, 0, 1);
1001                 facedir_i = 2;
1002         }
1003         if(r == 3){
1004                 dir = v3s16( 0, 0,-1);
1005                 facedir_i = 0;
1006         }
1007         v3s16 p = vmanip.m_area.MinEdge + v3s16(
1008                         16+random.range(0,15),
1009                         16+random.range(0,15),
1010                         16+random.range(0,15));
1011         vmanip.m_data[vmanip.m_area.index(p)] = MapNode(CONTENT_NC, facedir_i);
1012         u32 length = random.range(3,15);
1013         for(u32 j=0; j<length; j++)
1014         {
1015                 p -= dir;
1016                 vmanip.m_data[vmanip.m_area.index(p)] = MapNode(CONTENT_NC_RB);
1017         }
1018 }
1019
1020 /*
1021         Noise functions. Make sure seed is mangled differently in each one.
1022 */
1023
1024 /*
1025         Scaling the output of the noise function affects the overdrive of the
1026         contour function, which affects the shape of the output considerably.
1027 */
1028 #define CAVE_NOISE_SCALE 12.0
1029 //#define CAVE_NOISE_SCALE 10.0
1030 //#define CAVE_NOISE_SCALE 7.5
1031 //#define CAVE_NOISE_SCALE 5.0
1032 //#define CAVE_NOISE_SCALE 1.0
1033
1034 //#define CAVE_NOISE_THRESHOLD (2.5/CAVE_NOISE_SCALE)
1035 #define CAVE_NOISE_THRESHOLD (1.5/CAVE_NOISE_SCALE)
1036
1037 NoiseParams get_cave_noise1_params(u64 seed)
1038 {
1039         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 5, 0.7,
1040                         200, CAVE_NOISE_SCALE);*/
1041         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 4, 0.7,
1042                         100, CAVE_NOISE_SCALE);*/
1043         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 5, 0.6,
1044                         100, CAVE_NOISE_SCALE);*/
1045         /*return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 5, 0.3,
1046                         100, CAVE_NOISE_SCALE);*/
1047         return NoiseParams(NOISE_PERLIN_CONTOUR, seed+52534, 4, 0.5,
1048                         50, CAVE_NOISE_SCALE);
1049         //return NoiseParams(NOISE_CONSTANT_ONE);
1050 }
1051
1052 NoiseParams get_cave_noise2_params(u64 seed)
1053 {
1054         /*return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 5, 0.7,
1055                         200, CAVE_NOISE_SCALE);*/
1056         /*return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 4, 0.7,
1057                         100, CAVE_NOISE_SCALE);*/
1058         /*return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 5, 0.3,
1059                         100, CAVE_NOISE_SCALE);*/
1060         return NoiseParams(NOISE_PERLIN_CONTOUR_FLIP_YZ, seed+10325, 4, 0.5,
1061                         50, CAVE_NOISE_SCALE);
1062         //return NoiseParams(NOISE_CONSTANT_ONE);
1063 }
1064
1065 NoiseParams get_ground_noise1_params(u64 seed)
1066 {
1067         return NoiseParams(NOISE_PERLIN, seed+983240, 4,
1068                         0.55, 80.0, 40.0);
1069 }
1070
1071 NoiseParams get_ground_crumbleness_params(u64 seed)
1072 {
1073         return NoiseParams(NOISE_PERLIN, seed+34413, 3,
1074                         1.3, 20.0, 1.0);
1075 }
1076
1077 NoiseParams get_ground_wetness_params(u64 seed)
1078 {
1079         return NoiseParams(NOISE_PERLIN, seed+32474, 4,
1080                         1.1, 40.0, 1.0);
1081 }
1082
1083 bool is_cave(u64 seed, v3s16 p)
1084 {
1085         double d1 = noise3d_param(get_cave_noise1_params(seed), p.X,p.Y,p.Z);
1086         double d2 = noise3d_param(get_cave_noise2_params(seed), p.X,p.Y,p.Z);
1087         return d1*d2 > CAVE_NOISE_THRESHOLD;
1088 }
1089
1090 /*
1091         Ground density noise shall be interpreted by using this.
1092
1093         TODO: No perlin noises here, they should be outsourced
1094               and buffered
1095                   NOTE: The speed of these actually isn't terrible
1096 */
1097 bool val_is_ground(double ground_noise1_val, v3s16 p, u64 seed)
1098 {
1099         //return ((double)p.Y < ground_noise1_val);
1100
1101         double f = 0.55 + noise2d_perlin(
1102                         0.5+(float)p.X/250, 0.5+(float)p.Z/250,
1103                         seed+920381, 3, 0.45);
1104         if(f < 0.01)
1105                 f = 0.01;
1106         else if(f >= 1.0)
1107                 f *= 1.6;
1108         double h = WATER_LEVEL + 10 * noise2d_perlin(
1109                         0.5+(float)p.X/250, 0.5+(float)p.Z/250,
1110                         seed+84174, 4, 0.5);
1111         /*double f = 1;
1112         double h = 0;*/
1113         return ((double)p.Y - h < ground_noise1_val * f);
1114 }
1115
1116 /*
1117         Queries whether a position is ground or not.
1118 */
1119 bool is_ground(u64 seed, v3s16 p)
1120 {
1121         double val1 = noise3d_param(get_ground_noise1_params(seed), p.X,p.Y,p.Z);
1122         return val_is_ground(val1, p, seed);
1123 }
1124
1125 // Amount of trees per area in nodes
1126 double tree_amount_2d(u64 seed, v2s16 p)
1127 {
1128         /*double noise = noise2d_perlin(
1129                         0.5+(float)p.X/250, 0.5+(float)p.Y/250,
1130                         seed+2, 5, 0.66);*/
1131         double noise = noise2d_perlin(
1132                         0.5+(float)p.X/125, 0.5+(float)p.Y/125,
1133                         seed+2, 4, 0.66);
1134         double zeroval = -0.39;
1135         if(noise < zeroval)
1136                 return 0;
1137         else
1138                 return 0.04 * (noise-zeroval) / (1.0-zeroval);
1139 }
1140
1141 double surface_humidity_2d(u64 seed, v2s16 p)
1142 {
1143         double noise = noise2d_perlin(
1144                         0.5+(float)p.X/500, 0.5+(float)p.Y/500,
1145                         seed+72384, 4, 0.66);
1146         noise = (noise + 1.0)/2.0;
1147         if(noise < 0.0)
1148                 noise = 0.0;
1149         if(noise > 1.0)
1150                 noise = 1.0;
1151         return noise;
1152 }
1153
1154 #if 0
1155 double randomstone_amount_2d(u64 seed, v2s16 p)
1156 {
1157         double noise = noise2d_perlin(
1158                         0.5+(float)p.X/250, 0.5+(float)p.Y/250,
1159                         seed+3829434, 5, 0.66);
1160         double zeroval = 0.1;
1161         if(noise < zeroval)
1162                 return 0;
1163         else
1164                 return 0.01 * (noise-zeroval) / (1.0-zeroval);
1165 }
1166 #endif
1167
1168 double largestone_amount_2d(u64 seed, v2s16 p)
1169 {
1170         double noise = noise2d_perlin(
1171                         0.5+(float)p.X/250, 0.5+(float)p.Y/250,
1172                         seed+14143242, 5, 0.66);
1173         double zeroval = 0.3;
1174         if(noise < zeroval)
1175                 return 0;
1176         else
1177                 return 0.005 * (noise-zeroval) / (1.0-zeroval);
1178 }
1179
1180 /*
1181         Incrementally find ground level from 3d noise
1182 */
1183 s16 find_ground_level_from_noise(u64 seed, v2s16 p2d, s16 precision)
1184 {
1185         // Start a bit fuzzy to make averaging lower precision values
1186         // more useful
1187         s16 level = myrand_range(-precision/2, precision/2);
1188         s16 dec[] = {31000, 100, 20, 4, 1, 0};
1189         s16 i;
1190         for(i = 1; dec[i] != 0 && precision <= dec[i]; i++)
1191         {
1192                 // First find non-ground by going upwards
1193                 // Don't stop in caves.
1194                 {
1195                         s16 max = level+dec[i-1]*2;
1196                         v3s16 p(p2d.X, level, p2d.Y);
1197                         for(; p.Y < max; p.Y += dec[i])
1198                         {
1199                                 if(!is_ground(seed, p))
1200                                 {
1201                                         level = p.Y;
1202                                         break;
1203                                 }
1204                         }
1205                 }
1206                 // Then find ground by going downwards from there.
1207                 // Go in caves, too, when precision is 1.
1208                 {
1209                         s16 min = level-dec[i-1]*2;
1210                         v3s16 p(p2d.X, level, p2d.Y);
1211                         for(; p.Y>min; p.Y-=dec[i])
1212                         {
1213                                 bool ground = is_ground(seed, p);
1214                                 /*if(dec[i] == 1 && is_cave(seed, p))
1215                                         ground = false;*/
1216                                 if(ground)
1217                                 {
1218                                         level = p.Y;
1219                                         break;
1220                                 }
1221                         }
1222                 }
1223         }
1224
1225         // This is more like the actual ground level
1226         level += dec[i-1]/2;
1227
1228         return level;
1229 }
1230
1231 double get_sector_average_ground_level(u64 seed, v2s16 sectorpos, double p=4);
1232
1233 double get_sector_average_ground_level(u64 seed, v2s16 sectorpos, double p)
1234 {
1235         v2s16 node_min = sectorpos*MAP_BLOCKSIZE;
1236         v2s16 node_max = (sectorpos+v2s16(1,1))*MAP_BLOCKSIZE-v2s16(1,1);
1237         double a = 0;
1238         a += find_ground_level_from_noise(seed,
1239                         v2s16(node_min.X, node_min.Y), p);
1240         a += find_ground_level_from_noise(seed,
1241                         v2s16(node_min.X, node_max.Y), p);
1242         a += find_ground_level_from_noise(seed,
1243                         v2s16(node_max.X, node_max.Y), p);
1244         a += find_ground_level_from_noise(seed,
1245                         v2s16(node_max.X, node_min.Y), p);
1246         a += find_ground_level_from_noise(seed,
1247                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y+MAP_BLOCKSIZE/2), p);
1248         a /= 5;
1249         return a;
1250 }
1251
1252 double get_sector_maximum_ground_level(u64 seed, v2s16 sectorpos, double p=4);
1253
1254 double get_sector_maximum_ground_level(u64 seed, v2s16 sectorpos, double p)
1255 {
1256         v2s16 node_min = sectorpos*MAP_BLOCKSIZE;
1257         v2s16 node_max = (sectorpos+v2s16(1,1))*MAP_BLOCKSIZE-v2s16(1,1);
1258         double a = -31000;
1259         // Corners
1260         a = MYMAX(a, find_ground_level_from_noise(seed,
1261                         v2s16(node_min.X, node_min.Y), p));
1262         a = MYMAX(a, find_ground_level_from_noise(seed,
1263                         v2s16(node_min.X, node_max.Y), p));
1264         a = MYMAX(a, find_ground_level_from_noise(seed,
1265                         v2s16(node_max.X, node_max.Y), p));
1266         a = MYMAX(a, find_ground_level_from_noise(seed,
1267                         v2s16(node_min.X, node_min.Y), p));
1268         // Center
1269         a = MYMAX(a, find_ground_level_from_noise(seed,
1270                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y+MAP_BLOCKSIZE/2), p));
1271         // Side middle points
1272         a = MYMAX(a, find_ground_level_from_noise(seed,
1273                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y), p));
1274         a = MYMAX(a, find_ground_level_from_noise(seed,
1275                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_max.Y), p));
1276         a = MYMAX(a, find_ground_level_from_noise(seed,
1277                         v2s16(node_min.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1278         a = MYMAX(a, find_ground_level_from_noise(seed,
1279                         v2s16(node_max.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1280         return a;
1281 }
1282
1283 double get_sector_minimum_ground_level(u64 seed, v2s16 sectorpos, double p=4);
1284
1285 double get_sector_minimum_ground_level(u64 seed, v2s16 sectorpos, double p)
1286 {
1287         v2s16 node_min = sectorpos*MAP_BLOCKSIZE;
1288         v2s16 node_max = (sectorpos+v2s16(1,1))*MAP_BLOCKSIZE-v2s16(1,1);
1289         double a = 31000;
1290         // Corners
1291         a = MYMIN(a, find_ground_level_from_noise(seed,
1292                         v2s16(node_min.X, node_min.Y), p));
1293         a = MYMIN(a, find_ground_level_from_noise(seed,
1294                         v2s16(node_min.X, node_max.Y), p));
1295         a = MYMIN(a, find_ground_level_from_noise(seed,
1296                         v2s16(node_max.X, node_max.Y), p));
1297         a = MYMIN(a, find_ground_level_from_noise(seed,
1298                         v2s16(node_min.X, node_min.Y), p));
1299         // Center
1300         a = MYMIN(a, find_ground_level_from_noise(seed,
1301                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y+MAP_BLOCKSIZE/2), p));
1302         // Side middle points
1303         a = MYMIN(a, find_ground_level_from_noise(seed,
1304                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_min.Y), p));
1305         a = MYMIN(a, find_ground_level_from_noise(seed,
1306                         v2s16(node_min.X+MAP_BLOCKSIZE/2, node_max.Y), p));
1307         a = MYMIN(a, find_ground_level_from_noise(seed,
1308                         v2s16(node_min.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1309         a = MYMIN(a, find_ground_level_from_noise(seed,
1310                         v2s16(node_max.X, node_min.Y+MAP_BLOCKSIZE/2), p));
1311         return a;
1312 }
1313
1314 bool block_is_underground(u64 seed, v3s16 blockpos)
1315 {
1316         s16 minimum_groundlevel = (s16)get_sector_minimum_ground_level(
1317                         seed, v2s16(blockpos.X, blockpos.Z));
1318
1319         if(blockpos.Y*MAP_BLOCKSIZE + MAP_BLOCKSIZE <= minimum_groundlevel)
1320                 return true;
1321         else
1322                 return false;
1323 }
1324
1325 #if 0
1326 #define AVERAGE_MUD_AMOUNT 4
1327
1328 double base_rock_level_2d(u64 seed, v2s16 p)
1329 {
1330         // The base ground level
1331         double base = (double)WATER_LEVEL - (double)AVERAGE_MUD_AMOUNT
1332                         + 20. * noise2d_perlin(
1333                         0.5+(float)p.X/500., 0.5+(float)p.Y/500.,
1334                         (seed>>32)+654879876, 6, 0.6);
1335
1336         /*// A bit hillier one
1337         double base2 = WATER_LEVEL - 4.0 + 40. * noise2d_perlin(
1338                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1339                         (seed>>27)+90340, 6, 0.69);
1340         if(base2 > base)
1341                 base = base2;*/
1342 #if 1
1343         // Higher ground level
1344         double higher = (double)WATER_LEVEL + 25. + 35. * noise2d_perlin(
1345                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1346                         seed+85039, 5, 0.69);
1347         //higher = 30; // For debugging
1348
1349         // Limit higher to at least base
1350         if(higher < base)
1351                 higher = base;
1352
1353         // Steepness factor of cliffs
1354         double b = 1.0 + 1.0 * noise2d_perlin(
1355                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1356                         seed-932, 7, 0.7);
1357         b = rangelim(b, 0.0, 1000.0);
1358         b = pow(b, 5);
1359         b *= 7;
1360         b = rangelim(b, 3.0, 1000.0);
1361         //dstream<<"b="<<b<<std::endl;
1362         //double b = 20;
1363
1364         // Offset to more low
1365         double a_off = -0.2;
1366         // High/low selector
1367         /*double a = 0.5 + b * (a_off + noise2d_perlin(
1368                         0.5+(float)p.X/500., 0.5+(float)p.Y/500.,
1369                         seed-359, 6, 0.7));*/
1370         double a = (double)0.5 + b * (a_off + noise2d_perlin(
1371                         0.5+(float)p.X/250., 0.5+(float)p.Y/250.,
1372                         seed-359, 5, 0.60));
1373         // Limit
1374         a = rangelim(a, 0.0, 1.0);
1375
1376         //dstream<<"a="<<a<<std::endl;
1377
1378         double h = base*(1.0-a) + higher*a;
1379 #else
1380         double h = base;
1381 #endif
1382         return h;
1383 }
1384
1385 double get_mud_add_amount(u64 seed, v2s16 p)
1386 {
1387         return ((float)AVERAGE_MUD_AMOUNT + 3.0 * noise2d_perlin(
1388                         0.5+(float)p.X/200, 0.5+(float)p.Y/200,
1389                         seed+91013, 3, 0.55));
1390 }
1391 #endif
1392
1393 bool get_have_sand(u64 seed, v2s16 p2d)
1394 {
1395         // Determine whether to have sand here
1396         double sandnoise = noise2d_perlin(
1397                         0.5+(float)p2d.X/500, 0.5+(float)p2d.Y/500,
1398                         seed+59420, 3, 0.50);
1399
1400         return (sandnoise > -0.15);
1401 }
1402
1403 /*
1404         Adds random objects to block, depending on the content of the block
1405 */
1406 void add_random_objects(MapBlock *block)
1407 {
1408         for(s16 z0=0; z0<MAP_BLOCKSIZE; z0++)
1409         for(s16 x0=0; x0<MAP_BLOCKSIZE; x0++)
1410         {
1411                 bool last_node_walkable = false;
1412                 for(s16 y0=0; y0<MAP_BLOCKSIZE; y0++)
1413                 {
1414                         v3s16 p(x0,y0,z0);
1415                         MapNode n = block->getNodeNoEx(p);
1416                         if(n.getContent() == CONTENT_IGNORE)
1417                                 continue;
1418                         if(content_features(n).liquid_type != LIQUID_NONE)
1419                                 continue;
1420                         if(content_features(n).walkable)
1421                         {
1422                                 last_node_walkable = true;
1423                                 continue;
1424                         }
1425                         if(last_node_walkable)
1426                         {
1427                                 // If block contains light information
1428                                 if(content_features(n).param_type == CPT_LIGHT)
1429                                 {
1430                                         if(n.getLight(LIGHTBANK_DAY) <= 3)
1431                                         {
1432                                                 if(myrand() % 300 == 0)
1433                                                 {
1434                                                         v3f pos_f = intToFloat(p+block->getPosRelative(), BS);
1435                                                         pos_f.Y -= BS*0.4;
1436                                                         ServerActiveObject *obj = new RatSAO(NULL, 0, pos_f);
1437                                                         std::string data = obj->getStaticData();
1438                                                         StaticObject s_obj(obj->getType(),
1439                                                                         obj->getBasePosition(), data);
1440                                                         // Add some
1441                                                         block->m_static_objects.insert(0, s_obj);
1442                                                         block->m_static_objects.insert(0, s_obj);
1443                                                         block->m_static_objects.insert(0, s_obj);
1444                                                         block->m_static_objects.insert(0, s_obj);
1445                                                         block->m_static_objects.insert(0, s_obj);
1446                                                         block->m_static_objects.insert(0, s_obj);
1447                                                         delete obj;
1448                                                 }
1449                                                 if(myrand() % 1000 == 0)
1450                                                 {
1451                                                         v3f pos_f = intToFloat(p+block->getPosRelative(), BS);
1452                                                         pos_f.Y -= BS*0.4;
1453                                                         ServerActiveObject *obj = new Oerkki1SAO(NULL,0,pos_f);
1454                                                         std::string data = obj->getStaticData();
1455                                                         StaticObject s_obj(obj->getType(),
1456                                                                         obj->getBasePosition(), data);
1457                                                         // Add one
1458                                                         block->m_static_objects.insert(0, s_obj);
1459                                                         delete obj;
1460                                                 }
1461                                         }
1462                                 }
1463                         }
1464                         last_node_walkable = false;
1465                 }
1466         }
1467         block->setChangedFlag();
1468 }
1469
1470 void make_block(BlockMakeData *data)
1471 {
1472         if(data->no_op)
1473         {
1474                 //dstream<<"makeBlock: no-op"<<std::endl;
1475                 return;
1476         }
1477
1478         v3s16 blockpos = data->blockpos;
1479
1480         /*dstream<<"makeBlock(): ("<<blockpos.X<<","<<blockpos.Y<<","
1481                         <<blockpos.Z<<")"<<std::endl;*/
1482
1483         ManualMapVoxelManipulator &vmanip = *(data->vmanip);
1484         v3s16 blockpos_min = blockpos - v3s16(1,1,1);
1485         v3s16 blockpos_max = blockpos + v3s16(1,1,1);
1486         // Area of center block
1487         v3s16 node_min = blockpos*MAP_BLOCKSIZE;
1488         v3s16 node_max = (blockpos+v3s16(1,1,1))*MAP_BLOCKSIZE-v3s16(1,1,1);
1489         // Full allocated area
1490         v3s16 full_node_min = (blockpos-1)*MAP_BLOCKSIZE;
1491         v3s16 full_node_max = (blockpos+2)*MAP_BLOCKSIZE-v3s16(1,1,1);
1492         // Area of a block
1493         double block_area_nodes = MAP_BLOCKSIZE*MAP_BLOCKSIZE;
1494
1495         v2s16 p2d_center(node_min.X+MAP_BLOCKSIZE/2, node_min.Z+MAP_BLOCKSIZE/2);
1496
1497         /*
1498                 Get average ground level from noise
1499         */
1500
1501         s16 approx_groundlevel = (s16)get_sector_average_ground_level(
1502                         data->seed, v2s16(blockpos.X, blockpos.Z));
1503         //dstream<<"approx_groundlevel="<<approx_groundlevel<<std::endl;
1504
1505         s16 approx_ground_depth = approx_groundlevel - (node_min.Y+MAP_BLOCKSIZE/2);
1506
1507         s16 minimum_groundlevel = (s16)get_sector_minimum_ground_level(
1508                         data->seed, v2s16(blockpos.X, blockpos.Z));
1509         // Minimum amount of ground above the top of the central block
1510         s16 minimum_ground_depth = minimum_groundlevel - node_max.Y;
1511
1512         s16 maximum_groundlevel = (s16)get_sector_maximum_ground_level(
1513                         data->seed, v2s16(blockpos.X, blockpos.Z), 1);
1514         // Maximum amount of ground above the bottom of the central block
1515         s16 maximum_ground_depth = maximum_groundlevel - node_min.Y;
1516
1517         #if 0
1518         /*
1519                 Special case for high air or water: Just fill with air and water.
1520         */
1521         if(maximum_ground_depth < -20)
1522         {
1523                 for(s16 x=node_min.X; x<=node_max.X; x++)
1524                 for(s16 z=node_min.Z; z<=node_max.Z; z++)
1525                 {
1526                         // Node position
1527                         v2s16 p2d(x,z);
1528                         {
1529                                 // Use fast index incrementing
1530                                 v3s16 em = vmanip.m_area.getExtent();
1531                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, node_min.Y, p2d.Y));
1532                                 for(s16 y=node_min.Y; y<=node_max.Y; y++)
1533                                 {
1534                                         // Only modify places that have no content
1535                                         if(vmanip.m_data[i].getContent() == CONTENT_IGNORE)
1536                                         {
1537                                                 if(y <= WATER_LEVEL)
1538                                                         vmanip.m_data[i] = MapNode(CONTENT_WATERSOURCE);
1539                                                 else
1540                                                         vmanip.m_data[i] = MapNode(CONTENT_AIR);
1541                                         }
1542
1543                                         data->vmanip->m_area.add_y(em, i, 1);
1544                                 }
1545                         }
1546                 }
1547
1548                 // We're done
1549                 return;
1550         }
1551         #endif
1552
1553         /*
1554                 If block is deep underground, this is set to true and ground
1555                 density noise is not generated, for speed optimization.
1556         */
1557         bool all_is_ground_except_caves = (minimum_ground_depth > 40);
1558
1559         /*
1560                 Create a block-specific seed
1561         */
1562         u32 blockseed = (u32)(data->seed%0x100000000ULL) + full_node_min.Z*38134234
1563                         + full_node_min.Y*42123 + full_node_min.X*23;
1564
1565         /*
1566                 Make some 3D noise
1567         */
1568
1569         //NoiseBuffer noisebuf1;
1570         //NoiseBuffer noisebuf2;
1571         NoiseBuffer noisebuf_cave;
1572         NoiseBuffer noisebuf_ground;
1573         NoiseBuffer noisebuf_ground_crumbleness;
1574         NoiseBuffer noisebuf_ground_wetness;
1575         {
1576                 v3f minpos_f(node_min.X, node_min.Y, node_min.Z);
1577                 v3f maxpos_f(node_max.X, node_max.Y, node_max.Z);
1578
1579                 //TimeTaker timer("noisebuf.create");
1580
1581                 /*
1582                         Cave noise
1583                 */
1584 #if 1
1585                 noisebuf_cave.create(get_cave_noise1_params(data->seed),
1586                                 minpos_f.X, minpos_f.Y, minpos_f.Z,
1587                                 maxpos_f.X, maxpos_f.Y, maxpos_f.Z,
1588                                 2, 2, 2);
1589                 noisebuf_cave.multiply(get_cave_noise2_params(data->seed));
1590 #endif
1591
1592                 /*
1593                         Ground noise
1594                 */
1595
1596                 // Sample length
1597                 v3f sl = v3f(4.0, 4.0, 4.0);
1598
1599                 /*
1600                         Density noise
1601                 */
1602                 if(all_is_ground_except_caves == false)
1603                         //noisebuf_ground.create(data->seed+983240, 6, 0.60, false,
1604                         noisebuf_ground.create(get_ground_noise1_params(data->seed),
1605                                         minpos_f.X, minpos_f.Y, minpos_f.Z,
1606                                         maxpos_f.X, maxpos_f.Y, maxpos_f.Z,
1607                                         sl.X, sl.Y, sl.Z);
1608
1609                 /*
1610                         Ground property noise
1611                 */
1612                 sl = v3f(2.5, 2.5, 2.5);
1613                 noisebuf_ground_crumbleness.create(
1614                                 get_ground_crumbleness_params(data->seed),
1615                                 minpos_f.X, minpos_f.Y, minpos_f.Z,
1616                                 maxpos_f.X, maxpos_f.Y+5, maxpos_f.Z,
1617                                 sl.X, sl.Y, sl.Z);
1618                 noisebuf_ground_wetness.create(
1619                                 get_ground_wetness_params(data->seed),
1620                                 minpos_f.X, minpos_f.Y, minpos_f.Z,
1621                                 maxpos_f.X, maxpos_f.Y+5, maxpos_f.Z,
1622                                 sl.X, sl.Y, sl.Z);
1623         }
1624
1625         /*
1626                 Make base ground level
1627         */
1628
1629         for(s16 x=node_min.X; x<=node_max.X; x++)
1630         for(s16 z=node_min.Z; z<=node_max.Z; z++)
1631         {
1632                 // Node position
1633                 v2s16 p2d(x,z);
1634                 {
1635                         // Use fast index incrementing
1636                         v3s16 em = vmanip.m_area.getExtent();
1637                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_min.Y, p2d.Y));
1638                         for(s16 y=node_min.Y; y<=node_max.Y; y++)
1639                         {
1640                                 // Only modify places that have no content
1641                                 if(vmanip.m_data[i].getContent() == CONTENT_IGNORE)
1642                                 {
1643                                         // First priority: make air and water.
1644                                         // This avoids caves inside water.
1645                                         if(all_is_ground_except_caves == false
1646                                                         && val_is_ground(noisebuf_ground.get(x,y,z),
1647                                                         v3s16(x,y,z), data->seed) == false)
1648                                         {
1649                                                 if(y <= WATER_LEVEL)
1650                                                         vmanip.m_data[i] = MapNode(CONTENT_WATERSOURCE);
1651                                                 else
1652                                                         vmanip.m_data[i] = MapNode(CONTENT_AIR);
1653                                         }
1654                                         else if(noisebuf_cave.get(x,y,z) > CAVE_NOISE_THRESHOLD)
1655                                                 vmanip.m_data[i] = MapNode(CONTENT_AIR);
1656                                         else
1657                                                 vmanip.m_data[i] = MapNode(CONTENT_STONE);
1658                                 }
1659
1660                                 data->vmanip->m_area.add_y(em, i, 1);
1661                         }
1662                 }
1663         }
1664
1665         /*
1666                 Add minerals
1667         */
1668
1669         {
1670                 PseudoRandom mineralrandom(blockseed);
1671
1672                 /*
1673                         Add meseblocks
1674                 */
1675                 for(s16 i=0; i<approx_ground_depth/4; i++)
1676                 {
1677                         if(mineralrandom.next()%50 == 0)
1678                         {
1679                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
1680                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
1681                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
1682                                 for(u16 i=0; i<27; i++)
1683                                 {
1684                                         v3s16 p = v3s16(x,y,z) + g_27dirs[i];
1685                                         u32 vi = vmanip.m_area.index(p);
1686                                         if(vmanip.m_data[vi].getContent() == CONTENT_STONE)
1687                                                 if(mineralrandom.next()%8 == 0)
1688                                                         vmanip.m_data[vi] = MapNode(CONTENT_MESE);
1689                                 }
1690
1691                         }
1692                 }
1693                 /*
1694                         Add others
1695                 */
1696                 {
1697                         u16 a = mineralrandom.range(0,15);
1698                         a = a*a*a;
1699                         u16 amount = 20 * a/1000;
1700                         for(s16 i=0; i<amount; i++)
1701                         {
1702                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
1703                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
1704                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
1705
1706                                 u8 base_content = CONTENT_STONE;
1707                                 MapNode new_content(CONTENT_IGNORE);
1708                                 u32 sparseness = 6;
1709
1710                                 if(noisebuf_ground_crumbleness.get(x,y+5,z) < -0.1)
1711                                 {
1712                                         new_content = MapNode(CONTENT_STONE, MINERAL_COAL);
1713                                 }
1714                                 else
1715                                 {
1716                                         if(noisebuf_ground_wetness.get(x,y+5,z) > 0.0)
1717                                                 new_content = MapNode(CONTENT_STONE, MINERAL_IRON);
1718                                         /*if(noisebuf_ground_wetness.get(x,y,z) > 0.0)
1719                                                 vmanip.m_data[i] = MapNode(CONTENT_MUD);
1720                                         else
1721                                                 vmanip.m_data[i] = MapNode(CONTENT_SAND);*/
1722                                 }
1723                                 /*else if(noisebuf_ground_crumbleness.get(x,y,z) > 0.1)
1724                                 {
1725                                 }*/
1726
1727                                 if(new_content.getContent() != CONTENT_IGNORE)
1728                                 {
1729                                         for(u16 i=0; i<27; i++)
1730                                         {
1731                                                 v3s16 p = v3s16(x,y,z) + g_27dirs[i];
1732                                                 u32 vi = vmanip.m_area.index(p);
1733                                                 if(vmanip.m_data[vi].getContent() == base_content)
1734                                                 {
1735                                                         if(mineralrandom.next()%sparseness == 0)
1736                                                                 vmanip.m_data[vi] = new_content;
1737                                                 }
1738                                         }
1739                                 }
1740                         }
1741                 }
1742                 /*
1743                         Add coal
1744                 */
1745                 //for(s16 i=0; i < MYMAX(0, 50 - abs(node_min.Y+8 - (-30))); i++)
1746                 //for(s16 i=0; i<50; i++)
1747                 u16 coal_amount = 30;
1748                 u16 coal_rareness = 60 / coal_amount;
1749                 if(coal_rareness == 0)
1750                         coal_rareness = 1;
1751                 if(mineralrandom.next()%coal_rareness == 0)
1752                 {
1753                         u16 a = mineralrandom.next() % 16;
1754                         u16 amount = coal_amount * a*a*a / 1000;
1755                         for(s16 i=0; i<amount; i++)
1756                         {
1757                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
1758                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
1759                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
1760                                 for(u16 i=0; i<27; i++)
1761                                 {
1762                                         v3s16 p = v3s16(x,y,z) + g_27dirs[i];
1763                                         u32 vi = vmanip.m_area.index(p);
1764                                         if(vmanip.m_data[vi].getContent() == CONTENT_STONE)
1765                                                 if(mineralrandom.next()%8 == 0)
1766                                                         vmanip.m_data[vi] = MapNode(CONTENT_STONE, MINERAL_COAL);
1767                                 }
1768                         }
1769                 }
1770                 /*
1771                         Add iron
1772                 */
1773                 u16 iron_amount = 8;
1774                 u16 iron_rareness = 60 / iron_amount;
1775                 if(iron_rareness == 0)
1776                         iron_rareness = 1;
1777                 if(mineralrandom.next()%iron_rareness == 0)
1778                 {
1779                         u16 a = mineralrandom.next() % 16;
1780                         u16 amount = iron_amount * a*a*a / 1000;
1781                         for(s16 i=0; i<amount; i++)
1782                         {
1783                                 s16 x = mineralrandom.range(node_min.X+1, node_max.X-1);
1784                                 s16 y = mineralrandom.range(node_min.Y+1, node_max.Y-1);
1785                                 s16 z = mineralrandom.range(node_min.Z+1, node_max.Z-1);
1786                                 for(u16 i=0; i<27; i++)
1787                                 {
1788                                         v3s16 p = v3s16(x,y,z) + g_27dirs[i];
1789                                         u32 vi = vmanip.m_area.index(p);
1790                                         if(vmanip.m_data[vi].getContent() == CONTENT_STONE)
1791                                                 if(mineralrandom.next()%8 == 0)
1792                                                         vmanip.m_data[vi] = MapNode(CONTENT_STONE, MINERAL_IRON);
1793                                 }
1794                         }
1795                 }
1796         }
1797
1798         /*
1799                 Add mud and sand and others underground (in place of stone)
1800         */
1801
1802         for(s16 x=node_min.X; x<=node_max.X; x++)
1803         for(s16 z=node_min.Z; z<=node_max.Z; z++)
1804         {
1805                 // Node position
1806                 v2s16 p2d(x,z);
1807                 {
1808                         // Use fast index incrementing
1809                         v3s16 em = vmanip.m_area.getExtent();
1810                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_max.Y, p2d.Y));
1811                         for(s16 y=node_max.Y; y>=node_min.Y; y--)
1812                         {
1813                                 if(vmanip.m_data[i].getContent() == CONTENT_STONE)
1814                                 {
1815                                         if(noisebuf_ground_crumbleness.get(x,y,z) > 1.3)
1816                                         {
1817                                                 if(noisebuf_ground_wetness.get(x,y,z) > 0.0)
1818                                                         vmanip.m_data[i] = MapNode(CONTENT_MUD);
1819                                                 else
1820                                                         vmanip.m_data[i] = MapNode(CONTENT_SAND);
1821                                         }
1822                                         else if(noisebuf_ground_crumbleness.get(x,y,z) > 0.7)
1823                                         {
1824                                                 if(noisebuf_ground_wetness.get(x,y,z) < -0.6)
1825                                                         vmanip.m_data[i] = MapNode(CONTENT_GRAVEL);
1826                                         }
1827                                         else if(noisebuf_ground_crumbleness.get(x,y,z) <
1828                                                         -3.0 + MYMIN(0.1 * sqrt((float)MYMAX(0, -y)), 1.5))
1829                                         {
1830                                                 vmanip.m_data[i] = MapNode(CONTENT_LAVASOURCE);
1831                                                 for(s16 x1=-1; x1<=1; x1++)
1832                                                 for(s16 y1=-1; y1<=1; y1++)
1833                                                 for(s16 z1=-1; z1<=1; z1++)
1834                                                         data->transforming_liquid.push_back(
1835                                                                         v3s16(p2d.X+x1, y+y1, p2d.Y+z1));
1836                                         }
1837                                 }
1838
1839                                 data->vmanip->m_area.add_y(em, i, -1);
1840                         }
1841                 }
1842         }
1843
1844         /*
1845                 Add dungeons
1846         */
1847
1848         //if(node_min.Y < approx_groundlevel)
1849         //if(myrand() % 3 == 0)
1850         //if(myrand() % 3 == 0 && node_min.Y < approx_groundlevel)
1851         //if(myrand() % 100 == 0 && node_min.Y < approx_groundlevel)
1852         //float dungeon_rarity = g_settings.getFloat("dungeon_rarity");
1853         float dungeon_rarity = 0.02;
1854         if(((noise3d(blockpos.X,blockpos.Y,blockpos.Z,data->seed)+1.0)/2.0)
1855                         < dungeon_rarity
1856                         && node_min.Y < approx_groundlevel)
1857         {
1858                 // Dungeon generator doesn't modify places which have this set
1859                 data->vmanip->clearFlag(VMANIP_FLAG_DUNGEON_INSIDE
1860                                 | VMANIP_FLAG_DUNGEON_PRESERVE);
1861
1862                 // Set all air and water to be untouchable to make dungeons open
1863                 // to caves and open air
1864                 for(s16 x=full_node_min.X; x<=full_node_max.X; x++)
1865                 for(s16 z=full_node_min.Z; z<=full_node_max.Z; z++)
1866                 {
1867                         // Node position
1868                         v2s16 p2d(x,z);
1869                         {
1870                                 // Use fast index incrementing
1871                                 v3s16 em = vmanip.m_area.getExtent();
1872                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, full_node_max.Y, p2d.Y));
1873                                 for(s16 y=full_node_max.Y; y>=full_node_min.Y; y--)
1874                                 {
1875                                         if(vmanip.m_data[i].getContent() == CONTENT_AIR)
1876                                                 vmanip.m_flags[i] |= VMANIP_FLAG_DUNGEON_PRESERVE;
1877                                         else if(vmanip.m_data[i].getContent() == CONTENT_WATERSOURCE)
1878                                                 vmanip.m_flags[i] |= VMANIP_FLAG_DUNGEON_PRESERVE;
1879                                         data->vmanip->m_area.add_y(em, i, -1);
1880                                 }
1881                         }
1882                 }
1883
1884                 PseudoRandom random(blockseed+2);
1885
1886                 // Add it
1887                 make_dungeon1(vmanip, random);
1888
1889                 // Convert some cobble to mossy cobble
1890                 for(s16 x=full_node_min.X; x<=full_node_max.X; x++)
1891                 for(s16 z=full_node_min.Z; z<=full_node_max.Z; z++)
1892                 {
1893                         // Node position
1894                         v2s16 p2d(x,z);
1895                         {
1896                                 // Use fast index incrementing
1897                                 v3s16 em = vmanip.m_area.getExtent();
1898                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, full_node_max.Y, p2d.Y));
1899                                 for(s16 y=full_node_max.Y; y>=full_node_min.Y; y--)
1900                                 {
1901                                         // (noisebuf not used because it doesn't contain the
1902                                         //  full area)
1903                                         double wetness = noise3d_param(
1904                                                         get_ground_wetness_params(data->seed), x,y,z);
1905                                         double d = noise3d_perlin((float)x/2.5,
1906                                                         (float)y/2.5,(float)z/2.5,
1907                                                         blockseed, 2, 1.4);
1908                                         if(vmanip.m_data[i].getContent() == CONTENT_COBBLE)
1909                                         {
1910                                                 if(d < wetness/3.0)
1911                                                 {
1912                                                         vmanip.m_data[i].setContent(CONTENT_MOSSYCOBBLE);
1913                                                 }
1914                                         }
1915                                         /*else if(vmanip.m_flags[i] & VMANIP_FLAG_DUNGEON_INSIDE)
1916                                         {
1917                                                 if(wetness > 1.2)
1918                                                         vmanip.m_data[i].setContent(CONTENT_MUD);
1919                                         }*/
1920                                         data->vmanip->m_area.add_y(em, i, -1);
1921                                 }
1922                         }
1923                 }
1924         }
1925
1926         /*
1927                 Add NC
1928         */
1929         {
1930                 PseudoRandom ncrandom(blockseed+9324342);
1931                 if(ncrandom.range(0, 1000) == 0 && blockpos.Y <= -3)
1932                 {
1933                         make_nc(vmanip, ncrandom);
1934                 }
1935         }
1936
1937         /*
1938                 Add top and bottom side of water to transforming_liquid queue
1939         */
1940
1941         for(s16 x=node_min.X; x<=node_max.X; x++)
1942         for(s16 z=node_min.Z; z<=node_max.Z; z++)
1943         {
1944                 // Node position
1945                 v2s16 p2d(x,z);
1946                 {
1947                         bool water_found = false;
1948                         // Use fast index incrementing
1949                         v3s16 em = vmanip.m_area.getExtent();
1950                         u32 i = vmanip.m_area.index(v3s16(p2d.X, node_max.Y, p2d.Y));
1951                         for(s16 y=node_max.Y; y>=node_min.Y; y--)
1952                         {
1953                                 if(water_found == false)
1954                                 {
1955                                         if(vmanip.m_data[i].getContent() == CONTENT_WATERSOURCE)
1956                                         {
1957                                                 v3s16 p = v3s16(p2d.X, y, p2d.Y);
1958                                                 data->transforming_liquid.push_back(p);
1959                                                 water_found = true;
1960                                         }
1961                                 }
1962                                 else
1963                                 {
1964                                         // This can be done because water_found can only
1965                                         // turn to true and end up here after going through
1966                                         // a single block.
1967                                         if(vmanip.m_data[i+1].getContent() != CONTENT_WATERSOURCE)
1968                                         {
1969                                                 v3s16 p = v3s16(p2d.X, y+1, p2d.Y);
1970                                                 data->transforming_liquid.push_back(p);
1971                                                 water_found = false;
1972                                         }
1973                                 }
1974
1975                                 data->vmanip->m_area.add_y(em, i, -1);
1976                         }
1977                 }
1978         }
1979
1980         /*
1981                 If close to ground level
1982         */
1983
1984         //if(abs(approx_ground_depth) < 30)
1985         if(minimum_ground_depth < 5 && maximum_ground_depth > -5)
1986         {
1987                 /*
1988                         Add grass and mud
1989                 */
1990
1991                 for(s16 x=node_min.X; x<=node_max.X; x++)
1992                 for(s16 z=node_min.Z; z<=node_max.Z; z++)
1993                 {
1994                         // Node position
1995                         v2s16 p2d(x,z);
1996                         {
1997                                 bool possibly_have_sand = get_have_sand(data->seed, p2d);
1998                                 bool have_sand = false;
1999                                 u32 current_depth = 0;
2000                                 bool air_detected = false;
2001                                 bool water_detected = false;
2002                                 bool have_clay = false;
2003
2004                                 // Use fast index incrementing
2005                                 s16 start_y = node_max.Y+2;
2006                                 v3s16 em = vmanip.m_area.getExtent();
2007                                 u32 i = vmanip.m_area.index(v3s16(p2d.X, start_y, p2d.Y));
2008                                 for(s16 y=start_y; y>=node_min.Y-3; y--)
2009                                 {
2010                                         if(vmanip.m_data[i].getContent() == CONTENT_WATERSOURCE)
2011                                                 water_detected = true;
2012                                         if(vmanip.m_data[i].getContent() == CONTENT_AIR)
2013                                                 air_detected = true;
2014
2015                                         if((vmanip.m_data[i].getContent() == CONTENT_STONE
2016                                                         || vmanip.m_data[i].getContent() == CONTENT_GRASS
2017                                                         || vmanip.m_data[i].getContent() == CONTENT_MUD
2018                                                         || vmanip.m_data[i].getContent() == CONTENT_SAND
2019                                                         || vmanip.m_data[i].getContent() == CONTENT_GRAVEL
2020                                                         ) && (air_detected || water_detected))
2021                                         {
2022                                                 if(current_depth == 0 && y <= WATER_LEVEL+2
2023                                                                 && possibly_have_sand)
2024                                                         have_sand = true;
2025
2026                                                 if(current_depth < 4)
2027                                                 {
2028                                                         if(have_sand)
2029                                                         {
2030                                                                 // Determine whether to have clay in the sand here
2031                                                                 double claynoise = noise2d_perlin(
2032                                                                                 0.5+(float)p2d.X/500, 0.5+(float)p2d.Y/500,
2033                                                                                 data->seed+4321, 6, 0.95) + 0.5;
2034
2035                                                                 have_clay = (y <= WATER_LEVEL) && (y >= WATER_LEVEL-2) && (
2036                                                                         ((claynoise > 0) && (claynoise < 0.04) && (current_depth == 0)) ||
2037                                                                         ((claynoise > 0) && (claynoise < 0.12) && (current_depth == 1))
2038                                                                         );
2039                                                                 if (have_clay)
2040                                                                         vmanip.m_data[i] = MapNode(CONTENT_CLAY);
2041                                                                 else
2042                                                                         vmanip.m_data[i] = MapNode(CONTENT_SAND);
2043                                                         }
2044                                                         #if 1
2045                                                         else if(current_depth==0 && !water_detected
2046                                                                         && y >= WATER_LEVEL && air_detected)
2047                                                                 vmanip.m_data[i] = MapNode(CONTENT_GRASS);
2048                                                         #endif
2049                                                         else
2050                                                                 vmanip.m_data[i] = MapNode(CONTENT_MUD);
2051                                                 }
2052                                                 else
2053                                                 {
2054                                                         if(vmanip.m_data[i].getContent() == CONTENT_MUD
2055                                                                 || vmanip.m_data[i].getContent() == CONTENT_GRASS)
2056                                                                 vmanip.m_data[i] = MapNode(CONTENT_STONE);
2057                                                 }
2058
2059                                                 current_depth++;
2060
2061                                                 if(current_depth >= 8)
2062                                                         break;
2063                                         }
2064                                         else if(current_depth != 0)
2065                                                 break;
2066
2067                                         data->vmanip->m_area.add_y(em, i, -1);
2068                                 }
2069                         }
2070                 }
2071
2072                 /*
2073                         Calculate some stuff
2074                 */
2075
2076                 float surface_humidity = surface_humidity_2d(data->seed, p2d_center);
2077                 bool is_jungle = surface_humidity > 0.75;
2078                 // Amount of trees
2079                 u32 tree_count = block_area_nodes * tree_amount_2d(data->seed, p2d_center);
2080                 if(is_jungle)
2081                         tree_count *= 5;
2082
2083                 /*
2084                         Add trees
2085                 */
2086                 PseudoRandom treerandom(blockseed);
2087                 // Put trees in random places on part of division
2088                 for(u32 i=0; i<tree_count; i++)
2089                 {
2090                         s16 x = treerandom.range(node_min.X, node_max.X);
2091                         s16 z = treerandom.range(node_min.Z, node_max.Z);
2092                         //s16 y = find_ground_level(data->vmanip, v2s16(x,z));
2093                         s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 4);
2094                         // Don't make a tree under water level
2095                         if(y < WATER_LEVEL)
2096                                 continue;
2097                         // Make sure tree fits (only trees whose starting point is
2098                         // at this block are added)
2099                         if(y < node_min.Y || y > node_max.Y)
2100                                 continue;
2101                         /*
2102                                 Find exact ground level
2103                         */
2104                         v3s16 p(x,y+6,z);
2105                         bool found = false;
2106                         for(; p.Y >= y-6; p.Y--)
2107                         {
2108                                 u32 i = data->vmanip->m_area.index(p);
2109                                 MapNode *n = &data->vmanip->m_data[i];
2110                                 if(n->getContent() != CONTENT_AIR && n->getContent() != CONTENT_WATERSOURCE && n->getContent() != CONTENT_IGNORE)
2111                                 {
2112                                         found = true;
2113                                         break;
2114                                 }
2115                         }
2116                         // If not found, handle next one
2117                         if(found == false)
2118                                 continue;
2119
2120                         {
2121                                 u32 i = data->vmanip->m_area.index(p);
2122                                 MapNode *n = &data->vmanip->m_data[i];
2123
2124                                 if(n->getContent() != CONTENT_MUD && n->getContent() != CONTENT_GRASS && n->getContent() != CONTENT_SAND)
2125                                                 continue;
2126
2127                                 // Papyrus grows only on mud and in water
2128                                 if(n->getContent() == CONTENT_MUD && y <= WATER_LEVEL)
2129                                 {
2130                                         p.Y++;
2131                                         make_papyrus(vmanip, p);
2132                                 }
2133                                 // Trees grow only on mud and grass, on land
2134                                 else if((n->getContent() == CONTENT_MUD || n->getContent() == CONTENT_GRASS) && y > WATER_LEVEL + 2)
2135                                 {
2136                                         p.Y++;
2137                                         //if(surface_humidity_2d(data->seed, v2s16(x, y)) < 0.5)
2138                                         if(is_jungle == false)
2139                                         {
2140                                                 bool is_apple_tree;
2141                                                 if(myrand_range(0,4) != 0)
2142                                                         is_apple_tree = false;
2143                                                 else
2144                                                         is_apple_tree = noise2d_perlin(
2145                                                                         0.5+(float)p.X/100, 0.5+(float)p.Z/100,
2146                                                                         data->seed+342902, 3, 0.45) > 0.2;
2147                                                 make_tree(vmanip, p, is_apple_tree);
2148                                         }
2149                                         else
2150                                                 make_jungletree(vmanip, p);
2151                                 }
2152                                 // Cactii grow only on sand, on land
2153                                 else if(n->getContent() == CONTENT_SAND && y > WATER_LEVEL + 2)
2154                                 {
2155                                         p.Y++;
2156                                         make_cactus(vmanip, p);
2157                                 }
2158                         }
2159                 }
2160
2161                 /*
2162                         Add jungle grass
2163                 */
2164                 if(is_jungle)
2165                 {
2166                         PseudoRandom grassrandom(blockseed);
2167                         for(u32 i=0; i<surface_humidity*5*tree_count; i++)
2168                         {
2169                                 s16 x = grassrandom.range(node_min.X, node_max.X);
2170                                 s16 z = grassrandom.range(node_min.Z, node_max.Z);
2171                                 s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 4);
2172                                 if(y < WATER_LEVEL)
2173                                         continue;
2174                                 if(y < node_min.Y || y > node_max.Y)
2175                                         continue;
2176                                 /*
2177                                         Find exact ground level
2178                                 */
2179                                 v3s16 p(x,y+6,z);
2180                                 bool found = false;
2181                                 for(; p.Y >= y-6; p.Y--)
2182                                 {
2183                                         u32 i = data->vmanip->m_area.index(p);
2184                                         MapNode *n = &data->vmanip->m_data[i];
2185                                         if(content_features(*n).is_ground_content
2186                                                         || n->getContent() == CONTENT_JUNGLETREE)
2187                                         {
2188                                                 found = true;
2189                                                 break;
2190                                         }
2191                                 }
2192                                 // If not found, handle next one
2193                                 if(found == false)
2194                                         continue;
2195                                 p.Y++;
2196                                 if(vmanip.m_area.contains(p) == false)
2197                                         continue;
2198                                 if(vmanip.m_data[vmanip.m_area.index(p)].getContent() != CONTENT_AIR)
2199                                         continue;
2200                                 /*p.Y--;
2201                                 if(vmanip.m_area.contains(p))
2202                                         vmanip.m_data[vmanip.m_area.index(p)] = CONTENT_MUD;
2203                                 p.Y++;*/
2204                                 if(vmanip.m_area.contains(p))
2205                                         vmanip.m_data[vmanip.m_area.index(p)] = CONTENT_JUNGLEGRASS;
2206                         }
2207                 }
2208
2209 #if 0
2210                 /*
2211                         Add some kind of random stones
2212                 */
2213
2214                 u32 random_stone_count = block_area_nodes *
2215                                 randomstone_amount_2d(data->seed, p2d_center);
2216                 // Put in random places on part of division
2217                 for(u32 i=0; i<random_stone_count; i++)
2218                 {
2219                         s16 x = myrand_range(node_min.X, node_max.X);
2220                         s16 z = myrand_range(node_min.Z, node_max.Z);
2221                         s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 1);
2222                         // Don't add under water level
2223                         /*if(y < WATER_LEVEL)
2224                                 continue;*/
2225                         // Don't add if doesn't belong to this block
2226                         if(y < node_min.Y || y > node_max.Y)
2227                                 continue;
2228                         v3s16 p(x,y,z);
2229                         // Filter placement
2230                         /*{
2231                                 u32 i = data->vmanip->m_area.index(v3s16(p));
2232                                 MapNode *n = &data->vmanip->m_data[i];
2233                                 if(n->getContent() != CONTENT_MUD && n->getContent() != CONTENT_GRASS)
2234                                         continue;
2235                         }*/
2236                         // Will be placed one higher
2237                         p.Y++;
2238                         // Add it
2239                         make_randomstone(data->vmanip, p);
2240                 }
2241 #endif
2242
2243 #if 0
2244                 /*
2245                         Add larger stones
2246                 */
2247
2248                 u32 large_stone_count = block_area_nodes *
2249                                 largestone_amount_2d(data->seed, p2d_center);
2250                 //u32 large_stone_count = 1;
2251                 // Put in random places on part of division
2252                 for(u32 i=0; i<large_stone_count; i++)
2253                 {
2254                         s16 x = myrand_range(node_min.X, node_max.X);
2255                         s16 z = myrand_range(node_min.Z, node_max.Z);
2256                         s16 y = find_ground_level_from_noise(data->seed, v2s16(x,z), 1);
2257                         // Don't add under water level
2258                         /*if(y < WATER_LEVEL)
2259                                 continue;*/
2260                         // Don't add if doesn't belong to this block
2261                         if(y < node_min.Y || y > node_max.Y)
2262                                 continue;
2263                         v3s16 p(x,y,z);
2264                         // Filter placement
2265                         /*{
2266                                 u32 i = data->vmanip->m_area.index(v3s16(p));
2267                                 MapNode *n = &data->vmanip->m_data[i];
2268                                 if(n->getContent() != CONTENT_MUD && n->getContent() != CONTENT_GRASS)
2269                                         continue;
2270                         }*/
2271                         // Will be placed one lower
2272                         p.Y--;
2273                         // Add it
2274                         make_largestone(data->vmanip, p);
2275                 }
2276 #endif
2277         }
2278
2279 }
2280
2281 BlockMakeData::BlockMakeData():
2282         no_op(false),
2283         vmanip(NULL),
2284         seed(0)
2285 {}
2286
2287 BlockMakeData::~BlockMakeData()
2288 {
2289         delete vmanip;
2290 }
2291
2292 }; // namespace mapgen
2293
2294