Collision Testing

[Thumper]

I was originally going to post this as a reply to xander333's post about his 2D collision issues, but it really didn't have to do with the original question.

Anyway, I was daydreaming about how i would go about calculating 2D collisions in math class today. Bounding boxes/circles is a quick and easy way to check if there was a collision. But something else occurred to me. Say you have a 1 pixel thin line, representing a wall or something. If you have a dot traveling towards that line, at say.. 10 pixels per frame, isn't it possible that dot could actually travel through the line (but should collide with that line) without actually touching the line, because of how fast it's moving?
I'm not sure how good i did at explaining that, so I drew something up in paint.

http://img98.imageshack.us/img98/4130/collisiony.png

So, I'm wondering how to test collisions like that.
Perhaps make a linear model? take the speed_x, and speed_y of the dot, and calculate for the next frame each of the points it will pass through, and test each point to see if it's on the line?
I'm not sure where I would start doing that either.

Ideas?

[Zhuge]

I was thinking of a similar situation, and considered, like you mentioned, taking the path of the object and interpolate. Then check if the wall and path intersect. Didn't ever actually come up with any code for it, though.

[Mathhead200]

Hm... Even if you don't update the picture except for say every Δt, you could still calculate the position/velocity/acceleration/... of each particle at every pixel, or at least fast enough to ensure at least one calculation per pixel for every particle. I think...

[Thumper]

That's correct Mathhead200. I'm speaking theoretically.

I'm still trying to work it out logically.
Scribbled some stuff down on paper.

You could take two points, one from the current frame, and one from the next frame (calculated by the speed at which the dot is moving), then find the equation for the line through them (y=mx+b), then test if the two lines, the wall and the one we drew, intersect at a point between the two end points.
Which all makes sense on paper, but algebra's always harder to code.

[Mathhead200]

It has got to be easier then trying to code calculus... o_0

[bartoli]

Wouldn't it be more efficient to increase the bounding box size in function of the object's speed?

[Disch]

I do this in my game's collision system. Everything is based on lines moving instead of bounding boxes.

What you do is have a map that consists of line segments. Then you make a line from the old position of the point to the new position.

If that generated line intersects with any wall lines, the object is hitting the wall and you stop them at the interseciton point.

Complex objects (rectangles) are just extrapolated from this idea. To move a rectangle around on such a map, you draw lines out from each of the 4 corners. You also have to draw lines from the end of the map's line segments in the opposite direction and see if they intersect with any of the box's lines.

It sounds complicated, and it is. But it works very well.

I might show my code when I get home (if I remember).

AFAIK, this is also what box2d and similar libs do.

[Thumper]

Awesome, that'd be great Disch. A little sneak peak would be much appreciated.
I'm sure it'd do a lot in helping me code some of it myself (which is the fun part)

Oh, and btw, I'm still using your resource manager :p

[ne555]

Hi. If you just want to know if there is intersection, use the cross product.
Then it's just a couple of sign tests.

[Disch]

ne555:

That's basically how it works with my engine (although I use Dot Product since it's 2D)

[ne555]

You make me curious.
With the cross product I test if the other endpoints lie at opposites sides of the trajectory line (POV object and obstacle).
But that it's possible because (u x v) n = |u| |v| sin(theta) (positive left, negative right)

¿what do you test with dot product?

[Disch]

what you just described is the dot product.

The cross product, afaik, is the 3d version of the same idea.

[ne555]

No, the operations are different

Dot product uv = u_i v_i = |u| |v| cos(theta) (an scalar)
Cross product u x v = e_{ijk} u_j v_k = |u| |v| sin(theta) n (a vector)

if uv = 0 then the vectors are orthogonal.
if u x v = 0 then the vectors are aligned.

[Disch]

oh pfft nevermind. XD

My brain is in a weird spot.

Anyway I can't explain it now, I'll try to throw up the code when I get home.

[Disch]

Okay my code is huge but here's the relevant tidbits excluding physics stuff.

Fundamental stuff:

typedef sf::Vector2<double> Point;

inline double Dot(const Point& a,const Point& b)                        { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b)                    { return (a.y*b.x) - (a.x*b.y); }

bool LineCollision( const Point& A1, const Point& A2,
                    const Point& B1, const Point& B2,
                    double* out                                )
{
    Point a(A2-A1);
    Point b(B2-B1);

    double f = PerpDot(a,b);
    if(!f)      // lines are parallel
        return false;
    
    Point c(B2-A2);
    double aa = PerpDot(a,c);
    double bb = PerpDot(b,c);

    if(f < 0)
    {
        if(aa > 0)     return false;
        if(bb > 0)     return false;
        if(aa < f)     return false;
        if(bb < f)     return false;
    }
    else
    {
        if(aa < 0)     return false;
        if(bb < 0)     return false;
        if(aa > f)     return false;
        if(bb > f)     return false;
    }

    if(out)
        *out = 1.0 - (aa / f);
    return true;
}

LineCollision takes line A (comprised of end points A1, A2) and line B. The idea is line B is the "motion" line (the player) and line A is the "stationary" line (the wall). IE: we are moving along line B, starting at B1 moving towards B2 until we hit line A.

