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:

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?

Answer 1

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.

Answer 2

Assumption: 1 If I understand correctly, these are methods of some Structure class. 2 hasStructureInRangeWithoutObstaclesInBetween is the only caller of collidesWithLine or at least that's how the question is presented.

Because of (2) b is always 0. I have a feeling it was not your intention. Please revisit you collidesWithLine method.