next »

[Overkill]

Alright, so very recently I was dorking around and going to make a cheesy single-screen HTML5 game, similar to Bubble Bobble. It was going pretty good, basic platforming, walls, collectables.

Here is a demo so far (tested in Opera, Chrome, Firefox): http://dl.dropbox.com/u/72165/plat/snapshot-2012-01-08/bobble.html

As with most single-screen games that leave openings on the edges of the screen, the player is able to wrap around the edges. However, my rectangular collision detection for walls can't account for collision with objects from the other edge of the screen.

You know, the usual:

Code:

if(entity.x < wall.x + wall.width
    && entity.x + entity.hitbox.width > wall.x
    && entity.y < wall.y + wall.height
    && entity.y + entity.hitbox.height > wall.y)
{
    // Collision!
}

For static walls, I could just extend the edges one extra row of tiles. This made it seem like you were colliding with the walls on the opposite edge of the screen. Which was fine, if every obstacle around the player is static.

But I want to have enemies and projectiles that can wrap around the screen, maybe even moving platforms that cross through.

How do I make collisions that will properly check something at the edges? For rendering sprites when they wrap around, it just draws at 4 locations: position, position - (w, 0), position - (0, h), position - (w, h). But I don't know that this works for collision-checking logic, if I need to apply correction to move out of walls after applying velocity. Any ideas?

I'm blanking out here, and figure it'll take less time to just ask.

[eigenbom]

Love the colours in your game!

If you restrict the wrapping to either vertical or horizontal (i.e., not allow someone to travel out the screen corner), then you could just split the entity's bounding box up into two whenever it wraps, and then check each one..

[surt]

I'd be handling the wrapping in the broad-phase and keep the collision function clean.
collect collision candidates
for each axis
  if collision bounds intersects world edge
    offset object to opposite edge
    collect collision candidates
purge duplicate candidates
perform standard narrow-phase

[rhys_vdw]

Couldn't you do something like...

Code:

var xPos = entity.x % WORLD_WIDTH;
var yPos = entity.y % WORLD_HEIGHT;
if(xPos < wall.x + wall.width
    && xPos + entity.hitbox.width > wall.x
    && yPos < wall.y + wall.height
    && yPos + entity.hitbox.height > wall.y)
{
    // Collision!
}

[eigenbom]

Couldn't you do something like...

Code:

var xPos = entity.x % WORLD_WIDTH;
var yPos = entity.y % WORLD_HEIGHT;
if(xPos < wall.x + wall.width
    && xPos + entity.hitbox.width > wall.x
    && yPos < wall.y + wall.height
    && yPos + entity.hitbox.height > wall.y)
{
    // Collision!
}

nope! :D

[Overkill]

Love the colours in your game!

If you restrict the wrapping to either vertical or horizontal (i.e., not allow someone to travel out the screen corner), then you could just split the entity's bounding box up into two whenever it wraps, and then check each one..

Thanks. Ahhh, I think I get where you're going with this, for horizontal motion, split the hitbox into the side on the right screen, and the side on the left screen, and same idea for vertical travel. And yeah, I've wondered about the corners, I have no idea if that'll actually be a problem or not, but if it turns out to be a limitation, I can live with that.

Hm... So if you're moving left, you only care about the left hitbox split on the right side of the screen, and for moving right you only about right hitbox split on the left side of the screen. I guess you need to split the collision target's hitbox in a similar way too.

I'm a little unsure how this would work, but it's giving me some thoughts.

I'd be handling the wrapping in the broad-phase and keep the collision function clean.
collect collision candidates
for each axis
  if collision bounds intersects world edge
    offset object to opposite edge
    collect collision candidates
purge duplicate candidates
perform standard narrow-phase

Hmm, so I don't have a broad phase for the collision detection yet, I'm chugging along with the crappy O(n^2) style method. I plan to eventually add spatial hashing when performance becomes a concern. But still, that gives me some ideas, thanks.

Couldn't you do something like...

Code:

var xPos = entity.x % WORLD_WIDTH;
var yPos = entity.y % WORLD_HEIGHT;
if(xPos < wall.x + wall.width
    && xPos + entity.hitbox.width > wall.x
    && yPos < wall.y + wall.height
    && yPos + entity.hitbox.height > wall.y)
{
    // Collision!
}

