5 files changed, 1202 insertions, 0 deletions

diff --git a/src/Generating/ComposableGenerator.cpp b/src/Generating/ComposableGenerator.cpp
index e96e9a645..6c00b5905 100644
--- a/src/Generating/ComposableGenerator.cpp
+++ b/src/Generating/ComposableGenerator.cpp
@@ -22,6 +22,7 @@
 #include "EndGen.h"
 #include "MineShafts.h"
 #include "Noise3DGenerator.h"
+#include "POCPieceGenerator.h"
 #include "Ravines.h"
 
 
@@ -364,6 +365,10 @@ void cComposableGenerator::InitFinishGens(cIniFile & a_IniFile)
 		{
 			m_FinishGens.push_back(new cStructGenOreNests(Seed));
 		}
+		else if (NoCaseCompare(*itr, "POCPieces") == 0)
+		{
+			m_FinishGens.push_back(new cPOCPieceGenerator(Seed));
+		}
 		else if (NoCaseCompare(*itr, "PreSimulator") == 0)
 		{
 			m_FinishGens.push_back(new cFinishGenPreSimulator);
diff --git a/src/Generating/POCPieceGenerator.cpp b/src/Generating/POCPieceGenerator.cpp
new file mode 100644
index 000000000..9ed4b565e
--- /dev/null
+++ b/src/Generating/POCPieceGenerator.cpp
@@ -0,0 +1,270 @@
+
+// POCPieceGenerator.cpp
+
+// Implements the cPOCPieceGenerator class representing a Proof-Of_Concept structure generator using the cPieceGenerator technique
+// The generator generates a maze of rooms at {0, 50, 0}
+
+#include "Globals.h"
+#include "POCPieceGenerator.h"
+#include "ChunkDesc.h"
+
+
+
+
+
+/** POC pieces are simple boxes that have connectors in the middle of their walls.
+Each wall has one connector, there are 3 connector types that get assigned semi-randomly.
+The piece also knows how to imprint itself in a cChunkDesc, each piece has a different color glass
+and each connector is uses a different color wool frame. */
+class cPOCPiece :
+	public cPiece
+{
+public:
+	cPOCPiece(int a_SizeXZ, int a_Height) :
+		m_SizeXZ(a_SizeXZ),
+		m_Height(a_Height)
+	{
+		m_Connectors.push_back(cConnector(m_SizeXZ / 2, a_Height / 2, 0,            0,            BLOCK_FACE_ZM));
+		m_Connectors.push_back(cConnector(m_SizeXZ / 2, a_Height / 2, m_SizeXZ - 1, 1,            BLOCK_FACE_ZP));
+		m_Connectors.push_back(cConnector(0,            a_Height / 2, m_SizeXZ / 2, 2,            BLOCK_FACE_XM));
+		m_Connectors.push_back(cConnector(m_SizeXZ - 1, a_Height - 1, m_SizeXZ / 2, m_SizeXZ % 3, BLOCK_FACE_XP));
+	}
+	
+	
+	/** Imprints the piece in the specified chunk. Assumes they intersect. */
+	void ImprintInChunk(cChunkDesc & a_ChunkDesc, const Vector3i & a_Pos, int a_NumCCWRotations)
+	{
+		int BlockX = a_ChunkDesc.GetChunkX() * cChunkDef::Width;
+		int BlockZ = a_ChunkDesc.GetChunkZ() * cChunkDef::Width;
+		Vector3i Min = a_Pos;
+		Min.Move(-BlockX, 0, -BlockZ);
+		Vector3i Max = Min;
+		Max.Move(m_SizeXZ - 1, m_Height - 1, m_SizeXZ - 1);
+		ASSERT(Min.x < cChunkDef::Width);
+		ASSERT(Min.z < cChunkDef::Width);
+		ASSERT(Max.x >= 0);
+		ASSERT(Max.z >= 0);
+		if (Min.x >= 0)
+		{
+			// Draw the XM wall:
+			a_ChunkDesc.FillRelCuboid(Min.x, Min.x, Min.y, Max.y, Min.z, Max.z, E_BLOCK_STAINED_GLASS, m_SizeXZ % 16);
+		}
+		if (Min.z >= 0)
+		{
+			// Draw the ZM wall:
+			a_ChunkDesc.FillRelCuboid(Min.x, Max.x, Min.y, Max.y, Min.z, Min.z, E_BLOCK_STAINED_GLASS, m_SizeXZ % 16);
+		}
+		if (Max.x < cChunkDef::Width)
+		{
+			// Draw the XP wall:
+			a_ChunkDesc.FillRelCuboid(Max.x, Max.x, Min.y, Max.y, Min.z, Max.z, E_BLOCK_STAINED_GLASS, m_SizeXZ % 16);
+		}
+		if (Max.z < cChunkDef::Width)
+		{
+			// Draw the ZP wall:
+			a_ChunkDesc.FillRelCuboid(Min.x, Max.x, Min.y, Max.y, Max.z, Max.z, E_BLOCK_STAINED_GLASS, m_SizeXZ % 16);
+		}
+		
+		// Draw all the connectors:
+		for (cConnectors::const_iterator itr = m_Connectors.begin(), end = m_Connectors.end(); itr != end; ++itr)
+		{
+			cConnector Conn = cPiece::RotateMoveConnector(*itr, a_NumCCWRotations, a_Pos.x, a_Pos.y, a_Pos.z);
+			Conn.m_Pos.Move(-BlockX, 0, -BlockZ);
+			if (
+				(Conn.m_Pos.x >= 0) && (Conn.m_Pos.x < cChunkDef::Width) &&
+				(Conn.m_Pos.z >= 0) && (Conn.m_Pos.z < cChunkDef::Width)
+			)
+			{
+				a_ChunkDesc.SetBlockTypeMeta(Conn.m_Pos.x, Conn.m_Pos.y, Conn.m_Pos.z, E_BLOCK_WOOL, itr->m_Type % 16);
+			}
+			
+			/*
+			// TODO: Frame the connectors
+			switch (itr->m_Direction)
+			{
+				case BLOCK_FACE_XM:
+				case BLOCK_FACE_XP:
+				{
+					// TODO
+					break;
+				}
+				
+				case BLOCK_FACE_ZM:
+				case BLOCK_FACE_ZP:
+				{
+					// TODO
+					break;
+				}
+			}
+			*/
+		}  // for itr - m_Connectors[]
+	}
+	
+protected:
+	int m_SizeXZ;
+	int m_Height;
+	cConnectors m_Connectors;
+	
+	// cPiece overrides:
+	virtual cConnectors GetConnectors(void) const override
+	{
+		return m_Connectors;
+	}
+	
+	virtual Vector3i GetSize(void) const override
+	{
+		return Vector3i(m_SizeXZ, m_Height, m_SizeXZ);
+	}
+	
+	virtual cCuboid GetHitBox(void) const override
+	{
+		return cCuboid(0, 0, 0, m_SizeXZ - 1, m_Height - 1, m_SizeXZ - 1);
+	}
+	
+	virtual bool CanRotateCCW(int a_NumRotations) const override
+	{
+		return true;
+	}
+};
+
+
+
+
+
+/*
+static void DebugPieces(const cPlacedPieces & a_Pieces)
+{
+	size_t idx = 0;
+	for (cPlacedPieces::const_iterator itr = a_Pieces.begin(), end = a_Pieces.end(); itr != end; ++itr, ++idx)
+	{
+		const cCuboid & HitBox = (*itr)->GetHitBox();
+		printf("  %u: %d rotations, {%d - %d, %d - %d}\n",
+			idx, (*itr)->GetNumCCWRotations(),
+			HitBox.p1.x, HitBox.p2.x, HitBox.p1.z, HitBox.p2.z
+		);
+	}  // for itr - a_Pieces[]
+}
+//*/
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPOCPieceGenerator:
+
+cPOCPieceGenerator::cPOCPieceGenerator(int a_Seed) :
+	m_Seed(a_Seed)
+{
+	// Prepare a vector of available pieces:
+	m_AvailPieces.push_back(new cPOCPiece(5, 3));
+	m_AvailPieces.push_back(new cPOCPiece(7, 5));
+	m_AvailPieces.push_back(new cPOCPiece(9, 5));
+	m_AvailPieces.push_back(new cPOCPiece(5, 7));
+	
+	// Generate the structure:
+	cBFSPieceGenerator Gen(*this, a_Seed);
+	Gen.PlacePieces(0, 50, 0, 6, m_Pieces);
+	
+	// DebugPieces(m_Pieces);
+	
+	// Get the smallest cuboid encompassing the entire generated structure:
+	cCuboid Bounds(0, 50, 0, 0, 50, 0);
+	for (cPlacedPieces::const_iterator itr = m_Pieces.begin(), end = m_Pieces.end(); itr != end; ++itr)
+	{
+		Vector3i MinCoords = (*itr)->GetCoords();
+		Bounds.Engulf(MinCoords);
+		Bounds.Engulf(MinCoords + (*itr)->GetPiece().GetSize());
+	}  // for itr - m_Pieces[]
+	m_Bounds = Bounds;
+}
+
+
+
+
+
+cPOCPieceGenerator::~cPOCPieceGenerator()
+{
+	cPieceGenerator::FreePieces(m_Pieces);
+}
+
+
+
+
+
+void cPOCPieceGenerator::GenFinish(cChunkDesc & a_ChunkDesc)
+{
+	int BlockX = a_ChunkDesc.GetChunkX() * cChunkDef::Width;
+	int BlockZ = a_ChunkDesc.GetChunkZ() * cChunkDef::Width;
+	if (
+		(BlockX + 16 < m_Bounds.p1.x) || (BlockX > m_Bounds.p2.x) ||  // X coords out of bounds of the generated structure
+		(BlockZ + 16 < m_Bounds.p1.z) || (BlockZ > m_Bounds.p2.z)     // Z coords out of bounds of the generated structure
+	)
+	{
+		return;
+	}
+	
+	// Imprint each piece in the chunk:
+	for (cPlacedPieces::const_iterator itr = m_Pieces.begin(), end = m_Pieces.end(); itr != end; ++itr)
+	{
+		const Vector3i & Pos = (*itr)->GetCoords();
+		Vector3i Size = (*itr)->GetPiece().GetSize();
+		if (((*itr)->GetNumCCWRotations() % 2) == 1)
+		{
+			std::swap(Size.x, Size.z);
+		}
+		if (
+			(Pos.x >= BlockX + 16) || (Pos.x + Size.x - 1 < BlockX) ||
+			(Pos.z >= BlockZ + 16) || (Pos.z + Size.z - 1 < BlockZ)
+		)
+		{
+			// This piece doesn't intersect the chunk
+			continue;
+		}
+			
+		((cPOCPiece &)(*itr)->GetPiece()).ImprintInChunk(a_ChunkDesc, Pos, (*itr)->GetNumCCWRotations());
+	}  // for itr - m_Pieces[]
+	a_ChunkDesc.UpdateHeightmap();
+}
+
+
+
+
+
+cPieces cPOCPieceGenerator::GetPiecesWithConnector(int a_ConnectorType)
+{
+	// Each piece has each connector
+	return m_AvailPieces;
+}
+
+
+
+
+
+cPieces cPOCPieceGenerator::GetStartingPieces(void)
+{
+	// Any piece can be a starting piece
+	return m_AvailPieces;
+}
+
+
+
+
+
+void cPOCPieceGenerator::PiecePlaced(const cPiece & a_Piece)
+{
+	UNUSED(a_Piece);
+}
+
+
+
+
+
+void cPOCPieceGenerator::Reset(void)
+{
+	// Nothing needed
+}
+
+
+
+
diff --git a/src/Generating/POCPieceGenerator.h b/src/Generating/POCPieceGenerator.h
new file mode 100644
index 000000000..de3114ce0
--- /dev/null
+++ b/src/Generating/POCPieceGenerator.h
@@ -0,0 +1,54 @@
+
+// POCPieceGenerator.h
+
+// Declares the cPOCPieceGenerator class representing a Proof-Of_Concept structure generator using the cPieceGenerator technique
+// The generator generates a maze of rooms at {0, 100, 0}
+
+
+
+
+
+#pragma once
+
+#include "PieceGenerator.h"
+#include "ComposableGenerator.h"
+
+
+
+
+
+class cPOCPieceGenerator :
+	public cFinishGen,
+	protected cPiecePool
+{
+public:
+	cPOCPieceGenerator(int a_Seed);
+	~cPOCPieceGenerator();
+	
+protected:
+	int m_Seed;
+	
+	/** The pieces from which the generated structure is built. */
+	cPieces m_AvailPieces;
+	
+	/** The placed pieces of the generated structure. */
+	cPlacedPieces m_Pieces;
+	
+	/** Bounds of the complete structure, to save on processing outside chunks. */
+	cCuboid m_Bounds;
+
+
+	// cFinishGen overrides:
+	virtual void GenFinish(cChunkDesc & a_ChunkDesc) override;
+	
+	// cPiecePool overrides:
+	virtual cPieces GetPiecesWithConnector(int a_ConnectorType) override;
+	virtual cPieces GetStartingPieces(void) override;
+	virtual void PiecePlaced(const cPiece & a_Piece) override;
+	virtual void Reset(void) override;
+} ;
+
+
+
+
+
diff --git a/src/Generating/PieceGenerator.cpp b/src/Generating/PieceGenerator.cpp
new file mode 100644
index 000000000..e3de5b951
--- /dev/null
+++ b/src/Generating/PieceGenerator.cpp
@@ -0,0 +1,626 @@
+
+// PieceGenerator.cpp
+
+// Implements the cBFSPieceGenerator class and cDFSPieceGenerator class 
+// representing base classes for generating structures composed of individual "pieces"
+
+#include "Globals.h"
+#include "PieceGenerator.h"
+
+
+
+
+
+#ifdef SELF_TEST
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// Self-test:
+
+static class cPieceGeneratorSelfTest :
+	public cPiecePool
+{
+public:
+	cPieceGeneratorSelfTest(void)
+	{
+		// Prepare the internal state:
+		InitializePieces();
+		
+		// Generate:
+		cBFSPieceGenerator Gen(*this, 0);
+		cPlacedPieces OutPieces;
+		Gen.PlacePieces(500, 50, 500, 3, OutPieces);
+		
+		// Print out the pieces:
+		printf("OutPieces.size() = %u\n", OutPieces.size());
+		size_t idx = 0;
+		for (cPlacedPieces::const_iterator itr = OutPieces.begin(), end = OutPieces.end(); itr != end; ++itr, ++idx)
+		{
+			const Vector3i & Coords = (*itr)->GetCoords();
+			cCuboid Hitbox = (*itr)->GetHitBox();
+			Hitbox.Sort();
+			printf("%u: {%d, %d, %d}, rot %d, hitbox {%d, %d, %d} - {%d, %d, %d} (%d * %d * %d)\n", idx,
+				Coords.x, Coords.y, Coords.z,
+				(*itr)->GetNumCCWRotations(),
+				Hitbox.p1.x, Hitbox.p1.y, Hitbox.p1.z,
+				Hitbox.p2.x, Hitbox.p2.y, Hitbox.p2.z,
+				Hitbox.DifX() + 1, Hitbox.DifY() + 1, Hitbox.DifZ() + 1
+			);
+		}  // itr - OutPieces[]
+		printf("Done.\n");
+		
+		// Free the placed pieces properly:
+		Gen.FreePieces(OutPieces);
+	}
+	
+	~cPieceGeneratorSelfTest()
+	{
+		// Dealloc all the pieces:
+		for (cPieces::iterator itr = m_Pieces.begin(), end = m_Pieces.end(); itr != end; ++itr)
+		{
+			delete *itr;
+		}
+		m_Pieces.clear();
+	}
+	
+protected:
+	class cTestPiece :
+		public cPiece
+	{
+		int m_Size;
+	public:
+		cTestPiece(int a_Size) :
+			m_Size(a_Size)
+		{
+		}
+		
+		virtual cConnectors GetConnectors(void) const override
+		{
+			// Each piece has 4 connectors, one of each type, plus one extra, at the center of its walls:
+			cConnectors res;
+			res.push_back(cConnector(m_Size / 2, 1, 0,          0, BLOCK_FACE_ZM));
+			res.push_back(cConnector(m_Size / 2, 1, m_Size - 1, 1, BLOCK_FACE_ZP));
+			res.push_back(cConnector(0,          1, m_Size / 2, 2, BLOCK_FACE_XM));
+			res.push_back(cConnector(m_Size - 1, 1, m_Size / 2, m_Size % 3, BLOCK_FACE_XP));
+			return res;
+		}
+		
+		virtual Vector3i GetSize(void) const override
+		{
+			return Vector3i(m_Size, 5, m_Size);
+		}
+		
+		virtual cCuboid GetHitBox(void) const override
+		{
+			return cCuboid(0, 0, 0, m_Size - 1, 4, m_Size - 1);
+		}
+		
+		virtual bool CanRotateCCW(int a_NumCCWRotations) const override
+		{
+			return true;
+		}
+	};
+	
+	cPieces m_Pieces;
+	
+	virtual cPieces GetPiecesWithConnector(int a_ConnectorType) override
+	{
+		// Each piece contains each connector
+		return m_Pieces;
+	}
+	
+	
+	virtual cPieces GetStartingPieces(void) override
+	{
+		return m_Pieces;
+	}
+	
+	
+	virtual void PiecePlaced(const cPiece & a_Piece) override
+	{
+		UNUSED(a_Piece);
+	}
+	
+	
+	virtual void Reset(void) override
+	{
+	}
+	
+	
+	void InitializePieces(void)
+	{
+		m_Pieces.push_back(new cTestPiece(5));
+		m_Pieces.push_back(new cTestPiece(7));
+		m_Pieces.push_back(new cTestPiece(9));
+	}
+} g_Test;
+
+#endif  // SELF_TEST
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPiece:
+
+	
+Vector3i cPiece::RotatePos(const Vector3i & a_Pos, int a_NumCCWRotations) const
+{
+	Vector3i Size = GetSize();
+	switch (a_NumCCWRotations)
+	{
+		case 0:
+		{
+			// No rotation needed
+			return a_Pos;
+		}
+		case 1:
+		{
+			// 1 CCW rotation:
+			return Vector3i(a_Pos.z, a_Pos.y, Size.x - a_Pos.x - 1);
+		}
+		case 2:
+		{
+			// 2 rotations ( = axis flip):
+			return Vector3i(Size.x - a_Pos.x - 1, a_Pos.y, Size.z - a_Pos.z - 1);
+		}
+		case 3:
+		{
+			// 1 CW rotation:
+			return Vector3i(Size.z - a_Pos.z - 1, a_Pos.y, a_Pos.x);
+		}
+	}
+	ASSERT(!"Unhandled rotation");
+	return a_Pos;
+}
+
+
+
+
+
+cPiece::cConnector cPiece::RotateMoveConnector(const cConnector & a_Connector, int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const
+{
+	cPiece::cConnector res(a_Connector);
+	
+	// Rotate the res connector:
+	Vector3i Size = GetSize();
+	switch (a_NumCCWRotations)
+	{
+		case 0:
+		{
+			// No rotation needed
+			break;
+		}
+		case 1:
+		{
+			// 1 CCW rotation:
+			res.m_Direction = RotateBlockFaceCCW(res.m_Direction);
+			break;
+		}
+		case 2:
+		{
+			// 2 rotations ( = axis flip):
+			res.m_Direction = MirrorBlockFaceY(res.m_Direction);
+			break;
+		}
+		case 3:
+		{
+			// 1 CW rotation:
+			res.m_Direction = RotateBlockFaceCW(res.m_Direction);
+			break;
+		}
+	}
+	res.m_Pos = RotatePos(a_Connector.m_Pos, a_NumCCWRotations);
+	
+	// Move the res connector:
+	res.m_Pos.x += a_MoveX;
+	res.m_Pos.y += a_MoveY;
+	res.m_Pos.z += a_MoveZ;
+	
+	return res;
+}
+
+
+
+
+
+cCuboid cPiece::RotateHitBoxToConnector(
+	const cPiece::cConnector & a_MyConnector,
+	const Vector3i & a_ToConnectorPos,
+	int a_NumCCWRotations
+) const
+{
+	ASSERT(a_NumCCWRotations == (a_NumCCWRotations % 4));
+	Vector3i ConnPos = RotatePos(a_MyConnector.m_Pos, a_NumCCWRotations);
+	ConnPos = a_ToConnectorPos - ConnPos;
+	return RotateMoveHitBox(a_NumCCWRotations, ConnPos.x, ConnPos.y, ConnPos.z);
+}
+
+
+
+
+
+cCuboid cPiece::RotateMoveHitBox(int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const
+{
+	ASSERT(a_NumCCWRotations == (a_NumCCWRotations % 4));
+	cCuboid res = GetHitBox();
+	res.p1 = RotatePos(res.p1, a_NumCCWRotations);
+	res.p2 = RotatePos(res.p2, a_NumCCWRotations);
+	res.p1.Move(a_MoveX, a_MoveY, a_MoveZ);
+	res.p2.Move(a_MoveX, a_MoveY, a_MoveZ);
+	return res;
+}
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPiece::cConnector:
+
+cPiece::cConnector::cConnector(int a_X, int a_Y, int a_Z, int a_Type, eBlockFace a_Direction) :
+	m_Pos(a_X, a_Y, a_Z),
+	m_Type(a_Type),
+	m_Direction(a_Direction)
+{
+}
+
+
+
+
+
+cPiece::cConnector::cConnector(const Vector3i & a_Pos, int a_Type, eBlockFace a_Direction) :
+	m_Pos(a_Pos),
+	m_Type(a_Type),
+	m_Direction(a_Direction)
+{
+}
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPlacedPiece:
+
+cPlacedPiece::cPlacedPiece(const cPlacedPiece * a_Parent, const cPiece & a_Piece, const Vector3i & a_Coords, int a_NumCCWRotations) :
+	m_Parent(a_Parent),
+	m_Piece(&a_Piece),
+	m_Coords(a_Coords),
+	m_NumCCWRotations(a_NumCCWRotations)
+{
+	m_Depth = (m_Parent == NULL) ? 0 : (m_Parent->GetDepth() + 1);
+	m_HitBox = a_Piece.RotateMoveHitBox(a_NumCCWRotations, a_Coords.x, a_Coords.y, a_Coords.z);
+	m_HitBox.Sort();
+}
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPieceGenerator:
+
+cPieceGenerator::cPieceGenerator(cPiecePool & a_PiecePool, int a_Seed) :
+	m_PiecePool(a_PiecePool),
+	m_Noise(a_Seed),
+	m_Seed(a_Seed)
+{
+}
+
+
+
+
+
+void cPieceGenerator::FreePieces(cPlacedPieces & a_PlacedPieces)
+{
+	for (cPlacedPieces::iterator itr = a_PlacedPieces.begin(), end = a_PlacedPieces.end(); itr != end; ++itr)
+	{
+		delete *itr;
+	}  // for itr - a_PlacedPieces[]
+	a_PlacedPieces.clear();
+}
+
+
+
+
+
+cPlacedPiece * cPieceGenerator::PlaceStartingPiece(int a_BlockX, int a_BlockY, int a_BlockZ, cFreeConnectors & a_OutConnectors)
+{
+	m_PiecePool.Reset();
+	int rnd = m_Noise.IntNoise3DInt(a_BlockX, a_BlockY, a_BlockZ) / 7;
+	
+	// Choose a random one of the starting pieces:
+	cPieces StartingPieces = m_PiecePool.GetStartingPieces();
+	cPiece * StartingPiece = StartingPieces[rnd % StartingPieces.size()];
+	rnd = rnd >> 16;
+	
+	// Choose a random supported rotation:
+	int Rotations[4] = {0};
+	int NumRotations = 1;
+	for (int i = 1; i < ARRAYCOUNT(Rotations); i++)
+	{
+		if (StartingPiece->CanRotateCCW(i))
+		{
+			Rotations[NumRotations] = i;
+			NumRotations += 1;
+		}
+	}
+	int Rotation = Rotations[rnd % NumRotations];
+	
+	cPlacedPiece * res = new cPlacedPiece(NULL, *StartingPiece, Vector3i(a_BlockX, a_BlockY, a_BlockZ), Rotation);
+
+	// Place the piece's connectors into a_OutConnectors:
+	const cPiece::cConnectors & Conn = StartingPiece->GetConnectors();
+	for (cPiece::cConnectors::const_iterator itr = Conn.begin(), end = Conn.end(); itr != end; ++itr)
+	{
+		a_OutConnectors.push_back(
+			cFreeConnector(res, StartingPiece->RotateMoveConnector(*itr, Rotation, a_BlockX, a_BlockY, a_BlockZ))
+		);
+	}
+
+	return res;
+}
+
+
+
+
+
+bool cPieceGenerator::TryPlacePieceAtConnector(
+	const cPlacedPiece & a_ParentPiece,
+	const cPiece::cConnector & a_Connector,
+	cPlacedPieces & a_OutPieces,
+	cPieceGenerator::cFreeConnectors & a_OutConnectors
+)
+{
+	// Translation of direction - direction -> number of CCW rotations needed:
+	// You need DirectionRotationTable[rot1][rot2] CCW turns to connect rot1 to rot2 (they are opposite)
+	static const int DirectionRotationTable[6][6] =
+	{
+		/*         YM, YP, ZM, ZP, XM, XP
+		/* YM */ { 0,  0,  0,  0,  0,  0},
+		/* YP */ { 0,  0,  0,  0,  0,  0},
+		/* ZM */ { 0,  0,  2,  0,  1,  3},
+		/* ZP */ { 0,  0,  0,  2,  3,  1},
+		/* XM */ { 0,  0,  3,  1,  2,  0},
+		/* XP */ { 0,  0,  1,  3,  0,  2},
+	};
+	
+	// Get a list of available connections:
+	const int * RotTable = DirectionRotationTable[a_Connector.m_Direction];
+	cConnections Connections;
+	cPieces AvailablePieces = m_PiecePool.GetPiecesWithConnector(a_Connector.m_Type);
+	Connections.reserve(AvailablePieces.size());
+	Vector3i ConnPos = a_Connector.m_Pos;  // The position at which the new connector should be placed - 1 block away from the connector
+	AddFaceDirection(ConnPos.x, ConnPos.y, ConnPos.z, a_Connector.m_Direction);
+	
+	/*
+	// DEBUG:
+	printf("Placing piece at connector pos {%d, %d, %d}, direction %s\n", ConnPos.x, ConnPos.y, ConnPos.z, BlockFaceToString(a_Connector.m_Direction).c_str());
+	//*/
+	
+	for (cPieces::iterator itrP = AvailablePieces.begin(), endP = AvailablePieces.end(); itrP != endP; ++itrP)
+	{
+		cPiece::cConnectors Connectors = (*itrP)->GetConnectors();
+		for (cPiece::cConnectors::iterator itrC = Connectors.begin(), endC = Connectors.end(); itrC != endC; ++itrC)
+		{
+			if (itrC->m_Type != a_Connector.m_Type)
+			{
+				continue;
+			}
+			// This is a same-type connector, find out how to rotate to it:
+			int NumCCWRotations = RotTable[itrC->m_Direction];
+			if (!(*itrP)->CanRotateCCW(NumCCWRotations))
+			{
+				// Doesn't support this rotation
+				continue;
+			}
+			if (!CheckConnection(a_Connector, ConnPos, **itrP, *itrC, NumCCWRotations, a_OutPieces))
+			{
+				// Doesn't fit in this rotation
+				continue;
+			}
+			Connections.push_back(cConnection(**itrP, *itrC, NumCCWRotations));
+		}  // for itrC - Connectors[]
+	}  // for itrP - AvailablePieces[]
+	if (Connections.empty())
+	{
+		// No available connections, bail out
+		return false;
+	}
+	
+	// Choose a random connection from the list:
+	int rnd = m_Noise.IntNoise3DInt(a_Connector.m_Pos.x, a_Connector.m_Pos.y, a_Connector.m_Pos.z) / 7;
+	cConnection & Conn = Connections[rnd % Connections.size()];
+	
+	// Place the piece:
+	/*
+	// DEBUG
+	printf("Chosen connector at {%d, %d, %d}, direction %s, needs %d rotations\n",
+		Conn.m_Connector.m_Pos.x, Conn.m_Connector.m_Pos.y, Conn.m_Connector.m_Pos.z,
+		BlockFaceToString(Conn.m_Connector.m_Direction).c_str(),
+		Conn.m_NumCCWRotations
+	);
+	//*/
+	
+	Vector3i NewPos = Conn.m_Piece->RotatePos(Conn.m_Connector.m_Pos, Conn.m_NumCCWRotations);
+	ConnPos -= NewPos;
+	cPlacedPiece * PlacedPiece = new cPlacedPiece(&a_ParentPiece, *(Conn.m_Piece), ConnPos, Conn.m_NumCCWRotations);
+	a_OutPieces.push_back(PlacedPiece);
+	
+	// Add the new piece's connectors to the list of free connectors:
+	cPiece::cConnectors Connectors = Conn.m_Piece->GetConnectors();
+	
+	/*
+	// DEBUG:
+	printf("Adding %u connectors to the pool\n", Connectors.size() - 1);
+	//*/
+	
+	for (cPiece::cConnectors::const_iterator itr = Connectors.begin(), end = Connectors.end(); itr != end; ++itr)
+	{
+		if (itr->m_Pos.Equals(Conn.m_Connector.m_Pos))
+		{
+			// This is the connector through which we have been connected to the parent, don't add
+			continue;
+		}
+		a_OutConnectors.push_back(cFreeConnector(PlacedPiece, Conn.m_Piece->RotateMoveConnector(*itr, Conn.m_NumCCWRotations, ConnPos.x, ConnPos.y, ConnPos.z)));
+	}
+	
+	return true;
+}
+
+
+
+
+
+bool cPieceGenerator::CheckConnection(
+	const cPiece::cConnector & a_ExistingConnector,
+	const Vector3i & a_ToPos,
+	const cPiece & a_Piece,
+	const cPiece::cConnector & a_NewConnector,
+	int a_NumCCWRotations,
+	const cPlacedPieces & a_OutPieces
+)
+{
+	// For each placed piece, test the hitbox against the new piece:
+	cCuboid RotatedHitBox = a_Piece.RotateHitBoxToConnector(a_NewConnector, a_ToPos, a_NumCCWRotations);
+	RotatedHitBox.Sort();
+	for (cPlacedPieces::const_iterator itr = a_OutPieces.begin(), end = a_OutPieces.end(); itr != end; ++itr)
+	{
+		if ((*itr)->GetHitBox().DoesIntersect(RotatedHitBox))
+		{
+			return false;
+		}
+	}
+	return true;
+}
+
+
+
+
+
+//*
+// DEBUG:
+void cPieceGenerator::DebugConnectorPool(const cPieceGenerator::cFreeConnectors & a_ConnectorPool, size_t a_NumProcessed)
+{
+	printf("  Connector pool: %u items\n", a_ConnectorPool.size() - a_NumProcessed);
+	size_t idx = 0;
+	for (cPieceGenerator::cFreeConnectors::const_iterator itr = a_ConnectorPool.begin() + a_NumProcessed, end = a_ConnectorPool.end(); itr != end; ++itr, ++idx)
+	{
+		printf("    %u: {%d, %d, %d}, type %d, direction %s, depth %d\n",
+			idx,
+			itr->m_Connector.m_Pos.x, itr->m_Connector.m_Pos.y, itr->m_Connector.m_Pos.z,
+			itr->m_Connector.m_Type,
+			BlockFaceToString(itr->m_Connector.m_Direction).c_str(),
+			itr->m_Piece->GetDepth()
+		);
+	}  // for itr - a_ConnectorPool[]
+}
+//*/
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPieceGenerator::cConnection:
+
+cPieceGenerator::cConnection::cConnection(cPiece & a_Piece, cPiece::cConnector & a_Connector, int a_NumCCWRotations) :
+	m_Piece(&a_Piece),
+	m_Connector(a_Connector),
+	m_NumCCWRotations(a_NumCCWRotations)
+{
+}
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cPieceGenerator::cFreeConnector:
+
+cPieceGenerator::cFreeConnector::cFreeConnector(cPlacedPiece * a_Piece, const cPiece::cConnector & a_Connector) :
+	m_Piece(a_Piece),
+	m_Connector(a_Connector)
+{
+}
+
+
+
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// cBFSPieceGenerator:
+
+cBFSPieceGenerator::cBFSPieceGenerator(cPiecePool & a_PiecePool, int a_Seed) :
+	super(a_PiecePool, a_Seed)
+{
+}
+
+
+
+
+
+void cBFSPieceGenerator::PlacePieces(int a_BlockX, int a_BlockY, int a_BlockZ, int a_MaxDepth, cPlacedPieces & a_OutPieces)
+{
+	a_OutPieces.clear();
+	cFreeConnectors ConnectorPool;
+	
+	// Place the starting piece:
+	a_OutPieces.push_back(PlaceStartingPiece(a_BlockX, a_BlockY, a_BlockZ, ConnectorPool));
+	
+	/*
+	// DEBUG:
+	printf("Placed the starting piece at {%d, %d, %d}\n", a_BlockX, a_BlockY, a_BlockZ);
+	cCuboid Hitbox = a_OutPieces[0]->GetHitBox();
+	Hitbox.Sort();
+	printf("  Hitbox: {%d, %d, %d} - {%d, %d, %d} (%d * %d * %d)\n",
+		Hitbox.p1.x, Hitbox.p1.y, Hitbox.p1.z,
+		Hitbox.p2.x, Hitbox.p2.y, Hitbox.p2.z,
+		Hitbox.DifX() + 1, Hitbox.DifY() + 1, Hitbox.DifZ() + 1
+	);
+	DebugConnectorPool(ConnectorPool, 0);
+	//*/
+	
+	// Place pieces at the available connectors:
+	/*
+	Instead of removing them one by one from the pool, we process them sequentially and take note of the last
+	processed one. To save on memory, once the number of processed connectors reaches a big number, a chunk
+	of the connectors is removed.
+	*/
+	size_t NumProcessed = 0;
+	while (ConnectorPool.size() > NumProcessed)
+	{
+		cFreeConnector & Conn = ConnectorPool[NumProcessed];
+		if (Conn.m_Piece->GetDepth() < a_MaxDepth)
+		{
+			if (TryPlacePieceAtConnector(*Conn.m_Piece, Conn.m_Connector, a_OutPieces, ConnectorPool))
+			{
+				/*
+				// DEBUG:
+				const cPlacedPiece * NewPiece = a_OutPieces.back();
+				const Vector3i & Coords = NewPiece->GetCoords();
+				printf("Placed a new piece at {%d, %d, %d}, rotation %d\n", Coords.x, Coords.y, Coords.z, NewPiece->GetNumCCWRotations());
+				cCuboid Hitbox = NewPiece->GetHitBox();
+				Hitbox.Sort();
+				printf("  Hitbox: {%d, %d, %d} - {%d, %d, %d} (%d * %d * %d)\n",
+					Hitbox.p1.x, Hitbox.p1.y, Hitbox.p1.z,
+					Hitbox.p2.x, Hitbox.p2.y, Hitbox.p2.z,
+					Hitbox.DifX() + 1, Hitbox.DifY() + 1, Hitbox.DifZ() + 1
+				);
+				DebugConnectorPool(ConnectorPool, NumProcessed + 1);
+				//*/
+			}
+		}
+		NumProcessed++;
+		if (NumProcessed > 1000)
+		{
+			ConnectorPool.erase(ConnectorPool.begin(), ConnectorPool.begin() + NumProcessed);
+			NumProcessed = 0;
+		}
+	}
+}
+
+
+
+
diff --git a/src/Generating/PieceGenerator.h b/src/Generating/PieceGenerator.h
new file mode 100644
index 000000000..9dd5bcfba
--- /dev/null
+++ b/src/Generating/PieceGenerator.h
@@ -0,0 +1,247 @@
+
+// PieceGenerator.h
+
+// Declares the cBFSPieceGenerator class and cDFSPieceGenerator class 
+// representing base classes for generating structures composed of individual "pieces"
+
+/*
+Each uses a slightly different approach to generating:
+	- DFS extends pieces one by one until it hits the configured depth (or can't connect another piece anymore),
+		then starts looking at adjacent connectors (like depth-first search).
+	- BFS keeps a pool of currently-open connectors, chooses one at random and tries to place a piece on it,
+		thus possibly extending the pool of open connectors (like breadth-first search).
+*/
+
+
+
+
+
+#pragma once
+
+#include "../Defines.h"
+#include "../Cuboid.h"
+#include "../Noise.h"
+
+
+
+
+
+/** Represents a single piece. Can have multiple connectors of different types where other pieces can connect. */
+class cPiece
+{
+public:
+	// Force a virtual destructor in all descendants
+	virtual ~cPiece() {}
+	
+	struct cConnector
+	{
+		/** Position relative to the piece */
+		Vector3i m_Pos;
+		
+		/** Type of the connector. Any arbitrary number; the generator connects only connectors of the same type. */
+		int m_Type;
+		
+		/** Direction in which the connector is facing.
+		Will be matched by the opposite direction for the connecting connector. */
+		eBlockFace m_Direction;
+		
+		cConnector(int a_X, int a_Y, int a_Z, int a_Type, eBlockFace a_Direction);
+		cConnector(const Vector3i & a_Pos, int a_Type, eBlockFace a_Direction);
+	};
+	
+	typedef std::vector<cConnector> cConnectors;
+	
+	/** Returns all of the available connectors that the piece has.
+	Each connector has a (relative) position in the piece, and a type associated with it. */
+	virtual cConnectors GetConnectors(void) const = 0;
+	
+	/** Returns the dimensions of this piece.
+	The dimensions cover the entire piece, there is no block that the piece generates outside of this size. */
+	virtual Vector3i GetSize(void) const = 0;
+	
+	/** Returns the "hitbox" of this piece.
+	A hitbox is what is compared and must not intersect other pieces' hitboxes when generating. */
+	virtual cCuboid GetHitBox(void) const = 0;
+	
+	/** Returns true if the piece can be rotated CCW the specific number of 90-degree turns. */
+	virtual bool CanRotateCCW(int a_NumRotations) const = 0;
+	
+	/** Returns a copy of the a_Pos after rotating the piece the specified number of CCW rotations. */
+	Vector3i RotatePos(const Vector3i & a_Pos, int a_NumCCWRotations) const;
+
+	/** Returns a copy of the connector that is rotated and then moved by the specified amounts. */
+	cConnector RotateMoveConnector(const cConnector & a_Connector, int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const;
+	
+	/** Returns the hitbox after the specified number of rotations and moved so that a_MyConnector is placed at a_ToConnectorPos. */
+	cCuboid RotateHitBoxToConnector(const cConnector & a_MyConnector, const Vector3i & a_ToConnectorPos, int a_NumCCWRotations) const;
+	
+	/** Returns the hitbox after the specified number of CCW rotations and moved by the specified amounts. */
+	cCuboid RotateMoveHitBox(int a_NumCCWRotations, int a_MoveX, int a_MoveY, int a_MoveZ) const;
+};
+
+typedef std::vector<cPiece *> cPieces;
+
+
+
+
+
+/** This class is an interface that provides pieces for the generator. It can keep track of what pieces were
+placed and adjust the returned piece vectors. */
+class cPiecePool
+{
+public:
+	// Force a virtual destructor in all descendants:
+	virtual ~cPiecePool() {}
+	
+	/** Returns a list of pieces that contain the specified connector type.
+	The cPiece pointers returned are managed by the pool and the caller doesn't free them. */
+	virtual cPieces GetPiecesWithConnector(int a_ConnectorType) = 0;
+	
+	/** Returns the pieces that should be used as the starting point.
+	Multiple starting points are supported, one of the returned piece will be chosen. */
+	virtual cPieces GetStartingPieces(void) = 0;
+	
+	/** Called after a piece is placed, to notify the pool that it has been used.
+	The pool may adjust the pieces it will return the next time. */
+	virtual void PiecePlaced(const cPiece & a_Piece) = 0;
+	
+	/** Called when the pool has finished the current structure and should reset any piece-counters it has
+	for a new structure. */
+	virtual void Reset(void) = 0;
+};
+
+
+
+
+
+/** Represents a single piece that has been placed to specific coords in the world. */
+class cPlacedPiece
+{
+public:
+	cPlacedPiece(const cPlacedPiece * a_Parent, const cPiece & a_Piece, const Vector3i & a_Coords, int a_NumCCWRotations);
+	
+	const cPiece &   GetPiece          (void) const { return *m_Piece; }
+	const Vector3i & GetCoords         (void) const { return m_Coords; }
+	const int        GetNumCCWRotations(void) const { return m_NumCCWRotations; }
+	const cCuboid &  GetHitBox         (void) const { return m_HitBox; }
+	const int        GetDepth          (void) const { return m_Depth; }
+	
+protected:
+	const cPlacedPiece * m_Parent;
+	const cPiece * m_Piece;
+	Vector3i m_Coords;
+	int m_NumCCWRotations;
+	cCuboid m_HitBox;
+	int m_Depth;
+};
+
+typedef std::vector<cPlacedPiece *> cPlacedPieces;
+
+
+
+
+
+class cPieceGenerator
+{
+public:
+	cPieceGenerator(cPiecePool & a_PiecePool, int a_Seed);
+	
+	/** Cleans up all the memory used by the placed pieces.
+	Call this utility function instead of freeing the items on your own. */
+	static void FreePieces(cPlacedPieces & a_PlacedPieces);
+	
+protected:
+	/** The type used for storing a connection from one piece to another, while building the piece tree. */
+	struct cConnection
+	{
+		cPiece * m_Piece;                  // The piece being connected
+		cPiece::cConnector m_Connector;    // The piece's connector being used (relative non-rotated coords)
+		int m_NumCCWRotations;             // Number of rotations necessary to match the two connectors
+		
+		cConnection(cPiece & a_Piece, cPiece::cConnector & a_Connector, int a_NumCCWRotations);
+	};
+	typedef std::vector<cConnection> cConnections;
+	
+	/** The type used for storing a pool of connectors that will be attempted to expand by another piece. */
+	struct cFreeConnector
+	{
+		cPlacedPiece * m_Piece;
+		cPiece::cConnector m_Connector;
+		
+		cFreeConnector(cPlacedPiece * a_Piece, const cPiece::cConnector & a_Connector);
+	};
+	typedef std::vector<cFreeConnector> cFreeConnectors;
+
+
+	cPiecePool & m_PiecePool;
+	cNoise m_Noise;
+	int m_Seed;
+
+	
+	/** Selects a starting piece and places it, including the rotations.
+	Also puts the piece's connectors in a_OutConnectors. */
+	cPlacedPiece * PlaceStartingPiece(int a_BlockX, int a_BlockY, int a_BlockZ, cFreeConnectors & a_OutConnectors);
+	
+	/** Tries to place a new piece at the specified (placed) connector. Returns true if successful. */
+	bool TryPlacePieceAtConnector(
+		const cPlacedPiece & a_ParentPiece,      // The existing piece to a new piece should be placed
+		const cPiece::cConnector & a_Connector,  // The existing connector (world-coords) to which a new piece should be placed
+		cPlacedPieces & a_OutPieces,             // Already placed pieces, to be checked for intersections
+		cFreeConnectors & a_OutConnectors        // List of free connectors to which the new connectors will be placed
+	);
+
+	/** Checks if the specified piece would fit with the already-placed pieces, using the specified connector
+	and number of CCW rotations.
+	a_ExistingConnector is in world-coords and is already rotated properly
+	a_ToPos is the world-coords position on which the new connector should be placed (1 block away from a_ExistingConnector, in its Direction)
+	a_NewConnector is in the original (non-rotated) coords.
+	Returns true if the piece fits, false if not. */
+	bool CheckConnection(
+		const cPiece::cConnector & a_ExistingConnector,  // The existing connector
+		const Vector3i & a_ToPos,                        // The position on which the new connector should be placed
+		const cPiece & a_Piece,                          // The new piece
+		const cPiece::cConnector & a_NewConnector,       // The connector of the new piece 
+		int a_NumCCWRotations,                           // Number of rotations for the new piece to align the connector
+		const cPlacedPieces & a_OutPieces                // All the already-placed pieces to check
+	);
+	
+	/** DEBUG: Outputs all the connectors in the pool into stdout.
+	a_NumProcessed signals the number of connectors from the pool that should be considered processed (not listed). */
+	void DebugConnectorPool(const cPieceGenerator::cFreeConnectors & a_ConnectorPool, size_t a_NumProcessed);
+} ;
+
+
+
+
+
+class cBFSPieceGenerator :
+	public cPieceGenerator
+{
+	typedef cPieceGenerator super;
+	
+public:
+	cBFSPieceGenerator(cPiecePool & a_PiecePool, int a_Seed);
+	
+	/** Generates a placement for pieces at the specified coords.
+	Caller must free each individual cPlacedPiece in a_OutPieces. */
+	void PlacePieces(int a_BlockX, int a_BlockY, int a_BlockZ, int a_MaxDepth, cPlacedPieces & a_OutPieces);
+};
+
+
+
+
+
+class cDFSPieceGenerator :
+	public cPieceGenerator
+{
+public:
+	cDFSPieceGenerator(cPiecePool & a_PiecePool, int a_Seed);
+	
+	/** Generates a placement for pieces at the specified coords.
+	Caller must free each individual cPlacedPiece in a_OutPieces. */
+	void PlacePieces(int a_BlockX, int a_BlockY, int a_BlockZ, cPlacedPieces & a_OutPieces);
+};
+
+
+
+