Collision Detection Issues

Question

I have a little issue with my Collision Detection System for a Game. In the game are several structures which connect to each other. However they should not connect when there is another structure in between them.

For some weird reason it sometimes fails to connect to directly adjacent structures when there is a structure in a direct line behind them. Rarely it produces other weird connections.

Picture:

BUG

The red marked nodes are supposed to be connected.

Code:

public void drawConnections(Graphics g) {
    ArrayList<EnergyContainer> structurecopy = (ArrayList<EnergyContainer>) Mainclass.structures.clone(); //all structures in a list
    structurecopy.remove(this); //as we are member of the list
    structurecopy.removeIf(t -> (!hasStructureInRangeWithoutObstaclesInBetween(t))); 
    structurecopy.removeIf(t -> !t.receivesEnergyfromNeighbors()); //unimportant check if it is allowed to connect (its working)
    structurecopy.forEach(t -> drawConnectionTo(t, g)); //also works fine 
}

public boolean hasStructureInRangeWithoutObstaclesInBetween(Structure structureWhichShouldBeInRange) {
    // if in Range
    if (getRange() >= Math.hypot(structureWhichShouldBeInRange.getX() - getX(),
            structureWhichShouldBeInRange.getY() - getY())){ //checks if structure is in range
        ArrayList<EnergyContainer> structureclone = (ArrayList<EnergyContainer>) Mainclass.structures.clone();
        structureclone.remove(this); //again removes itself from the list
        structureclone.remove(structureWhichShouldBeInRange); //also removes target - so it doesn't block itself
        structureclone.removeIf(t -> !t.collidesWithLine(this.getX(), structureWhichShouldBeInRange.getX(),
                this.getY(), structureWhichShouldBeInRange.getY())); //removes it when it does not collide
        return structureclone.size() == 0; //returns true when no collisions are found
    }
    return false;
}

public boolean collidesWithLine(int x1, int x2, int y1, int y2) {
    // Line Segment - Circle Collision Detection
    double dx = x2 - x1;
    double dy = y2 - y1;
    double a = dx * dx + dy * dy; //this is the distance
    double b = 2 * dx * (x1 - getX()) + 2 * dy * (y1 - getY());
    double c = getX() * getX() + getY() * getY() + x1 * x1 + y1 * y1 - 2 * (getX() * x1 + getY() * y1)
            - getCollisionRadius() * getCollisionRadius();
    double discriminant = b * b - 4 * a * c;
    return discriminant >= 0; // no intersection -> discriminant <0

}

(I added the comments for this text only, so please ignore them if they'd cause compile errors).

Can someone tell me what I am doing wrong?

Well i really could need at least a hint...and i dont want to cause duplicates so... — kleopi
Maybe this is a bit broad. Can you explain the maths you are using and where you think the problem might be? — halfer
My suggestion is writing a unit test for collidesWithLine() to find out whether you've misplaced an operator. It's hard too see what the calculation actually does, so it's easy to mix up '+' with '*' for example. Other than that, your snippet does not show the full picture yet. What is this in the scope of collidesWithLine()? A javadoc comment could help there aswell. — SME_Dev
The distance between two points: sqrt( (x2-x1)^2 + (y2-y1)^2), but you are calculating the distance without the square root. This is something I could spot easily, there may be other defects in the code. — ahoxha

Uchiha Itachi Uchiha Itachi · Accepted Answer · 2017-03-02T18:52:59

There might be a couple problems here:

First: As Marat stated: b may be return a value of 0. This is would be happening if your getX() and getY() are returning x1 and y1. If that's the case, you are essentially doing this: (2dx * 0) + (2dy * 0). If that's the case, it can negatively impact your later equations.

Secondly: More than likely, you are ALWAYS returning true from this courtesy of your final equation:

double discriminant = b * b - 4 * a * c;
//This breaks down to discriminant = b^2 * 4ac

Even if b is 0 at this point, as long as either a or c have a value greater than 0, return discriminant >= 0; will be true;

I would HIGHLY recommend putting a breakpoint in at the 2 parts I mentioned and check your values prior to and after the code executing so you can see what's going on with the math.

Also, the Unity API has collision detection functions. You should look in to that. https://docs.unity3d.com/Manual/PhysicsSection.html

Hope that helps.

Collision Detection Issues

Picture:

Code:

2 Answers