CODEWITHSUNDEEP
java2dcollision-detectionslick2d
Mike Trpcic
Mike Trpcic

Reputation: 25659

What is the fastest way to find overlaps in an array of rectangles?

I'm working on a "game" in my spare time, almost purely as a learning experience, and am at the point where collision detection between the player entity and enemy entities needs to occur.

Both the player and all enemies share a base class, Entity, which gives them access to x, y, height, and width properties. Using these, I can build a rectangle for each entity, and try to find overlaps. If there is an overlap, a collision has occurred.

So, with the logic above, we can pretend that the following data is in an array of Rectangles:

X    Y    HEIGHT   WIDTH
------------------------
0    0    25       50
0    50   25       25
0    100  25       30
50   200  25       50
150  250  25       25
150  50   25       30

What is the fastest way to determine if any of those entities (Rectangles) are intersecting with any other? Simply looping through the array and comparing each element to each other element is not performant enough (O(n^2)). Is there a better way?

Upvotes: 3

Views: 771

Answers (1)

Mark Byers
Mark Byers

Reputation: 838766

You want to use some sort of spatial index or structure that allows you to quickly find elements that are near each other.

One commonly used data structure is a quadtree.

Upvotes: 6

Related Questions