next »

[st33d]

Quadtrees should be used when you've got lot's of different size objects. Otherwise the overhead of running one doesn't get you much.

Spatial Hashing is also fairly costly to run if you clear the hash each frame.

Just partitioning out the space is good enough. Some fixed cells and you're good to go.

However

I built a partitioning system when I needed upto 300 stackable moving crates. It could also cope with more and ran in Flash.

When I used the same system for a platform game I stripped out the partition and just ran it raw, everything testing against everything (but only when they moved).

Did it slow down.

No it bloody didn't.

Guess what - I was also running two concurrent game engines, both running physics simulations of their own! (Two player metroidvania).

You shouldn't even be thinking about spatial hashes or quadtrees unless you're bottlenecking. And even then, just cutting up the area into cells is good enough. And if you are bottlenecking, look at how you're rendering stuff - that might be the real issue.

[Overkill]

Here is the collision code I went with, big thanks to BorisTheBrave!

Code:

function checkRectangleIntersection(position, size, targetPosition, targetSize)
{
    var dx = positiveMod(targetPosition.x - position.x, screen.width);
    var dy = positiveMod(targetPosition.y - position.y, screen.height);
    return (dx < size.width || dx + targetSize.width > screen.width)
        && (dy < size.height || dy + targetSize.height > screen.height)
}

I would also like to extend a thanks to everyone else (eigenbom, raigan, IdleDeveloper, static, fecal_brunch, Veracity, st33d, hopefully not missing anyone), this discussion was helpful! But alright, there's a lot of debating going on, and there's no way I can address everything.

As far as broad-phase stuff goes, I'll reiterate: I'll care about it when I actually notice performance problems. The narrow-phase collision would have to be the same anyways, so really broad phase is a distraction from the real problem.

All broad-phase does is lower the subset of objects being checked, it doesn't actually make the collision detection of two objects in a wrapped coordinate space any less complex. Moving to broad phase collision later hopefully shouldn't be that difficult if I find I need it later. Rewriting code is a fact of life, I'd rather pay the cost later than up front, when it isn't clear yet that performance will be impacted for the small number of collision bodies in a given scene.



Now, as far as performance goes, I wrongly said that performance would be O(n^2), but in fact, it would be a series of simple O(m*n) checks, because I am only evaluating collisions between bodies I care about. And this is how I'd want to do it anyways, since distinct systems of objects are managed differently internally. I imagine the total collisions will be roughly:

Code:

|collectables|                         (collectables vs. player)
    + |enemies|                        (enemies vs. player)
    + |player projectiles| * |enemies| (player projectile vs. enemy)
    + |enemy projectiles|              (enemy projectiles vs. player)
    + (|enemies| + 1) * |walls|        (player/enemies vs. walls)
    + |projectiles| * |walls|          (projectiles vs. walls)

I am aware that sometimes the phrase "premature optimization is the root of all evil" is the root of all evil. And yes, this particular case could be very crappy, but assuming something like 30 collectables, 8 enemies, 5 player projectiles, 16 enemy projectiles, 10 walls:

Code:

30 + 8 + (5 * 8) + 16 + ((8 + 1) * 10) + ((5 + 16) * 10)
    = 30 + 8 + 40 + 16 + 90 + 210
    = 394

394 AABB collisions seems like it should be possible these days without much frame-rate loss, even in a fairly unoptimized JavaScript interpreter.

Also the fact that I've done pixel-based collision detection in a Lua-based sidescroller engine without issues on low-end machines, and st33d's discussion about his two-player metroidvania, makes me think it's possible to run without a big performance hit.

I'm willing to settle for "good enough for now" instead of perfect code in this particular case. If it turns out to not be good enough down the road, it's probably easy enough to refactor and implement broad-phase spacial partitioning. Nonetheless, thanks Veracity, for suggesting some performance stuff. It's just not my top priority yet.

[BorisTheBrave]

Did it slow down.

No it bloody didn't.

That is because your narrow phase was cheap (testing collision of two boxes). Broadphase is more important when the narrow phase is expensive (testing collision of two arbitrarily rotated polygons).

[st33d]

Fair point. I'd made the assumption that he was making a straight platformer but didn't mention that assumption.

[BorisTheBrave]

No, I think you are right for here. Just illustrating what the main point of broadphases is in most games. It's cutting out work, not changing from O(n) to O(log(n)).