I’m Rob, and welcome to my section of the XG hive mind! I wanted somewhere to store and talk about solved / partially solved issues that crop up during development. Hopefully it’ll be semi-blog style, and not just the outpouring of this poor crazed programmers ravaged mind! Lets get into it!
Ok, so here at XG we’re currently working on some procedural content ideas. I’ve been looking to place object in 2D space, and not have them intersect.
Each object has a bounding volume/box and to make life easy is Axis Aligned (AABB), each object can be any size.
Now it’s a simple test to see if two AABB hit each other:
bool IsHit(AABB In)
if (In.Min.x > Max.x) return (false); // In is to the Right (+x)
if (In.Max.x < Min.x) return (false); // In is to the Left (-x)
if (In.Min.y > Max.y) return (false); // In is Above (+y)
if (In.Max.y < Min.y) return (false); // In is Below (-y)
Diag 1: Edges of Box for testing
As you can see we Test all 4 Edges to see if they are outside the bounds of the box, but what this does not tell us is what sides/edges where hit! This is important for us to be able to separate intersecting objects. The possible intersections are as follows:
Diag 2: Test Cases 1-4
I tried a few options to see which edges were hit, but in the end the best option seemed to be to test which corner was inside the box and extrapolate the result from there.
// Test if Point is inside box
bool IsHit(Vector2 In)
if (In.x > Max.x) return (false);
if (In.x < Min.x) return (false);
if (In.y > Max.y) return (false);
if (In.y < Min.y) return (false);
int DirectionHit(AABB In)
int CornersHit = 0; // Bit Flag
int EdgeHit = 0; // Bit Flag
CornersHit |= 1; // Lower Left
if (IsHit(In.Min + In.Size.x))
CornersHit |= 2; // Lower Right
CornersHit |= 4; // Upper Right
if (IsHit(In.Min + In.Size.y))
CornersHit |= 8; // Upper Left
if ((CornersHit & 0x03) == 0x03)
EdgeHit |= 1; // Lower
if ((CornersHit & 0x06) == 0x06)
EdgeHit |= 2; // Right
if ((CornersHit & 0x0C) == 0x0C)
EdgeHit |= 4; // Upper
if ((CornersHit & 0x09) == 0x09)
EdgeHit |= 8; // Left
Things to Note
First, the Objects need to be tested A.DirectionHit(B) and B.DirectionHit(A) to Satisfy test 3.
Second, this code will fail the fourth test. This is because none of the points are ever inside the a box, but the edges pass through.
Once we can find these intersection by testing, we can then solve them. Solving is fairly simple and just a matter of moving the Object based on which edge is hit. The complexity grows has the number of objects increase too, but that’s another problem entirely!
Looking back at what I said right at the start, I think we’ll categorize this post under option 2!