summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authormadmaxoft@gmail.com <madmaxoft@gmail.com@0a769ca7-a7f5-676a-18bf-c427514a06d6>2012-07-27 18:47:55 +0200
committermadmaxoft@gmail.com <madmaxoft@gmail.com@0a769ca7-a7f5-676a-18bf-c427514a06d6>2012-07-27 18:47:55 +0200
commitb521456a01fbb89a48677109b0473968f82f2dbc (patch)
treea83ba90c51aff1c5453d8f78384bf7fc5a8a49da
parentFixed a possible crash in Ravines. (diff)
downloadcuberite-b521456a01fbb89a48677109b0473968f82f2dbc.tar
cuberite-b521456a01fbb89a48677109b0473968f82f2dbc.tar.gz
cuberite-b521456a01fbb89a48677109b0473968f82f2dbc.tar.bz2
cuberite-b521456a01fbb89a48677109b0473968f82f2dbc.tar.lz
cuberite-b521456a01fbb89a48677109b0473968f82f2dbc.tar.xz
cuberite-b521456a01fbb89a48677109b0473968f82f2dbc.tar.zst
cuberite-b521456a01fbb89a48677109b0473968f82f2dbc.zip
-rw-r--r--source/Caves.cpp654
-rw-r--r--source/Caves.h18
-rw-r--r--source/cChunkGenerator.cpp6
3 files changed, 621 insertions, 57 deletions
diff --git a/source/Caves.cpp b/source/Caves.cpp
index 1f7453389..7415dfbf1 100644
--- a/source/Caves.cpp
+++ b/source/Caves.cpp
@@ -3,9 +3,31 @@
// Implements the various cave structure generators:
// - cStructGenWormNestCaves
+// - cStructGenDualRidgeCaves
// - cStructGenMarbleCaves
// - cStructGenNetherCaves
+/*
+WormNestCave generator:
+Caves are generated in "nests" - groups of tunnels generated from a single point.
+For each chunk, all the nests that could intersect it are generated.
+For each nest, first the schematic structure is generated (tunnel from ... to ..., branch, tunnel2 from ... to ...)
+Then each tunnel is randomized by inserting points in between its ends.
+Finally each tunnel is smoothed and Bresenham-3D-ed so that it is a collection of spheres with their centers next to each other.
+When the tunnels are ready, they are simply carved into the chunk, one by one.
+To optimize, each tunnel keeps track of its bounding box, so that it can be skipped for chunks that don't intersect it.
+
+MarbleCaves generator:
+For each voxel a 3D noise function is evaluated, if the value crosses a boundary, the voxel is dug out, otherwise it is kept.
+Problem with this is the amount of CPU work needed for each chunk.
+Also the overall shape of the generated holes is unsatisfactory - there are whole "sheets" of holes in the ground.
+
+DualRidgeCaves generator:
+Instead of evaluating a single noise function, two different noise functions are multiplied. This produces
+regular tunnels instead of sheets. However due to the sheer amount of CPU work needed, the nosie functions need to be
+reduced in complexity in order for this generator to be useful, so the caves' shapes are "bubbly" at best.
+*/
+
#include "Globals.h"
#include "Caves.h"
@@ -13,14 +35,23 @@
+/// How many nests in each direction are generated for a given chunk. Must be an even number
+#define NEIGHBORHOOD_SIZE 8
+
+
+
+
+
struct cDefPoint
{
int m_BlockX;
+ int m_BlockY;
int m_BlockZ;
int m_Radius;
- cDefPoint(int a_BlockX, int a_BlockZ, int a_Radius) :
+ cDefPoint(int a_BlockX, int a_BlockY, int a_BlockZ, int a_Radius) :
m_BlockX(a_BlockX),
+ m_BlockY(a_BlockY),
m_BlockZ(a_BlockZ),
m_Radius(a_Radius)
{
@@ -33,29 +64,37 @@ typedef std::vector<cDefPoint> cDefPoints;
-/// A single non-branching tunnel
+/// A single non-branching tunnel of a WormNestCave
class cCaveTunnel
{
- cDefPoints m_Points;
+ // The bounding box, including the radii around defpoints:
+ int m_MinBlockX, m_MaxBlockX;
+ int m_MinBlockY, m_MaxBlockY;
+ int m_MinBlockZ, m_MaxBlockZ;
/// Generates the shaping defpoints for the ravine, based on the ravine block coords and noise
- void GenerateBaseDefPoints(int a_BlockX, int a_BlockZ, int a_Size, cNoise & a_Noise);
+ void Randomize(cNoise & a_Noise);
- /// Refines (adds and smooths) defpoints from a_Src into a_Dst
- void RefineDefPoints(const cDefPoints & a_Src, cDefPoints & a_Dst);
+ /// Refines (adds and smooths) defpoints from a_Src into a_Dst; returns false if no refinement possible (segments too short)
+ bool RefineDefPoints(const cDefPoints & a_Src, cDefPoints & a_Dst);
- /// Does one round of smoothing, two passes of RefineDefPoints()
+ /// Does rounds of smoothing, two passes of RefineDefPoints(), as long as they return true
void Smooth(void);
/// Linearly interpolates the points so that the maximum distance between two neighbors is max 1 block
void FinishLinear(void);
-public:
- // Coords for which the ravine was generated (not necessarily the center)
- int m_BlockX;
- int m_BlockZ;
+ /// Calculates the bounding box of the points present
+ void CalcBoundingBox(void);
- cCaveTunnel(int a_BlockStartX, int a_BlockStartZ, int a_Size, cNoise & a_Noise);
+public:
+ cDefPoints m_Points;
+
+ cCaveTunnel(
+ int a_BlockStartX, int a_BlockStartY, int a_BlockStartZ,
+ int a_BlockEndX, int a_BlockEndY, int a_BlockEndZ,
+ cNoise & a_Noise
+ );
/// Carves the tunnel into the chunk specified
void ProcessChunk(
@@ -63,6 +102,10 @@ public:
cChunkDef::BlockTypes & a_BlockTypes,
cChunkDef::HeightMap & a_HeightMap
);
+
+ #ifdef _DEBUG
+ AString ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const;
+ #endif // _DEBUG
} ;
typedef std::vector<cCaveTunnel *> cCaveTunnels;
@@ -75,7 +118,11 @@ typedef std::vector<cCaveTunnel *> cCaveTunnels;
class cStructGenWormNestCaves::cCaveSystem
{
public:
- cCaveSystem(int a_BlockX, int a_BlockZ, int a_Size, cNoise & a_Noise);
+ // The generating block position; is read directly in cStructGenWormNestCaves::GetCavesForChunk()
+ int m_BlockX;
+ int m_BlockZ;
+
+ cCaveSystem(int a_BlockX, int a_BlockZ, int a_MaxOffset, int a_Size, cNoise & a_Noise);
~cCaveSystem();
/// Carves the cave system into the chunk specified
@@ -85,12 +132,21 @@ public:
cChunkDef::HeightMap & a_HeightMap
);
+ #ifdef _DEBUG
+ AString ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const;
+ #endif // _DEBUG
+
protected:
- int m_BlockX;
- int m_BlockZ;
+ int m_Size;
cCaveTunnels m_Tunnels;
void Clear(void);
+
+ /// Generates a_Segment successive tunnels, with possible branches. Generates the same output for the same [x, y, z, a_Segments]
+ void GenerateTunnelsFromPoint(
+ int a_OriginX, int a_OriginY, int a_OriginZ,
+ cNoise & a_Noise, int a_Segments
+ );
} ;
@@ -100,27 +156,389 @@ protected:
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cCaveTunnel:
+cCaveTunnel::cCaveTunnel(
+ int a_BlockStartX, int a_BlockStartY, int a_BlockStartZ,
+ int a_BlockEndX, int a_BlockEndY, int a_BlockEndZ,
+ cNoise & a_Noise
+)
+{
+ m_Points.push_back(cDefPoint(a_BlockStartX, a_BlockStartY, a_BlockStartZ, 5));
+ m_Points.push_back(cDefPoint(a_BlockEndX, a_BlockEndY, a_BlockEndZ, 5));
+
+ if ((a_BlockStartY <= 0) && (a_BlockEndY <= 0))
+ {
+ // Don't bother detailing this cave, it's under the world anyway
+ return;
+ }
+
+ Randomize(a_Noise);
+ Smooth();
+
+ // We know that the linear finishing won't affect the bounding box, so let's calculate it now, as we have less data:
+ CalcBoundingBox();
+
+ FinishLinear();
+}
+
+
+
+
+
+void cCaveTunnel::Randomize(cNoise & a_Noise)
+{
+ // Repeat 4 times:
+ for (int i = 0; i < 4; i++)
+ {
+ // For each already present point, insert a point in between it and its predecessor, shifted randomly.
+ int PrevX = m_Points.front().m_BlockX;
+ int PrevY = m_Points.front().m_BlockY;
+ int PrevZ = m_Points.front().m_BlockZ;
+ cDefPoints Pts;
+ Pts.reserve(m_Points.size() * 2);
+ Pts.push_back(m_Points.front());
+ for (cDefPoints::const_iterator itr = m_Points.begin() + 1, end = m_Points.end(); itr != end; ++itr)
+ {
+ int len = (PrevX - itr->m_BlockX) * (PrevX - itr->m_BlockX);
+ len += (PrevY - itr->m_BlockY) * (PrevY - itr->m_BlockY);
+ len += (PrevZ - itr->m_BlockZ) * (PrevZ - itr->m_BlockZ);
+ len = 3 * (int)sqrt((double)len) / 4;
+ int x = (itr->m_BlockX + PrevX) / 2 + ((a_Noise.IntNoise3DInt(PrevX, PrevY, PrevZ + i) / 17) % (len + 1) - len / 2);
+ int y = (itr->m_BlockY + PrevY) / 2 + ((a_Noise.IntNoise3DInt(PrevY, PrevZ, PrevX + i) / 17) % (len / 2 + 1) - len / 4);
+ int z = (itr->m_BlockZ + PrevZ) / 2 + ((a_Noise.IntNoise3DInt(PrevZ, PrevX, PrevY + i) / 17) % (len + 1) - len / 2);
+ Pts.push_back(cDefPoint(x, y, z, 5));
+ Pts.push_back(*itr);
+ PrevX = itr->m_BlockX;
+ PrevY = itr->m_BlockY;
+ PrevZ = itr->m_BlockZ;
+ }
+ std::swap(Pts, m_Points);
+ }
+}
+
+
+
+
+
+bool cCaveTunnel::RefineDefPoints(const cDefPoints & a_Src, cDefPoints & a_Dst)
+{
+ // Smoothing: for each line segment, add points on its 1/4 lengths
+ bool res = false;
+ int Num = a_Src.size() - 2; // this many intermediary points
+ a_Dst.clear();
+ a_Dst.reserve(Num * 2 + 2);
+ cDefPoints::const_iterator itr = a_Src.begin() + 1;
+ a_Dst.push_back(a_Src.front());
+ int PrevX = a_Src.front().m_BlockX;
+ int PrevY = a_Src.front().m_BlockY;
+ int PrevZ = a_Src.front().m_BlockZ;
+ int PrevR = a_Src.front().m_Radius;
+ for (int i = 0; i <= Num; ++i, ++itr)
+ {
+ int dx = itr->m_BlockX - PrevX;
+ int dy = itr->m_BlockY - PrevY;
+ int dz = itr->m_BlockZ - PrevZ;
+ if (abs(dx) + abs(dz) + abs(dy) < 6)
+ {
+ // Too short a segment to smooth-subdivide into quarters
+ PrevX = itr->m_BlockX;
+ PrevY = itr->m_BlockY;
+ PrevZ = itr->m_BlockZ;
+ PrevR = itr->m_Radius;
+ continue;
+ }
+ int dr = itr->m_Radius - PrevR;
+ int Rad1 = std::max(PrevR + 1 * dr / 4, 1);
+ int Rad2 = std::max(PrevR + 3 * dr / 4, 1);
+ a_Dst.push_back(cDefPoint(PrevX + 1 * dx / 4, PrevY + 1 * dy / 4, PrevZ + 1 * dz / 4, Rad1));
+ a_Dst.push_back(cDefPoint(PrevX + 3 * dx / 4, PrevY + 3 * dy / 4, PrevZ + 3 * dz / 4, Rad2));
+ PrevX = itr->m_BlockX;
+ PrevY = itr->m_BlockY;
+ PrevZ = itr->m_BlockZ;
+ PrevR = itr->m_Radius;
+ res = true;
+ }
+ a_Dst.push_back(a_Src.back());
+ return res && (a_Src.size() < a_Dst.size());
+}
+
+
+
+
+
+void cCaveTunnel::Smooth(void)
+{
+ cDefPoints Pts;
+ while (true)
+ {
+ if (!RefineDefPoints(m_Points, Pts))
+ {
+ std::swap(Pts, m_Points);
+ return;
+ }
+ if (!RefineDefPoints(Pts, m_Points))
+ {
+ return;
+ }
+ }
+}
+
+
+
+
+
+void cCaveTunnel::FinishLinear(void)
+{
+ // For each segment, use Bresenham's 3D line algorithm to draw a "line" of defpoints
+ cDefPoints Pts;
+ std::swap(Pts, m_Points);
+
+ m_Points.reserve(Pts.size() * 3);
+ int PrevX = Pts.front().m_BlockX;
+ int PrevY = Pts.front().m_BlockY;
+ int PrevZ = Pts.front().m_BlockZ;
+ for (cDefPoints::const_iterator itr = Pts.begin() + 1, end = Pts.end(); itr != end; ++itr)
+ {
+ int x1 = itr->m_BlockX;
+ int y1 = itr->m_BlockY;
+ int z1 = itr->m_BlockZ;
+ int dx = abs(x1 - PrevX);
+ int dy = abs(y1 - PrevY);
+ int dz = abs(z1 - PrevZ);
+ int sx = (PrevX < x1) ? 1 : -1;
+ int sy = (PrevY < y1) ? 1 : -1;
+ int sz = (PrevZ < z1) ? 1 : -1;
+ int err = dx - dz;
+ int R = itr->m_Radius;
+
+ if (dx >= std::max(dy, dz)) // x dominant
+ {
+ int yd = dy - dx / 2;
+ int zd = dz - dx / 2;
+
+ while (true)
+ {
+ m_Points.push_back(cDefPoint(PrevX, PrevY, PrevZ, R));
+
+ if (PrevX == x1)
+ {
+ break;
+ }
+
+ if (yd >= 0) // move along y
+ {
+ PrevY += sy;
+ yd -= dx;
+ }
+
+ if (zd >= 0) // move along z
+ {
+ PrevZ += sz;
+ zd -= dx;
+ }
+
+ // move along x
+ PrevX += sx;
+ yd += dy;
+ zd += dz;
+ }
+ }
+ else if (dy >= std::max(dx, dz)) // y dominant
+ {
+ int xd = dx - dy / 2;
+ int zd = dz - dy / 2;
+
+ while (true)
+ {
+ m_Points.push_back(cDefPoint(PrevX, PrevY, PrevZ, R));
+
+ if (PrevY == y1)
+ {
+ break;
+ }
+
+ if (xd >= 0) // move along x
+ {
+ PrevX += sx;
+ xd -= dy;
+ }
+
+ if (zd >= 0) // move along z
+ {
+ PrevZ += sz;
+ zd -= dy;
+ }
+
+ // move along y
+ PrevY += sy;
+ xd += dx;
+ zd += dz;
+ }
+ }
+ else
+ {
+ // z dominant
+ ASSERT(dz >= std::max(dx, dy));
+ int xd = dx - dz / 2;
+ int yd = dy - dz / 2;
+
+ while (true)
+ {
+ m_Points.push_back(cDefPoint(PrevX, PrevY, PrevZ, R));
+
+ if (PrevZ == z1)
+ {
+ break;
+ }
+
+ if (xd >= 0) // move along x
+ {
+ PrevX += sx;
+ xd -= dz;
+ }
+
+ if (yd >= 0) // move along y
+ {
+ PrevY += sy;
+ yd -= dz;
+ }
+
+ // move along z
+ PrevZ += sz;
+ xd += dx;
+ yd += dy;
+ }
+ } // if (which dimension is dominant)
+ } // for itr
+}
+
+
+
+
+
+void cCaveTunnel::CalcBoundingBox(void)
+{
+ m_MinBlockX = m_MaxBlockX = m_Points.front().m_BlockX;
+ m_MinBlockY = m_MaxBlockY = m_Points.front().m_BlockY;
+ m_MinBlockZ = m_MaxBlockZ = m_Points.front().m_BlockZ;
+ for (cDefPoints::const_iterator itr = m_Points.begin() + 1, end = m_Points.end(); itr != end; ++itr)
+ {
+ m_MinBlockX = std::min(m_MinBlockX, itr->m_BlockX - itr->m_Radius);
+ m_MaxBlockX = std::max(m_MaxBlockX, itr->m_BlockX + itr->m_Radius);
+ m_MinBlockY = std::min(m_MinBlockY, itr->m_BlockY - itr->m_Radius);
+ m_MaxBlockY = std::max(m_MaxBlockY, itr->m_BlockY + itr->m_Radius);
+ m_MinBlockZ = std::min(m_MinBlockZ, itr->m_BlockZ - itr->m_Radius);
+ m_MaxBlockZ = std::max(m_MaxBlockZ, itr->m_BlockZ + itr->m_Radius);
+ } // for itr - m_Points[]
+}
+
+
+
+
+
void cCaveTunnel::ProcessChunk(
int a_ChunkX, int a_ChunkZ,
cChunkDef::BlockTypes & a_BlockTypes,
cChunkDef::HeightMap & a_HeightMap
)
{
- // TODO
+ int BaseX = a_ChunkX * cChunkDef::Width;
+ int BaseZ = a_ChunkZ * cChunkDef::Width;
+ if (
+ (BaseX > m_MaxBlockX) || (BaseX + cChunkDef::Width < m_MinBlockX) ||
+ (BaseX > m_MaxBlockX) || (BaseX + cChunkDef::Width < m_MinBlockX)
+ )
+ {
+ // Tunnel does not intersect the chunk at all, bail out
+ return;
+ }
+
+ int BlockStartX = a_ChunkX * cChunkDef::Width;
+ int BlockStartZ = a_ChunkZ * cChunkDef::Width;
+ int BlockEndX = BlockStartX + cChunkDef::Width;
+ int BlockEndZ = BlockStartZ + cChunkDef::Width;
+ for (cDefPoints::const_iterator itr = m_Points.begin(), end = m_Points.end(); itr != end; ++itr)
+ {
+ if (
+ (itr->m_BlockX + itr->m_Radius < BlockStartX) ||
+ (itr->m_BlockX - itr->m_Radius > BlockEndX) ||
+ (itr->m_BlockZ + itr->m_Radius < BlockStartZ) ||
+ (itr->m_BlockZ - itr->m_Radius > BlockEndZ)
+ )
+ {
+ // Cannot intersect, bail out early
+ continue;
+ }
+
+ // Carve out a sphere around the xyz point, m_Radius in diameter:
+ int DifX = itr->m_BlockX - BlockStartX; // substitution for faster calc
+ int DifZ = itr->m_BlockZ - BlockStartZ; // substitution for faster calc
+ for (int z = 0; z < cChunkDef::Width; z++) for (int x = 0; x < cChunkDef::Width; x++)
+ {
+ // TODO
+ } // for x, z
+
+ #ifdef _DEBUG
+ // For debugging purposes, outline the shape of the cave:
+ if (
+ (DifX >= 0) && (DifX < cChunkDef::Width) &&
+ (itr->m_BlockY > 0) && (itr->m_BlockY < cChunkDef::Height) &&
+ (DifZ >= 0) && (DifZ < cChunkDef::Width)
+ )
+ {
+ cChunkDef::SetBlock(a_BlockTypes, DifX, itr->m_BlockY, DifZ, E_BLOCK_GLOWSTONE);
+ }
+ #endif // _DEBUG
+ } // for itr - m_Points[]
}
+#ifdef _DEBUG
+AString cCaveTunnel::ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const
+{
+ AString SVG;
+ SVG.reserve(m_Points.size() * 20 + 200);
+ AppendPrintf(SVG, "<path style=\"fill:none;stroke:#%06x;stroke-width:1px;\"\nd=\"", a_Color);
+ char Prefix = 'M'; // The first point needs "M" prefix, all the others need "L"
+ for (cDefPoints::const_iterator itr = m_Points.begin(); itr != m_Points.end(); ++itr)
+ {
+ AppendPrintf(SVG, "%c %d,%d ", Prefix, a_OffsetX + itr->m_BlockX, a_OffsetZ + itr->m_BlockZ);
+ Prefix = 'L';
+ }
+ SVG.append("\"/>\n");
+ return SVG;
+}
+#endif // _DEBUG
+
+
+
+
+
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cStructGenWormNestCaves::cCaveSystem:
-cStructGenWormNestCaves::cCaveSystem::cCaveSystem(int a_BlockX, int a_BlockZ, int a_Size, cNoise & a_Noise) :
+cStructGenWormNestCaves::cCaveSystem::cCaveSystem(int a_BlockX, int a_BlockZ, int a_MaxOffset, int a_Size, cNoise & a_Noise) :
m_BlockX(a_BlockX),
- m_BlockZ(a_BlockZ)
+ m_BlockZ(a_BlockZ),
+ m_Size(a_Size)
{
- // TODO: Generate a cave system
+ int Num = 1 + a_Noise.IntNoise2DInt(a_BlockX, a_BlockZ) % 3;
+ for (int i = 0; i < Num; i++)
+ {
+ int OriginX = a_BlockX + (a_Noise.IntNoise3DInt(13 * a_BlockX, 17 * a_BlockZ, 11 * i) / 19) % a_MaxOffset;
+ int OriginZ = a_BlockZ + (a_Noise.IntNoise3DInt(17 * a_BlockX, 13 * a_BlockZ, 11 * i) / 23) % a_MaxOffset;
+ int OriginY = 20 + (a_Noise.IntNoise3DInt(19 * a_BlockX, 13 * a_BlockZ, 11 * i) / 17) % 20;
+
+ // Generate three branches from the origin point:
+ // The tunnels generated depend on X, Y, Z and Branches,
+ // for the same set of numbers it generates the same offsets!
+ // That's why we add a +1 to X in the third line
+ GenerateTunnelsFromPoint(OriginX, OriginY, OriginZ, a_Noise, 3);
+ GenerateTunnelsFromPoint(OriginX, OriginY, OriginZ, a_Noise, 2);
+ GenerateTunnelsFromPoint(OriginX + 1, OriginY, OriginZ, a_Noise, 3);
+ }
}
@@ -137,25 +555,99 @@ cStructGenWormNestCaves::cCaveSystem::~cCaveSystem()
-void cStructGenWormNestCaves::cCaveSystem::Clear(void)
+void cStructGenWormNestCaves::cCaveSystem::ProcessChunk(
+ int a_ChunkX, int a_ChunkZ,
+ cChunkDef::BlockTypes & a_BlockTypes,
+ cChunkDef::HeightMap & a_HeightMap
+)
{
- // TODO
+ for (cCaveTunnels::const_iterator itr = m_Tunnels.begin(), end = m_Tunnels.end(); itr != end; ++itr)
+ {
+ (*itr)->ProcessChunk(a_ChunkX, a_ChunkZ, a_BlockTypes, a_HeightMap);
+ } // for itr - m_Tunnels[]
}
-void cStructGenWormNestCaves::cCaveSystem::ProcessChunk(
- int a_ChunkX, int a_ChunkZ,
- cChunkDef::BlockTypes & a_BlockTypes,
- cChunkDef::HeightMap & a_HeightMap
-)
+#ifdef _DEBUG
+AString cStructGenWormNestCaves::cCaveSystem::ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const
{
+ AString SVG;
+ SVG.reserve(512 * 1024);
for (cCaveTunnels::const_iterator itr = m_Tunnels.begin(), end = m_Tunnels.end(); itr != end; ++itr)
{
- (*itr)->ProcessChunk(a_ChunkX, a_ChunkZ, a_BlockTypes, a_HeightMap);
+ SVG.append((*itr)->ExportAsSVG(a_Color, a_OffsetX, a_OffsetZ));
} // for itr - m_Tunnels[]
+
+ // Base point highlight:
+ AppendPrintf(SVG, "<path style=\"fill:none;stroke:#ff0000;stroke-width:1px;\"\nd=\"M %d,%d L %d,%d\"/>\n",
+ a_OffsetX + m_BlockX - 5, a_OffsetZ + m_BlockZ, a_OffsetX + m_BlockX + 5, a_OffsetZ + m_BlockZ
+ );
+ AppendPrintf(SVG, "<path style=\"fill:none;stroke:#ff0000;stroke-width:1px;\"\nd=\"M %d,%d L %d,%d\"/>\n",
+ a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ - 5, a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ + 5
+ );
+
+ // A gray line from the base point to the first point of the ravine, for identification:
+ AppendPrintf(SVG, "<path style=\"fill:none;stroke:#cfcfcf;stroke-width:1px;\"\nd=\"M %d,%d L %d,%d\"/>\n",
+ a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ,
+ a_OffsetX + m_Tunnels.front()->m_Points.front().m_BlockX,
+ a_OffsetZ + m_Tunnels.front()->m_Points.front().m_BlockZ
+ );
+
+ // Offset guides:
+ if (a_OffsetX > 0)
+ {
+ AppendPrintf(SVG, "<path style=\"fill:none;stroke:#0000ff;stroke-width:1px;\"\nd=\"M %d,0 L %d,1024\"/>\n",
+ a_OffsetX, a_OffsetX
+ );
+ }
+ if (a_OffsetZ > 0)
+ {
+ AppendPrintf(SVG, "<path style=\"fill:none;stroke:#0000ff;stroke-width:1px;\"\nd=\"M 0,%d L 1024,%d\"/>\n",
+ a_OffsetZ, a_OffsetZ
+ );
+ }
+
+ return SVG;
+}
+#endif // _DEBUG
+
+
+
+
+
+void cStructGenWormNestCaves::cCaveSystem::Clear(void)
+{
+ for (cCaveTunnels::const_iterator itr = m_Tunnels.begin(), end = m_Tunnels.end(); itr != end; ++itr)
+ {
+ delete *itr;
+ }
+ m_Tunnels.clear();
+}
+
+
+
+
+
+void cStructGenWormNestCaves::cCaveSystem::GenerateTunnelsFromPoint(
+ int a_OriginX, int a_OriginY, int a_OriginZ,
+ cNoise & a_Noise, int a_NumSegments
+)
+{
+ int DoubleSize = m_Size * 2;
+ for (int i = a_NumSegments - 1; i >= 0; --i)
+ {
+ int EndX = a_OriginX + (((a_Noise.IntNoise3DInt(a_OriginX, a_OriginY, a_OriginZ + 11 * a_NumSegments) / 7) % DoubleSize) - m_Size) / 2;
+ int EndY = a_OriginY + (((a_Noise.IntNoise3DInt(a_OriginY, 13 * a_NumSegments, a_OriginZ + a_OriginX) / 7) % DoubleSize) - m_Size) / 4;
+ int EndZ = a_OriginZ + (((a_Noise.IntNoise3DInt(a_OriginZ + 17 * a_NumSegments, a_OriginX, a_OriginY) / 7) % DoubleSize) - m_Size) / 2;
+ m_Tunnels.push_back(new cCaveTunnel(a_OriginX, a_OriginY, a_OriginZ, EndX, EndY, EndZ, a_Noise));
+ GenerateTunnelsFromPoint(EndX, EndY, EndZ, a_Noise, i);
+ a_OriginX = EndX;
+ a_OriginY = EndY;
+ a_OriginZ = EndZ;
+ } // for i - a_NumSegments
}
@@ -176,7 +668,7 @@ cStructGenWormNestCaves::~cStructGenWormNestCaves()
void cStructGenWormNestCaves::ClearCache(void)
{
- for (cCaves::const_iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end; ++itr)
+ for (cCaveSystems::const_iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end; ++itr)
{
delete *itr;
} // for itr - m_Cache[]
@@ -196,9 +688,9 @@ void cStructGenWormNestCaves::GenStructures(
cBlockEntityList & a_BlockEntities // Block entities may be added or deleted
)
{
- cCaves Caves;
+ cCaveSystems Caves;
GetCavesForChunk(a_ChunkX, a_ChunkZ, Caves);
- for (cCaves::const_iterator itr = Caves.begin(); itr != Caves.end(); ++itr)
+ for (cCaveSystems::const_iterator itr = Caves.begin(); itr != Caves.end(); ++itr)
{
(*itr)->ProcessChunk(a_ChunkX, a_ChunkZ, a_BlockTypes, a_HeightMap);
} // for itr - Caves[]
@@ -208,16 +700,10 @@ void cStructGenWormNestCaves::GenStructures(
-void cStructGenWormNestCaves::GetCavesForChunk(int a_ChunkX, int a_ChunkZ, cStructGenWormNestCaves::cCaves & a_Caves)
+void cStructGenWormNestCaves::GetCavesForChunk(int a_ChunkX, int a_ChunkZ, cStructGenWormNestCaves::cCaveSystems & a_Caves)
{
- // TODO: Implement proper caching
- // - don't destroy caves that are reusable
- // - don't create caves that are already in the cache
-
- ClearCache();
-
- int BaseX = a_ChunkX * cChunkDef::Width / m_Size;
- int BaseZ = a_ChunkZ * cChunkDef::Width / m_Size;
+ int BaseX = a_ChunkX * cChunkDef::Width / m_Grid;
+ int BaseZ = a_ChunkZ * cChunkDef::Width / m_Grid;
if (BaseX < 0)
{
--BaseX;
@@ -226,18 +712,92 @@ void cStructGenWormNestCaves::GetCavesForChunk(int a_ChunkX, int a_ChunkZ, cStru
{
--BaseZ;
}
- BaseX -= 4;
- BaseZ -= 4;
- for (int x = 0; x < 8; x++)
+ BaseX -= NEIGHBORHOOD_SIZE / 2;
+ BaseZ -= NEIGHBORHOOD_SIZE / 2;
+
+ // Walk the cache, move each cave system that we want into a_Caves:
+ int StartX = BaseX * m_Grid;
+ int EndX = (BaseX + NEIGHBORHOOD_SIZE + 1) * m_Grid;
+ int StartZ = BaseZ * m_Grid;
+ int EndZ = (BaseZ + NEIGHBORHOOD_SIZE + 1) * m_Grid;
+ for (cCaveSystems::const_iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end;)
{
- int RealX = (BaseX + x) * m_Size;
- for (int z = 0; z < 8; z++)
+ if (
+ ((*itr)->m_BlockX >= StartX) && ((*itr)->m_BlockX < EndX) &&
+ ((*itr)->m_BlockZ >= StartZ) && ((*itr)->m_BlockZ < EndZ)
+ )
+ {
+ // want
+ a_Caves.push_back(*itr);
+ itr = m_Cache.erase(itr);
+ }
+ else
{
- int RealZ = (BaseZ + z) * m_Size;
- m_Cache.push_back(new cCaveSystem(RealX, RealZ, m_Size, m_Noise));
+ // don't want
+ ++itr;
+ }
+ } // for itr - m_Cache[]
+
+ for (int x = 0; x < NEIGHBORHOOD_SIZE; x++)
+ {
+ int RealX = (BaseX + x) * m_Grid;
+ for (int z = 0; z < NEIGHBORHOOD_SIZE; z++)
+ {
+ int RealZ = (BaseZ + z) * m_Grid;
+ bool Found = false;
+ for (cCaveSystems::const_iterator itr = a_Caves.begin(), end = a_Caves.end(); itr != end; ++itr)
+ {
+ if (((*itr)->m_BlockX == RealX) && ((*itr)->m_BlockZ == RealZ))
+ {
+ Found = true;
+ break;
+ }
+ }
+ if (!Found)
+ {
+ a_Caves.push_back(new cCaveSystem(RealX, RealZ, m_MaxOffset, m_Size, m_Noise));
+ }
}
}
- a_Caves = m_Cache;
+
+ // Copy a_Caves into m_Cache to the beginning:
+ cCaveSystems CavesCopy(a_Caves);
+ m_Cache.splice(m_Cache.begin(), CavesCopy, CavesCopy.begin(), CavesCopy.end());
+
+ // Trim the cache if it's too long:
+ if (m_Cache.size() > 100)
+ {
+ cCaveSystems::const_iterator itr = m_Cache.begin();
+ std::advance(itr, 100);
+ for (cCaveSystems::const_iterator end = m_Cache.end(); itr != end; ++itr)
+ {
+ delete *itr;
+ }
+ itr = m_Cache.begin();
+ std::advance(itr, 100);
+ m_Cache.erase(itr, m_Cache.end());
+ }
+
+ /*
+ // Uncomment this block for debugging the caves' shapes in 2D using an SVG export
+ #ifdef _DEBUG
+ AString SVG;
+ SVG.append("<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<svg xmlns=\"http://www.w3.org/2000/svg\" width=\"1024\" height = \"1024\">\n");
+ SVG.reserve(2 * 1024 * 1024);
+ for (cCaveSystems::const_iterator itr = a_Caves.begin(), end = a_Caves.end(); itr != end; ++itr)
+ {
+ int Color = 0x10 * abs((*itr)->m_BlockX / m_Grid);
+ Color |= 0x1000 * abs((*itr)->m_BlockZ / m_Grid);
+ SVG.append((*itr)->ExportAsSVG(Color, 512, 512));
+ }
+ SVG.append("</svg>\n");
+
+ AString fnam;
+ Printf(fnam, "wnc\\%03d_%03d.svg", a_ChunkX, a_ChunkZ);
+ cFile File(fnam, cFile::fmWrite);
+ File.Write(SVG.c_str(), SVG.size());
+ #endif // _DEBUG
+ //*/
}
diff --git a/source/Caves.h b/source/Caves.h
index ec3ecdf0f..8af9974fe 100644
--- a/source/Caves.h
+++ b/source/Caves.h
@@ -78,9 +78,11 @@ class cStructGenWormNestCaves :
public cStructureGen
{
public:
- cStructGenWormNestCaves(int a_Seed, int a_Size = 128) :
+ cStructGenWormNestCaves(int a_Seed, int a_Size = 64, int a_Grid = 96, int a_MaxOffset = 128) :
m_Noise(a_Seed),
- m_Size(128)
+ m_Size(a_Size),
+ m_Grid(a_Grid),
+ m_MaxOffset(a_MaxOffset)
{
}
@@ -88,17 +90,19 @@ public:
protected:
class cCaveSystem; // fwd: Caves.cpp
- typedef std::list<cCaveSystem *> cCaves;
+ typedef std::list<cCaveSystem *> cCaveSystems;
- cNoise m_Noise;
- int m_Size; // relative size, in blocks, of the nests produced. Also used for spacing.
- cCaves m_Cache;
+ cNoise m_Noise;
+ int m_Size; // relative size of the cave systems' caves. Average number of blocks of each initial tunnel
+ int m_MaxOffset; // maximum offset of the cave nest origin from the grid cell the nest belongs to
+ int m_Grid; // average spacing of the nests
+ cCaveSystems m_Cache;
/// Clears everything from the cache
void ClearCache(void);
/// Returns all caves that *may* intersect the given chunk. All the caves are valid until the next call to this function.
- void GetCavesForChunk(int a_ChunkX, int a_ChunkZ, cCaves & a_Caves);
+ void GetCavesForChunk(int a_ChunkX, int a_ChunkZ, cCaveSystems & a_Caves);
// cStructGen override:
virtual void GenStructures(
diff --git a/source/cChunkGenerator.cpp b/source/cChunkGenerator.cpp
index 3e8a6e9e9..c6b6fc26a 100644
--- a/source/cChunkGenerator.cpp
+++ b/source/cChunkGenerator.cpp
@@ -326,13 +326,13 @@ void cChunkGenerator::InitStructureGens(cIniFile & a_IniFile)
{
m_StructureGens.push_back(new cStructGenRavines(m_Seed, 128));
}
- /*
+ //*
// TODO: Not implemented yet; need a name
- else if (NoCaseCompare(*itr, "caves") == 0)
+ else if (NoCaseCompare(*itr, "wormnestcaves") == 0)
{
m_StructureGens.push_back(new cStructGenWormNestCaves(m_Seed));
}
- */
+ //*/
else
{
LOGWARNING("Unknown structure generator: \"%s\". Ignoring.", itr->c_str());