Perfect collision system (in LWJGL)

Game Mechanics
#1

Like in topic. I am writing 2d game in LWJGL and I have encountered one serious problem.

There is situation like this: if ship A collides with ship B, both of them should activate collision logic (change of speed, direction, damage both ships etc.). How can I check if one object collides with second one? I need to have really very accurate detection, best possibly pixel to pixel.

Currently I am using PNGDecoder to get texture width and height and place texture into ByteBuffer. ByteBuffer is used to display texture into screen, texture is “caged” inside GL_QUADS with width and height equal to texture width and height.

#2

I have a myriad of suggestions for you:

  • Use LibGDX as it will make your life easier. It allows you to still use OpenGL albeit with a stronger set of tools that you will inevitably need for any game, as well as backends for Android/HTML5/iOS
  • Don’t use GL_QUADS as they are deprecated; instead it would be more efficient to make a sprite batcher ideally with shaders and such. LibGDX of course already includes this for you…
  • Use polygons if you are ok with losing a bit of precision. This is ideal if you plan to rotate or scale your sprites.
  • Use a “mask” texture (i.e. black & white) if you need pixel-perfect collision. This is fast and easy but not ideal if you plan to rotate or scale your sprites, plus it requires an extra image for each sprite.
  • Use stencil buffer if you want to try and incorporate the GPU, although it may not necessarily be much more efficient
#3

You are unisg OpenGl so use stencil buffers, it will be the fastest way to do it.

#4

I think this will be the best solution, but how can I do this? Is it possible to make stencil buffer from byte buffer?

#5

What id personally do is create a polygon boundary box and have a list of all the points and create a if statement with the conditions being set as equations to determine if the point is inside. (It’s called linear programming, wiki should help you understand this) and then check the points of one polygon to the condition of the conditions of collision. Example if you have a line with points 0,0 and 1,0 with a boundary box with points 0,0 0,1 1,1 and 1,0 then you would check each point with if( x < 1 & x > 0 & y > 0 & y < 1) where x and y are the point cordinates. You could use two polygonswith both of their points and conditions. I have a self made doc explaining it with picture but its not with me.

#6

The method I’m currently thinking using is to check for basic bounding box collisions (using the Rectangle class and the intersects() method). If it detects a collision, I plan on having it check for pixel-perfect collision. Sometimes I render more than a thousand different bullets, so there won’t be a need for pixel-perfect collision detection every update.

The basic idea behind my perfect-pixel collision detection method is to iterate though every pixel in one sprite and check it for every pixel in another sprite. The code then checks the contents to see if both locations contain one opaque pixel. One way to simplify this loop is to return true as soon as a collision is detected. Another method to speed it up would be to only consider the area that the two sprites overlap each other (but I haven’t had time to figure that out yet). Another point is that you also have to factor in the offset between the two sprites. Handle any ArrayIndexOutOfBoundsExceptions and throw them away, that just means that the pixels you’re checking against don’t exist.

Example code using 2 byte[][] arrays. 1 means opaque pixel, 0 means transparent pixel.


public static boolean intersectsByte(byte[][] a1, byte[][] a2, int x, int y) {
    for (int i = 0; i < a1.length; i++) {
        for (int j = 0; j < a1[0].length; j++) {
            if (a1[i][j] == 1) {
                for (int k = 0; k < a1.length; k++) {
                    for (int l = 0; l < a1[0].length; l++) {
                        try {
                            if (a2[k - x][l - y] == 1) { return true; }
                        } catch (Exception ex) { } } } } } }
    return false; }

(Ignore the terrible formatting, I’m just trying to keep my post length sane.)

#7

UnconventionalT, you should rather make the appropriate checks and remove the try/catch clause.

#8

You mean something like checking if (k - x) is greater/smaller than a2.length and if (l - y) is greater/smaller than a2[0].length? That wouldn’t be necessary if I check only the areas that are overlapping.

Also, why? Is this just a bad programming practice?

#9

Using try/catch for logic is bad practice, as is suppressing exceptions.

#10

Ok, here we are.


public static boolean intersectsByte(byte[][] a1, byte[][] a2, int x, int y) {
    for (int i = 0; i < a1.length; i++) {
        for (int j = 0; j < a1[0].length; j++) {
            if (a1[i][j] == 1) {
                for (int k = 0; k < a1.length; k++) {
                    for (int l = 0; l < a1[0].length; l++) {
                        if (((k - x) >= 0) && ((k - x) < a2.length) && ((l - y) >= 0) && ((l - y) < a2[0].length)) {
                            if (a2[k - x][l - y] == 1) {
                                return true; } } } } } } }
    return false; }

EDIT: It looks like the Rectangle’s intersection() method could be useful for only checking the areas in which two locations intersect.