3 files changed, 144 insertions, 0 deletions

diff --git a/source/BioGen.cpp b/source/BioGen.cpp
index 51e508700..e897e229d 100644
--- a/source/BioGen.cpp
+++ b/source/BioGen.cpp
@@ -26,6 +26,96 @@ void cBioGenConstant::GenBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap
 

 

 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

+// cBioGenCache:

+

+cBioGenCache::cBioGenCache(cBiomeGen * a_BioGenToCache, int a_CacheSize) :

+	m_BioGenToCache(a_BioGenToCache),

+	m_CacheSize(a_CacheSize),

+	m_CacheOrder(new int[a_CacheSize]),

+	m_CacheData(new sCacheData[a_CacheSize]),

+	m_NumHits(0),

+	m_NumMisses(0),

+	m_TotalChain(0)

+{

+	for (int i = 0; i < m_CacheSize; i++)

+	{

+		m_CacheOrder[i] = i;

+		m_CacheData[i].m_ChunkX = 0x7fffffff;

+		m_CacheData[i].m_ChunkZ = 0x7fffffff;

+	}

+}

+

+

+

+

+

+cBioGenCache::~cBioGenCache()

+{

+	delete m_CacheData;

+	delete m_CacheOrder;

+	delete m_BioGenToCache;

+}

+

+

+

+

+

+void cBioGenCache::GenBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap & a_BiomeMap)

+{

+	if (((m_NumHits + m_NumMisses) % 1024) == 10)

+	{

+		LOGD("BioGenCache: %d hits, %d misses, saved %.2f %%", m_NumHits, m_NumMisses, 100.0 * m_NumHits / (m_NumHits + m_NumMisses));

+		LOGD("BioGenCache: Avg cache chain length: %.2f", (float)m_TotalChain / m_NumHits);

+	}

+	

+	for (int i = 0; i < m_CacheSize; i++)

+	{

+		if (

+			(m_CacheData[m_CacheOrder[i]].m_ChunkX != a_ChunkX) ||

+			(m_CacheData[m_CacheOrder[i]].m_ChunkZ != a_ChunkZ)

+		)

+		{

+			continue;

+		}

+		// Found it in the cache

+		int Idx = m_CacheOrder[i];

+		

+		// Move to front:

+		for (int j = i; j > 0; j--)

+		{

+			m_CacheOrder[j] = m_CacheOrder[j - 1];

+		}

+		m_CacheOrder[0] = Idx;

+		

+		// Use the cached data:

+		memcpy(a_BiomeMap, m_CacheData[Idx].m_BiomeMap, sizeof(a_BiomeMap));

+		

+		m_NumHits++;

+		m_TotalChain += i;

+		return;

+	}  // for i - cache

+	

+	// Not in the cache:

+	m_NumMisses++;

+	m_BioGenToCache->GenBiomes(a_ChunkX, a_ChunkZ, a_BiomeMap);

+	

+	// Insert it as the first item in the MRU order:

+	int Idx = m_CacheOrder[m_CacheSize - 1];

+	for (int i = m_CacheSize - 1; i > 0; i--)

+	{

+		m_CacheOrder[i] = m_CacheOrder[i - 1];

+	}  // for i - m_CacheOrder[]

+	m_CacheOrder[0] = Idx;

+	memcpy(m_CacheData[Idx].m_BiomeMap, a_BiomeMap, sizeof(a_BiomeMap));

+	m_CacheData[Idx].m_ChunkX = a_ChunkX;

+	m_CacheData[Idx].m_ChunkZ = a_ChunkZ;

+}

+

+

+

+

+

+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 // cBiomeGenList:

 

 void cBiomeGenList::InitializeBiomes(const AString & a_Biomes)

diff --git a/source/BioGen.h b/source/BioGen.h
index e701b6ec9..9a119ef2e 100644
--- a/source/BioGen.h
+++ b/source/BioGen.h
@@ -39,6 +39,42 @@ protected:
 

 

 

