我正在制作一个基于 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 矩形的算法，让我解释一下：
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 对图块进行分组
- 不要与现有组重叠
- 将所有图块分组
