地形/山算法并不如预期 [英] Terrain/Mountain algorithm not working as intended

问题描述

我想创建上有一个山区地形，用一个很基本的原则，这个高度映射图所示：

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

它从一个随机点与高度= 4 ，然后逐渐减小它amonst邻居。

It starts at a random point with height = 4, and then gradually decreases it amonst the neighbours.

递归的想法很简单，我开始点，递归顶端/下/左/右与的高度 - 1 （在这个例子中），且仅当没有遇到，我设置它们的值。

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.

我实现它，如下所示：

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 recursiveUpdate(final float[][] heightMapping, final boolean[][] traversed, final int x, final int z, final float startHeight, final boolean positive) {
    if (x < 0 || x >= width || z < 0 || z >= depth) {
        return;
    }
    if (traversed[x][z]) {
        return;
    }
    if ((positive && startHeight <= 0f) || (!positive && startHeight >= 0f)) {
        heightMapping[x][z] = 0f;
        return;
    }
    traversed[x][z] = true;
    heightMapping[x][z] = startHeight;
    recursiveUpdate(heightMapping, traversed, x, z - 1, calculateNewStartHeight(startHeight, positive), positive);
    recursiveUpdate(heightMapping, traversed, x, z + 1, calculateNewStartHeight(startHeight, positive), positive);
    recursiveUpdate(heightMapping, traversed, x - 1, z, calculateNewStartHeight(startHeight, positive), positive);
    recursiveUpdate(heightMapping, traversed, x + 1, z, calculateNewStartHeight(startHeight, positive), positive);
}

private float calculateNewStartHeight(final float startHeight, final boolean positive) {
    float delta = startHeight / maxDecayFactor;
    return (positive) ? startHeight - delta : startHeight + delta;
}

但是它给了我下面的输出：

However it gives me the following output:

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.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  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.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  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.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  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.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  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.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  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.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  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.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  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.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  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.1  
1.9  1.6  1.2  1.0  0.8  0.6  0.5  0.4  0.3  0.3  0.2  0.2  0.1  0.1  0.1  0.1  
2.4  3.0  3.8  4.7  5.9  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.1 

使用问题在于它形成了一个行现在，这是不是我的意图，而不是逐步理顺。

With the issue being that it forms a line now, which was not my intention, instead of gradually smoothing out.

如何才能实现我想要的算法？

How can I implement my desired algorithm?

推荐答案

你的递归方法的问题在于它基本上是执行的 DFS ，所以你总是在一个方向，跟随时间最长的分支。但是，这个分支总是腐烂。
既然你还保持了走过设置 - 它错误地确保你不访问同一个顶点以后为其他分支（其他递归调用）。

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).

有2种方式来解决这个问题：

There are 2 ways to solve this issue:

1. 更优雅，很可能更有效率 - 从DFS改变你的算法来 BFS 。在距离1从源改变的细胞，然后细胞以距离为2，等等...
2. 那么优雅 - 但需要最小的改动code：改变，而不是你的算法的停止条件，如果（遍历[X] [Z]）{返回; } 执行类似如果（heightMapping [X] [Z]> startHeight）{返回; } 。这将确保您可以更新的高度，如果它要更高，工作打算。

1. 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...
2. 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.

BFS的更新应该是这样的（伪code）：

---

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

这篇关于地形/山算法并不如预期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！