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());