二维均匀网格碰撞检测算法 [英] Uniform grid collision detection between circles in 2d

问题描述

我正在做一个2D街机游戏，我有5种不同大小的圆圈：船、导弹和3种怪物。

如下所示：

目前我正在使用暴力碰撞检测，在不考虑碰撞概率的情况下，我检查每一枚导弹和每一只怪物。遗憾的是，这会让这个过程变得非常缓慢。

这是我的网格类，但它不完整。我将非常感谢你的帮助。

    public class Grid {

    int rows;
    int cols;
    double squareSize;
    private ArrayList<Circle>[][] grid;

    public Grid(int sceneWidth, int sceneHeight, int squareSize) {
        this.squareSize = squareSize;
// Calculate how many rows and cols for the grid.
        rows = (sceneHeight + squareSize) / squareSize;
        cols = (sceneWidth + squareSize) / squareSize;
// Create grid
        this.grid = (ArrayList[][]) new ArrayList[cols][rows]; //Generic array creation error workaround
    }

The addObject method inside the Grid class.
    public void addObject(Circle entity) {
// Adds entity to every cell that it's overlapping with.
        double topLeftX = Math.max(0, entity.getLayoutX() / squareSize);
        double topLeftY = Math.max(0, entity.getLayoutY() / squareSize);
        double bottomRightX = Math.min(cols - 1, entity.getLayoutX() + entity.getRadius() - 1) / squareSize;
        double bottomRightY = Math.min(rows - 1, entity.getLayoutY() + entity.getRadius() - 1) / squareSize;

        for (double x = topLeftX; x < bottomRightX; x++) {
            for (double y = topLeftY; y < bottomRightY; y++) {
                grid[(int) x][(int) y].add(entity); //Cast types to int to prevent loosy conversion type error.
            }
        }
    }

但这就是我完全不知所措的地方。我甚至不确定我提供的源代码是否正确。请让我知道如何使基于网格的碰撞工作。我基本上读过了我能弄到的所有教程，但没有多少效果。 谢谢。

推荐答案

我发现在对象本身中存储表示对象与哪些单元格重叠的二进制数更容易(我猜也更快)(而不是为每个单元格保存一个数组)。我认为它被称为空间蒙版。

更具体地说，在任何碰撞测试之前，我为topLeft、topRight计算2^(x/column_width + columns*y/row_width)...然后将这4个组合成一个数字(使用按位OR)，这样我就得到了一个类似5(00000011，表示对象命中单元格1和2)的数字。

使用这种方法，然后使用所有其他对象继续测试每个对象，但如果它们不在同一单元格中，则跳过较慢的部分：

1. 检查两个对象中数字的位与(仅当两个对象的某些单元格都为1时才为!=0)。
2. 如果结果不是0，请执行适当的(缓慢的)冲突检查(在您的情况下可能是毕达哥拉斯，因为它们是圆，我认为毕达哥拉斯比检查边界正方形更快)。

这篇关于二维均匀网格碰撞检测算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！