Erosion 7
From DaveWiki
Our next (big) step is to add the code for finding lakes in the height map. Our basic algorithm will be:
- Find a local minimum (just like during the erosion process)
- Start filling this minimum little by little
- Once the filling "overflows" and reaches sea level we stop
#include "erosion6.h" /* Stores basic information on one lake */ struct lake_t { int X; /* The position of the local minimum that started the lake */ int Y; float Height; /* The computed height of the lake */ int OutX; /* The estimated output location of the lake */ int OutY; int Tag; /* Custom field for future use */ }; /* Define a dynamic list of lakes */ typedef std::vector<lake_t> CLakeVector; class CErosionSample7 : public CErosionSample6 { public: /* Controls how accurately the lake levels are computed */ float FILL_DELTA; /* Extra height maps for storing the lake information */ utils::NoiseMap m_LakeMap; utils::NoiseMap m_LakeTempMap; utils::NoiseMap m_CombinedMap; /* Used during the lake filling process */ utils::NoiseMap* m_pFillLakeSource; utils::NoiseMap* m_pFillLakeOutput; /* Used during the lake detection process */ bool m_FoundLakeOut; int m_LakeOutX; int m_LakeOutY; /* List of existing lakes */ CLakeVector m_Lakes; /* * Class Constructor */ CErosionSample7() { FILL_DELTA = 0.001f; m_FoundLakeOut = false; m_LakeOutX = -1; m_LakeOutY = -1; } /* * Override to initialize the new erosion height map. */ virtual void CreateBaseNoise (void) { CErosionSample6::CreateBaseNoise(); m_LakeMap.SetSize(m_Width, m_Height); davelib::FillHeightMap(m_LakeMap, -1); } /* * Fills a lake at the given position to the given level using a recursive flood fill that fills in all * points adjacent to (X,Y) that are lower than Level. If a point lower than PrevLevel is encountered that * position is recorded as a possible lake output point. If sea level is reached the function immediately * stops filling and returns true. */ virtual bool FillLake (const int X, const int Y, const float Level, const float PrevLevel) { bool Result; /* Stop if we've reached sea level */ if (m_pFillLakeSource->GetValue(X, Y) <= m_SeaLevel) return (true); /* Ignore land higher than the lake level */ if (m_pFillLakeSource->GetValue(X, Y) >= Level || m_pFillLakeSource->GetValue(X, Y) >= Level) return (false); /* Check for going below the previous lake level, this indicates * we've found a possible lake output. */ if (!m_FoundLakeOut && m_pFillLakeSource->GetValue(X, Y) < PrevLevel) { m_LakeOutX = X; m_LakeOutY = Y; m_FoundLakeOut = true; } m_pFillLakeSource->SetValue(X, Y, Level); if (m_pFillLakeOutput != NULL) m_pFillLakeOutput->SetValue(X, Y, Level); if (X+1 < m_Width) { Result = FillLake(X+1, Y+0, Level, PrevLevel); if (Result) return (true); if (Y+1 < m_Height) { Result = FillLake(X+1, Y+1, Level, PrevLevel); if (Result) return (true); } if (Y-1 >= 0) { Result = FillLake(X+1, Y-1, Level, PrevLevel); if (Result) return (true); } } if (X-1 >= 0) { Result = FillLake(X-1, Y+0, Level, PrevLevel); if (Result) return (true); if (Y+1 < m_Height) { Result = FillLake(X-1, Y+1, Level, PrevLevel); if (Result) return (true); } if (Y-1 >= 0) { Result = FillLake(X-1, Y-1, Level, PrevLevel); if (Result) return (true); } } if (Y+1 < m_Height) { Result = FillLake(X+0, Y+1, Level, PrevLevel); if (Result) return (true); } if (Y-1 >= 0) { Result = FillLake(X+0, Y-1, Level, PrevLevel); if (Result) return (true); } return (false); } /* * Adds a new lake to the list of existing lakes. Does not check for duplicates. */ virtual void AddLake (const int X, const int Y, const float Level, const int OutX, const int OutY) { lake_t TempLake; TempLake.X = X; TempLake.Y = Y; TempLake.Height = Level; TempLake.OutX = OutX; TempLake.OutY = OutY; TempLake.Tag = 0; m_Lakes.push_back(TempLake); } /* * Looks for an existing lake at the given local minimum point. Returns the lake * object on success or NULL if none was found. */ virtual lake_t* FindExistingLake (const int X, const int Y) { CLakeVector::iterator iLake; iLake = m_Lakes.begin(); while( iLake != m_Lakes.end() ) { if (iLake->X == X && iLake->Y == Y) return &(*iLake); ++iLake; } return (NULL); } /* * Helper method to CreateLakeMap(), outputs one lake to the lake height map. */ virtual void CreateLakeMap (lake_t& Lake) { FillLake(Lake.X, Lake.Y, Lake.Height, -1); } /* * Outputs all found lakes to the lake height map. */ virtual void CreateLakeMap (void) { CLakeVector::iterator iLake; utils::NoiseMap TempMap; TempMap = m_HeightMap; m_pFillLakeSource = &TempMap; m_pFillLakeOutput = &m_LakeMap; m_FoundLakeOut = true; iLake = m_Lakes.begin(); while( iLake != m_Lakes.end() ) { CreateLakeMap(*iLake); ++iLake; } } /* * Computes the lake level from the given local minimum position. Slowly increases the lake level * until the lake overflows and reaches the sea. */ virtual bool FindLakeLevel (const int OrigX, const int OrigY) { bool Result; float LakeLevel; float NewLevel; m_LakeTempMap = m_HeightMap; m_LakeTempMap.SetBorderValue(2); m_pFillLakeSource = &m_LakeTempMap; m_pFillLakeOutput = &m_LakeTempMap; LakeLevel = m_LakeTempMap.GetValue(OrigX, OrigY); while (LakeLevel < 1.0) { NewLevel = LakeLevel + FILL_DELTA; m_FoundLakeOut = false; m_LakeOutX = -1; m_LakeOutY = -1; Result = FillLake(OrigX, OrigY, NewLevel, LakeLevel); if (Result) break; LakeLevel = NewLevel; } AddLake(OrigX, OrigY, LakeLevel, m_LakeOutX, m_LakeOutY); return (true); } /* * Starts looking for lakes from the given point in the height map. Returns true if a new or existing lake was found. */ virtual bool FindLakes (const int OrigX, const int OrigY) { float Value; bool Result; int X = OrigX; int Y = OrigY; /* Find the first local minimum from the original point */ do { Result = davelib::FindMinimumNeighbour(m_HeightMap, X, Y); } while (Result); /* Stop if we've reached sea level directly */ Value = m_HeightMap.GetValue(X, Y); if (Value <= m_SeaLevel) return (false); /* Already found this lake? */ if (FindExistingLake(X, Y) != NULL) return (true); printf("Lake found at (%d, %d)\n", OrigX, OrigY); FindLakeLevel(X, Y); return (true); } /* * Looks for lakes beginning at each point in the height map. */ virtual void FindAllLakes (void) { int X, Y; for (Y = 0; Y < m_HeightMap.GetHeight(); ++Y) { for (X = 0; X < m_HeightMap.GetWidth(); ++X) { FindLakes(X, Y); } } } /* * Combines the base height map and the lake map into one. */ virtual void CreateCombinedMap (void) { int X, Y; m_CombinedMap.SetSize(m_HeightMap.GetWidth(), m_HeightMap.GetHeight()); for (Y = 0; Y < m_HeightMap.GetHeight(); ++Y) { for (X = 0; X < m_HeightMap.GetWidth(); ++X) { if (m_LakeMap.GetValue(X,Y) > -1) { m_CombinedMap.SetValue(X, Y, m_LakeMap.GetValue(X,Y)); } else { m_CombinedMap.SetValue(X, Y, m_HeightMap.GetValue(X,Y)); } } } } }; int _tmain(int argc, _TCHAR* argv[]) { CErosionSample7 ErosionSample; ErosionSample.CreateBaseNoise(); ErosionSample.FillSeaLevel(0.1f); davelib::OutputHeightMapGrayScale("erosion7a.bmp", ErosionSample.m_HeightMap); ErosionSample.FindAllLakes(); ErosionSample.CreateLakeMap(); davelib::OutputHeightMapGrayScale("erosion7b.bmp", ErosionSample.m_LakeMap); ErosionSample.CreateCombinedMap(); davelib::OutputHeightMapGrayScale("erosion7c.bmp", ErosionSample.m_CombinedMap); return 0; }
There is a lot here so we'll explain on a method-by-method basis:
- FindAllLakes() -- The start of the process to find all lakes in the height map. Simply iterates through each point in the map and starts the find process. Note that this will find a large number of duplicate lakes but optimization at this point is not needed.
- FindLakes() -- Looks for all lakes beginning at the specified point. Just like the erosion process we travel downhill until we hit a local minimum. If we have already found this minimum we stop, otherwise we continue to try and determine what the lake level should be.
- FindLakeLevel() -- Determines what the level of the lake at the specified local minimum position should be. The lake is filled by slowly increasing the level until we find a level that touches the sea. The lake level will then be the previous level. Once a level is found the lake information is added to a list of known lakes.
- CreateLakeMap() -- These two method simply output all the currently found lakes to the m_LakeMap height map object.
- FindExistingLake() -- Attempt to find an existing lake based on the given local minimum position. Note that this technique is far from perfect as each lake may have multiple low points within it but it is sufficient to speed up the process somewhat.
- AddLake() -- Adds a new lake to the list of known lakes.
- FillLake() -- A relatively basic recursive flood fill method to fill a lake to a set level as well as to detect if sea level is reached and the possible location of the lake output. The flood fill is implemented by filling in adjacent pixels that are lower than the currently set fill level (i.e., water can flow downhill but not uphill). Thus when a lake basin is completely filled it will overflow and reach the sea stopping the fill process.
The ultimate result of all this is an height map recording all lake positions and levels:
A few notes on the lake finding technique so far:
- The process will find duplicate lakes if that lake has multiple low points (which larger lakes will typically have).
- The current implementation is slow (compared to the previous erosion steps), in part due to finding duplicate lakes.
- There is a balance in setting FILL_DELTA to find an accurate level versus not taking too long. A better (and much more complicated) method would be to use some sort of binary splitting to more accurately and quickly find a lake level.
