Jump to content
  • Advertisement
Sign in to follow this  
SteveHatcher

Asking feedback re my collision system

This topic is 1330 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi All,

 

I would like some advice on how I have implemented bounding box collision detection. I only ask because some of the code gets quite long and I feel I may be going about this unnecessarily complicated. I am using the DirectX Tool Kit for all of the heavy lifting.

 

My sprite class is responsibly for loading and dealing with sprites, and it has as a member my SpriteData structure:

struct SpriteData
{
    int         width;      // width of sprite in pixels
    int         height;     // height of sprite in pixels
    float       x;          // screen location (top left corner of sprite)
    float       y;
    float       scale;      
    float       angle;      
    RECT        rect;       
    XMVECTORF32 color;
    ID3D11ShaderResourceView *tex;
    XMFLOAT2 origin;
    RECT        boundingRect;
};

Hopefully it is mostly self explanatory. XMVECTORF32 color is so when I pass it to draw I can modify its shade. What I have here is RECT        boundingRect;. The purpose of this is to store the bounding rectangle per update section of my code. I do that with the following code:

 

shipSpr->GetBoundingBox(shipSpr->getX(), shipSpr->getY(), shipSpr->getSDBoundingRect());

 

Once I have the bounding box for 2 sprites, I check collision using:

 

if (shipSpr->Intersect(shipSpr2))

 

This is where things get a bit messy. This function is:

bool Sprite::Intersect(const Sprite *sprite) const
{

    if (fabs(spriteData.x + (spriteData.x + width) - sprite->spriteData.boundingRect.left - sprite->spriteData.boundingRect.right) < (spriteData.x + width) - spriteData.x + sprite->spriteData.boundingRect.right - sprite->spriteData.boundingRect.left)
    if (fabs(spriteData.y + (spriteData.y + height) - sprite->spriteData.boundingRect.top - sprite->spriteData.boundingRect.bottom) < ((spriteData.y + height) - spriteData.y + sprite->spriteData.boundingRect.bottom - sprite->spriteData.boundingRect.top))
        return true;

    return false;
}

It all works, but I am worried I am kind of forcing my program to get the information it needs with the long calls sprite->spriteData.boundingRect.right. Is this an acceptable design?

 

Secondly, an alternative approach I have seen is not to store the bounding box information within each sprite, but to just calculate it on the fly from another classes methods. Would this be advantageous?

 

Thanks for all input

Share this post


Link to post
Share on other sites
Advertisement

A general rule for collision detection routines - avoid any arithmetic operations that can be done prior to collision testing. I.e., if you do N collision tests against the same object, you may be performing N operations to calculate the same value, over-and-over. Perform boolean operations instead, in an order than may be optimized with early outs. Even if just 1 collision test is performed on an object, the necessary calcs will have to be done anyway. So do them once per collidable object per update.

 

Also, a sprite object class shouldn't include collision detection member functions. That's not the job of a sprite. Instead, use a function such as IntersectAABBs(AABB& box1, AABB& box2), and call it, e.g., with:

 

IntersectAABBs(sprite1->AABB, sprite2->AABB);

 

Assuming you're using axis aligned bounding boxes, you can use min/max value structures.

 

float2 minVals, maxVals;

 

where minVals.x is the minimum X value from any corner of the bounding box. minVals.y similarly. Perhaps something like:

 

minVal.x = rect.left; minVal.y = rect.top; maxVal.x = rect.left; maxVal.y = rect.bottom; // for Y where top is less than bottom

 

Calculate all min/max values for each object to be collided BEFORE any collision tests are made.

 

Then you can use only boolean operations to test for collision - e.g.,

 

Intersect( float2 &minVals1, float2 &maxVals1, float2 &minVals2, float2 &maxVals2 ); // minVals1 and maxVals1 for object1, similar for object2

 

Then:

// Checking an OR combination of conditions is often faster than checking an AND combination of conditions, depending on the compiler.

// So avoid the use of AND <&&> boolean operations, if possible.

// Consider: A minimum X value for object1 that's greater than object2's maximum X value -> no intersection.

// Similarly, if a maximum X value for object1 is less than object2's minimum X value -> no intersection.

if( minVals1.x > maxVals2.x || minVals1.y > maxVals2.y || minVals2.x > maxVals1.x || minVals2.y > maxVals2.y ) return false;

if( maxVals1.x < minVals2.x || maxVal1.y < minVals2.y || maxVals2.x < minVals1.x || maxVals2.y < minVals1.y ) return false;

