Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
The PathThe path is a key part of the entire process, as a river that doesn't follow a realistic path doesn't appear very river like at all (unless you are going for a non traditional world's river). In order to achieve our goal with the above mentioned restrictions the first thing we do is create a height sorted array of all the edge vertices on the map. In order to assure that we will pick a path that goes downhill whenever possible we will randomly pick our starting point from the higher 3/5th of the edge vertices and a goal point from the lower 1/5th of the edge vertices. The only other restriction we are going to place on the starting and ending points is that they must be on different edges of the map, using two points on the same edge will often result in a very small river that wont look right on the edge of the map. If you are using a smaller size map say for instance 257*257 vertices and you would like to increase your chances of a decent river it is suggested you further restrict the starting and ending points to be on opposite edges. Now that we have our starting and ending points of our river we need a way to calculate the path. To do this we are going to use to our advantage the fact that water is subject to gravity. Altering a simple ‘best first' path finding algorithm to use a heuristic that weighs neighboring nodes by their height as apposed to distance to the goal we can get a fairly realistic path. In efforts to more heavily penalize water from going uphill it is also suggested you add an additional penalty to the heuristic anytime the new node has a higher height than the current node. Several problems will arise with the path that has been formed. The first problem with the path is that the terrain was not formed with a river in mind and so it is not always possible for the river to make it from start to end without going at least slightly uphill. We will need to alter the terrain to allow the river to always realistically flow downwards but more on this in a bit. Another problem with the path is that when the path intersects and edge of the map before reaching its end point it has a tendency to stick to the edge as it has no terrain to travel to outside the edge of the terrain and chances are if it was driven to the edge of the map then it is lower then the inside of the map. This leads to sections of river "sticking" to the edge of the map. Cleaning up the pathOne of the uglier side effects of the "sticking" to the edge of the map is that the river tends to do "hops" where it hits the edge, then breaks off, then hits the edge then breaks off again. Sometimes it may look like a hop is merely the river coming back from somewhere off terrain but at other times it just looks horrible. In addition to this at the mention of hops the A.I. programmer cringed, so as a solution I suggest you loop through the river nodes looking for the longest hop in the river. In the case where you don't ever hit the edge between the start and goal nodes there will only be one hop which is of course the longest. Once you have located the longest hop, merely eliminate the nodes from all the other hops. Another ugly artifact is the hop's cousin. This is where the river gets within the rivers width of the edge of the terrain and also results in visible hops although not physical ones path wise. This, however, is rather easy to fix. I merely looped through the river and tested each node's relative closeness of the edge of the map, if it was too close I merely moved it inwards. The rivers path should look realistic enough that pushing in these few nodes will not look bad. Now that we have the actual path refined we will need to adjust the height of the path, currently it is laying on the surface of the terrain. What we want to do is move each vertex down along the y axis to either its current position minus half the river depth or a hair lower than the previous vertex, whichever is lower. In doing this we assure that the rivers path is always flowing downwards. As we have each of these new heights we will also want to adjust the stored height in the height map for each corresponding river vertex, doing so will scrape the path into the terrain if you will.
for ( i = m_vp3River.size()-1; i >= 0 ; --i )
{
// Convert the vertices coordinates to heightmap coordinates
int iRX = int(m_vp3River[i].x/m_MapInfo.fScale),
iRZ = int(m_vp3River[i].z/m_MapInfo.fScale);
// Lower the vertices half way down
m_vp3River[i].y -= HALFDEPTH*m_MapInfo.fScale;
// If we actually went up (water doesn't go up)
// then move us slightly lower than the previous vertex
if (i < (m_vp3River.size()-1) && m_vp3River[i].y >= m_vp3River[i+1].y)
m_vp3River[i].y = m_vp3River[i+1].y-(0.01f*m_MapInfo.fScale);
// store the new height in the heightmap
m_fHeightMap[iRX][iRZ] = m_vp3River[i].y;
}
Carving the pathNow that we have our refined river path, and even scraped the basis of the path into the terrain we need to carve the path. In order to combat any sudden drops we are going to carve a river bank into the terrain around the river, before we actually carve the river bed into the terrain. To achieve this riverbed I traversed through the list of river nodes and for each one I cycled through all terrain vertices within a square distance and found the slope of the line from the current river vertex to the current height map vertex being evaluated. If the slope was too high I merely reduce the height of the terrain. We repeat this cycle until all of the terrain surrounding the river is at a height we find adequate. An alternative to repeating the cycle could be to merely set the height the first time, but this tends to look more artificial and too uniform.
for ( i = m_vp3River.size()-1; i >= 0 ; --i )
{
// Convert the vertices coordinates to heightmap coordinates
int iRX = int(m_vp3River[i].x/m_MapInfo.fScale),
iRZ = int(m_vp3River[i].z/m_MapInfo.fScale);
// repeat variable
bool bAltered = true;
while ( bAltered )
{
// Our default assumption is that we don't change anything
// so we don't need to repeat the process
bAltered = false;
// Cycle through all valid terrain within the slope width
// of the current position
for ( int iX = max(0,iRX-SLOPE_WIDTH);
iX < min(m_MapInfo.iSize,iRX+SLOPE_WIDTH);
++iX )
{
for ( int iZ = max(0,iRZ-SLOPE_WIDTH);
iZ < min(m_MapInfo.iSize,iRZ+SLOPE_WIDTH);
++iZ )
{
float fSlope;
// find the slope from where we are to where we are checking
fSlope = (m_fHeightMap[iX][iZ] - m_fHeightMap[iRX][iRZ])
/(sqrt((iRX-iX)*(iRX-iX)+(iRZ-iZ)*(iRZ-iZ))*m_MapInfo.fScale);
if ( fSlope > SLOPE_VAL )
{
// the slope is too big so adjust the height and keep in mind
// that the terrain was altered and we should make another pass
m_fHeightMap[iX][iZ] -= HEIGHT_ADJ*m_MapInfo.fScale;
bAltered = true;
}
}
}
}
}
Some example code follows:
// Initialize the acceptable height changes in the terrain
// this will affect the smoothness
float fDeltaY = 0.5f*m_MapInfo.fScale;
float fAdjY = 0.3f*m_MapInfo.fScale;
// Initialize the repeat bool to run once
bAltered = true;
// loop while we are making changes
while ( bAltered )
{
// assume we aren't going to make changes
bAltered = false;
// for the entire terrain minus the last row and column
for ( int x = 0; x < m_MapInfo.iSize-1; ++x )
{
for ( int z = 0; z < m_MapInfo.iSize-1; ++z )
{
// Check our right and our north neighbors
if ( m_fHeightMap[x][z]-m_fHeightMap[x][z+1] > fDeltaY )
{
m_fHeightMap[x][z] -= fAdjY;
bAltered = true;
}
if ( m_fHeightMap[x][z]-m_fHeightMap[x+1][z] > fDeltaY )
{
m_fHeightMap[x][z] -= fAdjY;
bAltered = true;
}
}
}
// for the entire terrain minus the first row and column
for ( x = m_MapInfo.iSize-1; x > 0 ; --x )
{
for ( int z = m_MapInfo.iSize-1; z > 0; --z )
{
// check out our south and left neighbors
if ( m_fHeightMap[x][z]-m_fHeightMap[x][z-1] > fDeltaY )
{
m_fHeightMap[x][z] -= fAdjY;
bAltered = true;
}
if ( m_fHeightMap[x][z]-m_fHeightMap[x-1][z] > fDeltaY )
{
m_fHeightMap[x][z] -= fAdjY;
bAltered = true;
}
}
}
}
A note about the riverbed carving, because I carve a square pattern at each river node into the height map not only can it be wasteful time wise but it also causes some step like diagonals in the riverbed. One thing I did to fix this blemish is I go through the river nodes on last time and I average out the heights along the edge of the bed whenever moving diagonally across the map. I found this to be faster than handling it when carving the riverbed as it allowed me to make more assumptions in both cases but results may vary with longer rivers. |
|
This will give us a nice V shaped depression along the path of our terrain. This depression will be based on the half river depth height which we lowered all the river vertices too, not the bottom of the river bed. This is why we didn't lower all the river vertices to the bottom of the riverbed just yet. As some of you may guess this filter we just ran along the path of the river has its side effects and not good ones to say the least. At the edge of the riverbank depending on how far down we are carving into the terrain there may be some quite severe dips in the terrain. This shows mostly in longer rivers where the height was slowly decreased as it went to keep it flowing down, eventually this adds up and some terrain carving can be quite severe. Now one could possible use this to their advantage depending on the effect they are going for along the river, say for instance trying to carve the Grand Canyon, but it didn't really go for the rolling hills theme of my terrain so I will discuss a way to get rid of this nasty artifact. It is actually quite simple. To fix this we will merely cycle through every vertex on the terrain and compare it to each of its four neighbors. If there is too drastic a change in height, then the current vertex is lowered to some amount less than the max difference allowed. We will have to repeat this filter over and over until the desired effect is reached. In my case I wanted all sudden drops eliminated not just worn down so I had to loop through it until no more changes were made. This method is actually quite inefficient but it was not the bottle neck of my load time, however on larger terrains with longer rivers it certainly would be. I am quite confident, however, that an algorithm could easily be formed that smartly expanded from the river over and over until everything was satisfactory as apposed to covering the entire terrain. 
Now the terrain is ready for our riverbed. This is actually the simplest part; all we simply do is cycle through each vertex of the river and lower all height map vertices within a certain radius to a height less than that of the current river vertex. How much you lower it depends on the depth of the riverbed you are going for. This particular carve can leave some sharp edges but because of the riverbed the sharpness of the edges is already fairly small and can easily be smoothed out with a bilinear filter across the terrains heights. That is pretty much it as far as our actual river carving is concerned. There are so many spins one could apply to these algorithms to create different effects. I have found that in my implementation, it actually carves quite a bit of detail into an otherwise fairly plain terrain.
