Performance: multiple-phase collisions

[parasyte]

Objects should only do collision detection when they move. And the detection should be done in multiple phases using hash segments:
#1. Broad phase

The first phase is called the "broad phase", and it only attempts to resolve which objects/tiles collide, not how to handle the collision. In the broad phase, an AABB is created for the object's entire range of motion. See image below:

In resolving the broad phase, all range-of-motion AABBs will be stored into their closest hash segments, and collisions detected between other AABBs within those segments.

(Here "hash segment" means a square area of the world. A good starting point is to break the world into hash segments that are 4x4 tiles in size, though any size is possible.)
#2. Narrow phase

The narrow phase takes the collisions detected in the broad phase and finally resolves them by collision shape/position. Some broad-phase collisions will be false-positives, where the range-of-motion AABBs intersect, but an actual object collision did not take place. The narrow phase needs to be good at "bailing early" in these kinds of cases.

An algorithm like this should reduce the time complexity from O(n^2) to something more like O(log((n-s)^2)), where n is the total number of objects and s is the number of stationary objects. In other words, a huge performance gain in collision detection with a large number of objects.

[melonjs]

Another great article (but I guess you know it already) that also cover this topic and collision resolution itself :
http://www.metanetsoftware.com/technique/tutorialA.html

+1 for creating a AABB box representing the object motion (that for sure will fix issue #16), however this can only be used with fixed element (like Tile), right ? else an object going where the object was previously placed could trigger a false-positive collision.

Else for the phases approach, I've been looking at that as well, but considering that basically melonJS only supports AABB boxes, I didn't find how to efficiently do the broad phase, as basically (if' I'm not wrong, which I'm sure I am) it's about detecting which objects are intersecting with the object range of motions (which is already the narrow phase).

[parasyte]

Yeah, it's a super great article that I read through a while back. (It made me decide to use chipmunk rather than roll my own collision detection, as I was short on time.)

The false positives are ok in the broad phase, as long as they can be "bailed early" and don't cause too many false positives each frame. That would be a worst-case scenario, and would probably be an uncommon situation. I think only having MANY very small & very faster moving objects will actually create a lot of false positives within the range-of-motion AABBs.

The "broad phase" is usually more about figuring out which objects should be considered for collision checking. It's generally a good idea to use spacial hashing as your broad phase. This will tell you which objects are potentially colliding. You then use their range-of-motion AABBs to further narrow down the search. The "narrow phase" will resolve those collisions; in a physics engine, this means computing and applying response forces.

[melonjs]

@parasyte

I'm moving this one to the next release, unless you are yourself super hyper motivated in implementing this before :)
note, the tiled repo is quite active recently, the long due 0.9.0 version should be quite close now, and so the melonJS 0.9.5 release (else I guess at some point I should stop waiting for it and release is without the new image layer)

[parasyte]

@obiot ok! My motivation has turned to some other projects recently. :)

[melonjs]

@parasyte sure, anything exciting ?
I hope anyway to see you soon back on melonJS :):):)

Have fun,
Olivier

[melonjs]

Another great article :
http://buildnewgames.com/broad-phase-collision-detection/

[parasyte]

I started on this tonight, and it got me thinking of the future of melonJS. We want to integrate a physics engine officially. And physics engines do all of their collision detection with rigid bodies; even the environment is composed of rigid bodies. There isn't a distinction between collisions with the environment and collisions with other entities. I guess this property is unique to melonJS in its current form. :)

I would like to remove that distinction in this ticket. All collision checking should occur in one function, using the same data structures. This will ease the integration of a physics engine, and also clean up and make collision detection less work to manage. For compatibility purposes, I am not opposed to converting the collision tile layer into discrete objects within the new collision detection system. (Conversion happens after level load.)

The other thing I want to mention is that I probably won't be implementing an SAT algorithm here. Although I can if it makes more sense to do now than later. My concept is just to eliminate the performance issues, and fix bugs along the way. AABB collisions might be just fine for now. ;)

[melonjs]

@parasyte
Wow, I can see it has been a busy weekend for melonjs :)
On my side i'm still away, so i'm sorry i did not provide any real feedback, but I'll be back tomorrow morning !

[parasyte]

@obiot no worries!

My code for this ticket isn't ready for review yet. I want to keep melonJS simple, so I'm going to lump all collision phases into a single function. It isn't the "correct" way to do it, but we're not too concerned with physics accuracy anyway. :p

Regardless, this will be another big API-breaking change!

[melonjs]

@parasyte

a few comments on my side :

• i'm fully inline with merging both the entity collision function and the tile layer collision function into a world collision function, as it's definitely the general approach,
• having AABB as a start for tile collision would be fantastic anyway, i'm concerned however on how to re-implement slope collision with AABB (as AABB is rectangle only, right?), but it could be re-added later (through SAT or a Chipmunk/Box2D)
• it would really be nice to have the tile collision layer being converted in discrete objects, and actually, I really would like to keep the idea of the "collision" (named) layer, so that end-user could either use it wit tiles, or add (rectangle) polygon or whatever they need.
• shall we then also revisit the collisionBox approach ? maybe renamed it body as well, with the idea to make this notion more generic ?
• i think that once we will have a more clean implementation with AABB, adding SAT is very easy, as basically (and if i'm not wrong) it's just about adding more shapes, and corresponding collision detection between each of them.

About big API-breaking change, please do whatever you think is the best (though I would suggest to keep it as close as possible from the physic API out-there, to ease later integration, or addition). And anyway, if we do want to bring melonJS to the "next level", that's something we cannot avoid.

I'm very excited about this one, this is one of melonjs' major remaining weakness, and if we could have some breakthrough on this one, it would really be fantastic ! :)

