Collision detection and response

BlitzMax Forums/BlitzMax Programming/Collision detection and response

UnderwoodNullium (Posted 2008) [#1]

Hello Forum! $100.00 or £67.87 for working code! I've been working on a physics engine for a long time now, and I've been banging my head around forever trying to get this to work. I am using Verlet integration, and it's working great. The collision detection I've been using has been crude to say the least... and is incorrect. I know there are ways to use vectors to check for intersections, I just can't wrap my brain around it. I've read many, if not all, online pages I could find. Basically, is there any way that you have found to see if a moving point and a moving line segment (made from two moving points) have collided? If there's anyway to get the correct response velocities for said point and segment points, I would be very grateful. I know that asking other people to give you code is very non-programmer-like, but I can't do it. I could understand it if I had it in front of me! I will pay $100.00 or £67.87 to anyone who can get my existing engine to have collision detection and response. I know this is horrible of me and I should be shunned, but I don't care anymore. I'm desperate. I just thought of a method of making things simple and work very well, but I'm not sure if it will work: Anyways, here is the code: Engine Code: Rem Outbreak 2D Physics Engine Extention Development: 2/13/08 - 00/00/00 Extention members: Programming Blain Rinehart © Nullium, 2008 End Rem ' ------------------------------------------------------------------- ' Initialization ' ------------------------------------------------------------------- ' Globals Global PHYSICSAREA:Float[4] ' the area covered by the physics stuff... Global PAUSEPHYSICS:Int = 1 ' stop the physics engine? Global WINDX:Float = 0.0 ' the wind asserted along the x coordinate Global WINDY:Float = 0.0 ' the wind asserted along the y coordinate Global GRAVITYX:Float = 0.0 ' the gravity asserted along the x coordinate Global GRAVITYY:Float = 0.0 ' the gravity asserted along the y coordinate Global pointlist:TList = CreateList() ' the list that holds all of the points Global linklist:TList = CreateList() ' the list that holds all of the links ' Types Type point ' the point type Field selected:Int ' boolean: is the point selected for modification? Field frozen:Int ' boolean: is the point frozen to a specific place? Field x:Float,y:Float ' the x and y coordinates of the point Field vx:Float,vy:Float ' the x and y velocities (actually 'forces') of the point Field oldx:Float,oldy:Float ' the previous x and y coordinate positions Field gravityx:Float,gravityy:Float ' individual additions of gravity to the global ones Field mass:Float ' how 'massive' (pushable) is the point? Field orarray:Int[] ' point's relative orientation to each link array End Type Type link ' the link type Field selected:Int ' boolean: is the link selected for modification? Field frozen:Int ' boolean: is the link frozen to a specific place? Field kind:Int ' what kind of link is it? (1-6 kinds) Field stiffness:Int ' how 'springy' is the link? Field p1:point ' the first point of the link Field p2:point ' the second point of the link Field length:Float ' the literal length of the link Field friction:Float ' friction (0.0 - 1.0) of the link Field bounce:Float ' continguence (0.0 - 1.0) of the link (bounce) Field balance:Float ' the center of balance (determined by point masses) End Type ' ------------------------------------------------------------------- ' Creation Functions ' ------------------------------------------------------------------- ' Create Point ' Programmed by Blain Rinehart ' 5/10/08 Function CreatePoint:point(selected%,frozen%,x#,y#,vx#,vy#,gravityx#,gravityy#,mass#) Local p:point = New point ' create a new point variable p.selected = selected ' creator set p.frozen = frozen p.x = x p.y = y p.oldx = x p.oldy = y p.vx = vx p.vy = vy p.gravityx = gravityx p.gravityy = gravityy p.mass = mass ListAddLast(pointlist,p) ' add it to the end of the list Return(p) ' return the point handle End Function ' Create Link ' Programmed by Blain Rinehart ' 5/10/08 Function CreateLink:link(selected%,frozen%,kind%,stiffness%,p1:point,p2:point,friction#,bounce#) Local l:link = New link ' create a new link variable l.selected = selected ' creator set l.frozen = frozen l.kind = kind l.stiffness = stiffness l.p1 = p1 l.p2 = p2 l.length = GetDistance(l.p1.x,l.p1.y,l.p2.x,l.p2.y) l.friction = friction l.bounce = bounce l.balance = (l.p2.mass / (l.p1.mass + l.p2.mass)) ' (the center of balance) used for replacement ListAddLast(linklist,l) ' add it to the end of the list Return(l) ' return the link handle End Function ' ------------------------------------------------------------------- ' Update Functions ' ------------------------------------------------------------------- ' Integrate Point ' Programmed by Blain Rinehart ' 5/10/08 Function IntegratePoint:point(p:point) Local tempx# = p.x ' some holder variables Local tempy# = p.y Local tempvx# = 0 Local tempvy# = 0 p.vx = (p.vx + p.gravityx + GRAVITYX) ' this updates the velocities (forces, actually), with the p.vy = (p.vy + p.gravityy + GRAVITYY) ' addition of gravities, and the localized point gravities also tempx = (((2 * p.x) - p.oldx) + p.vx) ' this integrates the points with the above velocities and tempy = (((2 * p.y) - p.oldy) + p.vy) ' positions p.oldx = p.x ' update the previous coordinates p.oldy = p.y p.x = (tempx + WINDX) ' add some 'wind' to the mutated coordinates p.y = (tempy + WINDY) p.vx = 0 ' set the velocities (forces) to 0 (real velocity is implicit) p.vy = 0 Return(p) ' return the point End Function ' Update Point ' Programmed by Blain Rinehart ' 5/10/08 Function UpdatePoint:point(p:point) If PAUSEPHYSICS <> 0 Return(Null) If p.frozen <> 0 Return(Null) ' if frozen, don't update any position or movement of point IntegratePoint(p) ' this updates the position of the point If p.x < PHYSICSAREA[0] ' bound any points outside the system p.x = PHYSICSAREA[0] p.oldy = p.y p.oldx = PHYSICSAREA[0] p.vx = -p.vx p.vy = -p.vy EndIf If p.y < PHYSICSAREA[1] p.y = PHYSICSAREA[1] p.oldy = PHYSICSAREA[1] p.oldx = p.x p.vx = -p.vx p.vy = -p.vy EndIf If p.x > PHYSICSAREA[2] p.x = PHYSICSAREA[2] p.oldy = p.y p.oldx = PHYSICSAREA[2] p.vx = -p.vx p.vy = -p.vy EndIf If p.y > PHYSICSAREA[3] p.y = PHYSICSAREA[3] p.oldy = PHYSICSAREA[3] p.oldx = p.x p.vx = -p.vx p.vy = -p.vy EndIf Return(p) ' return the point End Function ' Update Link ' Programmed by Blain Rinehart ' 5/10/08 Function UpdateLink:link(l:link) If PAUSEPHYSICS <> 0 Return(Null) If l.frozen <> 1 Or (Not l) Return(Null) ' if frozen, don't update any position or movement of link Local distance# ' some holder variables Local stress# Local angle# distance = GetDistance(l.p1.x,l.p1.y,l.p2.x,l.p2.y) ' get the 'now' distance of the link points angle = GetAngle(l.p1.x,l.p1.y,l.p2.x,l.p2.y) ' get the angle between them stress = (distance - l.length) ' how much difference is there between the set and now distance? If l.p1.frozen <> 0 ' if the first point is frozen... l.p2.x = (l.p2.x - (Cos(angle) * stress / l.stiffness)) ' update only the second one fully l.p2.y = (l.p2.y - (Sin(angle) * stress / l.stiffness)) ElseIf l.p2.frozen <> 0 ' if the second point is frozen... l.p1.x = (l.p1.x + (Cos(angle) * stress / l.stiffness)) ' update only the first one fully l.p1.y = (l.p1.y + (Sin(angle) * stress / l.stiffness)) Else ' if neither... l.p1.x = (l.p1.x + (Cos(angle) * stress * l.balance / l.stiffness)) ' update both, with center of balance l.p1.y = (l.p1.y + (Sin(angle) * stress * l.balance / l.stiffness)) l.p2.x = (l.p2.x - (Cos(angle) * stress * (1 - l.balance) / l.stiffness)) l.p2.y = (l.p2.y - (Sin(angle) * stress * (1 - l.balance) / l.stiffness)) EndIf Return(l) ' return the link End Function ' Collision Detection ' Programmed by Blain Rinehart ' 12/24/08 Function CollisionDetection() For Local l:link = EachIn linklist For Local p:point = EachIn pointlist Next Next End Function ' Collision Response ' Programmed by Blain Rinehart ' 12/24/08 Function CollisionResponse() For Local l:link = EachIn linklist For Local p:point = EachIn pointlist Next Next End Function ' ------------------------------------------------------------------- ' Sub Functions (sub physics) ' ------------------------------------------------------------------- Function DistToLine:Float(ax#,ay#,bx#,by#,px#,py#) Local dx# = (bx - ax) Local dy# = (by - ay) Return(((ay - py) * dx + (px - ax) * dy) / Sqr(dy * dy + dx * dx)) End Function Function LinesCross:Int(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#) Local numa# Local numb# Local numc# Local ua#,ub# Local ra#,rb# numa# = (((x4# - x3#) * (y1# - y3#)) - ((y4# - y3#) * (x1# - x3#))) numb# = (((x2# - x1#) * (y1# - y3#)) - ((y2# - y1#) * (x1# - x3#))) numc# = (((y4# - y3#) * (x2# - x1#)) - ((x4# - x3#) * (y2# - y1#))) If numc# = 0 Return(0) Else ua# = (numa# / numc#) ub# = (numb# / numc#) ra# = (ua# >= 0) And (ua# <= 1) rb# = (ub# >= 0) And (ub# <= 1) If ra# And rb# Return(1) Else Return(0) End If End If End Function Function PointInCircleOfLink:Int(px#,py#,x1#,y1#,x2#,y2#) If GetDistance(((x2 + x1) / 2),((y2 + y1) / 2),px,py) >= (GetDistance(x1,y1,x2,y2) / 2) Return(0) Else Return(1) EndIf End Function Function PointCrossesLink:Int(px#,py#,x1#,y1#,x2#,y2#) Return(Sgn(((x2 - x1) * (py - y1)) - ((px - x1) * (y2 - y1)))) End Function ' Get Distance ' Programmed by Blain Rinehart ' 5/10/08 Function GetDistance:Float(x1#,y1#,x2#,y2#) Return(Sqr(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)))) End Function ' Get Angle ' Programmed by Blain Rinehart ' 5/10/08 Function GetAngle:Float(x1#,y1#,x2#,y2#) Return((ATan2((y2 - y1),(x2 - x1)) + 360) Mod 360) End Function ...and the 'example' code needed to run the engine: Rem Outbreak 2D Physics Engine Extention Development: 2/13/08 - 00/00/00 Extention members: Programming Blain Rinehart © Nullium, 2008 End Rem ' ------------------------------------------------------------------- ' Initialization ' ------------------------------------------------------------------- ' Setup SuperStrict SeedRnd(MilliSecs()) Include "Physics library.bmx" Graphics(1024,768,1) SetBlend(3) ' set up the physics area PHYSICSAREA = [20.0,-100.0,Float GraphicsWidth() - 20,Float GraphicsHeight() - 20] WINDX = 0.0 WINDY = 0.0 GRAVITYX = 0.0 GRAVITYY = 0.098 Local point1:point Local point2:point Local point3:point For Local loop:Int = 0 To 6 point1 = CreatePoint(0,0,650 - loop * 70,640 - loop * 70,0,0,0,0,1) point2 = CreatePoint(0,0,700 - loop * 70,650 - loop * 70,0,0,0,0,1) point3 = CreatePoint(0,0,650 - loop * 70,600 - loop * 70,0,0,0,0,1) CreateLink:link(0,1,1,1,point1,point2,1.0,1.0) CreateLink:link(0,1,1,1,point2,point3,1.0,1.0) CreateLink:link(0,1,1,1,point3,point1,1.0,1.0) point1 = Null point2 = Null point3 = Null Next While Not KeyHit(key_escape) Cls SetClsColor(40,40,40) DrawHUD() If KeyHit(key_space) PAUSEPHYSICS = (PAUSEPHYSICS + 1) Mod 2 EndIf SetColor(255,255,255) Local closest# = 500 Local closestp:point = Null For Local p:point = EachIn pointlist If MouseHit(1) And PAUSEPHYSICS = 0 For Local p2:point = EachIn pointlist p2.selected = 0 If GetDistance(MouseX(),MouseY(),p2.x,p2.y) < closest closestp = p2 closest = GetDistance(MouseX(),MouseY(),p2.x,p2.y) EndIf Next closestp.selected = 1 EndIf If MouseDown(1) And PAUSEPHYSICS = 0 If p.selected = 1 p.x = MouseX() p.y = MouseY() EndIf EndIf If p.selected = 1 drawtext2("Frozen: " + p.frozen,100,15,1) drawtext2("p.x : " + p.x,100,30,1) drawtext2("p.y : " + p.y,100,45,1) drawtext2("p.vx : " + p.vx,100,60,1) drawtext2("p.vy : " + p.vy,100,75,1) drawtext2("p.mass: " + p.mass,100,90,1) drawtext2("Gravity X add: " + p.gravityx,100,120,1) drawtext2("Gravity Y add: " + p.gravityy,100,135,1) SetColor(255,0,0) Else SetColor(255,255,255) EndIf If p.frozen = 1 SetColor(0,128,255) EndIf UpdatePoint(p) DrawOval(p.x-3,p.y-3,6,6) Next SetColor(0,255,0) For Local l:link = EachIn linklist UpdateLink(l) If l.kind = 2 SetColor(0,128,255) Else SetColor(255,100,0) DrawLine(l.p1.x,l.p1.y,l.p2.x,l.p2.y) Next CollisionDetection() Flip Wend End Function DrawHUD() SetColor(80,80,80) DrawText2(RSet("Outbreak Physics Engine",25),475,15,2) DrawText2(RSet("Blain Rinehart",25),475,40,2) DrawText2(RSet("Nullium 2008",25),475,55,2) SetColor(100,100,100) DrawText2("Physics paused (spacebar): " + PAUSEPHYSICS,700,15,1) DrawText2("Gravity X/Y: " + Int (GRAVITYX * 100) + ", " + Int (GRAVITYY * 100),700,40,1) DrawText2("Wind X/Y: " + Int (WINDX * 100) + ", " + Int (WINDY * 100),700,55,1) DrawText2("Total points: " + CountList(pointlist),700,80,1) DrawText2("Total links: " + CountList(linklist),700,95,1) SetColor(255,0,0) DrawLine(20,0,20,GraphicsHeight() - 20) DrawLine(20,GraphicsHeight() - 20,GraphicsWidth() - 20,GraphicsHeight() - 20) DrawLine(GraphicsWidth() - 20,0,GraphicsWidth() - 20,GraphicsHeight() - 20) End Function Function DrawText2(s:String,x%,y%,col%) SetColor(0,0,0) DrawText(s,x+3,y+3) Select col Case(1) SetColor(100,100,100) Case(2) SetColor(150,50,50) End Select DrawText(s,x,y) SetColor(255,255,255) End Function

Regular K (Posted 2008) [#2]

Function CollisionDetection() For Local l:link = EachIn linklist For Local l2:link = EachIn linklist If l = l2 Then Continue If l.p1 = l2.p1 Or l.p2 = l2.p2 Then Continue If l.p2 = l2.p1 Or l.p1 = l2.p2 Then Continue If LinesCross(l.p1.x, l.p1.y, l.p2.x, l2.p2.y, l2.p1.x, l2.p1.y, l2.p2.x, l2.p2.y) l.p1.vx = -l.p1.vx l.p1.vy = -l.p1.vy l.p2.vx = -l.p2.vx l.p2.vy = -l.p2.vy l2.p1.vx = -l2.p1.vx l2.p1.vy = -l2.p1.vy l2.p2.vx = -l2.p2.vx l2.p2.vy = -l2.p2.vy DrawRect l.p1.x - 2, l.p1.y - 2, 5, 5 EndIf Next Next End Function Well I got a start on some simple collision detection. Doesn't really work, but eh. It's a start.

UnderwoodNullium (Posted 2008) [#3]

Thanks for the code Regular K. I've tried that method before, and even tested the LinesCross() for future and past points, but it wouldn't work when I was trying to have just a single point and 'link'... I might try to re-implement the LinesCross() function again. Here's my original collision detection and 'response', which tested if a point's orientation to each line segment changed since the last frame, and attempts to update it if true... :P ' Collision Detection ' Programmed by Blain Rinehart ' 11/23/08 Function CollisionDetection:Int() Local index% ' the index for the array to link Local orientationnow% ' get the new orientation Local count% = CountList(linklist) ' how many links are there now? Local closestlink:link ' stores the closest link to that point Local closesttestdist# ' temp for testing distances Local index2% For Local p:point = EachIn pointlist If p.orarray.length <> count ' resize the array based on how many links there are (1 for each) p.orarray = p.orarray[..count] EndIf closesttestdist# = 100 ' set pretty far away... just in case index = 0 ' reset the index for the next point For Local l:link = EachIn linklist index = (index + 1) ' add one to the index index2 = index orientationnow = PointCrossesLink(p.x,p.y,l.p1.x,l.p1.y,l.p2.x,l.p2.y) ' what's the orientation now to the link? If p.orarray[index - 1] <> orientationnow ' if it's not equal, that means a point has crossed that link p.orarray[index - 1] = orientationnow If PointInCircleOfLink(p.x,p.y,l.p1.x,l.p1.y,l.p2.x,l.p2.y) ' only check if within segment bounds If Abs(DistToLine(p.oldx,p.oldy,l.p1.oldx,l.p1.oldy,l.p2.oldx,l.p2.oldy)) < closesttestdist# closesttestdist# = Abs(DistToLine(p.oldx,p.oldy,l.p1.oldx,l.p1.oldy,l.p2.oldx,l.p2.oldy)) closestlink = l ' the last one will be the closest link to update with EndIf EndIf EndIf Next If closestlink <> Null ' now on to the harder part... CollisionResponse(p,closestlink,index2) closestlink = Null EndIf Next End Function ' Collision Response ' Programmed by Blain Rinehart ' 5/10/08 Function CollisionResponse:Int(p:point,l:link,index%) Local penetration# = Abs(DistToLine(l.p1.x,l.p1.y,l.p2.x,l.p2.y,p.x,p.y)) Local pointangle# = GetAngle(p.oldx,p.oldy,p.x,p.y) Local normal1# = (GetAngle(l.p1.x,l.p1.y,l.p2.x,l.p2.y) + 90) Mod 360 Local normal2# = (GetAngle(l.p1.x,l.p1.y,l.p2.x,l.p2.y) + 270) Mod 360 Local normal# Local ptestx# = (p.x + Cos(pointangle)) Local ptesty# = (p.y + Sin(pointangle)) Local ntest1x# = (p.x + Cos(normal1)) Local ntest1y# = (p.y + Sin(normal1)) Local ntest2x# = (p.x + Cos(normal2)) Local ntest2y# = (p.y + Sin(normal2)) If (GetDistance(ptestx,ptesty,ntest1x,ntest1y) < GetDistance(ptestx,ptesty,ntest2x,ntest2y)) normal = normal2 Else normal = normal1 EndIf '=========== response now... If l.p1.frozen <> 0 And l.p2.frozen <> 0 ' if the link is frozen... p.x = (p.x + Cos(normal) * penetration) ' update the point p.y = (p.y + Sin(normal) * penetration) p.oldx = p.x p.oldy = p.y + .1 EndIf End Function Thanks again Mr. K...