From 9db9445e9fec2ce0ab52434e50cc21f30d4ef313 Mon Sep 17 00:00:00 2001 From: madmaxoft Date: Fri, 20 Jun 2014 17:10:18 +0200 Subject: Optimized Voronoi calculation. Fixes #818. --- src/Generating/BioGen.cpp | 21 ++++++++++++-------- src/Generating/BioGen.h | 7 ++++++- src/VoronoiMap.cpp | 49 ++++++++++++++++++++++++++++++++++++++--------- src/VoronoiMap.h | 25 +++++++++++++++++++++--- 4 files changed, 81 insertions(+), 21 deletions(-) (limited to 'src') diff --git a/src/Generating/BioGen.cpp b/src/Generating/BioGen.cpp index 3e3a034b2..a17555f37 100644 --- a/src/Generating/BioGen.cpp +++ b/src/Generating/BioGen.cpp @@ -747,7 +747,12 @@ cBioGenTwoLevel::cBioGenTwoLevel(int a_Seed) : m_VoronoiSmall(a_Seed + 2000), m_DistortX(a_Seed + 3000), m_DistortZ(a_Seed + 4000), - m_Noise(a_Seed + 5000) + m_Noise1(a_Seed + 5001), + m_Noise2(a_Seed + 5002), + m_Noise3(a_Seed + 5003), + m_Noise4(a_Seed + 5004), + m_Noise5(a_Seed + 5005), + m_Noise6(a_Seed + 5006) { } @@ -769,12 +774,12 @@ void cBioGenTwoLevel::GenBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap int BlockZ = BaseZ + z * 4; float BlockXF = (float)(16 * BlockX) / 128; float BlockZF = (float)(16 * BlockZ) / 128; - double NoiseX = m_Noise.CubicNoise3D(BlockXF / 16, BlockZF / 16, 1000); - NoiseX += 0.5 * m_Noise.CubicNoise3D(BlockXF / 8, BlockZF / 8, 2000); - NoiseX += 0.08 * m_Noise.CubicNoise3D(BlockXF, BlockZF, 3000); - double NoiseZ = m_Noise.CubicNoise3D(BlockXF / 16, BlockZF / 16, 4000); - NoiseZ += 0.5 * m_Noise.CubicNoise3D(BlockXF / 8, BlockZF / 8, 5000); - NoiseZ += 0.08 * m_Noise.CubicNoise3D(BlockXF, BlockZF, 6000); + double NoiseX = m_Noise1.CubicNoise2D(BlockXF / 16, BlockZF / 16); + NoiseX += 0.5 * m_Noise2.CubicNoise2D(BlockXF / 8, BlockZF / 8); + NoiseX += 0.08 * m_Noise3.CubicNoise2D(BlockXF, BlockZF); + double NoiseZ = m_Noise4.CubicNoise2D(BlockXF / 16, BlockZF / 16); + NoiseZ += 0.5 * m_Noise5.CubicNoise2D(BlockXF / 8, BlockZF / 8); + NoiseZ += 0.08 * m_Noise6.CubicNoise2D(BlockXF, BlockZF); DistortX[4 * x][4 * z] = BlockX + (int)(64 * NoiseX); DistortZ[4 * x][4 * z] = BlockZ + (int)(64 * NoiseZ); @@ -788,8 +793,8 @@ void cBioGenTwoLevel::GenBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap { for (int x = 0; x < cChunkDef::Width; x++) { - int BiomeGroup = m_VoronoiLarge.GetValueAt(DistortX[x][z], DistortZ[x][z]) / 7; int MinDist1, MinDist2; + int BiomeGroup = m_VoronoiLarge.GetValueAt(DistortX[x][z], DistortZ[x][z], MinDist1, MinDist2) / 7; int BiomeIdx = m_VoronoiSmall.GetValueAt(DistortX[x][z], DistortZ[x][z], MinDist1, MinDist2) / 11; cChunkDef::SetBiome(a_BiomeMap, x, z, SelectBiome(BiomeGroup, BiomeIdx, (MinDist1 < MinDist2 / 4) ? 0 : 1)); } diff --git a/src/Generating/BioGen.h b/src/Generating/BioGen.h index 8bd460d8f..227ec97d7 100644 --- a/src/Generating/BioGen.h +++ b/src/Generating/BioGen.h @@ -261,7 +261,12 @@ protected: /// The noise used to distort the inupt Z coord cPerlinNoise m_DistortZ; - cNoise m_Noise; + cNoise m_Noise1; + cNoise m_Noise2; + cNoise m_Noise3; + cNoise m_Noise4; + cNoise m_Noise5; + cNoise m_Noise6; // cBiomeGen overrides: diff --git a/src/VoronoiMap.cpp b/src/VoronoiMap.cpp index 7a36edebc..9c3ca7e65 100644 --- a/src/VoronoiMap.cpp +++ b/src/VoronoiMap.cpp @@ -11,7 +11,9 @@ cVoronoiMap::cVoronoiMap(int a_Seed, int a_CellSize) : - m_Noise(a_Seed), + m_Noise1(a_Seed + 1), + m_Noise2(a_Seed + 2), + m_Noise3(a_Seed + 3), m_CellSize(a_CellSize) { } @@ -57,26 +59,25 @@ int cVoronoiMap::GetValueAt(int a_X, int a_Y, int & a_MinDist1, int & a_MinDist2 int CellX = a_X / m_CellSize; int CellZ = a_Y / m_CellSize; + UpdateCell(CellX, CellZ); + // Get 5x5 neighboring cell seeds, compare distance to each. Return the value in the minumim-distance cell int MinDist = m_CellSize * m_CellSize * 16; // There has to be a cell closer than this int MinDist2 = MinDist; int res = 0; // Will be overriden - for (int x = CellX - 2; x <= CellX + 2; x++) + for (int x = 0; x < 5; x++) { - int BaseX = x * m_CellSize; - for (int z = CellZ - 2; z < CellZ + 2; z++) + for (int z = 0; z < 5; z++) { - int OffsetX = (m_Noise.IntNoise3DInt(x, 16 * x + 32 * z, z) / 8) % m_CellSize; - int OffsetZ = (m_Noise.IntNoise3DInt(x, 32 * x - 16 * z, z) / 8) % m_CellSize; - int SeedX = BaseX + OffsetX; - int SeedZ = z * m_CellSize + OffsetZ; + int SeedX = m_SeedX[x][z]; + int SeedZ = m_SeedZ[x][z]; int Dist = (SeedX - a_X) * (SeedX - a_X) + (SeedZ - a_Y) * (SeedZ - a_Y); if (Dist < MinDist) { MinDist2 = MinDist; MinDist = Dist; - res = m_Noise.IntNoise3DInt(x, x - z + 1000, z); + res = m_Noise3.IntNoise2DInt(x + CellX - 2, z + CellZ - 2); } else if (Dist < MinDist2) { @@ -93,3 +94,33 @@ int cVoronoiMap::GetValueAt(int a_X, int a_Y, int & a_MinDist1, int & a_MinDist2 + +void cVoronoiMap::UpdateCell(int a_CellX, int a_CellZ) +{ + // If the specified cell is currently cached, bail out: + if ((a_CellX == m_CurrentCellX) && (a_CellZ == m_CurrentCellZ)) + { + return; + } + + // Update the cell cache for the new cell position: + int NoiseBaseX = a_CellX - 2; + int NoiseBaseZ = a_CellZ - 2; + for (int x = 0; x < 5; x++) + { + int BaseX = (NoiseBaseX + x) * m_CellSize; + for (int z = 0; z < 5; z++) + { + int OffsetX = (m_Noise1.IntNoise2DInt(NoiseBaseX + x, NoiseBaseZ + z) / 8) % m_CellSize; + int OffsetZ = (m_Noise2.IntNoise2DInt(NoiseBaseX + x, NoiseBaseZ + z) / 8) % m_CellSize; + m_SeedX[x][z] = BaseX + OffsetX; + m_SeedZ[x][z] = (NoiseBaseZ + z) * m_CellSize + OffsetZ; + } // for z + } // for x + m_CurrentCellX = a_CellX; + m_CurrentCellZ = a_CellZ; +} + + + + diff --git a/src/VoronoiMap.h b/src/VoronoiMap.h index bcd37f9cf..84cf206e9 100644 --- a/src/VoronoiMap.h +++ b/src/VoronoiMap.h @@ -29,15 +29,34 @@ public: /// Returns the value in the cell into which the specified point lies, and the distance to the nearest Voronoi seed int GetValueAt(int a_X, int a_Y, int & a_MinDistance); - /// Returns the value in the cell into which the specified point lies, and the distances to the 2 nearest Voronoi seeds + /// Returns the value in the cell into which the specified point lies, and the distances to the 2 nearest Voronoi seeds. Uses a cache int GetValueAt(int a_X, int a_Y, int & a_MinDistance1, int & a_MinDistance2); - + protected: /// The noise used for generating Voronoi seeds - cNoise m_Noise; + cNoise m_Noise1; + cNoise m_Noise2; + cNoise m_Noise3; /// Size of the Voronoi cells (avg X/Y distance between the seeds) int m_CellSize; + + /** The X coordinate of the currently cached cell neighborhood */ + int m_CurrentCellX; + + /** The Z coordinate of the currently cached cell neighborhood */ + int m_CurrentCellZ; + + /** The seeds of cells around m_CurrentCellX, m_CurrentCellZ, X-coords */ + int m_SeedX[5][5]; + + /** The seeds of cells around m_CurrentCellX, m_CurrentCellZ, X-coords */ + int m_SeedZ[5][5]; + + + /** Updates the cached cell seeds to match the specified cell. Noop if cell pos already matches. + Updates m_SeedX and m_SeedZ. */ + void UpdateCell(int a_CellX, int a_CellZ); } ; -- cgit v1.2.3