java - 地形曲线到点阵列

Question

在我的 2D 游戏中，我使用图形工具来创建由黑色表示的漂亮、平滑的地形:

用 java 编写的简单算法每 15 个像素查找一次黑色，创建以下一组线条(灰色):

如您所见，有些地方映射得非常糟糕，有些地方映射得很好。在其他情况下，没有必要每 15 个像素采样一次，例如。如果地形平坦。

使用尽可能少的点将此曲线转换为一组点 [线] 的最佳方法是什么？每 15 个像素采样 = 55 FPS，10 个像素 = 40 FPS

下面的算法正在做这项工作，从右到左采样，输出可粘贴到代码数组中:

public void loadMapFile(String path) throws IOException {
    File mapFile = new File(path);
    image = ImageIO.read(mapFile);
    boolean black;
    System.out.print("{ ");

    int[] lastPoint = {0, 0};

    for (int x = image.getWidth()-1; x >= 0; x -= 15) {
        for (int y = 0; y < image.getHeight(); y++) {
            black = image.getRGB(x, y) == -16777216 ? true : false;

            if (black) {
                lastPoint[0] = x;
                lastPoint[1] = y;
                System.out.print("{" + (x) + ", " + (y) + "}, ");
                break;
            }

        }
    }

    System.out.println("}");
}

我在 Android 上开发，使用 Java 和 AndEngine

Answer 1

这个问题几乎与信号(例如声音)的数字化问题相同，其中基本规律是输入中的频率对于采样率来说太高的信号不会反射(reflect)在数字化中输出。所以担心的是，如果您检查过 30 个像素，然后按照 bmorris591 的建议测试中间部分，您可能会错过采样点之间的 7 个像素孔。这表明，如果您不能错过 10 个像素特征，则需要每 5 个像素扫描一次:您的采样率应该是信号中出现的最高频率的两倍。

可以帮助改进算法的一件事是更好的 y 维度搜索。目前您正在线性搜索天空和地形之间的交点，但二分搜索应该更快

int y = image.getHeight()/2; // Start searching from the middle of the image
int yIncr = y/2;
while (yIncr>0) {
    if (image.getRGB(x, y) == -16777216) {
        // We hit the terrain, to towards the sky
        y-=yIncr;
    } else {
        // We hit the sky, go towards the terrain
        y+=yIncr;
    }
    yIncr = yIncr/2;
}
// Make sure y is on the first terrain point: move y up or down a few pixels
// Only one of the following two loops will execute, and only one or two iterations max
while (image.getRGB(x, y) != -16777216) y++; 
while (image.getRGB(x, y-1) == -16777216) y--;

其他优化是可能的。如果你知道你的地形没有悬崖，那么你只需要搜索从 lastY+maxDropoff 到 lastY-maxDropoff 的窗口。此外，如果您的地形永远无法与整个位图一样高，则您也不需要搜索位图的顶部。这应该有助于释放一些 CPU 周期，您可以将它们用于更高分辨率的地形 x 扫描。