That won't work if you're on the right edge (xPos + entity.hitbox.width could be greater than WORLD_WIDTH, even though xPos is less than WORLD_WIDTH) or the bottom edge of the screen (for similar reasons).

[rhys_vdw]

That won't work if you're on the right edge (xPos + entity.hitbox.width could be greater than WORLD_WIDTH, even though xPos is less than WORLD_WIDTH) or the bottom edge of the screen (for similar reasons).

Yeah, I was a bit confused because you are only comparing one point for your entity (rather than its hit box). But I guess you got the gist of what I was suggesting.

Splitting the hit box will be computationally cheaper anyway.

[static]

You should think of the objects as repeating infinitely on the axes where the level repeats. Like the entire map is tiled in every direction, forever. Since you can't hit-test an infinite number of objects, you need to find a way to hit test a subset of them to get the behavior you want.

The easy way to do this is to duplicate the bounding boxes of the player. This doesn't account for situations where the levels don't repeat on both axes or if any object is larger than the period of a repeating level, but it doesn't look like you need to account for that.

So if the level is 100x100, and there's a 10x10 player in the top left corner, you'd end up with 9 bounding boxes...

Code:

(0, 0, 10, 10) - the original bounding box
(0, -100, 10, -90) - above
(-100, 0, -90, 10) - left
(-100, -100, -90, -90) - above and left
etc

Checking each of these bounding boxes against each of the enemies should give you the behavior you want. There's a lot of room for optimization here, like skipping duplicates in sections the player's bounding box is not touching, but it's probably not necessary. The duplicates only need to be generated for one side of the collision (either the player or enemies, but not both). Keep this in mind if you add projectiles, since they'll behave roughly the same way.

[Danmark]

Hmm, so I don't have a broad phase for the collision detection yet, I'm chugging along with the crappy O(n^2) style method. I plan to eventually add spatial hashing when performance becomes a concern.

Doing it in the broadphase is the simplest and cleanest solution to your problem. Implementing a spatial hash and writing the insertion part to account for wrapping is only a tad more work than making an obtuse and ill-performant multi-AABB solution. Doing the latter first, then throwing it away & doing the former at a later date is far more work.

If you're pretty sure you're going to need a spatial hash eventually, why not do it now?

[static]

If you're pretty sure you're going to need a spatial hash eventually, why not do it now?

Premature optimization.

[eigenbom]

I don't think the multi-AABB solution is obtuse. It's easy to understand and trivial to implement. Best to implement it and move on!

[Danmark]

If you're pretty sure you're going to need a spatial hash eventually, why not do it now?

Premature optimization.

Eight-word maxims ought never determine one's actions.

The actual reasons to avoid premature optimization, according to Knuth:

1) It wastes the programmer's time, as he frets about insignificant computational tasks.
Naive O(n^2) collision detection is known to be a huge task, even for a modest number of colliders.

2) It can harm code maintainability, as the programmer may sacrifice elegance/generality/readability/etc. for efficiency.
Doing collider wrapping in the spatial hash is arguably better from this perspective.

The central idea (1) is to not waste your time on things that CPU can't waste much of its time on anyway. Having to rewrite half of your game's fundamental systems is a very effective way to waste your time. Put another way, "premature" is not defined as "prior to measured deficiency in performance".

[static]

1) It wastes the programmer's time, as he frets about insignificant computational tasks.
Naive O(n^2) collision detection is known to be a huge task, even for a modest number of colliders.

I disagree with calling it naive. It's simple -- a starting off point.

Spatial hashing add a fair amount of overhead and complexity, and it's not clear if that's worth it. Simple AABB collision is also not O(n^2), it's O(n*m) where n is the number of objects that are colliding with m objects. If you've got one player, and 100 enemies, that's 100 iterations, not 101^2 iterations. A modern Javascript VM can handle 100 iterations per frame and yet that's more objects then many run-and-gun shooters.

2) It can harm code maintainability, as the programmer may sacrifice elegance/generality/readability/etc. for efficiency.
Doing collider wrapping in the spatial hash is arguably better from this perspective.

That's not true. A spatial hash algorithm is roughly the same as simpler AABB bounds checking, but with an additional layer of complexity involving inserting/removing/finding bucketed objects. Elegance/generality/readability come from simplicity, not from speed.

