New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Prevent object passing through walls / tunneling (implement CCD) #5

Open
liabru opened this Issue Feb 27, 2014 · 54 comments

Comments

Projects
None yet
@liabru
Owner

liabru commented Feb 27, 2014

Currently there is no continuous collision detection (CCD), so fast moving objects pass through other objects.

A description of the problem:
http://www.stencyl.com/help/view/continuous-collision-detection

Solution is to implement a CCD algorithm.

One I'm currently considering is speculative contacts, see here and here.

"we compute the closest distance d between the two objects; the idea is that we want to remove exactly the right amount of velocity from A such that it will be exactly in touching contact with B on the next frame"

I've already implemented the code that extends the AABB based on object velocity.

The next part is to find the closest distance between two objects and remove the required velocity.

@abataille

This comment has been minimized.

Show comment
Hide comment
@abataille

abataille Mar 14, 2014

I just added a poor man's solution to the tunneling problem. It detects if a body is outside the world bounds and then reverses the velocity and translates the body back. I tried via an event. Here is the code. Please have a look.
Events.on(_engine, 'afterTick afterRender', function (event)
{
// avoid tunneling
for (var i = 0; i < _world.bodies.length; i++)
{
var bodyA = _world.bodies[i];
if (bodyA.isStatic || bodyA.isSleeping)
{
continue;
}
var outside = false;
var adjustX = 0;
var adjustY = 0;
var epsilon = 0.01;
if (bodyA.bounds.min.y + epsilon >= _world.bounds.max.y)
{ // bottom
adjustY = Math.abs(bodyA.bounds.max.y - _world.bounds.max.y);
Body.translate(bodyA, {
x: 0,
y: -adjustY
});
bodyA.velocity.y = -1.0;
outside = true;
}
if (bodyA.bounds.max.x - epsilon<= _world.bounds.min.x)
{ // left
bodyA.velocity.x = 1.0;
adjustX = Math.abs(bodyA.bounds.min.x - _world.bounds.min.x);
Body.translate(bodyA, {
x: adjustX,
y: 0
});
outside = true;
}
if (bodyA.bounds.max.y - epsilon <= _world.bounds.min.y)
{ // Top
adjustY = Math.abs(bodyA.bounds.min.y - _world.bounds.min.y);
Body.translate(bodyA, {
x: 0,
y: adjustY // since body.bounds.min.y is negative
});
bodyA.velocity.y = 1.0;
outside = true;
}
if (bodyA.bounds.min.x + epsilon > _world.bounds.max.x)
{ // right
bodyA.velocity.x = -1.0;adjustX = Math.abs(bodyA.bounds.max.x - _world.bounds.max.x);
Body.translate(bodyA, {
x: -adjustX,
y: 0
});
outside = true;
}
if (outside)
{
Bounds.update(bodyA.bounds, bodyA.vertices, bodyA.velocity);
}
}
});

abataille commented Mar 14, 2014

I just added a poor man's solution to the tunneling problem. It detects if a body is outside the world bounds and then reverses the velocity and translates the body back. I tried via an event. Here is the code. Please have a look.
Events.on(_engine, 'afterTick afterRender', function (event)
{
// avoid tunneling
for (var i = 0; i < _world.bodies.length; i++)
{
var bodyA = _world.bodies[i];
if (bodyA.isStatic || bodyA.isSleeping)
{
continue;
}
var outside = false;
var adjustX = 0;
var adjustY = 0;
var epsilon = 0.01;
if (bodyA.bounds.min.y + epsilon >= _world.bounds.max.y)
{ // bottom
adjustY = Math.abs(bodyA.bounds.max.y - _world.bounds.max.y);
Body.translate(bodyA, {
x: 0,
y: -adjustY
});
bodyA.velocity.y = -1.0;
outside = true;
}
if (bodyA.bounds.max.x - epsilon<= _world.bounds.min.x)
{ // left
bodyA.velocity.x = 1.0;
adjustX = Math.abs(bodyA.bounds.min.x - _world.bounds.min.x);
Body.translate(bodyA, {
x: adjustX,
y: 0
});
outside = true;
}
if (bodyA.bounds.max.y - epsilon <= _world.bounds.min.y)
{ // Top
adjustY = Math.abs(bodyA.bounds.min.y - _world.bounds.min.y);
Body.translate(bodyA, {
x: 0,
y: adjustY // since body.bounds.min.y is negative
});
bodyA.velocity.y = 1.0;
outside = true;
}
if (bodyA.bounds.min.x + epsilon > _world.bounds.max.x)
{ // right
bodyA.velocity.x = -1.0;adjustX = Math.abs(bodyA.bounds.max.x - _world.bounds.max.x);
Body.translate(bodyA, {
x: -adjustX,
y: 0
});
outside = true;
}
if (outside)
{
Bounds.update(bodyA.bounds, bodyA.vertices, bodyA.velocity);
}
}
});

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru Mar 14, 2014

