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.

[obiot]

@Tokyonono

a small comment as well on your last post : the idea is not to reinvent the wheel but to provide a simple and efficient implementation that can fit with simple game where no advanced physics are required, as much as (as I also think) chipmunk is awesome, lots of games do not require such advances features as available in such more complete physics engine.

[parasyte]

As well, a physics engine could be quite negative for many types of games. A platformer requires hacks like "surface velocity" (acts like a treadmill) to implement walking. Eg, apply velocity only when touching a surface on a particular side (usually the "feet"). And characters need to be given an infinite moment of inertia or they rotate when colliding, etc.

@obiot That's kind of what I am experimenting with; the velocity is still the same, but I've added a new vector that will be a sum of all sub-pixel velocities over sequential frames. When the sum is >= 1 pixel, it will be allowed to update the object position and check for collisions. First attempt did not work as well as I hoped, but maybe soon. :)

[Tokyonono]

Well, 2 points:

• I made this game using different approaches (wild bunny's and others) and finally ended up using chipmunk, so I talk from my experience: nine-software.com/shared/avgn/
• Chipmunk can do eveything you need wit good perf. You will have developed a nice engine which will have similar perf than Chipmunk doing the same thing, that s my only point. But if you enjoy it, I will always support you guys, i love melonjs :-)

[parasyte]

@Tokyonono Good points, and I know we are reimplementing a lot of what Chipmunk already offers. :( It's problematic from that point of view, but it also means we will be able to do full collision detection outside of the realm of physics simulation. As far as I know, this is not possible with Chipmunk. And unfortunately, physics simulation will be a high entry barrier for many melonJS users. (I still spend multiple days getting a physics space configured properly when starting a new project with Chipmunk-js.)

The last remaining bug in collision response is a tricky one. I've seen some methods to counter this exact problem, and I could explain in more detail later (including images). The gist is that having multiple collision shapes on the same plane creates "micro gaps" that the collision detection engine needs to deal with intelligently. Especially for tile-based collision shapes, where every tile corner manifests this problem. :confounded:

Also as another reminder to myself: Need to add multiple collision shapes per ObjectEntity, and also support collision objects from Tiled. Multiple collision shapes are supported in Chipmunk as the shapes property.

[Tokyonono]

1/ It took me between 30s and 1min to configure my space: var gravity = cp.v(0, -750); this.space = new cp.Space(); this.space.gravity = gravity; It worked perfectly for me. The only setting a user of MelonJS would need to think of is the gravity. 2/ Isn't cleaner to put all the physics together and simulate it separately than having pieces of collision detection here and there? 3/ Will you handle sleeping objects ? 4/ The good thing with having a physics simulation separated is that when the framerate goes down, you can still simulate the physics correctly : // fixed timestep for physics simulation var timeAccumulator = 0.0; var fixedTimeStep = 1.0/120.0; // 120hz // resolve collisions var timeToRun = dt + timeAccumulator; while(timeToRun >= fixedTimeStep) { // run chipmunk step this.space.step(fixedTimeStep); timeToRun -= fixedTimeStep; } timeAccumulator = timeToRun; 5/ In the code I posted earlier (wild bunny's solution), check "isInternalCollision", which solves your issue with gaps (if we talk about the same thing) 6/ I am not trying to discourage you in any way, just giving an opinion, I am not even a big fan of Chipmunk, I used it because I had too...

[parasyte]

1. That's enough for basic config. But you still have to create shapes for the static body, define bodies and shapes for each entity (probably most of those with infinite moment of inertia, unless you want them to tumble and rotate), setting mass, and configuring the space damping is a good idea too (especially for top-down perspective). There's a lot more to bootstrap with Chipmunk today than with melonJS. The integration will fix that, but we're not ready for integration yet. :(
2. Certainly! This patch is trying to compile all of the collision detection stuff in melonJS to put it in a single place (collision.js) There are a few things for physics that don't belong in the collision module, like applying gravity.
3. Sleeping objects will be a great optimization! And not just for collision detection or physics. Actually we can get better perf by sleeping objects within the entire game engine: See ticket #191.
4. I really don't believe it's possible to separate physics simulation and collision detection, since all physics responses rely on accurate collision detection anyway.
5. Thanks for the tip! I'll have a look at that right now.
6. Understood. ;) And no offense taken. I fell into the same "trap" when I did the LPC game last year. Collision detection in melonJS wasn't adequate for my purposes, so I had to learn to use the Chipmunk physics engine just so I could use non-AABB collision shapes! That's something we should not require anyone to go through! We can integrate SAT.js pretty easily at a later time. But it's not as useful without a broad phase to eliminate impossible collisions.

