Terrain/Mountain algorithm not working as intended

Question

I want to create a terrain with a mountain on it, using a very basic principle, shown by this height mapping: ``` 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 2 3 2 1 0 0 0 0 0 1 2 3 4 3 2 1 0 0 0 0 0 1 2 3 2 1 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ``` It starts at a random point with `height = 4`, and then gradually decreases it amonst the neighbours. The recursive idea is simple, I start a point, recurse to the top/down/left/right with `height - 1` (in this example), and only if not encountered yet, I set their values. I implemented it as follows: ``` private void createMountain(final float[][] heightMapping, final float startHeight) { boolean[][] traversed = new boolean[width][depth]; boolean positive = (startHeight >= 0f); int x = random.nextInt(width); int z = random.nextInt(depth); recursiveUpdate(heightMapping, traversed, x, z, startHeight, positive); } private void recurs…

Accepted Answer

The problem with your recursive approach that it is basically performs a DFS, so you always go in one direction, following the longest branch. But this branch is always decaying. Since you are also maintaining a `traversed` set - it falsely ensures that you don't visit the same vertex later on for the other branch (the other recursive call).

There are 2 ways to solve this issue:

- More elegant and probably more efficient - change your algorithm from a DFS to BFS. change cells at distance 1 from the source, then cells at distance 2, and so on...

- Less elegant - but will require minimal changes to the code: change the stop condition of your algorithm, instead of ` if (traversed[x][z]) { return; }` do something like `if (heightMapping[x][z] > startHeight) { return; }`. This will ensure you can update the height if it should be higher and work as intended.

The BFS updating should be something like (pseudo-code):

```
Q <- new Queue() //or even better - priority queue that holds the highest point at the top
Q.push((x,y,height)
visited[width][depth]; //init as all false
while Q.empty() == false:
   curr <- Q.pop()
   if (sanity check for x<0 , y< 0 ,..):
      continue
   if visited[x][y] == true:
      continue
   if height <= 0: //or some epsilon instead of 0 if there are floating point issues
      continue
   heights[x][y] = height
   visited[x][y] = true
   Q.push(x+1,y,calculateNewHeight(...))
   ... //similarly for all directions
```

Terrain/Mountain algorithm not working as intended

Solution

Problem