+/// A simple cache that stores N most recently generated chunks' biomes; N being settable upon creation

+class cBioGenCache :

+	public cBiomeGen

+{

+public:

+	cBioGenCache(cBiomeGen * a_BioGenToCache, int a_CacheSize);  // Takes ownership of a_BioGenToCache

+	~cBioGenCache();

+	

+protected:

+

+	cBiomeGen * m_BioGenToCache;

+	

+	struct sCacheData

+	{

+		int m_ChunkX;

+		int m_ChunkZ;

+		cChunkDef::BiomeMap m_BiomeMap;

+	} ;

+	

+	// To avoid moving large amounts of data for the MRU behavior, we MRU-ize indices to an array of the actual data

+	int          m_CacheSize;

+	int *        m_CacheOrder;  // MRU-ized order, indices into m_CacheData array

+	sCacheData * m_CacheData;   // m_CacheData[m_CacheOrder[0]] is the most recently used

+	

+	// Cache statistics

+	int m_NumHits;

+	int m_NumMisses;

+	int m_TotalChain;  // Number of cache items walked to get to a hit (only added for hits)

+	

+	virtual void GenBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap & a_BiomeMap) override;

+} ;

+

+

+

+

+

 /// Base class for generators that use a list of available biomes. This class takes care of the list.

 class cBiomeGenList :

 	public cBiomeGen

diff --git a/source/cChunkGenerator.cpp b/source/cChunkGenerator.cpp
index 5aa50c20a..1687e0e13 100644
--- a/source/cChunkGenerator.cpp
+++ b/source/cChunkGenerator.cpp
@@ -111,6 +111,7 @@ void cChunkGenerator::InitBiomeGen(cIniFile & a_IniFile)
 		BiomeGenName = "constant";

 	}

 	

+	bool CacheOffByDefault = false;

 	if (NoCaseCompare(BiomeGenName, "constant") == 0)

 	{

 		AString Biome = a_IniFile.GetValue("Generator", "ConstantBiome", "Plains");

@@ -121,12 +122,14 @@ void cChunkGenerator::InitBiomeGen(cIniFile & a_IniFile)
 			b = biPlains;

 		}

 		m_BiomeGen = new cBioGenConstant(b);

+		CacheOffByDefault = true;  // we're generating faster than a cache would retrieve data :)

 	}

 	else if (NoCaseCompare(BiomeGenName, "checkerboard") == 0)

 	{

 		int BiomeSize = a_IniFile.GetValueI("Generator", "CheckerboardBiomeSize", 64);

 		AString Biomes = a_IniFile.GetValue("Generator", "CheckerBoardBiomes", "");

 		m_BiomeGen = new cBioGenCheckerboard(BiomeSize, Biomes);

+		CacheOffByDefault = true;  // we're (probably) generating faster than a cache would retrieve data

 	}

 	else if (NoCaseCompare(BiomeGenName, "voronoi") == 0)

 	{

@@ -144,6 +147,21 @@ void cChunkGenerator::InitBiomeGen(cIniFile & a_IniFile)
 		AString Biomes = a_IniFile.GetValue("Generator", "DistortedVoronoiBiomes", "");

 		m_BiomeGen = new cBioGenDistortedVoronoi(m_Seed, CellSize, Biomes);

 	}

+	

+	// Add a cache, if requested:

+	int CacheSize = a_IniFile.GetValueI("Generator", "BiomeGenCacheSize", CacheOffByDefault ? 0 : 64);

+	if (CacheSize > 0)

+	{

+		if (CacheSize < 4)

+		{

+			LOGWARNING("Biomegen cache size set too low, would hurt performance instead of helping. Increasing from %d to %d", 

+				CacheSize, 4

+			);

+			CacheSize = 4;

+		}

+		LOGINFO("Using a cache for biomegen of size %d.", CacheSize);

+		m_BiomeGen = new cBioGenCache(m_BiomeGen, CacheSize);

+	}

 }