3 files changed, 152 insertions, 6 deletions

diff --git a/src/Generating/Prefab.h b/src/Generating/Prefab.h
index 37db2ff16..472584c3a 100644
--- a/src/Generating/Prefab.h
+++ b/src/Generating/Prefab.h
@@ -95,6 +95,9 @@ public:
 	/** Returns the weight (chance) of this prefab generating as the next piece after the specified placed piece.
 	PiecePool implementations can use this for their GetPieceWeight() implementations. */
 	int GetPieceWeight(const cPlacedPiece & a_PlacedPiece, const cPiece::cConnector & a_ExistingConnector) const;
+	
+	/** Returns the unmodified DefaultWeight property for the piece. */
+	int GetDefaultWeight(void) const { return m_DefaultWeight; }
 
 protected:
 	/** Packs complete definition of a single block, for per-letter assignment. */
diff --git a/src/Generating/VillageGen.cpp b/src/Generating/VillageGen.cpp
index fb6191df2..3d89d7aa2 100644
--- a/src/Generating/VillageGen.cpp
+++ b/src/Generating/VillageGen.cpp
@@ -12,30 +12,167 @@
 
 
 
+/*
+How village generating works:
+By descending from a cGridStructGen, a semi-random grid is generated. A village may be generated for each of
+the grid's cells. Each cell checks the biomes in an entire chunk around it, only generating a village if all
+biomes are village-friendly. If yes, the entire village structure is built for that cell. If not, the cell
+is left village-less.
+
+A village is generated starting by its well. The well is placed in the grid's origin point. Then a set of
+random lengths roads is generated - 4 roads going from the well, then at the end of each road another set of
+roads, crossing them perpendicular, then at the end of those another set, up to a set maximum branching
+depth. The roads are placed in a T or L shape, with the old road being the center stem of the T. Roads avoid
+crossing each other and going further away from the well than the maximum block size of the village.
+Finally, houses are places along the roads, avoiding collisions with already-existing items.
+
+When the village is about to be drawn into a chunk, it queries the heights for each item intersecting the
+chunk. The prefabs are shifted so that their pivot points lie on the surface, and the roads are drawn
+directly by turning the surface blocks into gravel / sandstone.
+*/
+
 class cVillageGen::cVillage :
 	public cGridStructGen::cStructure
 {
 	typedef cGridStructGen::cStructure super;
 	
 public:
-	cVillage(int a_Seed, int a_OriginX, int a_OriginZ, cPrefabPiecePool & a_Prefabs) :
+	cVillage(
+		int a_Seed,
+		int a_OriginX, int a_OriginZ,
+		int a_MaxRoadDepth,
+		int a_MaxSize,
+		cPrefabPiecePool & a_Prefabs,
+		cTerrainHeightGen & a_HeightGen
+	) :
 		super(a_OriginX, a_OriginZ),
 		m_Seed(a_Seed),
-		m_Prefabs(a_Prefabs)
+		m_Noise(a_Seed),
+		m_MaxSize(a_MaxSize),
+		m_Borders(a_OriginX - a_MaxSize, 0, a_OriginZ - a_MaxSize, a_OriginX + a_MaxSize, 255, a_OriginZ + a_MaxSize),
+		m_Prefabs(a_Prefabs),
+		m_HeightGen(a_HeightGen)
 	{
+		PlaceWell();
+		BuildRoads(a_MaxRoadDepth);
+		PlaceHouses();
 	}
 	
 protected:
+	class cItem
+	{
+	public:
+		/* The position of the item, X/Z-wise: */
+		int m_MinX, m_MaxX, m_MinZ, m_MaxZ;
+		
+		/** The prefab to use. If NULL, this is a road. */
+		cPrefab * m_Prefab;
+		
+		/** Number of rotations that should be applied to the prefab. */
+		int m_NumRotations;
+		
+		/* The bottom of the prefab. Only valid if the item is a prefab, not valid for roads. */
+		int m_BaseY;
+		
+		/** Creates a new item with the specified parameters.
+		m_BaseY is set to -1 and will be adjusted later on when drawing. */
+		cItem(int a_MinX, int a_MaxX, int a_MinZ, int a_MaxZ, cPrefab * a_Prefab, int a_NumRotations) :
+			m_MinX(a_MinX),
+			m_MaxX(a_MaxX),
+			m_MinZ(a_MinZ),
+			m_MaxZ(a_MaxZ),
+			m_Prefab(a_Prefab),
+			m_NumRotations(a_NumRotations),
+			m_BaseY(-1)
+		{
+		}
+	} ;
+	typedef SharedPtr<cItem> cItemPtr;
+	typedef std::vector<cItemPtr> cItemPtrs;
+	
+	
 	/** Seed for the random functions */
 	int m_Seed;
 	
+	/** The noise used as a pseudo-random generator */
+	cNoise m_Noise;
+	
+	/** Maximum size, in X/Z blocks, of the village (radius from the origin) */
+	int m_MaxSize;
+	
+	/** Borders of the vilalge - no item may reach out of this cuboid. */
+	cCuboid m_Borders;
+	
 	/** Prefabs to use for buildings */
 	cPrefabPiecePool & m_Prefabs;
 	
+	/** The underlying height generator, used for placing the structures on top of the terrain. */
+	cTerrainHeightGen & m_HeightGen;
+	
+	/** The items that are generated in the village (houses, roads). */
+	cItemPtrs m_Items;
+	
+	
+	/** Places the well at the center of the village */
+	void PlaceWell(void)
+	{
+		// Pick a prefab from the starting pieces:
+		cPieces StartingPieces = ((cPiecePool &)m_Prefabs).GetStartingPieces();
+		ASSERT(!StartingPieces.empty());
+		int TotalWeight = 0;
+		for (cPieces::const_iterator itr = StartingPieces.begin(), end = StartingPieces.end(); itr != end; ++itr)
+		{
+			TotalWeight += ((const cPrefab *)(*itr))->GetDefaultWeight();
+		}
+		ASSERT(TotalWeight > 0);
+		int rnd = (m_Noise.IntNoise2DInt(m_OriginX, m_OriginZ) / 7) % TotalWeight;
+		cPiece * WellPiece = StartingPieces[0];
+		for (cPieces::const_iterator itr = StartingPieces.begin(), end = StartingPieces.end(); itr != end; ++itr)
+		{
+			rnd -= ((const cPrefab *)(*itr))->GetDefaultWeight();
+			if (rnd <= 0)
+			{
+				WellPiece = *itr;
+				break;
+			}
+		}
+		ASSERT(WellPiece != NULL);
+		
+		// Pick a rotation:
+		// TODO
+		int NumRotations = 0;
+		Vector3i Size = WellPiece->GetSize();
+		
+		// Put the well in the placed items array:
+		m_Items.push_back(cItemPtr(new cItem(m_OriginX, m_OriginX + Size.x, m_OriginZ, m_OriginZ + Size.z, (cPrefab *)WellPiece, NumRotations)));
+	}
+	
+	
+	/** Places the roads going from the well outwards. */
+	void BuildRoads(int a_MaxRoadDepth)
+	{
+		/*
+		ASSERT(m_Items.size() == 1);
+		const cItem & Well = *m_Items[0];
+		*/
+		// TODO
+	}
+	
+	
+	/** Places houses along the roads. */
+	void PlaceHouses(void)
+	{
+		// TODO
+	}
+	
+	
 	// cGrdStructGen::cStructure overrides:
 	virtual void DrawIntoChunk(cChunkDesc & a_Chunk) override
 	{
 		// TODO
+		// Iterate over all items
+		// Each intersecting prefab is placed on ground (if not already placed), then drawn
+		// Each intersecting road is drawn by replacing top soil blocks with gravel / sandstone blocks
 	}
 } ;
 
