9 files changed, 141 insertions, 217 deletions

diff --git a/src/Generating/CMakeLists.txt b/src/Generating/CMakeLists.txt
index 047452bbb..dcb4bb3a7 100644
--- a/src/Generating/CMakeLists.txt
+++ b/src/Generating/CMakeLists.txt
@@ -42,6 +42,7 @@ SET (HDRS
 	CompoGen.h
 	CompoGenBiomal.h
 	ComposableGenerator.h
+	CompositedHeiGen.h
 	DistortedHeightmap.h
 	DungeonRoomsFinisher.h
 	EndGen.h
diff --git a/src/Generating/CompoGen.cpp b/src/Generating/CompoGen.cpp
index ef13b7c6b..db43e34b6 100644
--- a/src/Generating/CompoGen.cpp
+++ b/src/Generating/CompoGen.cpp
@@ -417,6 +417,7 @@ void cCompoGenCache::ComposeTerrain(cChunkDesc & a_ChunkDesc, const cChunkDesc::
 		// Use the cached data:
 		memcpy(a_ChunkDesc.GetBlockTypes(),             m_CacheData[Idx].m_BlockTypes, sizeof(a_ChunkDesc.GetBlockTypes()));
 		memcpy(a_ChunkDesc.GetBlockMetasUncompressed(), m_CacheData[Idx].m_BlockMetas, sizeof(a_ChunkDesc.GetBlockMetasUncompressed()));
+		memcpy(a_ChunkDesc.GetHeightMap(),              m_CacheData[Idx].m_HeightMap,  sizeof(a_ChunkDesc.GetHeightMap()));
 		
 		m_NumHits++;
 		m_TotalChain += i;
@@ -436,6 +437,7 @@ void cCompoGenCache::ComposeTerrain(cChunkDesc & a_ChunkDesc, const cChunkDesc::
 	m_CacheOrder[0] = Idx;
 	memcpy(m_CacheData[Idx].m_BlockTypes, a_ChunkDesc.GetBlockTypes(),             sizeof(a_ChunkDesc.GetBlockTypes()));
 	memcpy(m_CacheData[Idx].m_BlockMetas, a_ChunkDesc.GetBlockMetasUncompressed(), sizeof(a_ChunkDesc.GetBlockMetasUncompressed()));
+	memcpy(m_CacheData[Idx].m_HeightMap,  a_ChunkDesc.GetHeightMap(),              sizeof(a_ChunkDesc.GetHeightMap()));
 	m_CacheData[Idx].m_ChunkX = ChunkX;
 	m_CacheData[Idx].m_ChunkZ = ChunkZ;
 }
diff --git a/src/Generating/CompoGen.h b/src/Generating/CompoGen.h
index 16c00c13d..03df0cf25 100644
--- a/src/Generating/CompoGen.h
+++ b/src/Generating/CompoGen.h
@@ -132,6 +132,7 @@ protected:
 		int m_ChunkZ;
 		cChunkDef::BlockTypes        m_BlockTypes;
 		cChunkDesc::BlockNibbleBytes m_BlockMetas;  // The metas are uncompressed, 1 meta per byte
+		cChunkDef::HeightMap         m_HeightMap;
 	} ;
 	
 	// To avoid moving large amounts of data for the MRU behavior, we MRU-ize indices to an array of the actual data
diff --git a/src/Generating/CompoGenBiomal.cpp b/src/Generating/CompoGenBiomal.cpp
index 1e3363606..0bb7f4802 100644
--- a/src/Generating/CompoGenBiomal.cpp
+++ b/src/Generating/CompoGenBiomal.cpp
@@ -570,220 +570,6 @@ protected:
 			return patDirt.Get();
 		}
 	}
