2

私は 2D タイル ベースのゲームを作成しています。AABB コリジョン アルゴリズムを使用していたときに、この問題で行き詰まってしまいました。タイルのマトリックスがあります。

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 でグループ化しないため、期待どおりではありません。

スクリプトの結果が期待される

最後に (長い投稿で申し訳ありません)、アルゴリズムは次のルールを尊重する必要があります。

  • タイルを Y ごとにグループ化することをお勧めします
  • Y でグループ化できない場合、X でタイルをグループ化します。
  • 既存のグループと重複しない
  • すべてのタイルをグループ化
4

1 に答える 1