Terrain / Mountain算法无法正常工作
我想创建一个有山的地形，使用一个非常基本的原理，由这个高度映射显示：
0 0 0 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递减到顶部/向下/向左/向右（在这个例子中），并且只有在没有遇到的情况下，我才设置它们的值。
我实现如下：
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 = width || z = depth) { return; } if (traversed[x][z]) { return; } if ((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
问题是它现在形成一条线，这不是我的意图，而不是逐渐平滑。
如何实现我想要的算法？
你的递归方法的问题在于它基本上执行DFS ，因此你总是朝着一个方向前进，遵循最长的分支。 但这个分支总是腐朽。
由于您还维护一个traversed集 – 它错误地确保您不会在以后访问另一个分支（另一个递归调用）时访问相同的顶点。
有两种方法可以解决此问题：
- 更优雅，可能更高效 – 将您的算法从DFS更改为BFS 。 更改距离源1距离的单元格，然后距离2处的单元格，依此类推……
- 不太优雅 – 但需要对代码进行最小的更改：更改算法的停止条件，而不是
if (traversed[x][z]) { return; }做一些像if (heightMapping[x][z] > startHeight) { 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
不需要递归。
假设您希望山顶位于x，y位置的高度h。
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
距离峰值的任何给定距离处的高度是山峰的高度，而不是与峰值的正交距离。 我假设你从全零开始，所以如果你离峰值足够远，那就不需要设置。