GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2011-07-15 21:06:14

Rani_sputnik
Member
Registered: 2011-04-24
Posts: 18

Collision detection for verlet physics *** SOLVED THANK YOU XOT ***

Right so all you need to know is this is collision detection for a verlet physics engine. This particular section is for moving particles colliding with moving constraints. I've found code that works on GameDev (Written in C++) and I've translated it into GML. But I must have made a tiny muck up somewhere along the way. I can't see it though, so can someone please have a look over this and let me know what could be going wrong? What should happen is some collisions should be missed, but the vast majority found (They should only be missed when the discriminant is very close to 0, in practical terms it means the particle has crossed the constraint's axis either twice very quickly or once only),

What happens is that bodies collide very often even when they are far away, because of this I have a feeling the problem lies in the variable u (towards the bottom). What this variable should do is cut out any 'collisions' with the infinete axis AB rather than the finite line segment AB, hence why I feel it is the problem, it's the only reason I can think of for the bodies colliding when they aren't even close to one another. I'm afraid that's as specific as I can be, I haven't found any patterns as yet. Anyways here's the code

Spoiler
Expand// Source code that works
    Vector AP = Pold - Aold;
    Vector AB = Bold - Aold;
    Vector Vp = Pnew - Pold;
    Vector Va = Anew - Aold;
    Vector Vb = Bnew - Bold;
    Vector Vap = Vp - Va;
    Vector Vab = Vb - Va;
Expand// My code
var APx,APy,ABx,ABy;
APx  = Poldx - Aoldx
APy  = Poldy - Aoldy
ABx  = Boldx - Aoldx
ABy  = Boldy - Aoldy
var Vpx,Vpy,Vax,Vay,Vbx,Vby;
Vpx  = Pnewx - Poldx
Vpy  = Pnewy - Poldy
Vax  = Anewx - Aoldx
Vay  = Anewy - Aoldy
Vbx  = Bnewx - Boldx
Vby  = Bnewy - Boldy
var Vapx,Vapy,Vabx,Vaby;
Vapx = Vpx - Vax
Vapy = Vpy - Vay
Vabx = Vbx - Vax
Vaby = Vby - Vay
Spoiler
Expand// Source Code
    double a = (Vap.x * Vab.y) - (Vap.y * Vab.x);
    double b = (AP.x*Vab.y + AB.y*Vap.x) - (AP.y*Vab.x + AB.x*Vap.y);
    double c = (AP.x * AB.y) - (AP.y * AB.x);
    double d = (b*b - 4*a*c);
	double t;

	
	if (fabs(a) < 0.00001f)
		return ParticleSegmentCollide(Pold, Pnew, Aold, Bold);

    if(d < 0.0f) 
        return false;
Expand// My code
// Quadratic formula
var qa,qb,qc,qd;
qa = (Vapx * Vaby) - (Vapy * Vabx)
qb = (APx*Vaby + ABy*Vapx) - (APy*Vabx + ABx*Vapy)
qc = (APx * ABy) - (APy * ABx)
qd = (qb*qb - 4*qa*qc)

// For now this just returns false - should be a script
if abs(qa) < 0.00001 then return false
if qd < 0 then return false
Spoiler
Expand// Source code

    double t0 = (-b - sqrt(d)) / (2.0f * a);
    double t1 = (-b + sqrt(d)) / (2.0f * a);
    double tmin = (t1 < t0)? t1 : t0;
    double tmax = (t1 > t0)? t1 : t0;
    
    if(tmin > 1.0f || tmax < 0.0f) 
        return false;

    double  tcoll = (tmin < 0.0f)? tmax : tmin;

    if(tcoll > 1.0f || tcoll < 0.0f) 
        return false;
Expand// My code
// Finding the two solutions
var t0,t1,tmin,tmax,tcoll;
t0 = (-qb - sqrt(qd)) / (2 * qa)
t1 = (-qb + sqrt(qd)) / (2 * qa)
tmin = min(t0,t1)
tmax = max(t0,t1)

