CODEWITHSUNDEEP
javagridjavafxcollision-detectionuniformgrid
Gregg1989
Gregg1989

Reputation: 695

Uniform grid collision detection between circles in 2d

I am working on a 2d arcade game where I have 5 types of circles with different sizes: The ship, the missiles, and 3 types of monsters.

This is what it looks like:

enter image description here

Currently I'm using brute force collision detection where I check every missile vs. every monster without taking probability of collision into account. Sadly, this makes the process REALLY slow.

This here is my Grid class, but it's incomplete. I'd greatly appreciate your help.

    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.
            }
        }
    }

But that's where I am at a complete loss. I'm not even sure the source code I provided is correct. Please let me know how to make the grid based collision work. I've read basically every tutorial I could get my hands on but without much effect. Thanks.

Upvotes: 1

Views: 983

Answers (1)

Rusca8
Rusca8

Reputation: 612

I found it easier (and I guess faster) to store in the object itself a binary number representing which cells the object overlaps with (instead of saving an array for every cell). I think it's called a spatial mask.

More specifically, before any collision testing, I calculate 2^(x/column_width + columns*y/row_width) for each of topLeft, topRight... then combine all those 4 in a single number (with a bitwise OR), so that I end up with a number like 5 (00000011, meaning the object hits the cells 1 and 2).

Having it this way, you then proceed to test each object with all the others, but skip the slow part if they fail to be in the same cell:

  1. Check the bitwise AND of the numbers in both objects (this will only be !=0 if some of the cells are 1 for both objects).
  2. If the result is something other than 0, do the proper (slow) collision checks (in your case probably pythagoras, since those are circles and I read pythagoras is faster than checking bounding squares).

Upvotes: 0

Related Questions