Owner

Thanks for sharing, but does this work?

I ask because body.velocity is technically read only - the engine uses position Verlet meaning velocity is implicit to changes in position (see here)!

So what you need to do instead is simply set the body position to be inside the world, the engine will handle the velocity change for you.

Either way, as you say this is indeed a poor mans solution, as it's only a solution to going outside of the world bounds.

BTW note the event name is not 'afterTick afterRender', those are two separate events (that happen to relate to the same point in the step). You only need to use one here (e.g. it's like jQuery's events), otherwise this will run twice per step.

What we really need implementing is speculative contacts. I'll get round to it at some point hopefully!

Owner

liabru commented Mar 14, 2014

Thanks for sharing, but does this work?

I ask because body.velocity is technically read only - the engine uses position Verlet meaning velocity is implicit to changes in position (see here)!

So what you need to do instead is simply set the body position to be inside the world, the engine will handle the velocity change for you.

Either way, as you say this is indeed a poor mans solution, as it's only a solution to going outside of the world bounds.

BTW note the event name is not 'afterTick afterRender', those are two separate events (that happen to relate to the same point in the step). You only need to use one here (e.g. it's like jQuery's events), otherwise this will run twice per step.

What we really need implementing is speculative contacts. I'll get round to it at some point hopefully!

@abataille

This comment has been minimized.

Show comment
Hide comment
@abataille

abataille Mar 14, 2014

You are right. velocity change is not necessary. Just the translation does it.
I know, it does not work for inside objects, but at least it leaves the bodies at the table.

abataille commented Mar 14, 2014

You are right. velocity change is not necessary. Just the translation does it.
I know, it does not work for inside objects, but at least it leaves the bodies at the table.

@liabru liabru self-assigned this Apr 22, 2014

@liabru liabru removed the bug label May 6, 2014

@shakiba

This comment has been minimized.

Show comment
Hide comment
@shakiba

shakiba commented May 11, 2014

+1

@liabru liabru removed their assignment May 11, 2014

@Danetag

This comment has been minimized.

Show comment
Hide comment
@Danetag

Danetag Nov 11, 2014

Still experiencing this issue, I guess it's still unsolved?

Danetag commented Nov 11, 2014

Still experiencing this issue, I guess it's still unsolved?

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru Nov 11, 2014

Owner

It's a pretty big feature to implement really, I've played around with some ideas for this but I've not yet got much working. It's a tricky one.

I'm considering implementing a simple version for now (ray casting) that should prevent some of the more obvious tunneling cases.

Owner

liabru commented Nov 11, 2014

It's a pretty big feature to implement really, I've played around with some ideas for this but I've not yet got much working. It's a tricky one.

I'm considering implementing a simple version for now (ray casting) that should prevent some of the more obvious tunneling cases.

@Danetag

This comment has been minimized.

Show comment
Hide comment
@Danetag

Danetag Nov 12, 2014

Ok I totally understand, thank you so much for all your hard work :)

Danetag commented Nov 12, 2014

Ok I totally understand, thank you so much for all your hard work :)

@anjiro

This comment has been minimized.

Show comment
Hide comment
@anjiro

anjiro Feb 16, 2015

Note that increasing engine.timing.timeScale can cause this issue as well.

anjiro commented Feb 16, 2015

Note that increasing engine.timing.timeScale can cause this issue as well.

@Sheepzez

This comment has been minimized.

Show comment
Hide comment
@Sheepzez

Sheepzez Nov 27, 2015

Still having this issue using latest master as of e698b6b. I have somewhat mitigated it by halving the engine.timing.timeScale value. Not sure of the repercussions of this, but works for my simple use case.

Sheepzez commented Nov 27, 2015

Still having this issue using latest master as of e698b6b. I have somewhat mitigated it by halving the engine.timing.timeScale value. Not sure of the repercussions of this, but works for my simple use case.

@liabru liabru referenced this issue Jan 9, 2016

Closed

bounds issue #189

@homerjam

This comment has been minimized.

Show comment
Hide comment
@homerjam

homerjam commented Jan 15, 2016

+1

@slaskis

This comment has been minimized.

Show comment
Hide comment
@slaskis

slaskis Jan 28, 2016

@liabru for https://cubeslam.com I ported a few SAT implementations to javascript but finally fell for this brilliant SAT implementation and converted it to be a part of this library.

