next »

[Zachary Lewis]

I'm looking for a really clever algorithm to check and handle collision between a rectangular character (of any size)  and rectangular tiles (of any size). Does anyone have a favorite?

[salade]

Do you mean broad phase? Narrow phase is gonna have to be Separating Axis, especially if you are just talking about AABB for all collision checking. It can also be extended to other shapes, which is a plus.

[Tycho Brahe]

When you say tile based, do you mean something like a rougelike, where the player is bound to a grid? or like mario, where there are world tiles..?

if its the latter, I would recommend having a look at mare and raigan's (from metanet) articles (http://www.metanetsoftware.com/technique.html) about how they did tile based collision, you never know, it might help.

[Zachary Lewis]

It's a platformer.

I was using a modified version of the separating axis theorem, but I believe the majority of my problem came with XNA not having a float-based Rectangle class.

You guys are fast. If you have any personal tips for platformer collision not in a tutorial, I'd appreciate hearing it!

[Theotherguy]

It's a platformer.

I was using a modified version of the separating axis theorem, but I believe the majority of my problem came with XNA not having a float-based Rectangle class.

You guys are fast. If you have any personal tips for platformer collision not in a tutorial, I'd appreciate hearing it!

Make a float based rectangle class. It is not hard.

[Tycho Brahe]

Make a float based rectangle class. It is not hard.

this

[Golds]

I suggest plugging in Box2D.  It's very fast, has a simple API, and you can use it for full-on simulation, or just collisions if you like.

Edit: Here's the XNA port.

[Ivan]

I dunno, as much as I love box2D, for non-rotated rectangle collision, box2d is very much overkill.

[Zachary Lewis]

It's a platformer.

I was using a modified version of the separating axis theorem, but I believe the majority of my problem came with XNA not having a float-based Rectangle class.

You guys are fast. If you have any personal tips for platformer collision not in a tutorial, I'd appreciate hearing it!

Make a float based rectangle class. It is not hard.

Make a float based rectangle class. It is not hard.

this

This is what I've been doing the past hour.

[Ivan]

Also, take a look at flixel and how it does collisions.

[Golds]

I dunno, as much as I love box2D, for non-rotated rectangle collision, box2d is very much overkill.

I disagree.

This is what I've been doing the past hour.

He could take the hour he's spent reinventing a class for handling axis aligned bounding box collisions instead on simply hooking in Box2D, and have very fast Axis Aligned collisions, with room to grow for the future.

Also, take a look at flixel and how it does collisions.

As much as I love flixel (and I really do love it), its collision response is pretty glitchy, especially when you start working with lots of moving bounding boxes, and these days, Quad Trees are something that you shouldn't be messing with unless you want to learn how to implement them as a technical learning exercise.

[Ivan]

I dunno, as much as I love box2D, for non-rotated rectangle collision, box2d is very much overkill.

I disagree.

This is what I've been doing the past hour.

He could take the hour he's spent a class for handling axis aligned bounding box collisions instead on simply hooking in Box2D, and have very fast Axis Aligned collisions, with room to grow for the future.

And he would have learned less about the world.

[Draknek]

Move character in x axis; check for collisions and move back if needed.
Move character in y axis; check for collisions and move back if needed.

For AABB against AABB tests, Box2D is definitely overkill.

[Golds]

Move character in x axis; check for collisions and move back if needed.
Move character in y axis; check for collisions and move back if needed.

For AABB against AABB tests, Box2D is definitely overkill.

Is it?  Ok so he writes this code to test every character against every box...  What happens when you build a level of a reasonable size, with multiple entities moving, bullets, and ground response?  Then you need to start writing a whole system to partition your collision tests, and then you start getting into some serious territory.  Why reinvent a system like this when it's already been done very well?

Do you all also suggest he write a blitter to copy his sprites to the screen?  That's a great learning exercise too, but one of the advantages of using something like XNA is the libraries it provides you so you can focus on content design and not technical implementation.

[Ivan]

The best decisions in life are always the most unreasonable ones 

[Tycho Brahe]