if tmin > 1 or tmax < 0 then return false
if tmin < 0 tcoll = tmax else tcoll = tmin
if tcoll > 1 or tcoll < 0 then return false
Spoiler
Expand// Source code
    Vector Pcoll = Pold + Vp * tcoll;
    Vector Acoll = Aold + Va * tcoll;
    Vector Bcoll = Bold + Vb * tcoll;
    
    AP = Pcoll - Acoll;
    AB = Bcoll - Acoll;

    double u = (AP * AB) / (AB * AB); // '*' = dot product!
   
    if (u < 0.0f || u > 1.0f) 
        return false;
Expand// My code
var Pcollx,Pcolly,Acollx,Acolly,Bcollx,Bcolly;
Pcollx = Poldx + Vpx * tcoll
Pcolly = Poldy + Vpy * tcoll
Acollx = Aoldx + Vax * tcoll
Acolly = Aoldy + Vay * tcoll
Bcollx = Boldx + Vbx * tcoll
Bcolly = Boldy + Vby * tcoll

APx = Pcollx - Acollx
APy = Pcolly - Acolly
ABx = Bcollx - Acollx
ABy = Bcolly - Acolly

var u;
// Is the point on the finite line
u = dot_product(APx,APy,ABx,ABy) / dot_product(ABx,ABy,ABx,ABy)
if u<0 or u>1 then return false

Just a heads up I can read C++ okay, I can't code it, so please speak BASIC to me (Ahahahahah get it?) Man I'm lame, thank you so much to anyone who looks this over.

I'm not fussed about people getting the source for this because so far I haven't done anything that original, so here we go...
Here's the link to what I've done
Also this is where I got the C++ code from,
I downloaded the first example that Papalazaru gave, (The working one).

With my example, yes the drawing is messed up I did it to check the engine checks each particle and constraint, and when it detects a collision is found it'll call keyboard_wait() so if it freezes - it's found a collision but you can keep it going but pressing any button.

Last edited by Rani_sputnik (2011-07-16 04:52:46)

Offline

#2 2011-07-16 01:02:35

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: Collision detection for verlet physics *** SOLVED THANK YOU XOT ***

Expandvar u;
// Is the point on the finite line
u = dot_product(APx,APy,ABx,ABy) / dot_product(ABx,ABy,ABx,ABy)
if u<0 or u>1 then return false

The problem appears to be with your use of Game Maker's built-in dot_product() function. It normalizes the supplied vectors, which your code doesn't expect. To fix the problem you can simply create your own dot_product() script to override Game Maker's built-in function.

Expand//  dot_product(x1,y1,x2,y2)
{
    return argument0 * argument2 + argument1 * argument3;
}

Some people complained loudly about this feature of dot_product() when it was added to GM, and here you have a perfect example of it causing difficulty.


Abusing forum power since 1986.

Offline

#3 2011-07-16 04:50:35

Rani_sputnik
Member
Registered: 2011-04-24
Posts: 18

Re: Collision detection for verlet physics *** SOLVED THANK YOU XOT ***

XOT I LOVE YOU! That has been giving me hell! For so long! I might cry... I'll do it... I'll cry... Thank you so much! smile smile smile

Offline

#4 2011-07-16 05:44:14

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: Collision detection for verlet physics *** SOLVED THANK YOU XOT ***

It pays to be skeptical of new GM features. wink

I built my own Verlet integrator last year, very similar to this one. I got about as far as you. My collision detection method was so slow, I didn't even bother working out collision response. Sort of derailed the game it was intended for. This detector you are using seems pretty fast. Maybe I can learn something from it.


Abusing forum power since 1986.

Offline

#5 2011-07-16 06:08:33

Rani_sputnik
Member
Registered: 2011-04-24
Posts: 18

Re: Collision detection for verlet physics *** SOLVED THANK YOU XOT ***

One thing I don't think I pointed out enough with this is that all credit for the collision detection is owed to papalazaru of gamedev.net. I am not confident that it's the best technique, but I just wanted to get something working haha. Why rewrite something that already exists right?

EDIT: Ditto  \/ \/ \/

Last edited by Rani_sputnik (2011-07-17 02:24:15)

Offline

#6 2011-07-16 11:53:19

xot
Administrator
Registered: 2007-08-18
Posts: 1,239

Re: Collision detection for verlet physics *** SOLVED THANK YOU XOT ***

I suppose I should have mentioned that I used the widely cited Thomas Jakobsen article as the basis for my Verlet integrator.


Abusing forum power since 1986.

Offline

Board footer

Powered by FluxBB