@@ -53,8 +190,8 @@ cPrefabPiecePool cVillageGen::m_PlainsVillage(g_PlainsVillagePrefabs, g_PlainsVi
 
 
 
-cVillageGen::cVillageGen(int a_Seed, int a_GridSize, cBiomeGen & a_BiomeGen, cTerrainHeightGen & a_HeightGen) :
-	super(a_Seed, a_GridSize, a_GridSize, 128, 128, 100),
+cVillageGen::cVillageGen(int a_Seed, int a_GridSize, int a_MaxRoadDepth, int a_MaxSize, cBiomeGen & a_BiomeGen, cTerrainHeightGen & a_HeightGen) :
+	super(a_Seed, a_GridSize, a_GridSize, a_MaxSize, a_MaxSize, 100),
 	m_BiomeGen(a_BiomeGen),
 	m_HeightGen(a_HeightGen)
 {
@@ -108,7 +245,7 @@ cGridStructGen::cStructurePtr cVillageGen::CreateStructure(int a_OriginX, int a_
 	{
 		return cStructurePtr();
 	}
-	return cStructurePtr(new cVillage(m_Seed, a_OriginX, a_OriginZ, *VillagePrefabs));
+	return cStructurePtr(new cVillage(m_Seed, a_OriginX, a_OriginZ, m_MaxRoadDepth, m_MaxSize, *VillagePrefabs, m_HeightGen));
 }
 
 
diff --git a/src/Generating/VillageGen.h b/src/Generating/VillageGen.h
index d3cc8ef9c..acbd76881 100644
--- a/src/Generating/VillageGen.h
+++ b/src/Generating/VillageGen.h
@@ -21,7 +21,7 @@ class cVillageGen :
 {
 	typedef cGridStructGen super;
 public:
-	cVillageGen(int a_Seed, int a_GridSize, cBiomeGen & a_BiomeGen, cTerrainHeightGen & a_HeightGen);
+	cVillageGen(int a_Seed, int a_GridSize, int a_MaxRoadDepth, int a_MaxSize, cBiomeGen & a_BiomeGen, cTerrainHeightGen & a_HeightGen);
 
 protected:
 	class cVillage;  // fwd: VillageGen.cpp
@@ -31,6 +31,12 @@ protected:
 
 	/** The prefabs for the plains village. We're not exactly using the cPiecePool functionality, only the containment. */
 	static cPrefabPiecePool m_PlainsVillage;
+	
+	/** Maximum number of roads generated one from another (tree depth). */
+	int m_MaxRoadDepth;
+	
+	/** Maximum size, in X/Z blocks, of the village (radius from the origin) */
+	int m_MaxSize;
 
 	/** The underlying biome generator that defines whether the village is created or not */
 	cBiomeGen & m_BiomeGen;