CODEWITHSUNDEEP
collision-detection
LunchMarble
LunchMarble

Reputation: 5141

Faster Collision Check Algorithm

Here's the code I am using now:

For Local i : Int = 0 To Entity.Entities.Count() - 1
        For Local j : Int = 0 To Entity.Entities.Count() - 1
            If j = i Or Not Entity(Entity.Entities.ValueAtIndex(i)).IsPhyicsEnabled Or Not Entity(Entity.Entities.ValueAtIndex(j)).IsPhyicsEnabled
                Continue
            EndIf

            Local a : Entity = Entity(Entity.Entities.ValueAtIndex(i));
            Local b : Entity = Entity(Entity.Entities.ValueAtIndex(j));

            Local dist : Float = Sqr(((a.Position.X - b.Position.X)^2) + ((a.Position.Y - b.Position.Y)^2))

            If dist < Min(a.Radius, b.Radius)
                a.Collide(b)
            EndIf
        Next
    Next

The trouble with this is the looping. Checks are done way too many times. Is there a way I can cut this down?

Upvotes: 0

Views: 296

Answers (2)

Dour High Arch
Dour High Arch

Reputation: 21712

Try this:

For Local i : Int = 0 To Entity.Entities.Count() - 1
    If Not Entity(Entity.Entities.ValueAtIndex(i)).IsPhyicsEnabled
        Continue
    EndIf

    Local a : Entity = Entity(Entity.Entities.ValueAtIndex(i));
    Local aRadiusSquared = a.Radius^2

    For Local j : Int = (i+1) To Entity.Entities.Count() - 1
        If Not Entity(Entity.Entities.ValueAtIndex(j)).IsPhyicsEnabled
            Continue
        EndIf

        Local b : Entity = Entity(Entity.Entities.ValueAtIndex(j));

        Local distSquared : Float = ((a.Position.X - b.Position.X)^2) + ((a.Position.Y - b.Position.Y)^2)

        If distSquared < Min(aRadiusSquared, b.Radius^2)
            a.Collide(b)
        EndIf
    Next
Next

Upvotes: 1

Narf the Mouse
Narf the Mouse

Reputation: 1568

I highly recommend "Game Physics Engine Development: How To Make A Robust Commercial-Grade Physics Engine For Your Game" (long title, but accurate). The website and GitHub webpage is fully maintained, AFAICT. To be honest, the code there is a lot better than the book's, at least as far as I've gotten.

Upvotes: 0

Related Questions