SAT based algorithm for collision detection/response

[obiot]

we discussed this already in the forum (and also as part of #103), but i'm creating a ticket for it, so that this is clearly identified.

Now that we correctly (at 99%) support polygone/polyline shape in melonJS this should be quite straightforward to implement, and implementation in javascript like the following are already a great reference :
https://github.com/jriecken/sat-js

Basic AABB detection (through the shape.getBounds() function) could still be used during broad phase, and then SAT to precisely calculate responses for colliding objects

Additional bonuses for this one :

• rewrite/redesign the me.Rect class as a subclass of polyshape #366 so that we only care about polygon to polygon
• should help fixing identified collision issue with isometric maps (e.g. [isometric] - Collision detection not working properly #52)
• perfect to add back slope support after we merged ticket Performance: multiple-phase collisions #103

[obiot]

I don't know why I forgot to add a reference to this ticket at each commit, but it's there now in the master branch !

a few comments :

• melonJS will not create anymore rectangle object for body shape but will automatically "convert" them to a polygon shape (including rectangle defined in Tiled)
• currently the engine will first do a fast and basic AABB detection using both polygons corresponding bounding box, and will then perform the full SAT collision check if they are overlapping
• the current implementation populate the x and y properties as previously, so that it offers backward compatibility with previous game implementation (let's decide if we remove it or keep it)

Some to-do list (in no particular order) :

• add Circle vs Polygon detection (done)
• use the object pooling system for vector/array objects ? (not required as the current code is more efficient in this specific case)
• ~~optimize the way collision check is done ~~(see Quadtree / spatial grid implementation #544)
• take in account the shape pos/offset (relatively to the body "parent" object) (done, there is however another issue that prevent from changing shapes position offset, and that causes renderable to be draw at the wrong position; particulary visible with polygon with a point of origin different from (0,0))
• fixed the ellipse size (draw) issue
• multiple shape support (now only the "active" shape is used through body.getShape()) ~~ (1.2.0 milestone, add multi-shape support for collision #539)
• extend polygon usage to tiled layer (1.2.0 milestone, Shape based collision layer #538)
• add rotation support to the PolyShape object (this is missing compared to the original SAT.js implementation) (1.2.0 milestone, add rotation support to the Polygon object  #540)
• add/fix documentation (done)
• further code cleaning (done I think)

[obiot]

On the quadtree topic (although kind of a different topic) :
https://github.com/mikechambers/ExamplesByMesh/tree/master/JavaScript/QuadTree

[obiot]

@agmcleod @parasyte hi guys, some advice required here :

What do you think we should do with the following :
https://github.com/melonjs/melonJS/blob/master/src/physics/solver.js#L50-62
this is a basic pooling mechanism to avoid new object creation and GC. Shall we use our me.pool class for it (even for Array object?), or shall we keep this way ?(as it provides a very fast way in this case and ensure that these objects are always available for collision solving)

Also, i was thinking to turn the current me.Solver (instantiable) class into maybe a me.collision singleton, what do you think ? (both class type and naming)

[agmcleod]

I'm pretty comfortable where it is. I like the idea of keeping it dry with re-using pooling, but the method here is also pretty clean, given it's just vectors. It's how i did pooling for the 4 vector points in a bezier curve in snowball.

I prefer me.Solver simply because. me.collision.collide reads kinda funny :)

[parasyte]

It's probably fine, the way it is. The melonJS pool code adds an extra property to the object to determine its type. Probably not the best thing, but that's how it is currently.

The old #103 API uses a me.collision singleton, but it has methods like check and updateMovement ... which doesn't sound as funny as me.collision.collide

[obiot]

Good, i'm keeping the light pooling functions then :)

Else for me.collision my idea was then to rather define a new me.collision.solve(a,b, (response)) function (with response being optional so that we don't go through the full response calculation if not necessary) that would replace the current one (the me.game.world.collide one as such would disappear, or stay for a little for backward compatibility), and also to add/document the Response base object under that same namespace.

[obiot]

just noticed a weird bug this morning in melonJS and i cannot find the root cause :)

when using Ellipse shape in Tiled, the final display (in the browser) size is wrong, as somehow (but I cannot find where) the object width and size got modified. This is however working perfectly when creating shape object manually (see the shape example)

[agmcleod]

that is rather interesting. I'll see if i can have a look this evening. On master?

[obiot]

Yea...

I'm taking a 7h flight later, will keep trying as well (although i barely have 3h of battery with my laptop)

[agmcleod]

dang. I think mine has around 4 or 5 hours total these days.

Safe flight!

On Mon, Jul 14, 2014 at 9:09 AM, Olivier Biot notifications@github.com
wrote:

Yea...

I'm taking a 7h flight later, will keep trying as well (although i barely
have 3h of battery with my laptop)

Regards,
Olivier

On 14 juil. 2014, at 18:35, Aaron McLeod notifications@github.com
wrote:

that is rather interesting. I'll see if i can have a look this evening.
On master?

—
Reply to this email directly or view it on GitHub.

—
Reply to this email directly or view it on GitHub
#394 (comment).

Aaron McLeod
http://agmprojects.com

[obiot]

Shitty company windows laptop, and i did not take my MBA, my fault :(

On 14 juil. 2014, at 18:40, Aaron McLeod notifications@github.com wrote:

dang. I think mine has around 4 or 5 hours total these days.

Safe flight!

On Mon, Jul 14, 2014 at 9:09 AM, Olivier Biot notifications@github.com
wrote:

Yea...

I'm taking a 7h flight later, will keep trying as well (although i barely
have 3h of battery with my laptop)

Regards,
Olivier

On 14 juil. 2014, at 18:35, Aaron McLeod notifications@github.com
wrote:

that is rather interesting. I'll see if i can have a look this evening.
On master?

—
Reply to this email directly or view it on GitHub.

—
Reply to this email directly or view it on GitHub
#394 (comment).

Aaron McLeod
http://agmprojects.com
—
Reply to this email directly or view it on GitHub.

[agmcleod]

@obiot so i put up a small example. 822b2b4

I was able to place a circle object, and then draw it to the correct position. I just had to account for the x y + radius, since tiled coordinates are top left for circles, but in the canvas it's the center.

I also changed the constructor slightly for the ellipses as it was initializing a new vector to this.pos, then passing the vector to the setShape() method, so i removed that redundency.

[obiot]

@parasyte @agmcleod

Hi Guys, with this last very commit :

• I changed the code structure to use a singleton
• renamed me.Solver to me.collision (i basically followed what we did with the dead #ticket103)
• deprecated the older function

I would appreciate if you could go through the documented API and provide feedback (positive or negative), and so that we can "freeze" the API.

I also added the possibility to deactivate the SAT collision detection and just basically use AABB detection with a simple true being returned in case of collision (might be useful for very simple case where no advance collision detection is required ?)

[parasyte]

@obiot I'll try to find some time to look at this. My week is super busy (work) and I'm trying to balance that with my other personal projects. ;) This is something I'm very interested in, however. So I may have a lot of [constructive!] criticism by the time I get around to it.

[obiot]

ahah, no problem, we are not in a hurry anyway, and I can keep working on it (like tracking that f**** issue with the ellipses) or work on other things (my next step is to add the quadtree code I was referring too earlier) in the mean time.

[obiot]

Note : any update to the English itself is also much appreciated, just to ensure that just more than just french speaking english understand it correctly :)

[obiot]

good news : there was no bug with the me.Ellipse object in melonJS, this is due to a bug in the platformer example, that forces the width and height properties in settings to different values before calling the parent constructor !

took me a loooong time to figure it out, just for a stupid bug not in melonJS at the end ! anyway I'm happy :P

[obiot]

Updated the todo list here and move some "subitems" to the next milestone (see #538, #539 and #540).

So, documentation to be finalised, and then we can call it a day for this one :)

[obiot]

closing this one !