-	
-
-
-	#if 0
-	/** Fills a single column with grass-based terrain (grass or water, dirt, stone). */
-	void FillColumnGrass(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc)
-	{
-		static const PatternItem pattern[] =
-		{
-			{ E_BLOCK_GRASS, 0},
-			{ E_BLOCK_DIRT,  0},
-			{ E_BLOCK_DIRT,  0},
-			{ E_BLOCK_DIRT,  0},
-		} ;
-		FillColumnPattern(a_RelX, a_RelZ, a_ShapeColumn, a_ChunkDesc, pattern, ARRAYCOUNT(pattern));
-	}
-
-
-
-	/** Fills a single column with grass-based terrain (grass or water, dirt, stone). */
-	void FillColumnStone(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc)
-	{
-		static const PatternItem pattern[] =
-		{
-			{ E_BLOCK_STONE, 0},
-		} ;
-		FillColumnPattern(a_RelX, a_RelZ, a_ShapeColumn, a_ChunkDesc, pattern, ARRAYCOUNT(pattern));
-	}
-
-
-
-	/** Fills a single column with Mesa-like terrain (variations of clay). */
-	void FillColumnMesa(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc)
-	{
-		// Fill with grass and dirt on the very top of mesa plateaus:
-		size_t curIdx = 0;
-		for (int y = 255; y > m_MesaDirtLevel; y--)
-		{
-			if (a_ShapeColumn[y] > 0)
-			{
-				a_ChunkDesc.SetBlockType(a_RelX, y, a_RelZ, (curIdx > 0) ? E_BLOCK_DIRT : E_BLOCK_GRASS);
-				curIdx += 1;
-			}
-			else
-			{
-				curIdx = 0;
-			}
-		}  // for y
-
-		// Fill with clays from the DirtLevel down to SandLevel:
-		for (int y = m_MesaDirtLevel; y > m_MesaSandLevel; y--)
-		{
-			if (a_ShapeColumn[y] > 0)
-			{
-				a_ChunkDesc.SetBlockTypeMeta(a_RelX, y, a_RelZ, m_MesaPattern[y].m_BlockType, m_MesaPattern[y].m_BlockMeta);
-			}
-			else
-			{
-				curIdx = 0;
-			}
-		}  // for y
-
-		// If currently air, switch to red sand pattern:
-		static const PatternItem redSandPattern[] =
-		{
-			{ E_BLOCK_SAND,         E_META_SAND_RED},
-			{ E_BLOCK_STAINED_CLAY, E_META_STAINED_CLAY_ORANGE},
-			{ E_BLOCK_STAINED_CLAY, E_META_STAINED_CLAY_ORANGE},
-			{ E_BLOCK_STAINED_CLAY, E_META_STAINED_CLAY_ORANGE},
-		};
-		Pattern pattern;
-		size_t patternSize;
-		if (curIdx == 0)
-		{
-			pattern = redSandPattern;
-			patternSize = ARRAYCOUNT(redSandPattern);
-		}
-		else
-		{
-			pattern = m_MesaPattern + m_MesaSandLevel;
-			patternSize = static_cast<size_t>(m_MesaSandLevel);
-		}
-
-		// Fill with current pattern (MesaPattern or RedSand) until sealevel:
-		for (int y = m_MesaSandLevel; y > m_SeaLevel; y--)
-		{
-			if (a_ShapeColumn[y] > 0)
-			{
-				if (curIdx >= patternSize)
-				{
-					a_ChunkDesc.SetBlockTypeMeta(a_RelX, y, a_RelZ, E_BLOCK_STAINED_CLAY, E_META_STAINED_CLAY_ORANGE);
-				}
-				else
-				{
-					a_ChunkDesc.SetBlockTypeMeta(a_RelX, y, a_RelZ, pattern[curIdx].m_BlockType, pattern[curIdx].m_BlockMeta);
-				}
-				curIdx += 1;
-			}
-			else
-			{
-				// Air resets the pattern to red sand:
-				curIdx = 0;
-				pattern = redSandPattern;
-				patternSize = ARRAYCOUNT(redSandPattern);
-			}
-		}  // for y
-
-		// If there is an ocean, fill it with water and then redsand:
-		int y = m_SeaLevel;
-		for (; y > 0; y--)
-		{
-			if ((a_ShapeColumn[y] == 0) || (curIdx >= ARRAYCOUNT(redSandPattern)))
-			{
-				// water pocket or out of red sand pattern, use stone from now on
-				break;
-			}
-			a_ChunkDesc.SetBlockTypeMeta(a_RelX, y, a_RelZ, E_BLOCK_STAINED_CLAY, E_META_STAINED_CLAY_ORANGE);
-			curIdx = curIdx + 1;
-		}  // for y
-
-		// The rest should be filled with stone:
-		for (; y > 0; y--)
-		{
-			if (a_ShapeColumn[y] > 0)
-			{
-				a_ChunkDesc.SetBlockType(a_RelX, y, a_RelZ, E_BLOCK_STONE);
-			}
-		}  // for y
-	}
-
-
-
-	/** Fills a single column with megataiga-based terrain (grass or podzol on top). */
-	void FillColumnMegaTaiga(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc)
-	{
-		// TODO
-	}
-
-
-
-	/** Fills a single column with sand-based terrain (such as desert or beach). */
-	void FillColumnSand(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc)
-	{
-		static const PatternItem pattern[] =
-		{
-			{ E_BLOCK_SAND,      0},
-			{ E_BLOCK_SAND,      0},
-			{ E_BLOCK_SAND,      0},
-			{ E_BLOCK_SANDSTONE, 0},
-		} ;
-		FillColumnPattern(a_RelX, a_RelZ, a_ShapeColumn, a_ChunkDesc, pattern, ARRAYCOUNT(pattern));
-	}
-
-
-
-	void FillColumnMycelium(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc)
-	{
-		static const PatternItem pattern[] =
-		{
-			{ E_BLOCK_MYCELIUM, 0},
-			{ E_BLOCK_DIRT,     0},
-			{ E_BLOCK_DIRT,     0},
-			{ E_BLOCK_DIRT,     0},
-		} ;
-		FillColumnPattern(a_RelX, a_RelZ, a_ShapeColumn, a_ChunkDesc, pattern, ARRAYCOUNT(pattern));
-	}
-
-
-
-	/** Fills the column with the specified pattern, repeating it if there's an air pocket in between. */
-	void FillColumnPattern(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc, Pattern a_Pattern, size_t a_PatternSize)
-	{
-		// Fill with pattern until sealevel:
-		size_t curIdx = 0;
-		for (int y = 255; y > m_SeaLevel; y--)
-		{
-			if (a_ShapeColumn[y] > 0)
-			{
-				// Continue with the pattern:
-				if (curIdx >= a_PatternSize)
-				{
-					a_ChunkDesc.SetBlockType(a_RelX, y, a_RelZ, E_BLOCK_STONE);
-				}
-				else
-				{
-					a_ChunkDesc.SetBlockTypeMeta(a_RelX, y, a_RelZ, a_Pattern[curIdx].m_BlockType, a_Pattern[curIdx].m_BlockMeta);
-				}
-				curIdx += 1;
-			}
-			else
-			{
-				// Air pocket, restart the pattern:
-				curIdx = 0;
-			}
-		}  // for y
-
-		// From sealevel downward use the ocean floor pattern:
-		FillOceanFloor(a_RelX, a_RelZ, a_ShapeColumn, a_ChunkDesc, a_Pattern, a_PatternSize, curIdx);
-	}
-
-
-	/** Fills the blocks from sealevel down to bottom with ocean-floor pattern.
-	a_PatternStartOffset specifies the offset at which to start the pattern, in case there was air just above. */
-	void FillOceanFloor(int a_RelX, int a_RelZ, const Byte * a_ShapeColumn, cChunkDesc & a_ChunkDesc, Pattern a_Pattern, size_t a_PatternSize, size_t a_PatternStartOffset)
-	{
-		for (int y = m_SeaLevel; y > 0; y--)
-		{
-			if (a_ShapeColumn[y] > 0)
-			{
-				// TODO
-			}
-		}  // for y
-	}
-	#endif
 } ;
 
 
