地形/山算法如预期

Question

我想创建上有一个山地形，使用非常基本的原则，通过这个高度映射出不工作，然后逐渐减少它在邻居之间。

递归的想法很简单，我开始一个点，递归到height - 1（在这个例子中）的顶部/下/左/右，只有没有遇到，我设置了它们的值。

我实现它，如下所示：

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 

Answer 2

有没有必要递归。

假设你想让山顶的高度为x，y。

height(x,y) = h 
for dist = 1 to h-1 
    for x' = x - dist to x + dist 
    x_dist = abs(x - x') 
    y_dist = dist - x_dist 
    height(x', y + y_dist) = h - dist 
    height(x', y - y_dist) = h - dist 

你在离山顶任何给定距离处的高度都是山峰的高度，而不是与山峰的正交距离。我假设你是从全零开始的，所以如果你距离高峰足够远，就不需要设置它们。