地形曲线的点的阵列(Terrain curve to array of points)

在我的2D游戏我使用图形工具，产生由黑色表示美观，平整地形：

用Java编写的简单算法寻找黑色每15个像素，创建以下组线（灰）：

正如你所看到的，有被映射非常糟糕的一些地方，有些是相当不错的。在其他情况下，将每隔15个像素采样不是必需的，如。如果地形平坦。

什么是隐蔽的这条曲线设置点[行]的最佳方式，用点尽可能少？采样，每15个像素= 55 FPS，10个像素= 40 FPS

下面的算法是做这个工作，由右至左采样，输出pasteable成代码数组：

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。另外，如果您的地形永远不能作为整个位图一样高，你不需要搜索位图的顶部要么。这将有助于释放可用于地形的高分辨率X扫描一些CPU周期。

Answer 2:

我建议寻找一种存在于白色和暗像素之间的边界过境点。之后，我们可以数字化的点。为了做到这一点，我们应该定义DELTA其指定点我们就应该跳过，而我们应该添加到结果列表。

DELTA = 3, Number of points = 223

DELTA = 5, Number of points = 136

DELTA = 10, Number of points = 70

下面，我已经把源代码，它打印的图像和寻找点。我希望，你能够阅读它，并找到一种方法来解决你的问题。

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.awt.image.DataBufferByte;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Program {

    public static void main(String[] args) throws IOException {
        BufferedImage image = ImageIO.read(new File("/home/michal/Desktop/FkXG1.png"));
        PathFinder pathFinder = new PathFinder(10);
        List<Point> borderPoints = pathFinder.findBorderPoints(image);
        System.out.println(Arrays.toString(borderPoints.toArray()));
        System.out.println(borderPoints.size());

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.getContentPane().add(new ImageBorderPanel(image, borderPoints));
        frame.pack();
        frame.setMinimumSize(new Dimension(image.getWidth(), image.getHeight()));
        frame.setVisible(true);
    }
}

class PathFinder {

    private int maxDelta = 3;

    public PathFinder(int delta) {
        this.maxDelta = delta;
    }

    public List<Point> findBorderPoints(BufferedImage image) {
        int width = image.getWidth();
        int[][] imageInBytes = convertTo2DWithoutUsingGetRGB(image);
        int[] borderPoints = findBorderPoints(width, imageInBytes);

        List<Integer> indexes = dwindlePoints(width, borderPoints);
        List<Point> points = new ArrayList<Point>(indexes.size());
        for (Integer index : indexes) {
            points.add(new Point(index, borderPoints[index]));
        }
        return points;
    }

    private List<Integer> dwindlePoints(int width, int[] borderPoints) {
        List<Integer> indexes = new ArrayList<Integer>(width);
        indexes.add(borderPoints[0]);
        int delta = 0;
        for (int index = 1; index < width; index++) {
            delta += Math.abs(borderPoints[index - 1] - borderPoints[index]);
            if (delta >= maxDelta) {
                indexes.add(index);
                delta = 0;
            }
        }
        return indexes;
    }

    private int[] findBorderPoints(int width, int[][] imageInBytes) {
        int[] borderPoints = new int[width];
        int black = Color.BLACK.getRGB();
        for (int y = 0; y < imageInBytes.length; y++) {
            int maxX = imageInBytes[y].length;
            for (int x = 0; x < maxX; x++) {
                int color = imageInBytes[y][x];
                if (color == black && borderPoints[x] == 0) {
                    borderPoints[x] = y;
                }
            }
        }
        return borderPoints;
    }

    private int[][] convertTo2DWithoutUsingGetRGB(BufferedImage image) {
        final byte[] pixels = ((DataBufferByte) image.getRaster().getDataBuffer()).getData();
        final int width = image.getWidth();
        final int height = image.getHeight();
        final boolean hasAlphaChannel = image.getAlphaRaster() != null;

        int[][] result = new int[height][width];
        if (hasAlphaChannel) {
            final int pixelLength = 4;
            for (int pixel = 0, row = 0, col = 0; pixel < pixels.length; pixel += pixelLength) {
                int argb = 0;
                argb += (((int) pixels[pixel] & 0xff) << 24); // alpha
                argb += ((int) pixels[pixel + 1] & 0xff); // blue
                argb += (((int) pixels[pixel + 2] & 0xff) << 8); // green
                argb += (((int) pixels[pixel + 3] & 0xff) << 16); // red
                result[row][col] = argb;
                col++;
                if (col == width) {
                    col = 0;
                    row++;
                }
            }
        } else {
            final int pixelLength = 3;
            for (int pixel = 0, row = 0, col = 0; pixel < pixels.length; pixel += pixelLength) {
                int argb = 0;
                argb += -16777216; // 255 alpha
                argb += ((int) pixels[pixel] & 0xff); // blue
                argb += (((int) pixels[pixel + 1] & 0xff) << 8); // green
                argb += (((int) pixels[pixel + 2] & 0xff) << 16); // red
                result[row][col] = argb;
                col++;
                if (col == width) {
                    col = 0;
                    row++;
                }
            }
        }

        return result;
    }
}

class ImageBorderPanel extends JPanel {

    private static final long serialVersionUID = 1L;

    private BufferedImage image;
    private List<Point> borderPoints;

    public ImageBorderPanel(BufferedImage image, List<Point> borderPoints) {
        this.image = image;
        this.borderPoints = borderPoints;
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        g.drawImage(image, 0, 0, null);

        Graphics2D graphics2d = (Graphics2D) g;

        g.setColor(Color.YELLOW);
        for (Point point : borderPoints) {
            graphics2d.fillRect(point.x, point.y, 3, 3);
        }
    }
}

在我的源代码我已经使用这个问题例如：