Grid based Collision Detection between circles

| | August 6, 2015

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.

One Response to “Grid based Collision Detection between circles”

1. Given the image depicting a very manageable number of spheres you shouldn’t have any problem checking every missile against every enemy.

You haven’t shown us the relevant code, but my best guess it that you are not using basic sphere-to-sphere collision detection like you should.

Basically every sphere has a centre position and a radius. For every pair of spheres, if the distance between the centres is less than the sum of their radii the spheres intersect, otherwise they don’t. If you implement this method right there should be no need to worry about performance unless you need to do a million or more checks per frame.

• How To Submit a iPhone App to the Appstore

by on July 5, 2012 - 0 Comments

The process to develop an iPhone app is not as hard as one might think. The entry into the app store has been opened up to many new types of develope...

• Develop iphone Apps on Windows

by on March 7, 2011 - 13 Comments

Top 10 Ways to Develop an iphone/ipad app without a Mac #1. Code in Java For Java developers, there is a workaround: XMLVM. XMLVM cross-compiles byte...

• Iphone Android App Ideas: Getting Started

by on March 19, 2011 - 3 Comments

Smartphone Application Ideas: Getting Started Smartphone application developers are constantly on the move. And since overzealous developers stick ...