Erosion 9

From DaveWiki

Jump to: navigation, search

Now that we have a lake detection system in place we can attempt to combine the lakes and erosion in order to produce a continuous river system which was our goal at the beginning. The lake creation code already records what it considers to be the lake output (shown as pink pixels in the following height map):

A sharp eye might notice that most of the lake outputs are not actually touching the lake which is due to how those points are chosen. For now this should be fine.

To modify our erosion system to take in account lakes the basic algorithm will be:

  1. Erode to a local minimum as before
  2. Find the lake associated with the local minimum
  3. Jump to the lake output (if found)
  4. Tag the lake to prevent circular erosion loops
  5. Continue the erosion process as normal
struct lake_t
{
	int   X;
	int   Y;
	float Height;
	int   OutX;
	int   OutY;
	int   Tag;         /* For tagging lakes to prevent potential infinite loops */
};
 
class CErosionSample
{
		/* Sets the tag value for all lakes */
	void TagLakes (const int Value)
	{
		CLakeVector::iterator iLake;
 
		iLake = m_Lakes.begin();
 
		while( iLake != m_Lakes.end() ) 
		{
			iLake->Tag = Value;
			++iLake;
		}
	}
 
	void ErodeAll (void)
	{
		utils::NoiseMap OrigMap = m_HeightMap;
		int X, Y;
 
		OrigMap.SetBorderValue(2);
 
		for (Y = 0; Y < OrigMap.GetHeight(); ++Y)
		{
			for (X = 0; X < OrigMap.GetWidth(); ++X)
			{
					/* Clear lake tags and start the erosion cycle including lakes */
				TagLakes(0);
				ErodeWithLakes(OrigMap, X, Y);
			}
		}
 
		BlendErosionMap();
	}
 
	/*
	 * Performs one erosion cycle starting at the given map location including the presence
	 * of previously detected lakes.
	 */
	void ErodeWithLakes (utils::NoiseMap& OrigMap, int X, int Y)
	{
		bool    Result;
		lake_t* pLake;
 
		while (true) 
		{
			ErodePoint(X, Y);
 
			Result = FindMinHeight(OrigMap, X, Y);
 
			if (!Result) 
			{
				pLake = FindExistingLake(X, Y);
 
					/* Found a minimum or point with no known lake */
				if (pLake == NULL) 
				{
					break;
				}
					/* Found a lake we've already been through on this erosion cycle */
				else if (pLake->Tag != 0)
				{
					break;
				}
					/* Jump to the output of this lake and continue eroding */
				else 
				{
					pLake->Tag = 1;
					X = pLake->OutX;
					Y = pLake->OutY;
				}
 
			}
		}
 
	}
 
};

With this in place the new erosion output can be compared to the previous version:
old erosion new erosion with lakes
While there is not a huge difference we can clearly see in some areas where the erosion stops in the original erosion but in the new version it continues on past it.

One issue which is evident from the new erosion is that it is now yet perfect. For example, there is one dark erosion path near the center of the map which stops abruptly. The reason for this is that lakes are still identified by a single minimum position even if the lake has multiple local minimums. What we need is to be able to better identify which lake we are in form any point.

There are a few ways to do this but for now we will just store all points defined in a lake and use that to check what lake a given point is in:

	/* Used for recording the defined points of a lake */
struct pos_t
{
	int X;
	int Y;
 
	pos_t(int x, int y) : X(x), Y(y) { }
};
 
typedef std::vector<pos_t> CPosVector;
 
struct lake_t
{
	int   X;
	int   Y;
	float Height;
	int   OutX;
	int   OutY;
	int   Tag;
 
		/* Points which make up the lake */
	CPosVector LakePos;
};
 
class CErosionSample 
{
 
	/*
	 * Used by the FindExistingLake2() method to see if the given point (X,Y) is present in
	 * the given lake. 
	 */
	bool FindPointInLake (lake_t& Lake, const int X, const int Y)
	{
		CPosVector::iterator iPos;
 
		iPos = Lake.LakePos.begin();
 
			/* Try to search first by position */
		while( iPos != Lake.LakePos.end() ) 
		{
			if (iPos->X == X && iPos->Y == Y) return (true);
			++iPos;
		}
		return (false);
	}
 
	/*
	 * Looks for a lake with the given position. If none is found it then searches
	 * through the points of all lakes for a match. Returns NULL if no lake is found.
	 */
	lake_t* FindExistingLake2 (const int X, const int Y)
	{
		CLakeVector::iterator iLake;
		bool Result;
 
 		m_LakeTempMap = m_LakeMap;
 
		iLake = m_Lakes.begin();
 
			/* Try to search first by position */
		while( iLake != m_Lakes.end() ) 
		{
			if (iLake->X == X && iLake->Y == Y) return &(*iLake);
			++iLake;
		}
 
		iLake = m_Lakes.begin();
 
			/* Try to search first by position */
		while( iLake != m_Lakes.end() ) 
		{
			Result = FindPointInLake(*iLake, X, Y);
			++iLake;
		}
 
		return (NULL);
	}
 
	bool FillLake (const int X, const int Y, const float Level, const float PrevLevel)
	{
		...
		if (m_pFillLakeOutput != NULL) m_pFillLakeOutput->SetValue(X, Y, Level);
 
			/* Update the points in the current lake if valid */
		if (m_pCurrentLake != NULL)
		{
			m_pCurrentLake->LakePos.push_back(pos_t(X, Y));
		}
		...
	}
 
};

While this method slows down the lake generation considerable (factor of 10), it results a more complete erosion:
File:Erosion8c.jpg

Personal tools