1

I want to make a game where the character is a rectangular prism that can be rotated, and the rest of the map are axis-aligned rectangular prisms. Everything other than the character will be static, so I was wondering what would be the best algorithm for finding if the character is colliding with any parts in the map. Any tutorials/code/advice would be much appreciated :)

Also, the character will only be rotated on the Y axis, if that helps.

Matt
  • 1,151
  • 3
  • 13
  • 34

2 Answers2

0

I believe one way to test for this is to check the 16 cases of line intersections:

http://www.math.niu.edu/~rusin/known-math/95/line_segs

If you want to optimize you could also check if the rectangles have no chance of overlapping, i.e. if all corners are to the right/left/above/below of the other rectangle.

Edit:

Se comment below.

Pedery
  • 3,632
  • 1
  • 27
  • 39
  • What are "the 16 cases of line intersections" here? The failure of edge segments to intersect will not guarantee nonintersection of prisms (or rectangles); for example, one object might be inside another. – hardmath Jun 02 '11 at 02:20
  • Ah true, but except that case it will cover all others. For the final case you can still use determinants since they will tell you whether a point is on one side of a line or another. So if you have organized all lines in your rectangle in a rotational manner, you can find out whether a point is inside or outside. Then you won't even have to check for the 16 intersections! – Pedery Jun 02 '11 at 03:38
  • I'll assume the 16 intersections you refer to means intersections between four edges of one rectangle and four of the other. Then you can cover all possibilities with three mutually exclusive cases: (1) rectangles don't intersect, (2) an edge of one rectangle intersects an edge of another, and (3) one rectangle lies in the interior of the other. This doesn't seem to be as efficient as the "axis of separation" approach, but more to the point, the question is about prisms (3D), not rectangles (2D). In 3D one would need to generalize (2) to check for intersections of the faces. – hardmath Jun 02 '11 at 14:45
  • Could be. I'm not gonna benchmark whether one approach is better than another. *However* if the polygon consists of four lines going P1-P2-P3-P4-P1 you could easily use determinants to find out whether one point is inside the polygon. So in this case the "one figure inside the other" case is handled with a simple if-test by using the values you've already calculated. – Pedery Jun 03 '11 at 03:09
0

In the special case that the character only rotates around its axis parallel to the Y-axis, the collision detection with another axis-aligned rectangular prism reduces to:

  1. Check if the character's Y-interval intersects the other prism's Y-interval.

  2. Check if the corresponding XZ-cross-sections of the two prisms intersect, which amounts to a problem of collision detection between two rotated rectangles.

If the answer to both the above is yes, then and only then do the prisms overlap.

Having reduced the particular problem to that of overlapping intervals and intersecting (rotated) rectangles, there are a number of good code resources for each of these tasks. The first task is pretty trivial:

Overlapping intervals

Two closed intervals [a,b] and [c,d] intersect if and only c ≤ b and a ≤ d. Here we also assume the intervals' notation is consistent, i.e. that a ≤ b and c ≤ d (otherwise swap the endpoints as necessary to make it so).

Intersecting rotated rectangles

A highly rated SO answer to this specific question is here. A Lua implementation I wrote for a slightly more general problem, Shortest distance between two rectangles, includes "early exit" optimizations (bounding circle and vertex in rectangle) that I mentioned on this thread. My Lua code returns "false" if the rotated rectangles intersect, otherwise the distance between them. For Java purposes the return value of zero in the collision cases would serve.

Community
  • 1
  • 1
hardmath
  • 8,753
  • 2
  • 37
  • 65