地形曲线到点阵列

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

这个问题与信号（例如声音）的数字化问题几乎相同，其基本规律是输入中频率对于采样率而言过高的信号将不会反映在数字化输出中。因此，令人担忧的是，如果您检查 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 扫描。