return true;

 

If you can do collision testing for your sprites using integer values, that will likely be even faster.

 

That's off the top of my head, so check for typos. wink.png

Edited by Buckeye

Share this post


Link to post
Share on other sites

Hi Buckeye, thanks a lot for your response.

 

Also, a sprite object class shouldn't include collision detection member functions. That's not the job of a sprite. Instead, use a function such as IntersectAABBs(AABB& box1, AABB& box2), and call it, e.g., with:

 

I thought this was the case, it did not seem right putting the collision detection code in the sprite class. I think i will put everything related to collision, eg the RECT struct and the Intersect functions into their own class. I can then give the sprite a "CollisionRect rect" member, and use that to the bounding box calcs and intersection tests.

 

Calculate all min/max values for each object to be collided BEFORE any collision tests are made.

 

Okay so rather than something like "IntersectAABB(sprite1->calcBoundingBox(), sprite2->calcBoundingBox())", the bounding boxes should be calculated prior, with something like sprite1BB = sprite1->calcBoundingBox(), and then "IntersectAABB(sprite1BB, sprite2BB)"? Would it be better to have the bounding boxes stored in the sprite class, the CollisionRect class, or the underlying SpriteData struct?

 

In the sprite class I could use simply sprite1->getBB(). But again this feels wrong and not the job of the sprite class.

 

In the spriteData struct I would use sprite1->spriteData.boundingBox

 

Or in the collisionRect class I would use sprite1->rect->getBB().

 

This kind of stuff confuses me greatly.

 

Then you can use only boolean operations to test for collision - e.g.,

Intersect( float2 &minVals1, float2 &maxVals1, float2 &minVals2, float2 &maxVals2 ); // minVals1 and maxVals1 for object1, similar for object2

 

For ease or readability, could I store these minVals and maxVals in the collisionRect class?

 

// Checking an OR combination of conditions is often faster than checking an AND combination of conditions, depending on the compiler.

// So avoid the use of AND <&&> boolean operations, if possible.

 

I thought the && operator can be used for this as it short circuits if false?

 

Thanks again for your detailed reply.

Share this post


Link to post
Share on other sites

I thought the && operator can be used for this as it short circuits if false?

 

You're correct. They can. Depends on whether the logical terms indicate success or failure in this case.

 

It's just the distributive law for negation in boolean logic: ~( A || B ) :: ~A && ~B   Those expression are logically equivalent.

 

Similarly, ~(A && B) :: ~A || ~B  are equivalent.

 

I.e.,

 

// this, that, foo, bar are NON-intersection tests - just me, maybe, I think in these terms
if( this || that || foo || bar ) return false; // indicate failure at the first non-intersection condition
return true; // if falls through, indicates success

// this, that, foo, bar are intersection tests
if( this && that && foo && bar ) return true; // fall through the if statement on the first failed intersection test
return false; // if falls through, indicate failure


I personally have not looked at how compilers would optimize those two situations. If I had to bet, I'd say it's a wash, or so close in performance as makes no difference. So, you pays your money and you takes your choice - whatever is more readable to you, or easier to maintain.

 

With regard to where to store data, keeping the rects and/or min/max structs as members of the sprite class is probably fine, easier to program, and a little more logical. I would keep them as structures, and not wrap them in a class. There just doesn't seem to be enough functionality associated with those structures to warrant that.

 

That doesn't necessarily mean that the sprite is the right place to update that info. In complicated situations, I could see having collision detection and resolution handled elsewhere.

 

But don't pass structures as arguments, pass references or pointers.

 

I.e.,
 

// not this
bool Intersect( RECT rect1, RECT rect2 ); // this actually makes a copy of both RECTs to be used by the function

// but this
Intersect( RECT &rect1, RECT &rect2 ); // passes only 2 references
// or
Intersect( RECT *rect1, RECT *rect2 ); // passes only 2 pointers
Edited by Buckeye

Share this post


Link to post
Share on other sites

Never noticed a measureable && vs || difference, but interesting recently with a 64bit MSVC 2013 program, I got a significant performance boost by change a "if (bool || intx == constant || intx == constant2) {simpleop;}"  to "if (bool | (intx == constant) | (intx == constant2) {simpleop;}". Not had time to look into it much, but seems MSVC always wants to generate branching code for && and ||, but in cases like this the cost of just doing those or and equality ops seems to have been a lot cheaper than dealing with the branches.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!