(Java) Collision Detection Walls

Question

I've been trying to use my collision detection to stop objects from going through each other. I can't figure out how to do it though.

When objects collide, I've tried reversing the direction of their velocity vector (so it moves away from where it's colliding) but sometimes the objects get stuck inside each other.

I've tried switching their velocities but this just parents objects to each other.

Is there a simple way to limit objects' movement so that they don't go through other objects? I've been using the rectangle intersects for collisions, and I've also tried circle collision detection (using distance between objects).

Ideas?

package objects;

import java.awt.Rectangle;

import custom.utils.Vector;
import sprites.Picture;
import render.Window;



// Super class (game objects)
public class Entity implements GameObject{


    private Picture self;
    protected Vector position;
    protected Vector velocity = new Vector(0,0);
    private GameObject[] obj_list = new GameObject[0];

    private boolean init = false;

    // Takes in a "sprite"
    public Entity(Picture i){
        self = i;
        position = new Vector(i.getXY()[0],i.getXY()[1]);
        ObjectUpdater.addObject(this);
    }



    public Object getIdentity() {
        return this;
    }

    // position handles
    public Vector getPosition(){
        return position;
    }

    public void setPosition(double x,double y){
        position.setValues(x,y);
        self.setXY(position);
    }

    public void setPosition(){
        position.setValues((int)Window.getWinSize()[0]/2,(int)Window.getWinSize()[1]/2);
    }

    // velocity handles
    public void setVelocity(double x,double y){ // Use if you're too lazy to make a vector
        velocity.setValues(x, y);
    }
    public void setVelocity(Vector xy){ // Use if your already have a vector
        velocity.setValues(xy.getValues()[0], xy.getValues()[1]);
    }

    public Vector getVelocity(){
        return velocity;
    }


    // inferface for all game objects (so they all update at the same time)

    public boolean checkInit(){
        return init;
    }

    public Rectangle getBounds() {
        double[] corner = position.getValues(); // Get the corner for the bounds
        int[] size = self.getImageSize(); // Get the size of the image

        return new Rectangle((int)Math.round(corner[0]),(int)Math.round(corner[1]),size[0],size[1]); // Make the bound
    }

    // I check for collisions where, this grabs all the objects and checks for collisions on each.

    private void checkCollision(){
        if (obj_list.length > 0){
        for (GameObject i: obj_list){
            if (getBounds().intersects(i.getBounds()) && i != this){
                // What happens here?
            }
        }
        }
    }

    public void updateSelf(){
        checkCollision();
        position = position.add(velocity);
        setPosition(position.getValues()[0],position.getValues()[1]);
        init = true;
    }


    public void pollObjects(GameObject[] o){
        obj_list = o;
    }

}

Hopefully it's not too difficult to read.

Edit: So I've been using the rectangle intersection method to calculate the position of an object and to modify velocity. It's working pretty well. The only problem is that some objects push others, but that's so big deal. Collision is pretty much an extra thing for the mini game I'm creating. Thanks a lot of the help.

All that being said, I'd still really appreciate elaboration on mentioned ideas since I'm not totally sure how to implement them into my project.

Answer 1

Without seeing your code, I can only guess what's happening. I suspect that your objects are getting stuck because they overshooting the boundaries of other objects, ending up inside. Make sure that each object's step is not just velocity * delta_time, but that the step size is limited by potential collisions. When there is a collision, calculate the time at which it occurred (which is somewhere in the delta_time) and follow the bounce to determine the final object location. Alternatively, just set the objects to be touching and the velocities changed according to the law of conservation of momentum.

EDIT After seeing your code, I can expand my answer. First, let me clarify some of my terminology that you asked about. Since each call to updateSelf simply adds the velocity vector to the current position, what you have in effect is a unit time increment (delta time is always 1). Put another way, your "velocity" is actually the distance (velocity * delta time) traveled since the last call to updateSelf. I would recommend using an explicit (float) time increment as part of your simulation.

