# Grid based Collision Detection between circles [duplicate]

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:

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

• You didn't mention your problem ? What is the wrong behaviour you're getting ? Commented Feb 1, 2014 at 8:45
• I'm not sure this is how I implement a grid-based collision. Also, I'm quite certain my Grid class is incomplete. I do not know how to write the code to make uniform grid collision happen in my 2d game. Commented Feb 1, 2014 at 8:46
• @ArthurWulfWhite I am struggling with writing the source code. I understand the concept, but I do not know how to put it in action. Commented Feb 1, 2014 at 9:07
• @user2915567 See this: gamedev.stackexchange.com/questions/39931/… It has been duplicated several times. :) You have to ask a specific question about a specific step you are stuck with. Otherwise use an engine that already does collisions (there are many). Commented Feb 1, 2014 at 9:11
• @ArthurWulfWhite I would like to write the code all by myself in order to learn more. Can you please refer me to a similar program that uses a grid for its collision and has all the necessary source code? Commented Feb 1, 2014 at 9:16