[parasyte]

@obiot Moved this ticket to 0.9.8! I won't be able to complete it and get it thoroughly tested by the end of the month. No need to hold up the release for this feature!

[obiot]

@parasyte oh really, I was honestly really looking for this one in 0.9.7 and do a big announcement with the reboot of the "new melonJS" (Apple style), the new official team (well us, but still) and all the new awesome features ! but for sure if you are busy with you real like and work, no problem and after all we are not getting paid for this !

Note that on my side I finally have to go for a business trip next week (in Brazil!), and will probably be in holiday the one after, which means that I'll be quite busy too. And although I should be able to manage closing the remaining small tickets, the release won't probably happen before the may 6th, as I won't probably have the time before that to publish the new version together with the website, etc.. So still .3 weeks to go ! :)

[parasyte]

I'm continuing to work on this, I just think it's not a good idea to publish it without at least a few weeks of community testing and feedback. As long as we keep the release cycle short, we can get this out for 0.9.8 in May/June!

[obiot]

well you got a point, as for sure we will have lots of feedback when publicly introducing the feature!

Let's then target a June release for 0.9.8 with this (except if you have a breakthrough within the 2 next weeks)

[obiot]

@parasyte

Hi Jason, end of June is in two weeks and we should decide what we do for that release. Do we anyway plan a release end of the month, with what is already done, or do extend the 0.9.8 release date to the new collision managment (unless you have been working on it and think it can be ready by the end of the month)

no problem with any of them, it's just plan stuff accordingly :)

[mluyties]

Hey guys,

I hope you don't mind me chiming in, but from someone that uses your engine and loves it, as well as works in the games industry and goes through this kind of development process all the time, I would suggest releasing 0.9.8 with what you have. I'd also suggest releasing a new engine version every month with your changes unless you literally have nothing.

• It's a whole lot easier for everyone to update their games in segments rather than in one huge drop like 0.9.7 was.
• It allows users to also hold off on certain drops if they feel it won't benefit their game right then and there.
• It also means that if someone is really excited about one of your changes that did make it in, they don't have to wait 2 months to get it if a certain feature falls through for the month.

By doing it in smaller chunks, it allows a little more flexibility and a little less pain by giving the user some choice.

Thanks, Mike

P.S. For some reason, my line breaks do not appear when I comment =(

[parasyte]

@mluyties I agree with that. And in general I agree with the "release early and often" strategy.

Anyway, this feature is not ready. And wot be ready in two weeks. ;) I recently merged master into the feature branch, but I haven't tested extensively. The merge had a few collisions that required manual resolution as well.

[obiot]

@mluyties no problem,. and I'm actually happy you are raising your voice here, as these ticket are also a placeholder for discussion (and not just me and Jason) ! However a one month cycle is very short, the point being that neither Jason or myself are fully dedicated to melonJS, and based on our regular workload we sometimes make little progress in one month time, and that's why we kind of decided to go with a 2 months cycle.

@parasyte do you mind however going through all opened (and untagged) ticket and see if there is something you do want do work on for the coming release ? on top of the collision stuff :P Else I will move the remaining stuff to the next release.

yeahhh 0.9.8 coming, next one will be 0.9.9 !!!! last version before a first stable/mature release ??? (we will need to celebrate that!)

[Tokyonono]

Let's do a Game Jam to celebrate MelonJS 1.0.0!! By the way, I never tried it before, but have you heard of Quadtree collision detection? Here are some interesting links (with a demo): http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ http://lab.polygonal.de/?p=202 And some implementations: https://github.com/silflow/quadtree-javascript http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/ Cheers!

[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 :)