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