It's very similar to your implementation but will also project ahead based on the polygons relative velocity to see if it will intersect and then returns a minimum translation vector which may be applied to keep two polygons from colliding if desired.

I found it to be quite stable and fast even in the pace of cube slam. Unfortunately google code just shut down so the implementation code for it is not viewable online anymore. But you can download it and have a look at the narrowphase implementation in lib/sim/physics.js#L74.

slaskis commented Jan 28, 2016

@liabru for https://cubeslam.com I ported a few SAT implementations to javascript but finally fell for this brilliant SAT implementation and converted it to be a part of this library.

It's very similar to your implementation but will also project ahead based on the polygons relative velocity to see if it will intersect and then returns a minimum translation vector which may be applied to keep two polygons from colliding if desired.

I found it to be quite stable and fast even in the pace of cube slam. Unfortunately google code just shut down so the implementation code for it is not viewable online anymore. But you can download it and have a look at the narrowphase implementation in lib/sim/physics.js#L74.

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru Jan 28, 2016

Owner

@slaskis I remember playing with cubeslam, awesome project!

Thanks for the info. I actually played with using SAT for continuous collisions but I couldn't get it working at the time, so I'll take a look at your implementation for some pointers.

Owner

liabru commented Jan 28, 2016

@slaskis I remember playing with cubeslam, awesome project!

Thanks for the info. I actually played with using SAT for continuous collisions but I couldn't get it working at the time, so I'll take a look at your implementation for some pointers.

@slaskis

This comment has been minimized.

Show comment
Hide comment
@slaskis

slaskis Jan 28, 2016

@liabru thanks! I hope it can help you get this sweet library even better

slaskis commented Jan 28, 2016

@liabru thanks! I hope it can help you get this sweet library even better

@dcrockwell

This comment has been minimized.

Show comment
Hide comment
@dcrockwell

dcrockwell Feb 7, 2016

+1 Seeing lots of tunneling with bodies passing through svg generated bodies.

dcrockwell commented Feb 7, 2016

+1 Seeing lots of tunneling with bodies passing through svg generated bodies.

@ser10us

This comment has been minimized.

Show comment
Hide comment
@ser10us

ser10us Mar 28, 2016

Is there any workaround for this issue? The proposal from @abataille doesn't work for me.

ser10us commented Mar 28, 2016

Is there any workaround for this issue? The proposal from @abataille doesn't work for me.

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru Mar 28, 2016

Owner

Not yet, I have a work in progress implementation. Depending on your needs, you could try doing some ray casts between updates (e.g. between centroids of bodies moving over a certain speed), if there's an intersection then move the body back. This won't be perfect but might help for some cases.

Owner

liabru commented Mar 28, 2016

Not yet, I have a work in progress implementation. Depending on your needs, you could try doing some ray casts between updates (e.g. between centroids of bodies moving over a certain speed), if there's an intersection then move the body back. This won't be perfect but might help for some cases.

@rikuw rikuw referenced this issue Apr 4, 2016

Open

pallon nopeus #4

@slaskis

This comment has been minimized.

Show comment
Hide comment
@slaskis

slaskis May 11, 2016

@liabru would you mind sharing your in progress implementation as a PR or branch? I'm curious what it looks like and maybe we can help out?

slaskis commented May 11, 2016

@liabru would you mind sharing your in progress implementation as a PR or branch? I'm curious what it looks like and maybe we can help out?

@IceReaper

This comment has been minimized.

Show comment
Hide comment
@IceReaper

IceReaper May 14, 2016

Will this also allow collision with simple lines? To be more specific imagine a force field, which limits you to not pass from both sides but has no thickness.
Which comes to the second idea of force fields coliding only in one direction, so you might move into the forcefield, but not leave it again.
Imagine it as a simple polygon which has only a one-sided face, you walk through it as you cannot see it. If you try to move back you see a wall there.
Used that feature to build some nasty tricky puzzles in prey a while ago, where the back-side was a portal placed inside a door. Which results in a door bringing you from a to b, but the same door back brings you from b to c :D

IceReaper commented May 14, 2016

Will this also allow collision with simple lines? To be more specific imagine a force field, which limits you to not pass from both sides but has no thickness.
Which comes to the second idea of force fields coliding only in one direction, so you might move into the forcefield, but not leave it again.
Imagine it as a simple polygon which has only a one-sided face, you walk through it as you cannot see it. If you try to move back you see a wall there.
Used that feature to build some nasty tricky puzzles in prey a while ago, where the back-side was a portal placed inside a door. Which results in a door bringing you from a to b, but the same door back brings you from b to c :D

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru May 14, 2016

Owner

@slaskis it is in a very unstable state, I was trying a different approach than using SAT. But it looks like it's not going to be viable, so I'm going to try implement it again in the same way you did. Looking at your code, the key part seems to be these lines right?

Owner

liabru commented May 14, 2016

@slaskis it is in a very unstable state, I was trying a different approach than using SAT. But it looks like it's not going to be viable, so I'm going to try implement it again in the same way you did. Looking at your code, the key part seems to be these lines right?

@staff0rd

This comment has been minimized.

Show comment
Hide comment
@staff0rd

staff0rd Nov 8, 2016

Either way, the CCD code will get merged soon after I finish work on #213 so you won't need to after that.

Is it time? :)

staff0rd commented Nov 8, 2016

Either way, the CCD code will get merged soon after I finish work on #213 so you won't need to after that.

Is it time? :)

@wmike1987

This comment has been minimized.

Show comment
Hide comment
@wmike1987

wmike1987 Feb 3, 2017

Any update on the ccd merge? I see it has a release-candidate label, that sounds promising!

wmike1987 commented Feb 3, 2017

Any update on the ccd merge? I see it has a release-candidate label, that sounds promising!

@liabru liabru referenced this issue Mar 12, 2017

Closed

merge ccd #389

@Buri

This comment has been minimized.

Show comment
Hide comment
@Buri

Buri Jul 2, 2017

Any updates on this issue?

Buri commented Jul 2, 2017

Any updates on this issue?

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru Jul 3, 2017

Owner

Unfortunately there were some issues with this initial approach after a bunch of testing. I've got a new approach I'm working on though which should be simpler and more performant too.

Owner

liabru commented Jul 3, 2017

Unfortunately there were some issues with this initial approach after a bunch of testing. I've got a new approach I'm working on though which should be simpler and more performant too.

@maltenuhn

This comment has been minimized.

Show comment
Hide comment
@maltenuhn

maltenuhn Aug 9, 2017

@liabru can the new approach do with help? Any specific things that'd push it along?

maltenuhn commented Aug 9, 2017

@liabru can the new approach do with help? Any specific things that'd push it along?

@xupertheo

This comment has been minimized.

Show comment
Hide comment
@xupertheo

xupertheo Aug 15, 2017

I have an idea. The object falls through the wall because the hitbox is too small. If the hitbox was bigger it would fix it. The size should be the size to the object + the velocity in that direction. If the object fall down the hitbox should be the size of the object + the y-velocity downwards.

xupertheo commented Aug 15, 2017

I have an idea. The object falls through the wall because the hitbox is too small. If the hitbox was bigger it would fix it. The size should be the size to the object + the velocity in that direction. If the object fall down the hitbox should be the size of the object + the y-velocity downwards.

@spiderworm

This comment has been minimized.

Show comment
Hide comment
@spiderworm

spiderworm Dec 5, 2017

@liabru Any update on this? It looks like you abandoned the CCD branch and maybe are implementing your new approach in a different branch? Perhaps I can help code it up. I'm trying to make a game for mobile and this is the most performant 2D physics JS library I've found so far. Just need to get this bit fixed.

spiderworm commented Dec 5, 2017

@liabru Any update on this? It looks like you abandoned the CCD branch and maybe are implementing your new approach in a different branch? Perhaps I can help code it up. I'm trying to make a game for mobile and this is the most performant 2D physics JS library I've found so far. Just need to get this bit fixed.

@zxb5102

This comment has been minimized.

Show comment
Hide comment
@zxb5102

zxb5102 Dec 6, 2017

Does that solve the problem now?

zxb5102 commented Dec 6, 2017

Does that solve the problem now?

@zxb5102

This comment has been minimized.

Show comment
Hide comment
@zxb5102

zxb5102 Dec 6, 2017

I have a similar problem with my project

zxb5102 commented Dec 6, 2017

I have a similar problem with my project

@liabru

This comment has been minimized.

Show comment
Hide comment
@liabru

liabru Dec 6, 2017

Owner

I have a partially working solution in a branch I've not yet pushed, but it still has some major issues. It's a tricky one. Maybe I should push it if other people are interested in helping?

Owner

liabru commented Dec 6, 2017

I have a partially working solution in a branch I've not yet pushed, but it still has some major issues. It's a tricky one. Maybe I should push it if other people are interested in helping?

@spiderworm

This comment has been minimized.

Show comment
Hide comment
@spiderworm

spiderworm Dec 6, 2017

@liabru Sounds like that might be a good idea? Along with a brief description of your approach, and of the problems that still need solving might be helpful.

spiderworm commented Dec 6, 2017

@liabru Sounds like that might be a good idea? Along with a brief description of your approach, and of the problems that still need solving might be helpful.

@billylo1

This comment has been minimized.

Show comment
Hide comment
@billylo1

billylo1 Dec 14, 2017

In my use case, I managed to work around it by listening to collisionEnd event, check if the bodies were forced out of the viewport. If so, re-position that body to bring it back. (this is good enough for my use case because I only need to make sure no objects can get thrown out of the bounding rectangles.

Hope this helps.

billylo1 commented Dec 14, 2017

In my use case, I managed to work around it by listening to collisionEnd event, check if the bodies were forced out of the viewport. If so, re-position that body to bring it back. (this is good enough for my use case because I only need to make sure no objects can get thrown out of the bounding rectangles.

Hope this helps.

@qwertyquerty

This comment has been minimized.

Show comment
Hide comment
@qwertyquerty

qwertyquerty Apr 4, 2018

Is this ever going to be continued?

qwertyquerty commented Apr 4, 2018

Is this ever going to be continued?

@pixelscripter

This comment has been minimized.

Show comment
Hide comment
@pixelscripter

pixelscripter Apr 10, 2018

I was also wondering about that @qwertyquerty. Any progress on implementing CCD @liabru ?

pixelscripter commented Apr 10, 2018

I was also wondering about that @qwertyquerty. Any progress on implementing CCD @liabru ?

@soulofmischief

This comment has been minimized.

Show comment
Hide comment
@soulofmischief

soulofmischief Apr 23, 2018

Also interested in seeing this feature.

soulofmischief commented Apr 23, 2018

Also interested in seeing this feature.

@whaqzhzd

This comment has been minimized.

Show comment
Hide comment
@whaqzhzd

whaqzhzd May 16, 2018

Any progress on implementing CCD

whaqzhzd commented May 16, 2018

Any progress on implementing CCD

@cheneyweb

This comment has been minimized.

Show comment
Hide comment
@cheneyweb

cheneyweb Jun 20, 2018

object passing through walls,I met this problem, too.
I'm really looking forward to the problem being solved

cheneyweb commented Jun 20, 2018

object passing through walls,I met this problem, too.
I'm really looking forward to the problem being solved

@7ammer

This comment has been minimized.

Show comment
Hide comment
@7ammer

7ammer Jul 2, 2018

^^^ Me too

7ammer commented Jul 2, 2018

^^^ Me too

@yungzhu

This comment has been minimized.

Show comment
Hide comment
@yungzhu

yungzhu Aug 17, 2018

Is there any way?

yungzhu commented Aug 17, 2018

Is there any way?

@fabienjuif

This comment has been minimized.

Show comment
Hide comment
@fabienjuif

fabienjuif Aug 18, 2018

EDIT 2: https://gist.github.com/fabienjuif/a7d9fc3e34e23f6000bcfc185dc0e341

EDIT: I fall into FPS issues, the engine run objects faster on 60FPS than on 30FPS. So don't try that at home :(


I did this trick for now:

  // engine
  // - run the engine several times, so we have the feeling the game is fast
  // - also, this avoid collision detecting issue since CCD is not implemented yet in matter-js
  let lastLoop = Date.now()
  for (let i = 0; i < RERUN; ++i) {
    Engine.update(engine, i === 0 ? delta : (Date.now() - lastLoop))
    lastLoop = Date.now()
  }

And divide all my velocities by the RERUN amount :)
It works, but I assume this is less performant

fabienjuif commented Aug 18, 2018

EDIT 2: https://gist.github.com/fabienjuif/a7d9fc3e34e23f6000bcfc185dc0e341

EDIT: I fall into FPS issues, the engine run objects faster on 60FPS than on 30FPS. So don't try that at home :(


I did this trick for now:

  // engine
  // - run the engine several times, so we have the feeling the game is fast
  // - also, this avoid collision detecting issue since CCD is not implemented yet in matter-js
  let lastLoop = Date.now()
  for (let i = 0; i < RERUN; ++i) {
    Engine.update(engine, i === 0 ? delta : (Date.now() - lastLoop))
    lastLoop = Date.now()
  }

And divide all my velocities by the RERUN amount :)
It works, but I assume this is less performant

@osfa

This comment has been minimized.

Show comment
Hide comment
@osfa

osfa commented Oct 4, 2018

+1

@maltenuhn

This comment has been minimized.

Show comment
Hide comment
@maltenuhn

maltenuhn Oct 4, 2018

maltenuhn commented Oct 4, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment