-----------------------------------

The_Bean

Wed Dec 10, 2008 7:07 pm


Definite Shape Collision Detection

-----------------------------------

Collision Detection method for any sides shapes, works by finding the intersection of the lines, and seeing if that point lies along the line segment.  Slows done a lot with many sides, and many shapes.

View.Set ("graphics:max,max,nobuttonbar,title:Shape Collision Detection")
type coordinates :
    record
        x, y : int
        m, b : real
        vLine : boolean
    end record
var numShapes : int := 50
var numSides : int := 5
var p : array 1 .. numShapes, 1 .. numSides of coordinates
Text.ColourBack (7)
Text.Colour (0)
cls
proc CreateShapes
    var x, y, r : int
    r := 50
    for shape : 1 .. numShapes
        x := Rand.Int (r, maxx - r)
        y := Rand.Int (r, maxy - r)
        for side : 1 .. numSides
            p (shape, side).vLine := false
            p (shape, side).x := round (cosd (side * 360 / numSides + 180 / numSides / 2) * r) + x
            p (shape, side).y := round (sind (side * 360 / numSides + 180 / numSides / 2) * r) + y
        end for
    end for
    for shape : 1 .. numShapes
        for side : 1 .. numSides
            Draw.Line (p (shape, side).x, p (shape, side).y, p (shape, side rem numSides + 1).x, p (shape, side rem numSides + 1).y, 0)
        end for
    end for
end CreateShapes
proc CollisionDetection
    var xi, yi : real
    var numCollisions : int := 0
    for shape : 1 .. numShapes
        for side : 1 .. numSides
            if p (shape, side rem numSides + 1).x = p (shape, side).x then
                p (shape, side).vLine := true
            else
                p (shape, side).m := (p (shape, side rem numSides + 1).y - p (shape, side).y) / (p (shape, side rem numSides + 1).x - p (shape, side).x)
                p (shape, side).b := p (shape, side).y - p (shape, side).m * p (shape, side).x
            end if
        end for
    end for
    for tr1 : 1 .. numShapes
        for tr2 : 1 .. tr1 - 1
            for n1 : 1 .. numSides
                for n2 : 1 .. numSides
                    if p (tr2, n2).vLine and ~p (tr1, n1).vLine or p (tr1, n1).vLine and ~p (tr2, n2).vLine then %if one line is a a perfect verticle
                        if p (tr2, n2).vLine then %if line 2 is the verticle
                            yi := p (tr1, n1).m * p (tr2, n2).x + p (tr1, n1).b
                            if min (p (tr1, n1).y, p (tr1, n1 rem numSides + 1).y) = yi and
                                    min (p (tr2, n2).y, p (tr2, n2 rem numSides + 1).y) = yi and
                                    p (tr2, n2).x >= min (p (tr1, n1).x, p (tr1, n1 rem numSides + 1).x) and
                                    p (tr2, n2).x = min (p (tr2, n2).x, p (tr2, n2 rem numSides + 1).x) and
                                    p (tr1, n1).x  min (p (tr1, n1).y, p (tr1, n1).y) and
                                    p (tr2, n2).y < max (p (tr1, n1).y, p (tr1, n1).y) or
                                    p (tr2, n2 rem numSides + 1).y > min (p (tr1, n1).y, p (tr1, n1).y) and
                                    p (tr2, n2 rem numSides + 1).y < max (p (tr1, n1).y, p (tr1, n1).y) then
                                Draw.Line (p (tr1, n1).x, p (tr1, n1).y, p (tr1, n1 rem numSides + 1).x, p (tr1, n1 rem numSides + 1).y, 12)
                                Draw.Line (p (tr2, n2).x, p (tr2, n2).y, p (tr2, n2 rem numSides + 1).x, p (tr2, n2 rem numSides + 1).y, 12)
                                numCollisions += 1
                            end if
                        end if
                    elsif p (tr2, n2).m ~= p (tr1, n1).m then %if none of them are a perfect verticle, and not parallel
                        xi := (p (tr1, n1).b - p (tr2, n2).b) / (p (tr2, n2).m - p (tr1, n1).m)
                        if min (p (tr1, n1).x, p (tr1, n1 rem numSides + 1).x) = xi and
                                min (p (tr2, n2).x, p (tr2, n2 rem numSides + 1).x) = xi then
                            Draw.Line (p (tr1, n1).x, p (tr1, n1).y, p (tr1, n1 rem numSides + 1).x, p (tr1, n1 rem numSides + 1).y, 12)
                            Draw.Line (p (tr2, n2).x, p (tr2, n2).y, p (tr2, n2 rem numSides + 1).x, p (tr2, n2 rem numSides + 1).y, 12)
                            numCollisions += 1
                        end if
                    end if
                end for
            end for
        end for
    end for
    put "Number of Collisions: ", numCollisions ..
end CollisionDetection

CreateShapes
CollisionDetection



-----------------------------------

saltpro15

Thu Dec 11, 2008 6:54 pm


RE:Definite Shape Collision Detection

-----------------------------------

wow, that's really good o.0 thanks.


-----------------------------------

Insectoid

Thu Dec 11, 2008 9:43 pm


RE:Definite Shape Collision Detection

-----------------------------------

Inspired by me! That is really cool that you figured that out. I gave up on mine (actually, I became to preoccupied with Ruby to continue work). Nice to see somebody finished it.


-----------------------------------

The_Bean

Thu Dec 11, 2008 9:52 pm


Re: Definite Shape Collision Detection

-----------------------------------

It looks a lot more complicated than it actually is, the bulk of it is for vertical lines because there slope is undefined, so theres quite a bit of special cases for them.  And there's still a problem when 1 triangle fits perfectly into another without touching any sides.