How can I do fast Triangle/Square vs Triangle collision detection?

Question

I have a game world where the objects are in a grid based environment with the following restrictions.

All of the triangles are 45-90-45 triangles that are unit length. They can only rotate 90°. The squares are of unit length and can not rotate (not that it matters)

I have the Square vs Square detection down and it is very very solid and very fast (max vs min on x and y values)

Wondering if there are any tricks I can employ since I have these restrictions on the triangles?

Answer 1

You could first treat every triangle as a square, then, once a collision with a triangle-as-square is detected, you could investigate further to see if collision actually occurred with the triangle.

Since both triangle and square are convex shapes, an overlap is easily detectable when one contains one or more vertexes of the other.
For axis aligned square, point containment test is easy as checking for minimum ad maximum for both x an y.
For triangles a point is in when signed distances of it from lines edges are lying on (computed with constant winding) are all positive (or all negative depending on your distance function).

Since in your case edges are always 0°, 90° or 45°, the containment test is easy as checking all this conditions (with AND operator)

   A /|
 p. / | C
   /__|
     B

• p.x<c.x
• p.y>b.y
• p.x+p.y> K

where K depends on the line equation of A and can be easily precomputed for the two cases (from lower right to upper left and the mirrored version) and adjusted with the position of the shape.

Answer 2

The triangle can be easily defined by three lines: horizontal, vertical, and diagonal:

• Line1: x = 0
• Line2: y = 0
• Line3: x = 1-y |/
• corner90: TOP_LEFT

or

• Line1: x = 1
• Line2: y = 0
• Line3: x = y \|
• corner90: TOP_RIGHT

or

• Line1: x = 0
• Line2: y = 1
• Line3: x = y |\
• corner90: BOT_LEFT

or

• Line1: x = 1
• Line2: y = 1
• Line3: x = 1-y /|
• corner90: BOT_RIGHT

These weird symbols are pictures of triangles, I just didn't bother to draw horizontal lines.

Now, You need first to treat the triangle as a square. If it collides, then You need to check the square against triangle's slope.

Let's define a function to check if a point is on 'good' side of the slope (outside the triangle):

function isOutSlope ( x, y, corner90 ):Boolean {
if ( corner90 == TOP_LEFT ) return x > 1-y // x = 1-y; //    |/
if ( corner90 == TOP_RIGHT ) return x < y // x = y; //    \|
if ( corner90 == BOT_LEFT ) return x > y // x = y; //    |\
if ( corner90 == BOT_RIGHT ) return x < 1-y // x = 1-y; //    /|
}

Now we need to check just one point of square - the one that is closest to corner90, when the two shapes almost collide, but not yet. If triangle.corner90 is TOP_LEFT, then it will be also top left corner of square , if corner90 is BOT_RIGHT, then it is bot right corner of square etc. If You don't understand my point here, then sketch a few situations, where square and square would collide, but square and rectangle either don't, almost or do collide; that should clear it up a little bit.

Let's make another function to make it more readable:

function getCornerLocalPos ( corner ):Point {
if ( corner == TOP_LEFT ) return new Point (0,0)
if ( corner == TOP_RIGHT ) return new Point (0,1)
if ( corner == BOT_LEFT ) return new Point (1,0)
if ( corner == BOT_RIGHT ) return new Point (1,1)
//else throw ERROR ("THIS IS A CIRCLE!!!")
}

So, let's make the main function

function detectSquareToTriangleCollision ( rect, triang ):Boolean {
if ( !detectSquareToSquareCollision (rect,triang) ) return False //if two squares wouldn't collide, then by no chance they won't if one turns to be a triangle.

//These deltas are used to translate one coordinate context to another
delta_x = rect.x - triang.x
delta_y = rect.y - triang.y
p = getCornerLocalPos ( triang.corner90 )
p.x += delta_x
p.y += delta_y

return isOutSlope ( p.x, p.y, triang.corner90 )
}

I didn't test it, but I sketched a little bit to make sure most is valid. I wrote the code for readability, but optimizing is straight-forward. I am not a native english speaker and hence I'm sorry if I accidentally insulted Your mother or did any other faux pas. I assumed same as Mr Anton - the triangles rotate in steps of 90 degrees, not in 0-90 degree range. If that would be the case, the thing would be a little bit more tricky, but the isOutSlope function code should be helpful.

Answer 3

Keep doing max vs min tests as you are, but also test in two coordinate systems rotated +/- 45 degrees. I.e. test max vs min across x, y, (x - y) and (-x + y). This'll work since any edge in your environment will be aligned with one of these (assuming I correctly read between the lines of your question).

If their coordinates are integers you can even get away with only testing the rotated systems iff you are only testing against objects in the same "cell". But if you're not already keeping a map of what objects are in what cells and vice versa, then this pretty much amounts to the same thing as the above.