The central idea (1) is to not waste your time on things that CPU can't waste much of its time on anyway. Having to rewrite half of your game's fundamental systems is a very effective way to waste your time. Put another way, "premature" is not defined as "prior to measured deficiency in performance".

The reason why premature optimization is bad is because there is no right way to do things. Bottlenecks in computer software are often hard to predict, and making choices that complicate your architecture or slow down development can delay the understanding and correcting of these bottlenecks. Premature optimization is often the cause of massive rewrites, not the answer to them. Simple AABB collision is a few dozen lines of code at best in Javascript, and easily replaceable with other techniques. It's not nearly as significant as you make it seem.

It seems just as likely OP could be constrained by the fillrate rather than bounds checking, making worrying about collision potentially meaningless. The overhead from spatial hashing may actually be slower if there are too little objects or the objects are too large compared to the tile size. If you are right, then OP should focus on Quadtrees rather than regular spatial hashing, as it's a better system for 2D collisions. Except that Quadtrees are significantly more complicated and time-consuming compared to regular spatial hashing, all for a problem that may not exist.

I've definitely gone down that road OP and boy is it time-consuming. I would recommend focusing on the actual game itself, unless you really want to learn about spatial hashing and Quadtrees, since they're probably not worth your time.

[st33d]

A co-worker dealt with this issue by having a secondary hitbox.

Each entity would effectively have a core collision object and a secondary collision object that would be brought in temporarily when wrap-around is occurring.

It sounds cheap, but it was very effective.

[IdleDeveloper]

I don't see why you cant use fecal_bunch's idea with a  little modification.  Just make a new number class that automatically does the wrapping for you.  Then define the position of your dynamic objects using this new number type.

Something like this (but you know that actually works).

Code:

class WrappingNumber
{
float Max;
float Number;

float GetNumber(){ return Number; }

WrappingNumber operator +( float rhs )
{
float NewNumber = Number + rhs;

if ( NewNumber > Max )
{
NewNumber -= Max;
}

// Just assert that the new number has to be less than max (RHS isn't greater than MAX) if we ever get this then we need additional code to wrap multiple times
check( NewNumber < Max );

return NewNumber;
}

WrappingNumber operator +( WrappingNumber& rhs )
{
return this + rhs.GetNumber( );
}
};

Using this your old collision code will should just fine.

[raigan]

This should be no different than the math you use when dealing with e.g rotations in 2D: the only use for absolute values (position) is to calculate relative values (deltas between two positions).

If a component of the delta is larger than half the range of that axis, you wrap it by adding/subtracting the axis' full range -- analogous to how you bring an angle delta that's outside +/- 180 into range by adding/subtracting 360.

