地形曲线到点阵 [英] Terrain curve to array of points

问题描述

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

In my 2D game I'm using graphic tools to create nice, smooth terrain represented by black color:

用java编写的简单算法每15个像素查找一次黑色，创建以下一组行（灰色）：

Simple algorithm written in java looks for black color every 15 pixels, creating following set of lines (gray):

正如你所看到的，有些地方的地图非常糟糕，有些地方非常好。在其他情况下，没有必要对每15个像素进行采样，例如。如果地形是平坦的。

As you can see, there's some places that are mapped very bad, some are pretty good. In other case it would be not necessary to sample every 15 pixels, eg. if terrain is flat.

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

What's the best way to covert this curve to set of points [lines], using as little points as possible? Sampling every 15 pixels = 55 FPS, 10 pixels = 40 FPS

以下算法正在执行该作业，从右向左采样，将可粘贴输出到代码数组中：

Following algorithm is doing that job, sampling from right to left, outputting pasteable into code array:

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

Im developing on Android, using Java and AndEngine

推荐答案

最有效的解决方案（关于所需的点）将允许沿X轴的点之间的可变间距。这样，大的平坦部分将需要非常少的点/样本，复杂的地形将使用更多。

The most efficient solution (with respect to points required) would be to allow for variable spacing between points along the X axis. This way, a large flat part would require very few points/samples and complex terrains would use more.

在3D网格处理中，有一个很好的网格简化算法，名为 二次边缘折叠，你可以适应你的问题。

In 3D mesh processing, there is a nice mesh simplification algorithm named "quadric edge collapse", which you can adapt to your problem.

这个想法，转化为你的问题 - 它实际上比原来的3D算法简单得多：

Here is the idea, translated to your problem - it actually gets much simpler than the original 3D algorithm:

1. 用太多的点表示你的曲线。


2. 对于每个点，测量误差（即如果你删除了它，那么与平滑地形的差异。


3. 删除产生最小错误的点。


4. 重复直到你减少了数量点足够远或错误太大。

1. Represent your curve with way too many points.
2. For each point, measure the error (i.e. difference to the smooth terrain) if you remove it.
3. Remove the point that gives the smallest error.
4. Repeat until you have reduced the number of points far enough or errors get too large.

更准确地说明第2步：给定点 P，Q，R ， Q 的误差是地形近似两条直线之间的差值， P-> Q 和 Q-> R ，您的地形近似只有一行 P-> R 。

To be more precise regarding step 2: Given points P, Q, R, the error of Q is the difference between the approximation of your terrain by two straight lines, P->Q and Q->R, and the approximation of your terrain by just one line P->R.

请注意，删除某个点时，只有其邻居需要更新其错误值。

Note that when a point is removed only its neighbors need an update of their error value.

这篇关于地形曲线到点阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！