1
\$\begingroup\$

I'm working on a small 2D top down racing game and I'm trying to implement SAT collision into my game to detect collision between cars. So, I made a small little Java2D program to test the algorithm out involving two boxes of different sizes.

As far as I can tell, the collision works just fine when one of the boxes are placed initially (in the constructor of the Renderer class where the Box objects are created) so that it must collide with the other box. (For example placing Box A at (250, 200) with width and height=100 and Box B at (300, 150) with width and height=250).

With this setup the program detects the collision, but when I move Box A out of the collision area to some other area of the screen using the arrow keys, the program still detects a "collision". Similarly, if I place Box A so that it will not collide initially and then move it to the other box so that it should collide, the program does not detect a collision no matter where I move Box A around/inside Box B.

I checked and printed out Box A and Box B's four points and it seems Box A's points are updated correctly as Box A moves, and Box B's points stay the same since it is not moving. Both boxes' axes seem to be correct according to my calculations. As far as I know, the SAT algorithm seems to be working since it works when the two boxes are set up to collide immediately, which leads me to think there is a problem with the updating - but I've checked the movement code and everything seems to update correctly, except the collision of course.

The only thing I can think of now is maybe my SAT algorithm needs to compensate for movement? Why does the program only detect collision when the two boxes are initially set up to collide immediately and not when I manually move Box A to Box B?

Here's Renderer.java, where the Box objects are created, the collision method called ( hasOverlap() ), and arrow key input is taken.

public class Renderer extends JPanel implements ActionListener, KeyListener {

private Frame frame;
private Timer timer;

private Box a;
private Box b;

public Renderer(Frame frame) {
    this.frame = frame;

    a = new Box(250, 200, 100, 100);
    b = new Box(300, 150, 250, 250);

    this.addKeyListener(this);
    this.setFocusable(true);

    timer = new Timer(20, this);
    timer.start();
}

private void update() {
    checkCollisions();
}

public void paintComponent(Graphics g) {
    super.paintComponent(g);

    Graphics2D g2d = (Graphics2D) g;

    g2d.translate(0, frame.getHeight());
    g2d.scale(1.0, -1.0);

    b.render(g);
    a.render(g);
}

@Override
public void actionPerformed(ActionEvent e) {
    update();
    repaint();
}

private void checkCollisions() {
    if(a.hasOverlap(b)) {
        System.out.println("Overlap");
        a.setColor(Color.RED);
        b.setColor(Color.RED);
    }

    else {
        System.out.println("Not overlapping");
        a.setColor(Color.GREEN);
        b.setColor(Color.BLACK);
    }
}

@Override
public void keyPressed(KeyEvent e) {
    if(e.getKeyCode() == KeyEvent.VK_LEFT)
        a.translate(-10, 0);

    if(e.getKeyCode() == KeyEvent.VK_RIGHT)
        a.translate(10, 0);

    if(e.getKeyCode() == KeyEvent.VK_UP)
        a.translate(0, 10);

    if(e.getKeyCode() == KeyEvent.VK_DOWN)
        a.translate(0, -10);
}

Here's Box.java, where hasOverlap() the main collision method is, where the points of the box is defined, the axes, etc.

public class Box {

public float x;
public float y;
public float w;
public float h;
public Vector2D center;
public Vector2D[] points;
public Vector2D[] axes;
public ArrayList<Projection> proj;
private Color color;

public Box(float x, float y, float w, float h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.center = new Vector2D(w/2 + x, h/2 + y);
    this.points = new Vector2D[4];
    this.proj = new ArrayList<Projection>();
    this.color = Color.BLACK;

    points[0] = new Vector2D(x, y); // Point A
    points[1] = new Vector2D(x, y+h); // Point B
    points[2] = new Vector2D(x+w, y+h); // point C
    points[3] = new Vector2D(x+w, y); // point D

    this.axes = setAxes(points);
}

public void render(Graphics g) {
    g.setColor(color);
    g.fillRect((int) x, (int) y, (int) w, (int) h);
}

public void translate(float x, float y) {
    for(int i = 0; i < points.length; i++) {
        points[i].x += x;
        points[i].y += y;
    }

    center.x += x;
    center.y += y;

    this.x = points[0].x;
    this.y = points[0].y;

    this.axes = setAxes(points);
}

public boolean hasOverlap(Box box) {
    // project and check on this box's axes
    for(int i = 0; i < axes.length; i++) {
        project(axes[i]);
        box.project(axes[i]);

        if(!getOverlap(proj.get(i), box.proj.get(i)))
            return false;
    }

    for(int j = 0; j < box.axes.length; j++) {
        project(box.axes[j]);
        box.project(box.axes[j]);

        if(!getOverlap(proj.get(j), box.proj.get(j)))
            return false;
    }

    return true;
}

// also normalizes the vectors to produce unit axes
private Vector2D[] setAxes(Vector2D[] points) {
    Vector2D[] axes = new Vector2D[points.length];
    Vector2D edge = new Vector2D(0, 0);

    for(int i = 0; i < points.length; i++) {
        if(i + 1 <= points.length - 1)
            edge = sub(points[i], points[i+1]);
        else
            edge = sub(points[i], points[0]);

        axes[i] = norm(getPerp(edge));
    }

    return axes;
}

// projects this box object onto the given axis, stores min and max as a vector for overlap testing
public void project(Vector2D axis) {
    float min = dotProduct(axis, points[0]);
    float max = min;

    for(int i = 1; i < points.length; i++) {
        float current = dotProduct(axis, points[i]);

        if(current < min)
            min = current;
        else if(current > max)
            max = current;
    }

    proj.add(new Projection(min, max));
}

// returns true if there an overlap on the axis
private boolean getOverlap(Projection a, Projection b) {
    return !(b.max < a.min || a.max < b.min);
}

// subtracts two vectors
private Vector2D sub(Vector2D a, Vector2D b) {
    return new Vector2D(a.x - b.x, a.y - b.y);
}

// gets the perpendicular vector of a vector. (x, y) => (y, -x) (with clockwise ordering of points)
private Vector2D getPerp(Vector2D a) {
    return new Vector2D(a.y, (-1) * a.x);
}

// normalizes vector (scales vector to length of 1, aka unit vector)
private Vector2D norm(Vector2D a) {
    float len = (float) (Math.sqrt(a.x*a.x + a.y*a.y));

    return new Vector2D(a.x / len, a.y / len);
}

private float dotProduct(Vector2D a, Vector2D b) {
    return (float) (a.x * b.x + a.y * b.y);
}

Thank you in advance!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.