Move character in x axis; check for collisions and move back if needed.
Move character in y axis; check for collisions and move back if needed.

For AABB against AABB tests, Box2D is definitely overkill.

Is it?  Ok so he writes this code to test every character against every box...  What happens when you build a level of a reasonable size, with multiple entities moving, bullets, and ground response?  Then you need to start writing a whole system to partition your collision tests, and then you start getting into some serious territory.  Why reinvent a system like this when it's already been done very well?

Do you all also suggest he write a blitter to copy his sprites to the screen?  That's a great learning exercise too, but one of the advantages of using something like XNA is the libraries it provides you so you can focus on content design and not technical implementation.

he should write his own blitter if he had extremely basic hardware. Simple problems usually require simple solutions, xna is a good thing to use as writing a game for both pc and xbox is not a simple problem therefore it requires a complex solution, in this case xna.
Collision is also one of areas in which it is best to learn how to do it, not only will you be able to write and use your own engine but you'll understand how to best integrate other parts of your game with systems like box2d. If zach is talking about collision detection for monolith then I think that a specialist solution, especially considering that the playing area wraps around in monolith and I don't think box2d supports this.

[Zachary Lewis]

If zach is talking about collision detection for monolith then I think that a specialist solution, especially considering that the playing area wraps around in monolith and I don't think box2d supports this.

Bingo. I've basically realized that my implementation of the separating axis theorem isn't going to cut it, so I'm going to handle collision on a Cartesian system then convert it into a cylindrical one. To prevent memory loss, I want something that can quickly handle my collisions so the trig has room to breathe.

[Zaphos]

I'm looking for a really clever algorithm to check and handle collision between a rectangular character (of any size)  and rectangular tiles (of any size). Does anyone have a favorite?

Are the tiles bound to a grid?  Are any of them rotated?

[Golds]

Collision is also one of areas in which it is best to learn how to do it, not only will you be able to write and use your own engine but you'll understand how to best integrate other parts of your game with systems like box2d. If zach is talking about collision detection for monolith then I think that a specialist solution, especially considering that the playing area wraps around in monolith and I don't think box2d supports this.

Box2D detects collisions.  Of course you can wrap objects around a playfield, move your object and check collisions.  Even if you're using full-on Box2D simulation to handle your game physics, it's just one line to move your object to any position:

body->SetPositionAndAngle(newPosition, newAngle);

I guess we can chalk this up to a difference in philosophy.  I've implemented collision systems from scratch many times, and I'm happy to not ever have to do it again.  You want a simple, fast way to check collisions for arbitrarily sized rectangles?  I still think Box2D is the best answer, and will allow your game to grow without blowing a bunch of time on your own less flexible solution.

[Draknek]

Ok so he writes this code to test every character against every box...  What happens when you build a level of a reasonable size, with multiple entities moving, bullets, and ground response?  Then you need to start writing a whole system to partition your collision tests, and then you start getting into some serious territory.  Why reinvent a system like this when it's already been done very well?

I agree that the broadphase provided by a physics engine would be excellent and nice to have, but unless you have a lot going on in a level it's completely irrelevant. When it does become relevant you can write a quick and simple grid-based implementation and you'll almost certainly be fine.

The collision resolution, on the other hand, is the part that would be total overkill. It's also not particularly suited to a platformer game: you can make it work and many people have, but it doesn't quite work out of the box.

On the other hand, my simple move-x-then-move-y algorithm can be quickly implemented and quickly understood. I'm confident that someone who's never used a physics engine before could get my approach working a lot faster than if they used Box2D.

That doesn't mean that physics engines are useless or that my algorithm is perfect. Certainly if the required features are likely to grow then a hand-rolled solution may in the end take significantly longer. But for the problem given - AABB against AABB platformer physics - it's a good solution.

Personally the last time I tried doing this with a physics engine (disclaimer: it wasn't Box2D but that doesn't mean Box2D is immune to this kind of issue), I had issues with a non-rotating square character walking on a grid of tiles where the character would bump into the cracks between tiles even though they should be completely aligned.