Second, the general problem of tracking collisions among multiple moving objects is very difficult. Whatever time increment is used, it is possible for an object to undergo many collisions in that increment. (Imagine an object squeezed between two other objects. In any given time interval, there is no limit to the number of times the object might bounce back and forth between the two surrounding ones.) Also, an object might (within the resolution of the computations) collide with multiple objects at the same time. The problem is even more complicated if the objects actually change size as they move (as your code suggests they may be doing).

Third, you have a significant source of errors because you are rounding all object positions to integer coordinates. I would recommend representing your objects with floating-point objects (Rectangle2D.Float rather than with Rectangle; Point2D.Float rather than Vector). I would also recommend replacing the position field with a rectangular bounds field that captures both the position and size. That way, you don't have to create a new object at each call to getBounds(). If the object sizes are constant, this would also simplify the bounds updating.

Finally, there's a significant problem with having the collision detection logic inside each object: when object A discovers that it would have hit object B, then it is also the case that object B would have hit object A! However, object B does its own calculations independently of object A. If you update A first, then B might miss the collision, and vice versa. It would be better to move the entire collision detection and object movement logic to a global algorithm and keep each game object relatively simple.

One approach (which I recommend) is to write an "updateGame" method that advances the game state by a given time increment. It would use an auxiliary data structure that records collisions, which might look like this:

public class Collision {
    public int objectIndex1;  // index of first object involved in collision
    public int objectIndex2;  // index of second object
    public int directionCode; // encoding of the direction of the collision
    public float time;        // time of collision
}

The overall algorithm advances the game from the current time to a new time defined by a parameter deltaTime. It might be structured something like this:

void updateGame(float deltaTime) {
    float step = deltaTime;
    do (
        Collision hit = findFirstCollision(step);
        if (hit != null) {
            step = Math.max(hit.time, MIN_STEP);
            updateObjects(step);
            updateVelocities(hit);
        } else {
            updateObjects(step);
        }
        deltaTime -= step;
        step = deltaTime;
    } while (deltaTime > 0);
}

/**
 * Finds the earliest collision that occurs within the given time
 * interval. It uses the current position and velocity of the objects
 * at the start of the interval. If no collisions occur, returns null.
 */
Collision findFirstCollision(float deltaTime) {
    Collision result = null;
    for (int i = 0; i < obj_list.length; ++i) {
        for (int j = i + 1; j < obj_list.length; ++j) {
            Collision hit = findCollision(i, j, deltaTime);
            if (hit != null) {
                if (result == null || hit.time < result.time) {
                    result = hit;
                }
            }
        }
    }
    return result;
}

/**
 * Calculate if there is a collision between obj_list[i1] and
 * obj_list[i2] within deltaTime, given their current positions
 * and velocities. If there is, return a new Collision object
 * that records i1, i2, the direction of the hit, and the time
 * at which the objects collide. Otherwise, return null.
 */
Collision findCollision(int i1, int i2, float deltaTime) {
    // left as an exercise for the reader
}

/**
 * Move every object by its velocity * step
 */
void updateObjects(float step) {
    for (GameObject obj : obj_list) {
        Point2D.Float pos = obj.getPosition();
        Point2D.Float velocity = obj.getVelocity();
        obj.setPosition(
            pos.getX() + step * velocity.getX(),
            pos.getY() + step * velocity.getY()
        );
    }
}

/**
 * Update the velocities of the two objects involved in a
 * collision. Note that this does not always reverse velocities
 * along the direction of collision (one object might be hit
 * from behind by a faster object). The algorithm should assume
 * that the objects are at the exact position of the collision
 * and just update the velocities.
 */
void updateVelocities(Collision collision) {
    // TODO - implement some physics simulation
}

The MIN_STEP constant is a minimum time increment to ensure that the game update loop doesn't get stuck updating such small time steps that it doesn't make progress. (With floating point, it's possible that deltaTime -= step; could leave deltaTime unchanged.)

Regarding the physics simulation: the Wikipedia article on Elastic collision provides some nice math for this problem.