Java 按最大可能的 AABB 对图块矩阵进行分组

Question

我正在制作一个基于 2D 图块的游戏，并且我正在使用 AABB 碰撞算法当我陷入这个问题时，我有一个 tile 矩阵：

Tile[][] matrix = new Tile[WIDTH][HEIGHT];

interface Tile {
    public boolean isSolid();
}

基于这个矩阵，我想计算 AABB 池这是一个简单的列表，在此处定义：

List<AABB> aabbPool = new ArrayList<AABB>();

class AABB {

    private int x;
    private int y;
    private int w;
    private int h;

    // Getter and Setter // 

}

我正在寻找一种能够迭代瓦片矩阵的算法并在矩阵中找到最大可能的 AABB-Rectangle 固体附着瓷砖，让我解释一下：

Grid = The matrix
White = Unsolid tile
Black = Solid Tile

给定此矩阵，算法将创建 aabb 池，如下所示

Red outline = Y preferred aabb
Green outline = X preferred aabb (Y is not possible)
Blue outline = XY group

最后，我创建了这个脚本来调试算法

public class AABBDebugger {

    // Public field just for debug
    static class AABB {

        public int xPosition;
        public int yPosition;
        public int width;
        public int height;

    }

    // Public field just for debug
    static class Tile {

        public static final int SIZE = 10;

        public boolean solid;
    }

    public static void main(String[] args) {

        // Matrix size
        int WIDTH = 50;
        int HEIGHT = 50;

        // Declaration of matrix and random initialization
        Tile[][] matrix = new Tile[WIDTH][HEIGHT];
        for (int xCoord = 0; xCoord < WIDTH; xCoord++) {
            for (int yCoord = 0; yCoord < HEIGHT; yCoord++) {
                matrix[xCoord][yCoord] = new Tile();
                matrix[xCoord][yCoord].solid = Math.random() > 0.5;
            }
        }

        // Inizialization of the collission pool
        List<AABB> aabbPool = new ArrayList<AABB>();

        // Magic method that create the collision pool
        magicMethod(matrix, WIDTH, HEIGHT, aabbPool);


        // Rendering of result
        Canvas canvas = new Canvas();
        canvas.setPreferredSize(new Dimension(WIDTH * Tile.SIZE, HEIGHT * Tile.SIZE));

        JFrame frame = new JFrame();
        frame.add(canvas);
        frame.pack();
        frame.setVisible(true);

        while (!Thread.interrupted()) {
            BufferStrategy bufferStrategy;
            while ((bufferStrategy = canvas.getBufferStrategy()) == null) {
                canvas.createBufferStrategy(2);
            }
            Graphics graphics = bufferStrategy.getDrawGraphics();

            for (int xCoord = 0; xCoord < WIDTH; xCoord++) {
                for (int yCoord = 0; yCoord < HEIGHT; yCoord++) {
                    graphics.setColor(matrix[xCoord][yCoord].solid ? Color.BLACK : Color.WHITE);
                    graphics.fillRect(xCoord * Tile.SIZE, yCoord * Tile.SIZE, Tile.SIZE, Tile.SIZE);
                }
            }

            for (AABB aabb : aabbPool) {
                graphics.setColor(Color.RED);
                graphics.drawRect(aabb.xPosition, aabb.yPosition, aabb.width, aabb.height);
            }

            bufferStrategy.show();
            graphics.dispose();
        }

        System.exit(0);
    }


    /*
     * The algorithm that i'm looking for
     * for cycle start from Y rather then X
     */
    private static void magicMethod(Tile[][] matrix, int WIDTH, int HEIGHT, List<AABB> aabbPool) {
        for (int yCoord = 0; yCoord < HEIGHT; yCoord++) {
            AABB aabb = null;
            for (int xCoord = 0; xCoord < WIDTH; xCoord++) {
                if (matrix[xCoord][yCoord].solid) {
                    if (aabb == null) {
                        aabb = new AABB();
                        aabb.yPosition = yCoord * Tile.SIZE;
                        aabb.xPosition = xCoord * Tile.SIZE;
                        aabb.height = Tile.SIZE;
                        aabb.width = Tile.SIZE;
                    } else {
                        aabb.width += Tile.SIZE;
                    }
                } else if (aabb != null) {
                    aabbPool.add(aabb);
                    aabb = null;
                }
            }
            if (aabb != null) {
                aabbPool.add(aabb);
                aabb = null;
            }
        }
    }

}

脚本产生这个结果：

但这不是我所期望的，因为该算法对图块进行了分组按 y 没问题，但如果可以的话，按 x 就不行了，就像那里

最后（很抱歉post）算法必须遵守这条规则：

最好按 Y 对图块进行分组
当 Y 不可能时，按 X 对图块进行分组
不要与现有组重叠
将所有图块分组

Answer 1

你仍然可以使用你的方法稍作改变：不要直接存储按 Y 分组的 single-tile 个 AABB 矩形（具有 width==Tile.SIZE 的矩形）；但将它们存储在临时 HashMap 中：Map<Integer, List<Integer>>，其中键是每个图块的 xCoord，值 yCoord 被添加到列表中）。通过这种方式，您可以跟踪每个 xCoord 的哪些图块尚未按 Y 分组。因此，在添加之前检查是否 width!=Tile.SIZE：

if (aabb.width != Tile.SIZE) {
    aabbPool.add(aabb);
} else {
    addToMap(xCoord,yCoord);
}
aabb = null;

方法addToMap可以实现如下：

private static void addToMap(Integer x, Integer y, Map<Integer, List<Integer>> xMap) {
        if (xMap.containsKey(x)) {
            xMap.get(x).add(y);
        } else {
            List<Integer> yList = new ArrayList<Integer>();
            yList.add(y);
            xMap.put(x, yList);
        }
    }

然后，调用以下方法作为 magicMethod 的最后一步；它将添加 single-tile AABB 矩形（无论如何都无法分组），或按 X 分组（尚未按 Y 分组）。

private static void groupByX(Map<Integer, List<Integer>> xMap, List<AABB> aabbPool) {
    //for each X
    for (Entry<Integer, List<Integer>> entry : xMap.entrySet()) {
        List<Integer> curList = entry.getValue();
        if (curList != null) {
            int curY = curList.get(0); //current yCoord
            int curH = 1; //current height
            //for each Y
            for (int i = 1; i < curList.size(); i++) {
                if (curY + curH == curList.get(i)) {
                    curH++;
                } else {
                    aabbPool.add(new AABB(entry.getKey()*Tile.SIZE, curY*Tile.SIZE, Tile.SIZE, curH*Tile.SIZE)); // *Tile.SIZE()
                    //reset
                    curY = curList.get(i);
                    curH = 1;
                }
            }
            //add the last AABB
            aabbPool.add(new AABB(entry.getKey()*Tile.SIZE, curY*Tile.SIZE, Tile.SIZE, curH*Tile.SIZE));
        }
    }
}

这是你得到的：

Java 按最大可能的 AABB 对图块矩阵进行分组

Java group tile matrix by largest possible AABB

java

algorithm

matrix

aabb