2 files changed, 262 insertions, 0 deletions

diff --git a/src/Generating/GridStructGen.cpp b/src/Generating/GridStructGen.cpp
new file mode 100644
index 000000000..975fd3fdc
--- /dev/null
+++ b/src/Generating/GridStructGen.cpp
@@ -0,0 +1,138 @@
+
+// GridStructGen.cpp
+
+// Implements the cGridStructGen class representing a common base class for structure generators that place structures in a semi-random grid
+
+#include "Globals.h"
+#include "GridStructGen.h"
+
+
+
+
+cGridStructGen::cGridStructGen(
+	int a_Seed,
+	int a_GridSizeX, int a_GridSizeZ,
+	int a_MaxStructureSizeX, int a_MaxStructureSizeZ,
+	size_t a_MaxCacheSize
+) :
+	m_Seed(a_Seed),
+	m_GridSizeX(a_GridSizeX),
+	m_GridSizeZ(a_GridSizeZ),
+	m_MaxStructureSizeX(a_MaxStructureSizeX),
+	m_MaxStructureSizeZ(a_MaxStructureSizeZ),
+	m_MaxCacheSize(a_MaxCacheSize)
+{
+}
+
+
+
+
+
+void cGridStructGen::GetStructuresForChunk(int a_ChunkX, int a_ChunkZ, cStructurePtrs & a_Structures)
+{
+	// Calculate the min and max grid coords of the structures to be returned:
+	int MinBlockX = a_ChunkX * cChunkDef::Width - m_MaxStructureSizeX;
+	int MinBlockZ = a_ChunkZ * cChunkDef::Width - m_MaxStructureSizeZ;
+	int MaxBlockX = a_ChunkX * cChunkDef::Width + m_MaxStructureSizeX + cChunkDef::Width - 1;
+	int MaxBlockZ = a_ChunkZ * cChunkDef::Width + m_MaxStructureSizeZ + cChunkDef::Width - 1;
+	int MinGridX = MinBlockX / m_GridSizeX;
+	int MinGridZ = MinBlockZ / m_GridSizeZ;
+	int MaxGridX = MaxBlockX / m_GridSizeX;
+	int MaxGridZ = MaxBlockX / m_GridSizeZ;
+	if (MinGridX < 0)
+	{
+		--MinGridX;
+	}
+	if (MinGridZ < 0)
+	{
+		--MinGridZ;
+	}
+	if (MaxGridX < 0)
+	{
+		--MaxGridX;
+	}
+	if (MaxGridZ < 0)
+	{
+		--MaxGridZ;
+	}
+
+	// Walk the cache, move each structure that we want into a_Structures:
+	for (cStructurePtrs::iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end;)
+	{
+		if (
+			((*itr)->m_OriginX >= MinBlockX) && ((*itr)->m_OriginX < MaxBlockX) &&
+			((*itr)->m_OriginZ >= MinBlockZ) && ((*itr)->m_OriginZ < MaxBlockZ)
+		)
+		{
+			// want
+			a_Structures.push_back(*itr);
+			itr = m_Cache.erase(itr);
+		}
+		else
+		{
+			// don't want
+			++itr;
+		}
+	}  // for itr - m_Cache[]
+
+	// Create those structures that haven't been in the cache:
+	for (int x = MinGridX; x < MaxGridX; x++)
+	{
+		int OriginX = x * m_GridSizeX;
+		for (int z = MinGridZ; z < MaxGridZ; z++)
+		{
+			int OriginZ = z * m_GridSizeZ;
+			bool Found = false;
+			for (cStructurePtrs::const_iterator itr = a_Structures.begin(), end = a_Structures.end(); itr != end; ++itr)
+			{
+				if (((*itr)->m_OriginX == OriginX) && ((*itr)->m_OriginZ == OriginZ))
+				{
+					Found = true;
+					break;
+				}
+			}  // for itr - a_Structures[]
+			if (!Found)
+			{
+				a_Structures.push_back(CreateStructure(OriginX, OriginZ));
+			}
+		}  // for z
+	}  // for x
+
+	// Copy a_Forts into m_Cache to the beginning:
+	cStructurePtrs StructuresCopy (a_Structures);
+	m_Cache.splice(m_Cache.begin(), StructuresCopy, StructuresCopy.begin(), StructuresCopy.end());
+
+	// Trim the cache if it's too long:
+	size_t CacheSize = 0;
+	for (cStructurePtrs::iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end; ++itr)
+	{
+		CacheSize += (*itr)->GetCacheCost();
+		if (CacheSize > m_MaxCacheSize)
+		{
+			// Erase all items from this one till the cache end
+			m_Cache.erase(itr, m_Cache.end());
+			break;
+		}
+	}
+}
+
+
+
+
+
+void cGridStructGen::GenFinish(cChunkDesc & a_ChunkDesc)
+{
+	int ChunkX = a_ChunkDesc.GetChunkX();
+	int ChunkZ = a_ChunkDesc.GetChunkZ();
+	cStructurePtrs Structures;
+	GetStructuresForChunk(ChunkX, ChunkZ, Structures);
+	for (cStructurePtrs::const_iterator itr = Structures.begin(); itr != Structures.end(); ++itr)
+	{
+		(*itr)->DrawIntoChunk(a_ChunkDesc);
+	}  // for itr - Structures[]
+}
+
+
+
+
+
diff --git a/src/Generating/GridStructGen.h b/src/Generating/GridStructGen.h
new file mode 100644
index 000000000..234cc75c5
--- /dev/null
+++ b/src/Generating/GridStructGen.h
@@ -0,0 +1,124 @@
+
+// GridStructGen.h
+
+// Declares the cGridStructGen class representing a common base class for structure generators that place structures in a semi-random grid
+
+
+
+
+
+#pragma once
+
+#include "ComposableGenerator.h"
+
+
+
+
+
+/** Generates structures in a semi-random grid.
+Defines a grid in the XZ space with predefined cell size in each direction. Each cell then receives exactly
+one structure (provided by the descendant class). The structure is placed within the cell, but doesn't need
+to be bounded by the cell, it can be well outside the cell; the generator uses the MaxStructureSize parameter
+to determine how far away from the cell the structure can be at most.
+This class provides a cache for the structures generated for successive chunks and manages that cache. It
+also provides the cFinishGen override that uses the cache to actually generate the structure into chunk data.
+
+After generating each chunk the cache is checked for size, each item in the cache has a cost associated with
+it and the cache is trimmed (from its least-recently-used end) so that the sum of the cost in the cache is
+less than m_MaxCacheSize
+
+To use this class, declare a descendant class that implements the overridable methods, then create an
+instance of that class. The descendant must provide the CreateStructure() function that is called to generate
+a structure at the specific grid cell.
+
+The descendant must use a specific cStructure descendant to provide the actual structure that gets generated.
+The structure must provide the DrawIntoChunk() function that generates the structure into the chunk data, and
+can override the GetCacheCost() function that returns the cost of that structure in the cache.
+*/
+class cGridStructGen :
+	public cFinishGen
+{
+public:
+	cGridStructGen(
+		int a_Seed,
+		int a_GridSizeX, int a_GridSizeZ,
+		int a_MaxStructureSizeX, int a_MaxStructureSizeZ,
+		size_t a_MaxCacheSize
+	);
+	
+protected:
+	/** Represents a single structure that occupies the grid point. Knows how to draw itself into a chunk. */
+	class cStructure
+	{
+	public:
+		/** The origin (the coords of the gridpoint for which the structure is generated) */
+		int m_OriginX, m_OriginZ;
+		
+		
+		/** Creates a structure that has its originset at the specified coords. */
+		cStructure (int a_OriginX, int a_OriginZ) :
+			m_OriginX(a_OriginX),
+			m_OriginZ(a_OriginZ)
+		{
+		}
+		
+		// Force a virtual destructor in descendants:
+		virtual ~cStructure() {}
+		
+		/** Draws self into the specified chunk */
+		virtual void DrawIntoChunk(cChunkDesc & a_ChunkDesc) = 0;
+		
+		/** Returns the cost of keeping this structure in the cache */
+		virtual size_t GetCacheCost(void) const { return 1; }
+	} ;
+	typedef SharedPtr<cStructure> cStructurePtr;
+	typedef std::list<cStructurePtr> cStructurePtrs;
+	
+	
+	/** Seed for generating the semi-random grid. */
+	int m_Seed;
+	
+	/** The size of each grid's cell in the X axis */
+	int m_GridSizeX;
+	
+	/** The size of each grid's cell in the Z axis */
+	int m_GridSizeZ;
+	
+	/** Maximum theoretical size of the structure in the X axis.
+	This limits the structures considered for a single chunk, so the lesser the number, the better performance.
+	Structures large than this may get cropped. */
+	int m_MaxStructureSizeX;
+	
+	/** Maximum theoretical size of the structure in the Z axis.
+	This limits the structures considered for a single chunk, so the lesser the number, the better performance.
+	Structures large than this may get cropped. */
+	int m_MaxStructureSizeZ;
+	
+	/** Maximum allowed sum of costs for items in the cache. Items that are over this cost are removed from the
+	cache, oldest-first */
+	size_t m_MaxCacheSize;
+	
+	/** Cache for the most recently generated structures, ordered by the recentness. */
+	cStructurePtrs m_Cache;
+	
+	
+	/** Clears everything from the cache */
+	void ClearCache(void);
+	
+	/** Returns all structures that may intersect the given chunk.
+	The structures are considered as intersecting iff their bounding box (defined by m_MaxStructureSize)
+	around their gridpoint intersects the chunk. */
+	void GetStructuresForChunk(int a_ChunkX, int a_ChunkZ, cStructurePtrs & a_Structures);
+
+	// cFinishGen overrides:
+	virtual void GenFinish(cChunkDesc & a_ChunkDesc) override;
+	
+	// Functions for the descendants to override:
+	/** Create a new structure at the specified gridpoint */
+	virtual cStructurePtr CreateStructure(int a_OriginX, int a_OriginZ) = 0;
+} ;
+
+
+
+
+