java - 地形/山地算法未按预期工作

Question

我想创建一个上面有山的地形，使用一个非常基本的原理，如这个高度映射所示:

0 0 0 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

它从 height = 4 的随机点开始，然后逐渐减小到邻居。

递归的思路很简单，我开始一个点，用height - 1递归到top/down/left/right(在这个例子中)，只有还没有遇到，我设置他们的值(value)观。

我是这样实现的:

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;
}

但是它给了我以下输出:

0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  
0.0  0.0  0.0  0.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 

问题是它现在形成一条线，这不是我的本意，而是逐渐平滑。

如何实现我想要的算法？

Answer 1

您的递归方法的问题基本上是执行 DFS ，所以你总是朝一个方向走，沿着最长的分支。但是这个分支总是在腐烂。
因为您还维护了一个traversed 集 - 它错误地确保您稍后不会为另一个分支(另一个递归调用)访问同一个顶点。

有两种方法可以解决这个问题:

1. 更优雅并且可能更高效 - 将您的算法从 DFS 更改为 BFS .更改距离源 1 处的单元格，然后更改距离 2 处的单元格，依此类推...
2. 不太优雅 - 但需要对代码进行最少的更改:更改算法的停止条件，而不是 if (traversed[x][z]) { return; } 做类似 if (heightMapping[x][z] > startHeight) { return; }。这将确保您可以更新高度(如果它应该更高)并按预期工作。

---

BFS 更新应该是这样的(伪代码):

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