src/mapgen_fractal.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2015 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
   4 Copyright (C) 2010-2015 paramat, Matt Gregory
   5
   6 This program is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU Lesser General Public License as published by
   8 the Free Software Foundation; either version 2.1 of the License, or
   9 (at your option) any later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU Lesser General Public License for more details.
  15
  16 You should have received a copy of the GNU Lesser General Public License along
  17 with this program; if not, write to the Free Software Foundation, Inc.,
  18 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  19 */
  20
  21
  22 #include "mapgen.h"
  23 #include "voxel.h"
  24 #include "noise.h"
  25 #include "mapblock.h"
  26 #include "mapnode.h"
  27 #include "map.h"
  28 #include "content_sao.h"
  29 #include "nodedef.h"
  30 #include "voxelalgorithms.h"
  31 //#include "profiler.h" // For TimeTaker
  32 #include "settings.h" // For g_settings
  33 #include "emerge.h"
  34 #include "dungeongen.h"
  35 #include "cavegen.h"
  36 #include "treegen.h"
  37 #include "mg_biome.h"
  38 #include "mg_ore.h"
  39 #include "mg_decoration.h"
  40 #include "mapgen_fractal.h"
  41
  42
  43 FlagDesc flagdesc_mapgen_fractal[] = {
  44         {NULL,    0}
  45 };
  46
  47 ///////////////////////////////////////////////////////////////////////////////////////
  48
  49
  50 MapgenFractal::MapgenFractal(int mapgenid, MapgenParams *params, EmergeManager *emerge)
  51         : MapgenBasic(mapgenid, params, emerge)
  52 {
  53         this->m_emerge = emerge;
  54         this->bmgr     = emerge->biomemgr;
  55
  56         //// amount of elements to skip for the next index
  57         //// for noise/height/biome maps (not vmanip)
  58         this->ystride = csize.X;
  59
  60         this->heightmap = new s16[csize.X * csize.Z];
  61
  62         MapgenFractalParams *sp = (MapgenFractalParams *)params->sparams;
  63
  64         this->spflags    = sp->spflags;
  65         this->cave_width = sp->cave_width;
  66         this->fractal    = sp->fractal;
  67         this->iterations = sp->iterations;
  68         this->scale      = sp->scale;
  69         this->offset     = sp->offset;
  70         this->slice_w    = sp->slice_w;
  71         this->julia_x    = sp->julia_x;
  72         this->julia_y    = sp->julia_y;
  73         this->julia_z    = sp->julia_z;
  74         this->julia_w    = sp->julia_w;
  75
  76         //// 2D terrain noise
  77         noise_seabed       = new Noise(&sp->np_seabed, seed, csize.X, csize.Z);
  78         noise_filler_depth = new Noise(&sp->np_filler_depth, seed, csize.X, csize.Z);
  79
  80         MapgenBasic::np_cave1 = sp->np_cave1;
  81         MapgenBasic::np_cave2 = sp->np_cave2;
  82
  83         //// Initialize biome generator
  84         biomegen = emerge->biomemgr->createBiomeGen(
  85                 BIOMEGEN_ORIGINAL, params->bparams, csize);
  86         biomemap = biomegen->biomemap;
  87
  88         this->formula = fractal / 2 + fractal % 2;
  89         this->julia   = fractal % 2 == 0;
  90
  91         //// Resolve nodes to be used
  92         c_stone                = ndef->getId("mapgen_stone");
  93         c_water_source         = ndef->getId("mapgen_water_source");
  94         c_lava_source          = ndef->getId("mapgen_lava_source");
  95         c_desert_stone         = ndef->getId("mapgen_desert_stone");
  96         c_ice                  = ndef->getId("mapgen_ice");
  97         c_sandstone            = ndef->getId("mapgen_sandstone");
  98
  99         c_cobble               = ndef->getId("mapgen_cobble");
 100         c_stair_cobble         = ndef->getId("mapgen_stair_cobble");
 101         c_mossycobble          = ndef->getId("mapgen_mossycobble");
 102         c_sandstonebrick       = ndef->getId("mapgen_sandstonebrick");
 103         c_stair_sandstonebrick = ndef->getId("mapgen_stair_sandstonebrick");
 104
 105         if (c_ice == CONTENT_IGNORE)
 106                 c_ice = CONTENT_AIR;
 107         if (c_mossycobble == CONTENT_IGNORE)
 108                 c_mossycobble = c_cobble;
 109         if (c_stair_cobble == CONTENT_IGNORE)
 110                 c_stair_cobble = c_cobble;
 111         if (c_sandstonebrick == CONTENT_IGNORE)
 112                 c_sandstonebrick = c_sandstone;
 113         if (c_stair_sandstonebrick == CONTENT_IGNORE)
 114                 c_stair_sandstonebrick = c_sandstone;
 115 }
 116
 117
 118 MapgenFractal::~MapgenFractal()
 119 {
 120         delete noise_seabed;
 121         delete noise_filler_depth;
 122
 123         delete biomegen;
 124
 125         delete[] heightmap;
 126 }
 127
 128
 129 MapgenFractalParams::MapgenFractalParams()
 130 {
 131         spflags    = 0;
 132         cave_width = 0.3;
 133         fractal    = 1;
 134         iterations = 11;
 135         scale      = v3f(4096.0, 1024.0, 4096.0);
 136         offset     = v3f(1.79, 0.0, 0.0);
 137         slice_w    = 0.0;
 138         julia_x    = 0.33;
 139         julia_y    = 0.33;
 140         julia_z    = 0.33;
 141         julia_w    = 0.33;
 142
 143         np_seabed       = NoiseParams(-14, 9,   v3f(600, 600, 600), 41900, 5, 0.6, 2.0);
 144         np_filler_depth = NoiseParams(0,   1.2, v3f(150, 150, 150), 261,   3, 0.7, 2.0);
 145         np_cave1        = NoiseParams(0,   12,  v3f(96,  96,  96),  52534, 4, 0.5, 2.0);
 146         np_cave2        = NoiseParams(0,   12,  v3f(96,  96,  96),  10325, 4, 0.5, 2.0);
 147 }
 148
 149
 150 void MapgenFractalParams::readParams(const Settings *settings)
 151 {
 152         settings->getFlagStrNoEx("mgfractal_spflags",  spflags, flagdesc_mapgen_fractal);
 153         settings->getFloatNoEx("mgfractal_cave_width", cave_width);
 154         settings->getU16NoEx("mgfractal_fractal",      fractal);
 155         settings->getU16NoEx("mgfractal_iterations",   iterations);
 156         settings->getV3FNoEx("mgfractal_scale",        scale);
 157         settings->getV3FNoEx("mgfractal_offset",       offset);
 158         settings->getFloatNoEx("mgfractal_slice_w",    slice_w);
 159         settings->getFloatNoEx("mgfractal_julia_x",    julia_x);
 160         settings->getFloatNoEx("mgfractal_julia_y",    julia_y);
 161         settings->getFloatNoEx("mgfractal_julia_z",    julia_z);
 162         settings->getFloatNoEx("mgfractal_julia_w",    julia_w);
 163
 164         settings->getNoiseParams("mgfractal_np_seabed",       np_seabed);
 165         settings->getNoiseParams("mgfractal_np_filler_depth", np_filler_depth);
 166         settings->getNoiseParams("mgfractal_np_cave1",        np_cave1);
 167         settings->getNoiseParams("mgfractal_np_cave2",        np_cave2);
 168 }
 169
 170
 171 void MapgenFractalParams::writeParams(Settings *settings) const
 172 {
 173         settings->setFlagStr("mgfractal_spflags",  spflags, flagdesc_mapgen_fractal, U32_MAX);
 174         settings->setFloat("mgfractal_cave_width", cave_width);
 175         settings->setU16("mgfractal_fractal",      fractal);
 176         settings->setU16("mgfractal_iterations",   iterations);
 177         settings->setV3F("mgfractal_scale",        scale);
 178         settings->setV3F("mgfractal_offset",       offset);
 179         settings->setFloat("mgfractal_slice_w",    slice_w);
 180         settings->setFloat("mgfractal_julia_x",    julia_x);
 181         settings->setFloat("mgfractal_julia_y",    julia_y);
 182         settings->setFloat("mgfractal_julia_z",    julia_z);
 183         settings->setFloat("mgfractal_julia_w",    julia_w);
 184
 185         settings->setNoiseParams("mgfractal_np_seabed",       np_seabed);
 186         settings->setNoiseParams("mgfractal_np_filler_depth", np_filler_depth);
 187         settings->setNoiseParams("mgfractal_np_cave1",        np_cave1);
 188         settings->setNoiseParams("mgfractal_np_cave2",        np_cave2);
 189 }
 190
 191
 192 /////////////////////////////////////////////////////////////////
 193
 194
 195 int MapgenFractal::getSpawnLevelAtPoint(v2s16 p)
 196 {
 197         bool solid_below = false;  // Dry solid node is present below to spawn on
 198         u8 air_count = 0;  // Consecutive air nodes above the dry solid node
 199         s16 seabed_level = NoisePerlin2D(&noise_seabed->np, p.X, p.Y, seed);
 200         // Seabed can rise above water_level or might be raised to create dry land
 201         s16 search_start = MYMAX(seabed_level, water_level + 1);
 202         if (seabed_level > water_level)
 203                 solid_below = true;
 204
 205         for (s16 y = search_start; y <= search_start + 128; y++) {
 206                 if (getFractalAtPoint(p.X, y, p.Y)) {  // Fractal node
 207                         solid_below = true;
 208                         air_count = 0;
 209                 } else if (solid_below) {  // Air above solid node
 210                         air_count++;
 211                         if (air_count == 2)
 212                                 return y - 2;
 213                 }
 214         }
 215
 216         return MAX_MAP_GENERATION_LIMIT;  // Unsuitable spawn point
 217 }
 218
 219
 220 void MapgenFractal::makeChunk(BlockMakeData *data)
 221 {
 222         // Pre-conditions
 223         assert(data->vmanip);
 224         assert(data->nodedef);
 225         assert(data->blockpos_requested.X >= data->blockpos_min.X &&
 226                 data->blockpos_requested.Y >= data->blockpos_min.Y &&
 227                 data->blockpos_requested.Z >= data->blockpos_min.Z);
 228         assert(data->blockpos_requested.X <= data->blockpos_max.X &&
 229                 data->blockpos_requested.Y <= data->blockpos_max.Y &&
 230                 data->blockpos_requested.Z <= data->blockpos_max.Z);
 231
 232         this->generating = true;
 233         this->vm   = data->vmanip;
 234         this->ndef = data->nodedef;
 235         //TimeTaker t("makeChunk");
 236
 237         v3s16 blockpos_min = data->blockpos_min;
 238         v3s16 blockpos_max = data->blockpos_max;
 239         node_min = blockpos_min * MAP_BLOCKSIZE;
 240         node_max = (blockpos_max + v3s16(1, 1, 1)) * MAP_BLOCKSIZE - v3s16(1, 1, 1);
 241         full_node_min = (blockpos_min - 1) * MAP_BLOCKSIZE;
 242         full_node_max = (blockpos_max + 2) * MAP_BLOCKSIZE - v3s16(1, 1, 1);
 243
 244         blockseed = getBlockSeed2(full_node_min, seed);
 245
 246         // Generate base terrain, mountains, and ridges with initial heightmaps
 247         s16 stone_surface_max_y = generateTerrain();
 248
 249         // Create heightmap
 250         updateHeightmap(node_min, node_max);
 251
 252         // Init biome generator, place biome-specific nodes, and build biomemap
 253         biomegen->calcBiomeNoise(node_min);
 254         biomegen->getBiomes(heightmap);
 255         MgStoneType stone_type = generateBiomes();
 256
 257         if (flags & MG_CAVES)
 258                 generateCaves(stone_surface_max_y, MGFRACTAL_LARGE_CAVE_DEPTH);
 259
 260         if ((flags & MG_DUNGEONS) && (stone_surface_max_y >= node_min.Y)) {
 261                 DungeonParams dp;
 262
 263                 dp.np_rarity  = nparams_dungeon_rarity;
 264                 dp.np_density = nparams_dungeon_density;
 265                 dp.np_wetness = nparams_dungeon_wetness;
 266                 dp.c_water    = c_water_source;
 267                 if (stone_type == MGSTONE_STONE) {
 268                         dp.c_cobble = c_cobble;
 269                         dp.c_moss   = c_mossycobble;
 270                         dp.c_stair  = c_stair_cobble;
 271
 272                         dp.diagonal_dirs = false;
 273                         dp.mossratio     = 3.0;
 274                         dp.holesize      = v3s16(1, 2, 1);
 275                         dp.roomsize      = v3s16(0, 0, 0);
 276                         dp.notifytype    = GENNOTIFY_DUNGEON;
 277                 } else if (stone_type == MGSTONE_DESERT_STONE) {
 278                         dp.c_cobble = c_desert_stone;
 279                         dp.c_moss   = c_desert_stone;
 280                         dp.c_stair  = c_desert_stone;
 281
 282                         dp.diagonal_dirs = true;
 283                         dp.mossratio     = 0.0;
 284                         dp.holesize      = v3s16(2, 3, 2);
 285                         dp.roomsize      = v3s16(2, 5, 2);
 286                         dp.notifytype    = GENNOTIFY_TEMPLE;
 287                 } else if (stone_type == MGSTONE_SANDSTONE) {
 288                         dp.c_cobble = c_sandstonebrick;
 289                         dp.c_moss   = c_sandstonebrick;
 290                         dp.c_stair  = c_sandstonebrick;
 291
 292                         dp.diagonal_dirs = false;
 293                         dp.mossratio     = 0.0;
 294                         dp.holesize      = v3s16(2, 2, 2);
 295                         dp.roomsize      = v3s16(2, 0, 2);
 296                         dp.notifytype    = GENNOTIFY_DUNGEON;
 297                 }
 298
 299                 DungeonGen dgen(this, &dp);
 300                 dgen.generate(blockseed, full_node_min, full_node_max);
 301         }
 302
 303         // Generate the registered decorations
 304         if (flags & MG_DECORATIONS)
 305                 m_emerge->decomgr->placeAllDecos(this, blockseed, node_min, node_max);
 306
 307         // Generate the registered ores
 308         m_emerge->oremgr->placeAllOres(this, blockseed, node_min, node_max);
 309
 310         // Sprinkle some dust on top after everything else was generated
 311         dustTopNodes();
 312
 313         //printf("makeChunk: %dms\n", t.stop());
 314
 315         updateLiquid(&data->transforming_liquid, full_node_min, full_node_max);
 316
 317         if (flags & MG_LIGHT)
 318                 calcLighting(node_min - v3s16(0, 1, 0), node_max + v3s16(0, 1, 0),
 319                         full_node_min, full_node_max);
 320
 321         //setLighting(node_min - v3s16(1, 0, 1) * MAP_BLOCKSIZE,
 322         //                      node_max + v3s16(1, 0, 1) * MAP_BLOCKSIZE, 0xFF);
 323
 324         this->generating = false;
 325 }
 326
 327
 328 bool MapgenFractal::getFractalAtPoint(s16 x, s16 y, s16 z)
 329 {
 330         float cx, cy, cz, cw, ox, oy, oz, ow;
 331
 332         if (julia) {  // Julia set
 333                 cx = julia_x;
 334                 cy = julia_y;
 335                 cz = julia_z;
 336                 cw = julia_w;
 337                 ox = (float)x / scale.X - offset.X;
 338                 oy = (float)y / scale.Y - offset.Y;
 339                 oz = (float)z / scale.Z - offset.Z;
 340                 ow = slice_w;
 341         } else {  // Mandelbrot set
 342                 cx = (float)x / scale.X - offset.X;
 343                 cy = (float)y / scale.Y - offset.Y;
 344                 cz = (float)z / scale.Z - offset.Z;
 345                 cw = slice_w;
 346                 ox = 0.0f;
 347                 oy = 0.0f;
 348                 oz = 0.0f;
 349                 ow = 0.0f;
 350         }
 351
 352         float nx = 0.0f;
 353         float ny = 0.0f;
 354         float nz = 0.0f;
 355         float nw = 0.0f;
 356
 357         for (u16 iter = 0; iter < iterations; iter++) {
 358
 359                 if (formula == 1) {  // 4D "Roundy"
 360                         nx = ox * ox - oy * oy - oz * oz - ow * ow + cx;
 361                         ny = 2.0f * (ox * oy + oz * ow) + cy;
 362                         nz = 2.0f * (ox * oz + oy * ow) + cz;
 363                         nw = 2.0f * (ox * ow + oy * oz) + cw;
 364                 } else if (formula == 2) {  // 4D "Squarry"
 365                         nx = ox * ox - oy * oy - oz * oz - ow * ow + cx;
 366                         ny = 2.0f * (ox * oy + oz * ow) + cy;
 367                         nz = 2.0f * (ox * oz + oy * ow) + cz;
 368                         nw = 2.0f * (ox * ow - oy * oz) + cw;
 369                 } else if (formula == 3) {  // 4D "Mandy Cousin"
 370                         nx = ox * ox - oy * oy - oz * oz + ow * ow + cx;
 371                         ny = 2.0f * (ox * oy + oz * ow) + cy;
 372                         nz = 2.0f * (ox * oz + oy * ow) + cz;
 373                         nw = 2.0f * (ox * ow + oy * oz) + cw;
 374                 } else if (formula == 4) {  // 4D "Variation"
 375                         nx = ox * ox - oy * oy - oz * oz - ow * ow + cx;
 376                         ny = 2.0f * (ox * oy + oz * ow) + cy;
 377                         nz = 2.0f * (ox * oz - oy * ow) + cz;
 378                         nw = 2.0f * (ox * ow + oy * oz) + cw;
 379                 } else if (formula == 5) {  // 3D "Mandelbrot/Mandelbar"
 380                         nx = ox * ox - oy * oy - oz * oz + cx;
 381                         ny = 2.0f * ox * oy + cy;
 382                         nz = -2.0f * ox * oz + cz;
 383                 } else if (formula == 6) {  // 3D "Christmas Tree"
 384                         // Altering the formula here is necessary to avoid division by zero
 385                         if (fabs(oz) < 0.000000001f) {
 386                                 nx = ox * ox - oy * oy - oz * oz + cx;
 387                                 ny = 2.0f * oy * ox + cy;
 388                                 nz = 4.0f * oz * ox + cz;
 389                         } else {
 390                                 float a = (2.0f * ox) / (sqrt(oy * oy + oz * oz));
 391                                 nx = ox * ox - oy * oy - oz * oz + cx;
 392                                 ny = a * (oy * oy - oz * oz) + cy;
 393                                 nz = a * 2.0f * oy * oz + cz;
 394                         }
 395                 } else if (formula == 7) {  // 3D "Mandelbulb"
 396                         if (fabs(oy) < 0.000000001f) {
 397                                 nx = ox * ox - oz * oz + cx;
 398                                 ny = cy;
 399                                 nz = -2.0f * oz * sqrt(ox * ox) + cz;
 400                         } else {
 401                                 float a = 1.0f - (oz * oz) / (ox * ox + oy * oy);
 402                                 nx = (ox * ox - oy * oy) * a + cx;
 403                                 ny = 2.0f * ox * oy * a + cy;
 404                                 nz = -2.0f * oz * sqrt(ox * ox + oy * oy) + cz;
 405                         }
 406                 } else if (formula == 8) {  // 3D "Cosine Mandelbulb"
 407                         if (fabs(oy) < 0.000000001f) {
 408                                 nx = 2.0f * ox * oz + cx;
 409                                 ny = 4.0f * oy * oz + cy;
 410                                 nz = oz * oz - ox * ox - oy * oy + cz;
 411                         } else {
 412                                 float a = (2.0f * oz) / sqrt(ox * ox + oy * oy);
 413                                 nx = (ox * ox - oy * oy) * a + cx;
 414                                 ny = 2.0f * ox * oy * a + cy;
 415                                 nz = oz * oz - ox * ox - oy * oy + cz;
 416                         }
 417                 } else if (formula == 9) {  // 4D "Mandelbulb"
 418                         float rxy = sqrt(ox * ox + oy * oy);
 419                         float rxyz = sqrt(ox * ox + oy * oy + oz * oz);
 420                         if (fabs(ow) < 0.000000001f && fabs(oz) < 0.000000001f) {
 421                                 nx = (ox * ox - oy * oy) + cx;
 422                                 ny = 2.0f * ox * oy + cy;
 423                                 nz = -2.0f * rxy * oz + cz;
 424                                 nw = 2.0f * rxyz * ow + cw;
 425                         } else {
 426                                 float a = 1.0f - (ow * ow) / (rxyz * rxyz);
 427                                 float b = a * (1.0f - (oz * oz) / (rxy * rxy));
 428                                 nx = (ox * ox - oy * oy) * b + cx;
 429                                 ny = 2.0f * ox * oy * b + cy;
 430                                 nz = -2.0f * rxy * oz * a + cz;
 431                                 nw = 2.0f * rxyz * ow + cw;
 432                         }
 433                 }
 434
 435                 if (nx * nx + ny * ny + nz * nz + nw * nw > 4.0f)
 436                         return false;
 437
 438                 ox = nx;
 439                 oy = ny;
 440                 oz = nz;
 441                 ow = nw;
 442         }
 443
 444         return true;
 445 }
 446
 447
 448 s16 MapgenFractal::generateTerrain()
 449 {
 450         MapNode n_air(CONTENT_AIR);
 451         MapNode n_stone(c_stone);
 452         MapNode n_water(c_water_source);
 453
 454         s16 stone_surface_max_y = -MAX_MAP_GENERATION_LIMIT;
 455         u32 index2d = 0;
 456
 457         noise_seabed->perlinMap2D(node_min.X, node_min.Z);
 458
 459         for (s16 z = node_min.Z; z <= node_max.Z; z++) {
 460                 for (s16 y = node_min.Y - 1; y <= node_max.Y + 1; y++) {
 461                         u32 vi = vm->m_area.index(node_min.X, y, z);
 462                         for (s16 x = node_min.X; x <= node_max.X; x++, vi++, index2d++) {
 463                                 if (vm->m_data[vi].getContent() == CONTENT_IGNORE) {
 464                                         s16 seabed_height = noise_seabed->result[index2d];
 465
 466                                         if (y <= seabed_height || getFractalAtPoint(x, y, z)) {
 467                                                 vm->m_data[vi] = n_stone;
 468                                                 if (y > stone_surface_max_y)
 469                                                         stone_surface_max_y = y;
 470                                         } else if (y <= water_level) {
 471                                                 vm->m_data[vi] = n_water;
 472                                         } else {
 473                                                 vm->m_data[vi] = n_air;
 474                                         }
 475                                 }
 476                         }
 477                         index2d -= ystride;
 478                 }
 479                 index2d += ystride;
 480         }
 481
 482         return stone_surface_max_y;
 483 }