[parasyte]

@obiot That all sounds totally reasonable and awesome.

For AABB collisions against the special tiles like slopes: Those will still be handled the same as current, with "pixel perfect" collisions against the 45° slopes. It will need to change later for SAT, but at least we won't drop a feature during the upgrade.

Collision layer conversion code is done! I need to take care of a few more things in the outlying areas and do some testing. After that, I'll push the initial commit to a new branch. :D

One more thing we might enforce is doing all collision handling in callbacks, and getting rid of the explicit me.ObjectEntity.collide() and collideType() methods. Chipmunk, for example, only supports custom collision handling in callbacks, but it supports three different callbacks for handling collisions at different phases of collision resolution.

For the me.ObjectEntity.collisionBox, we shouldn't rename it body, but something else like shape or collisionShape. A "body" in Chipmunk terms is the data structure that contains information about the position, rotation, etc. It's analogous to our me.ObjectEntity already. :) The "shape" defines how the body may collide to with other shapes in the space. So that shape is a lot like collisionBox. Although, Chipmunk also supports multiple shapes per body, and maybe this is something we could consider, too.

[melonjs]

@parasyte
Same, totally reasonable and awesome ;)

• with the new world collision being automatically done, does it mean we can get rid of the updateMovement as well ?
• I'm super ok with the callback system, but how do we then exclude objects from being "taken in account" during the collision detection ? I mean for sure you can just not specify any callback, but I would expect to be able to optimize a game by not including detection phase for those entities.
• shape is for sure fine, it's just a lack of knowledge on my side concerning chipmunk :) but that's actually exactly what I meant.

wow, that's become very concrete very fast I can't wait to play with the new branch !

[parasyte]

Not sure about getting rid of updateMovement! I was thinking about using it to call the new collision checks.

Excluding from collision is easy: I have a new property called collisionMask which can be set in Tiled (or JavaScript) which will mask collisions as desired. If not explicitly set, collisionMask defaults to 0xFFFFFFFF (i.e. collide with everything). It can be used kind of like this:

var masks = {
    PLAYER  : 0x00000001,
    ENEMY   : 0x00000002,
    COIN    : 0x00000004,
    POWERUP : 0x00000008,
};

game.PlayerObject.collisionMask = masks.PLAYER | masks.ENEMY | masks.COIN | masks.POWERUP;
game.CoinObject.collisionMask = masks.COIN;
game.EnemyObject.collisionMask = masks.ENEMY;
game.PowerupObject.collisionMask = masks.POWERUP;

Now game.PlayerObject can collide with everything, and enemies cannot collide with coins or powerups.

It can be a bit tricky to use masks, but it's also supported in Chipmunk!

[melonjs]

wow, that looks great, masks are actually very very good :)

about the collision check, I thought this would be actually automatically done, without requiring to manually call the function, it is not ? but I guess it will be clearer for me once I will see it :)

[parasyte]

Well, it's no more automatic than adding gravity to the velocity vector. ;) I'm sure we could clean this all up in some way, but I haven't really thought about it.

For performance reasons, we only want to check for collisions when an entity moves. And updateMovement is what does that right now.

[melonjs]

oh ok, got your point :)

[parasyte]

@obiot Here is the initial work! 👯 It's really early still, but it's pretty cool to watch with debug enabled.

[melonjs]

@parasyte so cool, I think I definitely need some time to read your code and understand how it works, but so far I liked what I saw, except for the try/catch :)

[melonjs]

@parasyte just played with it a little, and effectively seeing it running in debug mode is quite cool :)

I did provide a few comments, I hope you don't mind (but nothing really constructive), as I'm still in the phase where I need to understand all the code changes :)

but hey, quite a good good good work you put here !!!!!

[parasyte]

I have some ideas to optimize the code, but I think even the algorithm as it is will be quite a bit better for performance. My next step before working on the default collision handler will be building a basic collision test example, to better understand how it changes performance.

[parasyte]

@obiot Funny news! The collision test demo has worse performance in this branch than in master! :p Updating the grid cells in the broad phase part takes waaayyy too much time. This is actually very easy to fix. But for now ... sleep time! I'll try again tomorrow!

[obiot]

@parasyte that's very good news then, because I was also playing with the code, and a bit worried about performances :)

[parasyte]

@obiot The ticket-103 branch was really broken, so I deleted it from github. Then I locally rolled back a bunch of merge commits and did a single merge that fixed everything. I haven't yet touched the collide code in ObjectContainer -- I should do that right now.

Anyway, the new branch for this is ticket-103-clean

[obiot]

:):):)

On Aug 26, 2013, at 06:16 AM, Jason Oster notifications@github.com wrote:

@obiot The ticket-103 branch was really broken, so I deleted it from github. Then I locally rolled back a bunch of merge commits and did a single merge that fixed everything. I haven't yet touched the collide code in ObjectContainer -- I should do that right now.
Anyway, the new branch for this is ticket-103-clean
—
Reply to this email directly or view it on GitHub.

[obiot]

and... postponed again ! :(

(note that I'm really considering stop trying with this one and going with a simple physic engine integration)

[obiot]

Guys,

I decided to close this dead ticket, as it also spawned over the months (year) into a lots of different directions, with pages and pages of comments and it's time to let this one rest in peace.

but, and to quote my fellow countryman and scientist Antoine Lavoisier, since Nothing is lost, nothing is created, everything is transformed., this ticket already did transcend itself into the following ongoing tickets : #394, #543, #544 , so we will keep having fun with it somehow :)