Broad Phase Collision Detection

[thawkins]

So, I've been reading up on collision detection lately. I'm looking at algorithms such as Sweep & Prune, Quadtrees, etc... and I don't have the slightest clue where to begin. If anyone would be nice enough to point/link in the right direction, I'd greatly appreciate it.

[EdBoon]

So, I've been reading up on collision detection lately. I'm looking at algorithms such as Sweep & Prune, Quadtrees, etc... and I don't have the slightest clue where to begin. If anyone would be nice enough to point/link in the right direction, I'd greatly appreciate it.

There are lots of methods and algorithms out there, and since you have been looking into it I am going to assume you know the basic concept. The collision detection part is pretty similar in all cases.

The algorithms are ways to minimize the number of times each object checks the position of other objects. I had messed around A LOT with quad tree methods only to realize that for my application it wasn't the best solution because I was dealing with so many objects at the same time so then I looked into spatial hashing, which is more efficient. It all depends on your application, but if your just looking for knowledge, i would say quadtree is a nice concept to understand.

As far as the actual collision detection goes, in a simple very cheap way you can give each object a circle and check to see if 2 circles overlap, and move them in the opposite direction in the amount of space they overlap. heres an example:

Code: Select all

public void HandleCollide(GameEntity item)
        {
            Vector2 item2Center = new Vector2();
            Center.X = this.position.X + 32;
            Center.Y = this.position.Y + 32;


            Vector2 itemCenter = new Vector2();
            itemCenter.X = item.boundsBox.X + 32;
            itemCenter.Y = item.boundsBox.Y + 32;

            
            Vector2 toCollideTarget = (item2Center) - (itemCenter);

            float DistFromEachOther = (float)Math.Sqrt((toCollideTarget.X * toCollideTarget.X + toCollideTarget.Y * toCollideTarget.Y));
            float AmountOfOverlap = 32 + 32 - DistFromEachOther;

            if (AmountOfOverlap >= 0)
            {
                position.X += (toCollideTarget.X / DistFromEachOther) * AmountOfOverlap;
                position.Y += (toCollideTarget.Y / DistFromEachOther) * AmountOfOverlap;
            }
        }

Also each algorithm has a maximum efficiency possible due to its nature.

heres a couple links that i found helpful when I was in your position:

http://www.metanetsoftware.com/technique/tutorialA.html
http://www.metanetsoftware.com/technique/tutorialB.html

http://www.gamedev.net/reference/snippe ... atialHash/

http://www.gamedev.net/reference/articl ... cle736.asp

http://www.gamedev.net/reference/articl ... cle735.asp

http://www.gamasutra.com/view/feature/3 ... ction_.php


also i have a great paper on spatial hashing i can send to your email if interested

if you have more specific questions , we will be happy to help!

[Falco Girgis]

I recommend first looking into their strengths and weaknesses for particular applications before you dive into anything.

Broad-Phase collision detection is definitely some of the most hardcore mathematics you'll get into with game development. I've seen whole books dedicated to the topic (and wish to god I could afford them).

Before you invest an extreme amount of time in learning (and implementing) a few of them, learn a bit about them. They're all good and bad at certain things.