How can I effectively implement collision for a 2D game?

Question

I just started a new 2D game using Java, LWJGL, and Slick Util but I can't seem to figure out a good way to make collision detection. If I wanted to, it would be easy to detect collision between 2 entities with the Rectangle intersect method, but it can only check the collision with a certain area you specify. I have thought that I could make a list of every entity and its coordinates as its created and then run the intersect method through the list, but then it would check for collision with every entity on the entire map for every time the game updated and I think that would be too inefficient.

Does anyone know a more efficient way to create collision detection? If there was some way i could check if there was an entity at every point the character moved that would probably be the best.

If I have not enough information or I made this sound too confusing please tell me and I can try to clarify things. Also as a side question, what are the benefits of using slick util or slick 2D over one another. Thanks for the help!

Answer 1

The usual way to solve this is a scene graph, a hierarchical system of the objects of the game world.

You might want to look at this and this.

Shortened: you logically group your objects under nodes and assign the nodes a bounding rectangle that encompasses all its sub-nodes and leaves(objects). Everything is grouped again under one main node to access the tree. Now you can test a object for collision with a node, usually starting from the main node. If you get a hit you check its sub-nodes and leaves.

This will take some time to implement but can cut down on CPU usage if the tree structure/grouping is done right. It has also the benefit that you can implement local transforms which makes moving objects relative to each other easier.

Answer 2

Because I hate "The usual way", I made an array of all the coordinates and then checked if a single point hit the coordinate.

Here is a slight modification of my code to demonstrate (It is in 3D):

for (CannonBall can : GameServer.ballss){ //Go through all cannonballs
                    if (can.owner != cl){ //Can.owner is the ship, cl is the player the cannonball is being checked with to see if colliding.
                    int distancex = (int) (can.x - cl.z);
                    int distancez = (int) (can.z - cl.x);
                    final int distancey = (int) (can.y - cl.y);

                    double xRot = Math.cos(Math.toRadians(cl.rotation)) * (distancex - 0) - Math.sin(Math.toRadians(cl.rotation)) * (distancez - 0) + 0;
                    double zRot = Math.sin(Math.toRadians(cl.rotation)) * (distancex - 0) - Math.cos(Math.toRadians(cl.rotation)) * (distancez - 0) + 0;
                    distancex = (int) xRot;
                    distancez = (int) zRot;
                    try{

                        if (true){ //Skip different coordinates for different ships for demonstration purposes
                            i = GameServer.coords[GameServer.DELTA + distancex][GameServer.DELTA + distancez][GameServer.DELTA + (distancey)];
                        }
                        if (i == 1){
                            if (can.owner != cl){   
                            remcan.add(can);
                            if (can.type == 0){
                                double damage = (100 + Math.random()*25);
                                if (cl.type == 1){
                                    damage/=2;
                                }
                                if (cl.type == 2){
                                    damage*=2;
                                }
                                cl.damage-=damage;
                            }
                            if (can.type == 1){
                                double damage = (Math.random() * 500);
                                if (cl.type == 1){
                                    damage/=2;
                                }
                                if (cl.type == 2){
                                    damage*=2;
                                }
                                cl.damage-=damage;
                            }else{
                                double damage = (100 + Math.random()*25);
                                if (cl.type == 1){
                                    damage/=2;
                                }
                                if (cl.type == 2){
                                    damage*=2;
                                }
                                cl.damage-=damage;
                            }
                            crash = true;
                            if (cl.damage < 1){
                                if (!cl.sinking){
                                cl.sinking = true;


                               }

                            }
                        }
                        }
                    }catch (Exception e){
                        e.printStackTrace();
                    }
                    }

GameServer.coords is an int[][][], which is given coordinates like so:

public static int[][][] coords;
public void CollisionSetup(){
    try{
        File f = new File("res/coords.txt");
        String coords = readTextFile(f.getAbsolutePath());

        for (int i = 0; i < coords.length();){
            int i1 = i;
            for (; i1 < coords.length(); i1++){
                if (String.valueOf(coords.charAt(i1)).contains(",")){
                    break;
                }
            }
            String x = coords.substring(i, i1).replace(",", "");
            i = i1;
            i1 = i + 1;
            for (; i1 < coords.length(); i1++){
                if (String.valueOf(coords.charAt(i1)).contains(",")){
                    break;
                }
            }
            String y = coords.substring(i, i1).replace(",", "");;
            i = i1;
            i1 = i + 1;
            for (; i1 < coords.length(); i1++){
                if (String.valueOf(coords.charAt(i1)).contains(",")){
                    break;
                }
            }
            String z = coords.substring(i, i1).replace(",", "");;
            i = i1 + 1;
                //buildx.append(String.valueOf(coords.charAt(i)));
                ////System.out.println(x);
                ////System.out.println(y);
                ////System.out.println(z);
                //x = String.valueOf((int)Double.parseDouble(x));
                //y = String.valueOf((int)Double.parseDouble(y));
                //z = String.valueOf((int)Double.parseDouble(z));
            double sx = Double.valueOf(x);
            double sy =  Double.valueOf(y);
            double sz = Double.valueOf(z);
            javax.vecmath.Vector3f cor = new javax.vecmath.Vector3f(Float.parseFloat(x), Float.parseFloat(y), Float.parseFloat(z));
            //if (!arr.contains(cor)){
            if (cor.y > 0)
                arr.add(new javax.vecmath.Vector3f(cor));


            if (!ship.contains(new Vector3f((int) sx, (int) sy, (int) sz)))
                ship.add(new Vector3f((int) sx, (int) sy, (int) sz));
                Float.parseFloat(z)));
            }
    }
 public void setUpPhysics() {
        //coords = new int[20][20];

        coords = new int[80][80][80];
        coords1 = new int[80][80];
        //coords[-5 + DELTA][7 + DELTA] = 11;
        for (javax.vecmath.Vector3f vec : arr){
            coords[DELTA+(int) vec.x][DELTA+(int) vec.z][DELTA + (int) vec.y] = 1; //This is line 124
            coords1[DELTA+(int) vec.x][DELTA+(int) vec.z] = 1;
        }
  }

Though it has limitations on collision interaction, it works for cannonballs colliding with a ship and checking the front of a ship to see if it has hit another ship. Also, it uses barely any CPU.

No idea on the opinions of other programmers on such a method.