Say there's two or more moveable objects of any shape in 2D plane, each object has its own 2D boolean array to act as a bounds box which can range from 10 to 100 pixels, the program then reads each pixel from a image that represents it, and appropriatly changes the array to true(pixel has a alpha more then 1) or false(pixel has a alpha less than one).

Each time one of these objects moves, what would be the best accurate way to test if they hit another object in Java using as few APIs/libraries as possible?

  • 2
    \$\begingroup\$ Why would you store bounding box data in a 2D Array? Could you extrapolate on this? \$\endgroup\$
    – Sidar
    Jul 19 '13 at 11:24

You could use actual bounding shapes instead of per-pixel collision data (you incorrectly called it a "bounds box"). This greatly simplifies the computational requirements.

You can use a single primitive shape in most cases, e.g. an AABB (axis-aligned bounding box), circle, etc.

If you need (actually need, not just think you need with no analysis) more complex shapes, you can achieve those in several ways. The first is to allow multiple primitive shapes. A table side-view for instance can be represented by three AABBs: one for the top and one for each pair of legs. A tree is an AABB with a circle at the top. etc.

The second option is to use a polygon shape. Generally this will be a convex hull as the math is considerably simpler for convex hulls than for arbitrary polygons. Again you can use multiple shapes (potentially all convex hulls or a combination with other primitive shapes) to represent more intricate objects that cannot be accurately represented by one. A human character may have separate polygons for each limb apart from its head and torso, for instance.

Typically you really, really don't need per-pixel collision, especially if you support convex hulls. You can represent any object with a set of convex hulls. The results will be faster and easier and allow more things to be done with them (such as determining depth of overlap and so on).


What you essentially have is per pixel collision. Each of your array locations represent a pixel, I'm assuming that you have arbitrary shapes defined in these arrays. I'll assume an array position holds true if it's solid and false if it's not.

You check collisions by iterating through one array (the smaller preferably) and checking to see if any of its true values overlap with a true value in the second array.

vec2 diff = getOffset(array1, array2) //get the distance between the two arrays
for x = 0 to array1.xsize
    for y = 0 to array1.ysize
        if array1[x,y] //for each position, if it's true
            if array2[x-diff.x, y-diff.y]//if array2 has a true in the overlap position
                return collision 

You'll find some optimizations for other collision detection strategies work here too. For example, first finding your min/max values and creating a proper bounding box. Then you can just check if the two bounding boxes overlap before doing anything.

  • 1
    \$\begingroup\$ I tried that, however it reduces FPS from solid 60 to 11 when to objects are touching. but thanks for managing to understand my questions which clearly lacked information. \$\endgroup\$ Jul 19 '13 at 20:59
  • \$\begingroup\$ How large are the arrays? \$\endgroup\$
    – House
    Jul 19 '13 at 21:00
  • \$\begingroup\$ They range in size, rarely smaller then 10 and rarely bigger then 100 \$\endgroup\$ Jul 19 '13 at 21:01
  • \$\begingroup\$ Sounds like you need some further optimizations. For example, you can reduce the spans of you for loops to only loop over the parts of the arrays that are overlapping. And remember, you only have to check one array. \$\endgroup\$
    – House
    Jul 19 '13 at 21:03
  • \$\begingroup\$ Okay, I'll first reduce the resolution of the arrays and test for colliding pixels, then i'll narrow the search down to that area. \$\endgroup\$ Jul 19 '13 at 21:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .