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

Automatic collision detection and response #574

Open
obiot opened this Issue Sep 28, 2014 · 13 comments

Comments

3 participants
@obiot
Member

obiot commented Sep 28, 2014

as discussed here :
d5dc2aa

Implement a new collision method that will perform a complete collision check with responses and callbacks against every entity in a single call, and that will be performed by melonJS once per frame.

This would replace the check method entirely, and user code would not be responsible for, nor care anymore on how to perform collision detection.

A one-shot collision check will also be faster, as it will entirely eliminate duplicate object-pair collision checks. See also this thread: https://groups.google.com/d/msg/melonjs/7mIUAI1U6K8/FTz9Ui7qQgEJ

@obiot obiot added this to the 1.2.0 milestone Sep 28, 2014

@obiot obiot changed the title from Automatic collision check to Automatic collision detection and response Sep 28, 2014

@parasyte parasyte modified the milestones: 1.2.0, 1.3.0 Oct 22, 2014

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 23, 2014

Member

We discussed on gitter the possibility of moving me.collision.check to this.body.update. I'm ok with it, but we need to be careful about double-collisions. Take a look at the tutorial for an example of why this is bad: http://melonjs.github.io/tutorial-platformer/tutorial_step8/index.html

Both entities (player and enemy) are calling me.collision.check, and both have their own collision handler. This means both collision handlers are called twice every frame (once by each me.collision.check call).

IMHO we can fix this easily by removing the object from the QuadTree at the end of me.collision.check. That will prevent multiple collisions against that object per frame. It's safe because we already guarantee that all colliding objects have already been tested, called back, and responded.

Member

parasyte commented Dec 23, 2014

We discussed on gitter the possibility of moving me.collision.check to this.body.update. I'm ok with it, but we need to be careful about double-collisions. Take a look at the tutorial for an example of why this is bad: http://melonjs.github.io/tutorial-platformer/tutorial_step8/index.html

Both entities (player and enemy) are calling me.collision.check, and both have their own collision handler. This means both collision handlers are called twice every frame (once by each me.collision.check call).

IMHO we can fix this easily by removing the object from the QuadTree at the end of me.collision.check. That will prevent multiple collisions against that object per frame. It's safe because we already guarantee that all colliding objects have already been tested, called back, and responded.

@agmcleod

This comment has been minimized.

Show comment
Hide comment
@agmcleod

agmcleod Dec 23, 2014

Member

Any concern with bodies that don't have any collision? Such as using body.update() to move an entity based on velocity?

Member

agmcleod commented Dec 23, 2014

Any concern with bodies that don't have any collision? Such as using body.update() to move an entity based on velocity?

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 23, 2014

Member

Those don't exist. ;) A body without a shape is only wasting memory and CPU. Use a me.Sprite instead.

Member

parasyte commented Dec 23, 2014

Those don't exist. ;) A body without a shape is only wasting memory and CPU. Use a me.Sprite instead.

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 23, 2014

Member

I'm starting to think we may need to run the collision handlers pre-resolve. Right now the collision handlers are called independent of one another, with response handling between them. This makes it hard for the collision handlers to work together. There's a description of the phenomenon (and a workaround) in this thread: https://groups.google.com/d/msg/melonjs/lAS974m-IxU/uqWm7HdoAVYJ

The collision response and callbacks code might have to change to something like this:

// execute the onCollision callback
var respondA = objA.onCollision(response, objB);
var respondB = objB.onCollision(response, objA);

if (respondA !== false) {
    objA.body.respondToCollision(response);
}
if (respondB !== false) {
    objB.body.respondToCollision(response);
}

And optionally (though I can't think of a use for it at the moment) add a new post-resolve callback just after that. To allow for further processing immediately after the entities are no longer colliding (which may not be the case if both do not respond to the collision).

Member

parasyte commented Dec 23, 2014

I'm starting to think we may need to run the collision handlers pre-resolve. Right now the collision handlers are called independent of one another, with response handling between them. This makes it hard for the collision handlers to work together. There's a description of the phenomenon (and a workaround) in this thread: https://groups.google.com/d/msg/melonjs/lAS974m-IxU/uqWm7HdoAVYJ

The collision response and callbacks code might have to change to something like this:

// execute the onCollision callback
var respondA = objA.onCollision(response, objB);
var respondB = objB.onCollision(response, objA);

if (respondA !== false) {
    objA.body.respondToCollision(response);
}
if (respondB !== false) {
    objB.body.respondToCollision(response);
}

And optionally (though I can't think of a use for it at the moment) add a new post-resolve callback just after that. To allow for further processing immediately after the entities are no longer colliding (which may not be the case if both do not respond to the collision).

@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Dec 24, 2014

Member

if you remember i also propose a while ago to add 3 different handlers, one "pre-collision", the collision one, and a "post-collision" one (i think i even added them at some point), so on my side i'm still ok to do so :)

removing the object from the quadtree after collision might be a good idea, but it means that we totally prevent anyone to do anything else with it (e.g. pathfinding, pointer event).

and about entiiites/bodies without shapes I agree with Jason, a me.Sprite object should be used instead.

Member

obiot commented Dec 24, 2014

if you remember i also propose a while ago to add 3 different handlers, one "pre-collision", the collision one, and a "post-collision" one (i think i even added them at some point), so on my side i'm still ok to do so :)

removing the object from the quadtree after collision might be a good idea, but it means that we totally prevent anyone to do anything else with it (e.g. pathfinding, pointer event).

and about entiiites/bodies without shapes I agree with Jason, a me.Sprite object should be used instead.

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 24, 2014

Member

Yep, I just don't know how useful the multi-phase collision handlers are. I say we try to keep it simple for now, and add things as needed. The pre-solve phase is probably good enough I think.

Member

parasyte commented Dec 24, 2014

Yep, I just don't know how useful the multi-phase collision handlers are. I say we try to keep it simple for now, and add things as needed. The pre-solve phase is probably good enough I think.

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 24, 2014

Member

That's a good point against removing the item from the QuadTree. Two other options are:

  1. Add flags to prevent multiple collision checks against an object. (See the thread linked above.)
  2. Use a second QuadTree for general purpose lookups.
Member

parasyte commented Dec 24, 2014

That's a good point against removing the item from the QuadTree. Two other options are:

  1. Add flags to prevent multiple collision checks against an object. (See the thread linked above.)
  2. Use a second QuadTree for general purpose lookups.
@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Dec 24, 2014

Member
  1. create a temporary hash of of object collision check already done ? that could also be done within the following function :
    https://github.com/melonjs/melonJS/blob/master/src/physics/collision.js#L420-L426
Member

obiot commented Dec 24, 2014

  1. create a temporary hash of of object collision check already done ? that could also be done within the following function :
    https://github.com/melonjs/melonJS/blob/master/src/physics/collision.js#L420-L426
@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 24, 2014

Member

Yep, as long as the hash is cleared every frame, at the same time the QuadTree is rebuilt.

// Reset hash
api.debounce = {};

// Check if object is in hash
if (!(obj in abi.debounce)) {
    // Add object to hash
    api.debounce[obj] = true;
}
Member

parasyte commented Dec 24, 2014

Yep, as long as the hash is cleared every frame, at the same time the QuadTree is rebuilt.

// Reset hash
api.debounce = {};

// Check if object is in hash
if (!(obj in abi.debounce)) {
    // Add object to hash
    api.debounce[obj] = true;
}
@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Dec 24, 2014

Member

I would rather add the object GUID in the hash to avoid storing an additional object reference somewhere else. Else we will need to also consider this one when removing child items from a container :P:P:P

Member

obiot commented Dec 24, 2014

I would rather add the object GUID in the hash to avoid storing an additional object reference somewhere else. Else we will need to also consider this one when removing child items from a container :P:P:P

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 24, 2014

Member

👍

Member

parasyte commented Dec 24, 2014

👍

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Dec 29, 2014

Member

api.debounce (in the above example) will need an ES6 Map. There's a polyfill committed as part of #591. Chrome supports Map natively!

Member

parasyte commented Dec 29, 2014

api.debounce (in the above example) will need an ES6 Map. There's a polyfill committed as part of #591. Chrome supports Map natively!

@parasyte parasyte modified the milestones: 2.2.0, 2.1.0 Feb 7, 2015

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte May 29, 2015

Member

Putting this here before I forget: In addition to the items listed above (double collision handling, multiple collision response phases, optimizations, etc.) there's an issue with position and velocity correction using a single response object when the colliding entities are both moving; me.Body.respondToCollision expects objA to be moving and objB to be not moving. This will probably be fixed by #588 because handling mass requires that the velocity of both entities is taken into consideration.

Member

parasyte commented May 29, 2015

Putting this here before I forget: In addition to the items listed above (double collision handling, multiple collision response phases, optimizations, etc.) there's an issue with position and velocity correction using a single response object when the colliding entities are both moving; me.Body.respondToCollision expects objA to be moving and objB to be not moving. This will probably be fixed by #588 because handling mass requires that the velocity of both entities is taken into consideration.

@parasyte parasyte modified the milestones: 2.2.0, 3.0.0 Jul 26, 2015

@obiot obiot modified the milestones: 4.0.0, 3.0.0 Oct 27, 2015

@obiot obiot added this to the 4.1.0 milestone Sep 15, 2016

@obiot obiot removed this from the 4.0.0 milestone Sep 15, 2016

@obiot obiot modified the milestones: 5.0.0, 4.1.0 Jan 18, 2017

@obiot obiot added this to To Do (Core) in Roadmap Dec 4, 2017

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