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?

Prismatic

Well i really could need at least a hint...and i dont want to cause duplicates so... – Prismatic

stackoverflow.com/help/no-one-answers – Boyfriend

Maybe this is a bit broad. Can you explain the maths you are using and where you think the problem might be? – Boyfriend

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. – Fortnightly

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. – Hallah

Can we see what getX(), getY() and getCollisionRadius() look like. hard to tell where the math is going wrong if we don't know what values those functions are returning... – Lundgren

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.

Lundgren

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.

Married

It is the same class. Structure describes a "Building" in a game, therefore one of the nodes as shown on the provided picture. collidesWithLine is supposed to check whether the structure itself is on the line. The structure therefore has a circleshaped "hitbox" and the line is given by the parameters. – Prismatic

The other Method actually draws a line between two structures and checks for every other structure whether it is on that line. If any object except for start and end objects which definitely are on the line is on the line, it sees this connection as blocked. – Prismatic

Did you notice that b is always 0? – Married

Unless getX() and getY() return x1 and y1, b would literally never be 0... Without knowing what some of the values these functions return, it's hard to pinpoint where things are going wrong – Lundgren

To Geoff: In the code presented here x1 is always GetX(). Explanation: The only call to the function is in line 16. In this call x1 = this.GetX() and y1 = this.GetY(). In line 28 we calculate b. If we substitute x1 and y1 with passed values, we get that b is always 0. – Married