0
\$\begingroup\$

I recently implemented the SAT algorithm into my 2D game and at first it appeared to be working fine. However, when I move around and rotate the character in and out of the wall tiles, there are some angles and positions that do not register as a collision when the player and wall tile are clearly overlapping. I created my own RotatingRectangle class that rotates around the player and is the bounding box.

enter image description here

enter image description here

enter image description here

enter image description here

I am unsure what could be causing this, or if this is just natural SAT behaviour and it does not actually detect all collisions accurately? There are no other resources online for inconsistent SAT collision detection so I am lost. I will post my code for the projections and actual collision detection in case I made a silly mistake somewhere

    // Returns an array of projections, one onto each axes
    public Vector2[] ProjectOntoAxes(List<Vector2> points)
    {
        Vector2[] projections = new Vector2[2];

        for (int i = 0; i < Axes.Length; i++)
        {
            float max = float.MinValue;
            float min = float.MaxValue;

            for (int j = 0; j < points.Count; j++)
            {
                float res = Vector2.Dot(Axes[i], points[j]);

                if (res < min)
                {
                    min = res;
                }
                else if (res > max)
                {
                    max = res;
                }
            }

            projections[i] = new Vector2(min, max);
        }

        return projections;
    }

        private bool PlayerTileCollision(Tile tile)
    {
        // Check overlap on projections onto player axes
        Vector2[] projections = Player.BoundingRect.ProjectOntoAxes(tile.BoundingRect.Corners);
        for (int j = 0; j < projections.Length; j++)
        {
            if (Player.BoundingRect.Projections[j].X > projections[j].Y ||
                Player.BoundingRect.Projections[j].Y < projections[j].X)
            {
                // No overlap can exit
                return false;
            }
        }
        // Check overlap on projections onto tile axes
        projections = tile.BoundingRect.ProjectOntoAxes(Player.BoundingRect.Corners);
        for (int j = 0; j < projections.Length; j++)
        {
            if (projections[j].X > tile.BoundingRect.Projections[j].Y ||
                projections[j].Y < tile.BoundingRect.Projections[j].X)
            {
                // No overlap can exit
                return false;
            }
        }

        return true;
    }

UDPATE: I have added code to visualise the projections and axes to see what is going on, and it appears that the projection code is not properly selecting the correct minimum and maximum values. I will try to figure out why now. (Purple lines are player projections and orange is the projections of that tile I am standing on, the top left one and the player axes can be visualised via the white lines at the origin)

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Please post an answer instead of editing your question if you managed to solve your issue. \$\endgroup\$ – Tyyppi_77 Dec 7 '17 at 7:21
3
\$\begingroup\$

I am happy to say that I have squashed the bug. The visualisations really aided me and I strongly recommend anybody struggling with anything to try and get whatever it is your working on onto the screen. Now for how I fixed the bug and what it was. The reason it was not properly setting the min and max projections is due to the ProjectOntoAxes method. For the min and max values, I initially set them to the complete opposite values via the lines

float min = float.MaxValue;
float max = float.MinValue;

This was so that they were guaranteed to be set to one of the corners. Now the bug causing lines are the if and else if conditional statements inside the for loop. What was happening was that if the very first corner checked was actually the maximum value, it would actually always set off the first if statement checking if it is less than the minimum because the minimum is literally the highest value possible. Due to the next if having an else before it, it would not be checked and thus the max value will not actually be set to the real max value. Therefore the simple fix was to remove the else and just have to regular if statements, this allows for the case where if the first corner checked is actually going to end up being the maximum, it will still trigger the second if statement for setting the maximum value.

This:

if (res < min) {
min = res;
} else if (res > max) {
max = res;
}

became this:

if (res < min) {
min = res;
} if (res > max) {
max = res;
}
\$\endgroup\$
1
\$\begingroup\$

Your projection is incorrect. Instead of

$$projected = \vec a \cdot \vec b$$

(Where \$\cdot\$ means dot product)

you need to use

$$projected = \vec a \cdot \frac{\vec b}{|\vec b|}$$

(Where \$|\vec v|\$ is the length of the \$\vec v\$ vector and \$ \vec a\$ is the axis)

\$\endgroup\$
  • \$\begingroup\$ I assume you mean b, not v? \$\endgroup\$ – Maximus Minimus Dec 13 '17 at 17:39
  • \$\begingroup\$ @MaximusMinimus v is just a placeholder there \$\endgroup\$ – Bálint Dec 13 '17 at 17:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.