diff --git a/src/Generating/ComposableGenerator.cpp b/src/Generating/ComposableGenerator.cpp
index 5420e12ac..4192dfa72 100644
--- a/src/Generating/ComposableGenerator.cpp
+++ b/src/Generating/ComposableGenerator.cpp
@@ -19,6 +19,8 @@
 
 #include "CompoGenBiomal.h"
 
+#include "CompositedHeiGen.h"
+
 #include "Caves.h"
 #include "DistortedHeightmap.h"
 #include "DungeonRoomsFinisher.h"
@@ -173,7 +175,6 @@ void cComposableGenerator::DoGenerate(int a_ChunkX, int a_ChunkZ, cChunkDesc & a
 	if (a_ChunkDesc.IsUsingDefaultComposition())
 	{
 		m_CompositionGen->ComposeTerrain(a_ChunkDesc, shape);
-		ShouldUpdateHeightmap = true;
 	}
 
 	if (a_ChunkDesc.IsUsingDefaultFinish())
@@ -264,11 +265,17 @@ void cComposableGenerator::InitCompositionGen(cIniFile & a_IniFile)
 {
 	m_CompositionGen = cTerrainCompositionGen::CreateCompositionGen(a_IniFile, m_BiomeGen, m_ShapeGen, m_ChunkGenerator.GetSeed());
 	
+	// Add a cache over the composition generator:
+	// Even a cache of size 1 is useful due to the CompositedHeiGen cache after us doing re-composition on its misses
 	int CompoGenCacheSize = a_IniFile.GetValueSetI("Generator", "CompositionGenCacheSize", 64);
-	if (CompoGenCacheSize > 1)
+	if (CompoGenCacheSize > 0)
 	{
-		m_CompositionGen = cTerrainCompositionGenPtr(new cCompoGenCache(m_CompositionGen, 32));
+		m_CompositionGen = std::make_shared<cCompoGenCache>(m_CompositionGen, CompoGenCacheSize);
 	}
+
+	// Create a cache of the composited heightmaps, so that finishers may use it:
+	m_CompositedHeightCache = std::make_shared<cHeiGenMultiCache>(std::make_shared<cCompositedHeiGen>(m_ShapeGen, m_CompositionGen), 16, 24);
+	// 24 subcaches of depth 16 each = 96 KiB of RAM. Acceptable, for the amount of work this saves.
 }
 
 
diff --git a/src/Generating/CompositedHeiGen.h b/src/Generating/CompositedHeiGen.h
new file mode 100644
index 000000000..fa33a7861
--- /dev/null
+++ b/src/Generating/CompositedHeiGen.h
@@ -0,0 +1,49 @@
+
+// CompositedHeiGen.h
+
+// Declares the cCompositedHeiGen class representing a cTerrainHeightGen descendant that calculates heightmap of the composited terrain
+// This is used to further cache heightmaps for chunks already generated for finishers that require only heightmap information
+
+
+
+
+
+#pragma once
+
+#include "ComposableGenerator.h"
+
+
+
+
+
+class cCompositedHeiGen:
+	public cTerrainHeightGen
+{
+public:
+	cCompositedHeiGen(cTerrainShapeGenPtr a_ShapeGen, cTerrainCompositionGenPtr a_CompositionGen):
+		m_ShapeGen(a_ShapeGen),
+		m_CompositionGen(a_CompositionGen)
+	{
+	}
+
+
+
+	// cTerrainheightGen overrides:
+	virtual void GenHeightMap(int a_ChunkX, int a_ChunkZ, cChunkDef::HeightMap & a_HeightMap) override
+	{
+		cChunkDesc::Shape shape;
+		m_ShapeGen->GenShape(a_ChunkX, a_ChunkZ, shape);
+		cChunkDesc desc(a_ChunkX, a_ChunkZ);
+		desc.SetHeightFromShape(shape);
+		m_CompositionGen->ComposeTerrain(desc, shape);
+		memcpy(a_HeightMap, desc.GetHeightMap(), sizeof(a_HeightMap));
+	}
+
+protected:
+	cTerrainShapeGenPtr m_ShapeGen;
+	cTerrainCompositionGenPtr m_CompositionGen;
+};
+
+
+
+
diff --git a/src/Generating/HeiGen.cpp b/src/Generating/HeiGen.cpp
index 86f934c16..61d087c17 100644
--- a/src/Generating/HeiGen.cpp
+++ b/src/Generating/HeiGen.cpp
@@ -150,6 +150,51 @@ bool cHeiGenCache::GetHeightAt(int a_ChunkX, int a_ChunkZ, int a_RelX, int a_Rel
 
 
 ////////////////////////////////////////////////////////////////////////////////
+// cHeiGenMultiCache:
+
+cHeiGenMultiCache::cHeiGenMultiCache(cTerrainHeightGenPtr a_HeiGenToCache, size_t a_SubCacheSize, size_t a_NumSubCaches):
+	m_NumSubCaches(a_NumSubCaches)
+{
+	// Create the individual sub-caches:
+	m_SubCaches.reserve(a_NumSubCaches);
+	for (size_t i = 0; i < a_NumSubCaches; i++)
+	{
+		m_SubCaches.push_back(std::make_shared<cHeiGenCache>(a_HeiGenToCache, a_SubCacheSize));
+	}
+}
+
+
+
+
+
+void cHeiGenMultiCache::GenHeightMap(int a_ChunkX, int a_ChunkZ, cChunkDef::HeightMap & a_HeightMap)
+{
+	// Get the subcache responsible for this chunk:
+	const size_t cacheIdx = ((size_t)a_ChunkX + m_CoeffZ * (size_t)a_ChunkZ) % m_NumSubCaches;
+
+	// Ask the subcache:
+	m_SubCaches[cacheIdx]->GenHeightMap(a_ChunkX, a_ChunkZ, a_HeightMap);
+}
+
+
+
+
+
+bool cHeiGenMultiCache::GetHeightAt(int a_ChunkX, int a_ChunkZ, int a_RelX, int a_RelZ, HEIGHTTYPE & a_Height)
+{
+	// Get the subcache responsible for this chunk:
+	const size_t cacheIdx = ((size_t)a_ChunkX + m_CoeffZ * (size_t)a_ChunkZ) % m_NumSubCaches;
+
+	// Ask the subcache:
+	return m_SubCaches[cacheIdx]->GetHeightAt(a_ChunkX, a_ChunkZ, a_RelX, a_RelZ, a_Height);
+}
+
+
+
+
+
+
+////////////////////////////////////////////////////////////////////////////////
 // cHeiGenClassic:
 
 cHeiGenClassic::cHeiGenClassic(int a_Seed) :
diff --git a/src/Generating/HeiGen.h b/src/Generating/HeiGen.h
index d91ace3bd..fe0a023e4 100644
--- a/src/Generating/HeiGen.h
+++ b/src/Generating/HeiGen.h
@@ -63,6 +63,38 @@ protected:
 
 
 
+/** Caches heightmaps in multiple underlying caches to improve the distribution and lower the chain length. */
+class cHeiGenMultiCache:
+	public cTerrainHeightGen
+{
+public:
+	cHeiGenMultiCache(cTerrainHeightGenPtr a_HeightGenToCache, size_t a_SubCacheSize, size_t a_NumSubCaches);
+
+	// cTerrainHeightGen overrides:
+	virtual void GenHeightMap(int a_ChunkX, int a_ChunkZ, cChunkDef::HeightMap & a_HeightMap) override;
+	
+	/** Retrieves height at the specified point in the cache, returns true if found, false if not found */
+	bool GetHeightAt(int a_ChunkX, int a_ChunkZ, int a_RelX, int a_RelZ, HEIGHTTYPE & a_Height);
+
+protected:
+	typedef SharedPtr<cHeiGenCache> cHeiGenCachePtr;
+	typedef std::vector<cHeiGenCachePtr> cHeiGenCachePtrs;
+
+
+	/** The coefficient used to turn Z coords into index (x + Coeff * z). */
+	static const size_t m_CoeffZ = 5;
+
+	/** Number of sub-caches, pulled out of m_SubCaches.size() for performance reasons. */
+	size_t m_NumSubCaches;
+
+	/** The individual sub-caches. */
+	cHeiGenCachePtrs m_SubCaches;
+};
+
+
+
+
+
 class cHeiGenFlat :
 	public cTerrainHeightGen
 {
diff --git a/src/Generating/StructGen.cpp b/src/Generating/StructGen.cpp
index 1c83cf78f..ca8f0411f 100644
--- a/src/Generating/StructGen.cpp
+++ b/src/Generating/StructGen.cpp
@@ -42,6 +42,7 @@ void cStructGenTrees::GenFinish(cChunkDesc & a_ChunkDesc)
 				cChunkDesc::Shape workerShape;
 				m_BiomeGen->GenBiomes           (BaseX, BaseZ, WorkerDesc.GetBiomeMap());
 				m_ShapeGen->GenShape            (BaseX, BaseZ, workerShape);
+				WorkerDesc.SetHeightFromShape   (workerShape);
 				m_CompositionGen->ComposeTerrain(WorkerDesc, workerShape);
 			}
 			else