next »

[LemonScented]

I'm a huge fan of Box2D, but has anyone who is recommending it actually tried the XNA port? I did, a couple of months ago, and the performance was absolutely awful. Unusably slow. After a bit of Googling I found Physics2D.net which seemed to perform a lot better.

All that being said, I'm with Draknek in that if you're only dealing with non-rotated rectangles, and if you plan to have custom collision response (which you very probably do), and assuming it's just a simple platformer, and especially if you've not done it before, roll your own AABB rectangle collision.

[salade]

Oh goodie, another argument over the merits of box2d. Not every collision thread has to turn into this y'know.

I want something that can quickly handle my collisions so the trig has room to breathe.

what uses trig?

[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?

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

They are all bound to a grid, yes. They are not rotated. They all have an AABB.

Oh goodie, another argument over the merits of box2d. Not every collision thread has to turn into this y'know.

I want something that can quickly handle my collisions so the trig has room to breathe.

what uses trig?

The psuedo-3D effect I am using for Monolith.

[Skofo]

Using Box2D for regular ol' collision? What an interesting idea... I always assumed that using Box2D for simple game physics is not very efficient because it is built for full-blown rigid body physics; is this not the case?

[capnmikey]

Are you familiar with vector maths?  There are hilariously fast/easy ways to solve some problems which intuitively look like they need trig, though it depends exactly what you're doing.

Anyways, you may want to check out the Sweep and Prune algo.  Its description uses the phrase "exploits temporal coherence", which makes it a good candidate for the most elegant

Also, System.Drawing.RectangleF

Edit:

@Skofo - It's been a while since I picked through Box2D's sweet, sweet innards, but I remember being impressed by how well separated the collision and rigid body stuffs were.  It wouldn't be hard to only use the collision code, even if it's not supported out of the box.

I would probably roll my own 2D code, but I had a similar "Ah ha!" moment when I realized PhysX could be used for 3D collisions.

[Zachary Lewis]

Are you familiar with vector maths?  There are hilariously fast/easy ways to solve some problems which intuitively look like they need trig, though it depends exactly what you're doing.

Anyways, you may want to check out the Sweep and Prune algo.  Its description uses the phrase "exploits temporal coherence", which makes it a good candidate for the most elegant

Also, System.Drawing.RectangleF

Edit:

@Skofo - It's been a while since I picked through Box2D's sweet, sweet innards, but I remember being impressed by how well separated the collision and rigid body stuffs were.  It wouldn't be hard to only use the collision code, even if it's not supported out of the box.

I would probably roll my own 2D code, but I had a similar "Ah ha!" moment when I realized PhysX could be used for 3D collisions.

I've got the rotation down fine. Where we're going, we don't need vectors. :D

I've seen System.Drawing.RectangleF, but the XBOX360 doesn't support that library, so it's right out.

[Stegersaurus]

Just to add to physics engines, for XNA games a common 2d physics engine to use is Farseer Physics, which I know the newest version is being built on top of Box2d XNA. I've been using Farseer and it has some nice interfaces/features, as well as optimizations designed for XBox use (low/no garbage creation on already created objects) but is, like many physics engines, not a perfect machine. If you're just making non-rotated rectangular platforms and characters I'd probably go with rolling your own solution though. It's good to learn it even if you eventually use pre-built tools.

[Triplefox]

My suggestion: It's a good idea to get a book on game physics even if realistic physics is not the goal, because they have all the concepts you need to do good fake physics too - contact points, minimum-distance separation, broadphases, etc. The suggestion of "just do something yourself" is mostly good if you like really hard puzzles that other people have already solved.

[raigan]

First of all, from playing the Monolith demo: what's wrong with what you're doing right now? It seemed great to me.

I'm also going to have to side with the "Box2D is overkill" faction.. it's just way too much work/complexity, it doesn't make sense to apply a powerful general solution to something very simple and specific like axis-aligned rectangles.

Since the "most elegant" solution is going to be specific to what it needs to do, what do you want that you don't already have? You could use a grid of on/off values (i.e no explicit rectangular "tile" objects), or you could merge tiles into horizontal slabs..

As others have mentioned, you definitely should be able to work directly with the world, which is really just a grid whose x-axis wraps; this just means that you would do "player.x = player.x % world_width" to "wrap" the player around the edge of the grid. This is actually analogous to how rotation/orientation is usually dealt width: positions are wrapped to within [0, world_width] and vectors (deltas between two positions) are wrapped to within [-world_width/2, world_width/2] so that they point to the shortest path between two points.

[Zachary Lewis]

First of all, from playing the Monolith demo: what's wrong with what you're doing right now? It seemed great to me.

The algorithm breaks down for non-player characters.

[raigan]

Are NPCs a different size than the player? Or do you need them to behave differently? (i.e you can't just use whatever method you're using for the player).

I can't see why it would just break down unless there's some important difference in the way that NPCs move/collide..

[Martin 2BAM]

Is the purpose of your algorithm learning, a game or an engine/lib?

For a game, do the game first! Just check with a good old O(N²) overlap.
If the collisions become a bottleneck or look awkward, fix it later. For that I suggest an abstraction layer that gets called on these events:
Entity added
Entity moved
Entity destroyed
Perform the collision/response between entities

You could later implement a super-structure (tilemap, quad-tree, ...) for performance.

For learning, use a quad-tree with a special "static" (never-moving) entity array on each node seems to me like a cool solution for sparse entity collision checks, more than fit to what you want. Do a simple test (no graphics) and just stress-test it.
Make a hull by the given entities' velocities (previous position vs. next position) to somewhat mitigate the "skipping" of fast moving objects.

For an engine, first be really sure if you're going to continue development on it and release it... or it will be used for just one game (happened to all of us )




Regards

[Zachary Lewis]

Are NPCs a different size than the player? Or do you need them to behave differently? (i.e you can't just use whatever method you're using for the player).

I can't see why it would just break down unless there's some important difference in the way that NPCs move/collide..

They behave completely differently. The player only has to worry about collisions with the blocks near the center, but the npcs can walk around the map, leading to very weird collision on the sides of the tower (where several blocks overlap).

I believe I'm at the point in this project where I say, "Alright! That was a great first attempt!" Then, I start over from scratch, making it better.

[BorisTheBrave]

Box2D Platformer Pro's and Cons (from me, your friendly neighbourhood Box2D junkie/dev):

Pro:

• All pre-made, including vector library, game loop, and various other things
• Broadphase means blindingly fast when dealing with large worlds
• Extras you might well want: area queries, raycasts, controllers, sensors
• Continuous physics means bullets can never travel through things, regardless of speed.
• Kinematic bodies + friction = easy moving platforms. In fact quite a lot of gimmicks & special effects are possibly just by tweaking parameters.

Cons:

• Harder to get that old school feel.
• Toe stubbing requires hacks to avoid (toe-stubbing is my terminology for when you place two tiles next to each other, and other boxes fail to slide smoothly over the join)
• The events API is not tailored to AABB cases, which makes it seem overly complex.
• Physics shortcomings e.g. having difficulty with very large stacks, varying masses. You're hand rolled engine probably has the same problems, but its easier to hack around in your own code.

This is versus rolling your own engine.

[Impossible]

They behave completely differently. The player only has to worry about collisions with the blocks near the center, but the npcs can walk around the map, leading to very weird collision on the sides of the tower (where several blocks overlap).

At first I had no idea what you were talking about, but then I looked at the video of Monolith .  It seems like you need to rethink the problem and do collision in a different space.  From what you're saying, instead of having a flat tile map, you are actually changing block positions based on the player\camera position and performing collisions in the same space that blocks are rendered in.  

What you need to do is decouple collision from player position, or alternatively transform blocks relative to each NPC in the same way you are transforming them relative to the player and perform collisions then.

[oahda]

The system I have developed for my 2D platformer doesn't deal with square collisions object, but polygon collision objects, which are split up into triangles to check for perfect collision within these triangular shapes.

I obviously have quite simple collision polygons, but they still give more precision and look nicer than just square collision blocks, and as the collision polygons are obviously invisible, and all that's visible are the tiles and the sprites, which gives you a pretty good illusion of an almost pixel perfect collision system.

This also allows for slopes of all angles very easily.

To make sure that I don't blow out the RAM just to check for collisions, I make sure to have as few block objects as possible, and I make sure that as few blocks as possible are checked at the same time. For this system to work, it is important that I add the blocks in the right order, from the beginning of the level to the end of it.

To make sure that I have as few blocks as possible, I simply allow every block object to have a repetition parameter, so that the same block can actually be as many blocks as I want to. The reason I do this is because the collision algorithm works much better when using several small blocks than huge ones.

To check for collisions, there is a for loop that goes through all the blocks of the course, but it breaks itself if the next block it checks is out of range, so that it doesn't have to check more blocks than necessary, and there is a variable to keep track of how far you are into the level, so that you do not loop through any blocks behind you either. So, mostly, thanks to the repetition parameter, mostly just one block or two is in the loop at the moment. Then there is, of course, another for loop within this one to loop through the repetitions, but like I said, this only happens for one block and then the loop will break, so it isn't slow either.

[raigan]

Impossible is right -- your player/camera/NPCs should be moving through the world, the world shouldn't be moving at all!

All the objects and tiles should "live" in worldspace; tile positions are fixed and the camera/player/NPCs move around. To draw the world, you determine the screenspace position by calculating the position of each object relative to the camera's position.

This way, by moving the camera around you create the *illusion* that the world is moving, without actually having to make the world move. The benefit of decomposing things like this is that many difficult problems become sane -- i.e you can now treat NPCs and player uniformly, since both are just rectangles moving around the fixed tile shapes.

[oahda]

Impossible is right -- your player/camera/NPCs should be moving through the world, the world shouldn't be moving at all!

All the objects and tiles should "live" in worldspace; tile positions are fixed and the camera/player/NPCs move around. To draw the world, you determine the screenspace position by calculating the position of each object relative to the camera's position.

This way, by moving the camera around you create the *illusion* that the world is moving, without actually having to make the world move. The benefit of decomposing things like this is that many difficult problems become sane -- i.e you can now treat NPCs and player uniformly, since both are just rectangles moving around the fixed tile shapes.

Isn't it obvious that the world should have a fixed position and that there should be a viewport moving around?

[Skofo]

I agree with what the couple other people have said. Make the actual map work like a simple 2D plane that warps characters from one side to the other, and do all the cylinder stuff in the render layer. It's actually a little mind-boggling to think of it being done any other way. 

[Ben_Hurr]

The original Super Mario bros. did that, hahaha
But that was in the 80's, holy shit.