It returns true if there was a collision. If 'out' is provided, and there is a collision, out is filled with the distance at which the intersection occured, scaled between 0..1. So if the collision occured exactly halfway between B1 and B2, '*out' would be 0.5.

Applied Fundamentals:

Expanding on simple Line Collision, my Map class allows you to do collision checks via the following functions:

bool Map::Block::LineMove(const Point& pta,const Point& ptb,Point& mov,const Corner** outhitpoint,bool dropthru)
{
    bool hit = false;
    double hitdist;

    for(int y = u; y <= d; ++y)
    {
        for(int x = l; x <= r; ++x)
        {
            for(std::list<Corner>::iterator p = mMap.mCornerBlocks(x,y).begin(); p != mMap.mCornerBlocks(x,y).end(); ++p)
            {
                Point p2(p->pt - mov);
                if(LineCollision(pta,ptb,p->pt,p2,&hitdist))
                {
                    if(dropthru && (p->prop & Prop_DropThru))   // ignore drop thru if requested
                        continue;

                    hit = true;

                    hitdist -= cEjectWeight;
                    if(hitdist < 0)
                        hitdist = 0;
                    mov *= hitdist;

                    if(outhitpoint)
                        *outhitpoint = &(*p);
                }
            }
        }
    }

    return hit;
}
bool Map::Block::PointMove(const Point& pt,Point& mov,const Map::Line** outhitline,double dropthrux)
{
    bool hit = false;
    double hitdist;

    for(int y = u; y <= d; ++y)
    {
        for(int x = l; x <= r; ++x)
        {
            for(std::list<const Line*>::iterator p = mMap.mLineBlocks(x,y).begin(); p != mMap.mLineBlocks(x,y).end(); ++p)
            {
                if(LineCollision((*p)->a,(*p)->b,pt,pt + mov,&hitdist))
                {
                    // ignore appropriate DropThru walls
                    if( (*p)->prop & Prop_DropThru )
                    {
                        // if the line is steeper than the object's upfoot, ignore it (drop thrus act as floors, but never as walls)
                        if((*p)->unit.x < dropthrux)
                            continue;

                        // if we're coming in from below the drop-thru line, ignore it
                        const Point la(     pt - (*p)->b);
                        double pd = PerpDot( la, (*p)->unit );
                        if(pd >= 0)
                            continue;
                    }

                    hit = true;

                    hitdist -= cEjectWeight;
                    if(hitdist < 0)
                        hitdist = 0;
                    mov *= hitdist;

                    if(outhitline)
                        *outhitline = *p;
                }
            }
        }
    }
    return hit;
}

These simply take an origin point (pt) or an origin line (pta,ptb) and attempt to move it on vector 'mov'. If any walls are hit, the function returns true, and 'outhitline' or 'outhitpoint' are filled to give information about the wall you hit (that wall's position, slope, properties, etc)

The whole mLineBlocks and mCornerBlocks thing is like a rough filter I used. Basically I broke the map into "sections" of 200x200 pixels or something and have a list of all the lines/corners in each section. That way you only have to check collisions with lines in the sections you're nearby instead of having to check against the whole map (which would be expensive for very large maps).

Putting it all Together

Objects call this function which sees how far they can move in any given direction on the map:

MotionRect::hit_t MotionRect::DoMoveHit(Map::Block& blk,Point& mov,const Map::Corner*& cornerhit,const Map::Line*& linehit,bool dropthru)
{
    hit_t hit = hit_none;

    double dropx = dropthru ? 2.0 : mSlideFootUnit.x;

    if(blk.PointMove( Pt(Focal), mov, &linehit, dropx ))    hit = hit_focal;
    if(blk.PointMove( Pt(SL), mov, &linehit ))              hit = hit_vlcorner;
    if(blk.PointMove( Pt(SR), mov, &linehit ))              hit = hit_vrcorner;

    if(blk.LineMove( Pt(UL), Pt(SL), mov, &cornerhit ))     hit = hit_lside;
    if(blk.LineMove( Pt(UR), Pt(SR), mov, &cornerhit ))     hit = hit_rside;
    if(blk.LineMove( Pt(UL), Pt(UR), mov, &cornerhit ))     hit = hit_top;
    if(blk.LineMove( Pt(Focal), Pt(SL), mov, &cornerhit ))  hit = hit_vlside;
    if(blk.LineMove( Pt(Focal), Pt(SR), mov, &cornerhit ))  hit = hit_vrside;

    // have to test the upper left/right corners last, to reduce side effects
    if(blk.PointMove( Pt(UL), mov, &linehit ))              hit = hit_ul;
    if(blk.PointMove( Pt(UR), mov, &linehit ))              hit = hit_ur;

    return hit;
}

This moves all the lines/corners of the player and reports which part of the player hit a wall (if any). Which part of the player hit a wall is important for my physics stuff.


Anyway that's basically the idea. Like I said it's really complicated, but it works really well.

I don't recommend it for a first time project.