Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Fast collision detection ideas  (Read 8214 times)

0 Members and 1 Guest are viewing this topic.

fredreichbier

  • Newbie
  • *
  • Posts: 6
    • View Profile
Fast collision detection ideas
« on: July 21, 2008, 03:30:48 pm »
Hello!

I need collision detection, but I have many many sprites (some in the view, but more outside of it), and checking whether one sprite collides with any of others would take ... uhm ... a very long time (right?). Do you have any ideas how to detect collisions more fast?

I was thinking about only checking the sprites which are displayed in the view. Is there an easy way to get them (fast)? Or do you have a completely different idea?

Cheers,

Fred

Hiura

  • SFML Team
  • Hero Member
  • *****
  • Posts: 4321
    • View Profile
    • Email
Fast collision detection ideas
« Reply #1 on: July 21, 2008, 03:49:23 pm »
well, I don't know exactly. but I would make two "if" test : on the x coord and on the y one. Juste to see what is in the box of the view.

The best way to know one good method is to read physical engine. But witch one?

I cannot telle you more sorry.
SFML / OS X developer

quasius

  • Full Member
  • ***
  • Posts: 166
    • View Profile
Fast collision detection ideas
« Reply #2 on: July 21, 2008, 04:26:15 pm »
You need some kind of organizational structure where the sprites are placed in.  For example, you could keep all sprites in a hash table where the hash is based on the world-location so each "world zone" has its own bucket in the hash table.  Then you could rapidly access only sprites near the one you are testing.
You can also look up "quad-tree," which is another (slightly more complicated) standard solution for this problem.
If you don't want to do either of those, you could just test if each sprite is within a certain maximum sprite size distance from the colliding sprite before doing a full collision detection.  (Don't use the "distance formula" here.  sqrt is slow.)  This might help, but is still not very scalable since even those tests on enough sprites will bog down your frame rate.

Edit:  In general this is referred to as "broad-phase," "mid-phase," and "narrow phase" collision detection.  Broad-phase uses a quad tree, hash table, or similar to see if the object is even in the "ball park."  Mid-phase tests if the "bounding boxes" (the smallest 2D or 3D, non-rotated box shape that encompasses the object) overlap.  Narrow-phase is the actual collision detection that takes into account rotation, odd shapes, or whatever else you need.
Any serious and fast collision detection will use (at least) those 3 phases.  The second paragraph solution I gave basically skips the broad-phase test.  It's also possible you're not concerned with narrow-phase tests if you only care if the sprite's bounding boxes are intersecting and not the actual displayed shapes.

quasius

  • Full Member
  • ***
  • Posts: 166
    • View Profile
Fast collision detection ideas
« Reply #3 on: July 21, 2008, 04:30:00 pm »
Quote from: "Hiura"

The best way to know one good method is to read physical engine. But witch one?


A good, free, open-source physics engine you can look at is Bullet.  But that's probably waaay more solution than he's looking for.  (Although if you can figure out what's going on in something like Bullet, you will learn a lot.)

Edit: A better (IMO) free, but not open-source physics engine is Ageia PhysX (now owned by Nvidia).

SirJulio

  • Full Member
  • ***
  • Posts: 241
    • View Profile
Fast collision detection ideas
« Reply #4 on: July 21, 2008, 06:55:30 pm »
Quote from: "quasius"

A good, free, open-source physics engine you can look at is Bullet.  But that's probably waaay more solution than he's looking for.  (Although if you can figure out what's going on in something like Bullet, you will learn a lot.)

Edit: A better (IMO) free, but not open-source physics engine is Ageia PhysX (now owned by Nvidia).


Agree for PhysX, this engine is just awesome. Bullet and ODE are cool too.

But for the op problem, maybe a lightweight engine (I guess his project is in 2d only) like Box2D (zlib licence i think) could do the job.

fredreichbier

  • Newbie
  • *
  • Posts: 6
    • View Profile
Fast collision detection ideas
« Reply #5 on: July 21, 2008, 07:15:50 pm »
Hello,

first, many thanks for your interesting answers.
I think I will pick up the hashmap idea for now; seems to be easy and effective - later I'll try to make it with a quadtree.

A 'problem' with physics engines is that I'm using DSFML, so I can only use already ported engines or engines that are written in C.

Could I use chipmunk for this, too?

Edit: My project is 2d-only, right :)

quasius

  • Full Member
  • ***
  • Posts: 166
    • View Profile
Fast collision detection ideas
« Reply #6 on: July 21, 2008, 07:24:35 pm »
Quote from: "fredreichbier"
Hello,

first, many thanks for your interesting answers.
I think I will pick up the hashmap idea for now; seems to be easy and effective - later I'll try to make it with a quadtree.

A 'problem' with physics engines is that I'm using DSFML, so I can only use already ported engines or engines that are written in C.

Could I use chipmunk for this, too?

Edit: My project is 2d-only, right :)


I don't know much about chipmunk, but I thought I'd mention a quick "gotcha" if you're going down the hash table route.  First off, you should be inserting pointers, not actual sprites into the hash table.  This is because if an object overlaps 2 or more spaces in your "zone grid," you will need to insert its pointer into the hash bucket of every zone it touches not just the one of it's position (default upper-left) reported by SFML.  Otherwise, you will fail to find the sprite when you should in some cases.

Hiura

  • SFML Team
  • Hero Member
  • *****
  • Posts: 4321
    • View Profile
    • Email
Fast collision detection ideas
« Reply #7 on: July 21, 2008, 07:25:33 pm »
Quote from: "[url=http://wiki.slembcke.net/main/published/Chipmunk
Features[/url]"]C99 implementation, no external dependencies
So I think it's ok.
SFML / OS X developer

SirJulio

  • Full Member
  • ***
  • Posts: 241
    • View Profile
Fast collision detection ideas
« Reply #8 on: July 21, 2008, 11:01:10 pm »
Quote from: "fredreichbier"
Hello,

first, many thanks for your interesting answers.
I think I will pick up the hashmap idea for now; seems to be easy and effective - later I'll try to make it with a quadtree.

A 'problem' with physics engines is that I'm using DSFML, so I can only use already ported engines or engines that are written in C.

Could I use chipmunk for this, too?

Edit: My project is 2d-only, right :)


Ok, so for D language, you could use Blaze (heavily inspired by Box2D and chipmunk). ODE is also available with Derelict.

Blaze is written in D (pretty cool actually i'm just waiting for CCD !), ODE is loaded at runtime. Blaze doesn't have extensive documentation (see the demos, and Box2d chipmunk docs maybe =D), but maybe you could give it a shot. ODE is a mature engine with lots of documentation. Up to you. =)