Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
I think you're asking about line-rectangle collision. Is your game character in the shape of a rectangle, and the level is made of lines? Further explain what you're trying to do. What tools are you using? C++ or XNA or ActionScript or...? –  Olhovsky May 10 '11 at 1:56
    
@Olhovsky - edited. –  Jopo May 10 '11 at 2:09
    
Sigh, if you want your question answered, then just play along and answer my questions about your question -- it really does make things easier, even if it doesn't seem relevant to you right now. Anyways, I've started an answer for you below. –  Olhovsky May 10 '11 at 3:15
    
@Jopo tools are not irrelevant because they provide a common ground for which to communicate the idea, and since many libraries (e.g. XNA) provide tools to do this intersection test for you. Unless of course, your preferred language to communicate in is pure math with latex. Anyways, see if my answer below helps or not. Let me know :) –  Olhovsky May 10 '11 at 3:26
    
@Olhovsky - I am using XNA. I originally did not want to say this because I did not want to deter anyone from answering my question simply because of my technology choice. As an off-topic, I was reading your blog and wish you best of luck on your DBP project! It looks quite good so far. –  Jopo May 10 '11 at 3:50

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Sorry, I understand your confusion in my situation. My character is axis-aligned. My level is made up of straight, axis-aligned lines that are scattered throughout the level. I believe this is the last situation you have presented. –  Jopo May 10 '11 at 3:26
    
Okay, let me edit my answer to reflect that. –  Olhovsky May 10 '11 at 3:29
    
Jopo: I added some code for you which does the intersection test that you want. I just wrote that off the top of my head, so hopefully I didn't make any mistakes, and you get the idea :) –  Olhovsky May 10 '11 at 3:39
    
Edited answer to correct a mistake in my code. –  Olhovsky May 10 '11 at 3:45
    
Added the intersect_amount to the code, so that you can just add that value to your player position to correct collisions. (The value will be negative when the player is intersecting a line from below, or positive when the player is on top of the line, intersecting it.) –  Olhovsky May 10 '11 at 3:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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