Thursday, September 1, 2016

Line-Rectangle Collision Detection and Response


I've looked through Google and none of the solutions seem to pinpoint my idea. Ultimately, I want to create a level editor where I can draw lines and have them exported to a file for my engine to read. I'm having trouble getting path-rectangle to work. I'm using this in the context of a platformer, so I'm also interested in knowing which direction and distance the collision came from so I can resolve it. Which is the best algorithm for doing this? I'm only concerned about axis aligned rectangles.


EDIT: My character is represented as a rectangle and the level is represented by lines. The tools really do not matter as I'm looking for the mathematics behind it, not necessarily an implementation.



Answer



Well, a simple way to test the intersection of a line segment against a rectangle is to do a line segment test against each line segment that the rectangle is made of.


However for axis aligned boxes we can do things more efficiently.


Here is the easiest to understand code that I could find:


http://www.garagegames.com/community/blogs/view/309



There are slightly more efficient ways, but that should suit you fine.


There are dozens of implementations of this all over the internet. Search for "line AABB intersection".


However, you say that your box is an axis aligned box (AABB), so does this mean that your lines are also axis aligned?


In that case, all you really need to test is whether each of the Y values of the four points of the AABB are above or below the Y value defined by your line, and whether each of those point's X values are within the X values defined by the segment ends of the line.


As I said in the comment on your question, explain to us what you're trying to do, because as it stands your question doesn't make very much sense.


If you're trying to make a game where you have lines that are not axis aligned, but the player is axis aligned, i.e., you have a box player that has only one corner of the box touching the lines, then my advice is to not make that game.


If you want to make a game where the box is lined up with the line, then my answer needs to change because then you want to know about OBB vs line intersection instead.


If you want to make a game where the lines of the level are axis aligned, then you don't need to test the player box against the level lines, you only need to test the box points agains the level line segments.




For axis aligned level lines vs AABB player:



Player position and bounding box diagram.


Each line segment of your level is made up of a Y value (the height of the line on the screen) and two X values (the left and right extents of the line). A line is a struct/class that stores X1, X2, Y.


Your AABB player is represented by two points, bottom left and top right (call them bottom_left and top_right).


C# code:


bool test_line_intersection(Line line, Vector2 bottom_left, 
Vector2 top_right, out float intersect_amount){
intersect_amount = 0;

if(top_right.X < line.X1){
// player is not intersecting line.

return false;
}

if(bottom_left.X > line.X2){
// player is not intersecting line.
return false;
}

if(bottom_left.Y < line.Y && top_right.Y > line.Y){
// bottom of player is below line 0, and player is intersecting line

intersect_amount = line.Y - bottom_left.Y;
return true;
}

// player is not intersecting line.
return false;
}

If this function returns true then there is an intersection. In that case, add intersect_amount to the player position, and the player will no longer be intersecting with the line.


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...