Definite Shape Collision Detection
| Author |
Message |
The_Bean
|
 Posted: Wed Dec 10, 2008 7:07 pm Post subject: 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.
| Turing: |
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
max (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
max (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 <= max (p (tr1, n1 ).x, p (tr1, n1 rem numSides + 1).x ) 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
elsif p (tr1, n1 ).vLine then %if line 1 is the verticle
yi := p (tr2, n2 ).m * p (tr1, n1 ).x + p (tr2, n2 ).b
if min (p (tr1, n1 ).y, p (tr1, n1 rem numSides + 1).y ) <= yi and
max (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
max (p (tr2, n2 ).y, p (tr2, n2 rem numSides + 1).y ) >= yi and
p (tr1, n1 ).x >= min (p (tr2, n2 ).x, p (tr2, n2 rem numSides + 1).x ) and
p (tr1, n1 ).x <= max (p (tr2, n2 ).x, p (tr2, n2 rem numSides + 1).x ) 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 ).vLine and p (tr1, n1 ).vLine then % if both lines are a perfect verticle
if p (tr2, n2 ).x = p (tr1, n1 ).x then
if p (tr2, n2 ).y > 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
max (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 and
max (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
|
|
|
|
|
|
 |
Sponsor
Sponsor
|
|
|
saltpro15
|
| Posted: Thu Dec 11, 2008 6:54 pm Post subject: RE:Definite Shape Collision Detection |
|
|
| wow, that's really good o.0 thanks. |
|
|
|
|
|
Insectoid
|
| Posted: Thu Dec 11, 2008 9:43 pm Post subject: 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
|
| Posted: Thu Dec 11, 2008 9:52 pm Post subject: 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. |
|
|
|
|
|
|
|
Register
Wiki
Blog
Search
Turing
Chat Room
Members