This correctly-wrapped delta is all you need to perform AABB-vs-AABB tests. (i.e AABB-vs-AABB is just a matter of calculating the delta and comparing that to the sum of the AABBs' halfwidths)

Of course, I haven't actually tried this so maybe I'm wrong, but it seems to me that the best way to represent spaces that wrap is to use numbers that wrap.

[Overkill]

Oh! I woke up with a silly idea this morning:

a bunch of poorly thought out math

EDIT:

Actually, noooope. That looks wrong at the step I added wrapping. The modulo will ensure the value is between 0 .. w - 1, so each condition will pass unless x = 0 or y = 0 for that particular calculation. So it'll probably react as if you're always colliding. That's kind of dumb.

[BorisTheBrave]

Code:

// Computes (a-b) mod modulo, in the range [0,modulo]
float diffModulo(float a, float b, float modulo)
{
  // If only languages defined modulo the sensible way
  float r = (a-b)%modulo;
  if(r<0) r += modulo;
  return r;
}
bool TestOverlappingRanges(float lower1, float width1, float lower2, float width2, float modulo)
{
  lower2 = diffModulo(lower2, lower1, modulo);
  return lower2 <= width1          // lower2 is in range 1
      || lower2 + width2 >= modulo // lower1 is in range 2
      ;
}

bool TestRects(Rect rect1, Rect rect2, Vec size){
  return TestOverlappingRanges(rect1.x, rect1.width,  rect2.x, rect2.width,  size.x) &&
         TestOverlappingRanges(rect1.y, rect1.height, rect2.y, rect2.height, size.y);
}

 

[eigenbom]

A co-worker dealt with this issue by having a secondary hitbox.

Each entity would effectively have a core collision object and a secondary collision object that would be brought in temporarily when wrap-around is occurring.

It sounds cheap, but it was very effective.

This is an awesome solution. Ideas like this really highlight the difference between the pragmatist and the "intellectual". I wish I was the former, but I got too many merit certificates as a kid, so I'm more of the latter ... but I'm getting there ...

[Danmark]

Simple AABB collision is also not O(n^2), it's O(n*m) where n is the number of objects that are colliding with m objects. If you've got one player, and 100 enemies, that's 100 iterations, not 101^2 iterations.

I know, but that itself is an optimization. As soon as you've made that optimization, then throughout the remainder of the project, you need to be aware of the distinction between objects that and objects that can't cause collisions: more complexity. Things get much worse when wrapping is taken into account. Note that OP explicitly stated he's using O(n^2) collision right now:

Hmm, so I don't have a broad phase for the collision detection yet, I'm chugging along with the crappy O(n^2) style method.

Shouldn't waste time improving a deeply flawed technique when you easily swap in an elegant one.

Spatial hashing add a fair amount of overhead and complexity... A spatial hash algorithm is roughly the same as simpler AABB bounds checking, but with an additional layer of complexity involving inserting/removing/finding bucketed objects.

Assuming OP has access to vector and set classes (if not, he backed the wrong horse in the first place), it really isn't as hard as you make out, particularly because a spatial hash doesn't typically need to retain information between frames (just as the O(n^2) algo doesn't). He should be able to write one in a few minutes. Then, he probably won't need to worry about collision detection in his game again, and as a bonus, he can even reuse his spatial hash in future projects.

In any case you missed the point:

That [doing collider wrapping in the spatial hash is better in terms of elegance/generality/readability] is not true... Elegance/generality/readability come from simplicity, not from speed.

Efficiency should certainly defer to elegance/generality/readability, at least to start with, but a more efficient solution isn't necessarily inferior in those respects. In this case, sticking with O(n^2) collision detection & implementing wrapping via multiple aliases is ugly and hackish. The spatial hash isn't merely an optimization- with the specialized insertion method, it's also a clean way of integrating collision with the world's topology.

The thing is, if efficiency becomes a problem, your solution wastes lots of time, making it risky. It already performs an order of magnitude slower than the already inefficient O(n^2) algo (OTOH I'm pretty sure OP's levels are constrained such that AABBs never overlap a corner, so he'd only need 4 aliases/5 AABBs in total per object). There is, as you say, plenty of room for optimization (& complexity, & inelegance). Hacks tend to beget more hacks, and should be avoided except where absolutely necessary. Better to go with something that gives reasonable guarantees from the start.

The reason why premature optimization is bad is because there is no right way to do things. Bottlenecks in computer software are often hard to predict, and making choices that complicate your architecture or slow down development can delay the understanding and correcting of these bottlenecks.

There's always one right way to do things. We don't fly blind in game development. We know what we have: specialized experience, generalized experience; knowledge of various algorithms, data structures, means of combining them; knowledge of the computer's operation; a concept for the game we're making, a rough idea of how much "wiggle room" we have in its design. Of course, only OP knows these factors precisely as they pertain to him. What I proposed was a solution that is risk-averse (good guarantees) and versatile (lets OP change the game's design more easily). Could be wrong, but I believe this will save time in the long run. Designing something efficient ahead-of-time isn't always to optimize prematurely.

Besides, bottlenecks are usually easy to predict, because they tend to fall in one of a few patterns.

The overhead from spatial hashing may actually be slower if there are too little objects or the objects are too large compared to the tile size. If you are right, then OP should focus on Quadtrees rather than regular spatial hashing, as it's a better system for 2D collisions.

1. Cell size is trivial to configure in a spatial hash. OP's game would have to be very sparse for spatial hashing to be slower.
2. On the contrary, quadtrees are only superior when the world size is large (OP's game is a single-screen platformer), or where collider sizes vary greatly (not likely).
[you can write a spatial hash that deals with large worlds, it just takes far more time]