next »

[dspencer]

Hi

I know people here have been involved with making 2D platform games (run and jump/Mario style/whatever you want to call them). I've tried a few times but I've never been satisfied with how my collision detection and resolution works out. So, I was wondering two things:

1) How do you deal with collision resolution? Both in terms of getting the player to stay on platforms, and also in terms of moving platforms. Right now I have a system checking really think rectangles on each side of the player, but it ends up being really inefficient (to the point of it being the problem for the frame rate without any of the other mechanics in the game).
2) How do you structure your game? In terms of object oriented design. I've tried to lay it out, and it always seems to break good design principals. My CS prof at school said this is just one of the realities of programming - OO doesn't always work out perfectly when put into practice - but I wanted to anyone who had made a game just to see their perspetive on it.

Also - if anyone could recommend a good tutorial to look at, on these topics?

Thanks so much!

[BorisTheBrave]

1) I use Box2D, a physics engine. Even if you don't want the phsyics (though I do), it does collision detection and resolution well.

2) I have the reverse problem, of building up too rigid a system at the expense of it being too hard to make a decent game from it, or at least wasting enough time to lose interest. It's probably an impossible compromise between the two. I'd love to hear other people's answers.

[nihilocrat]

I'm curious just how you strip out the collision reaction out of Box2D (i.e. the physics) and leave the detection in. Do you just set all your bodies/shapes as sensors?

As for design, I follow what I figure is MVC (but I'm probably mistaken). There's a Model, View, and Controller object... Model handles the logical aspects of the game, View the visual stuff (and visual-only stuff which has no bearing on gameplay, like particle systems), and Controller is literally the code for controls. I use an event system (see also: 'Observer' pattern) when something in the game occurs; stuff like "bullet_shot", "player_death", etc..

For example, when a "bullet_shot" event occurs, the model creates a bullet object at the specified location with the specified speed and such. The View creates a sprite for it, and plays the sound for the bullet being fired. The Controller, well, actually it does nothing, the controller doesn't react to anything but input events, or in the case of "player_death" it disables the controls.

The advantage is that you don't have to keep references to everything everywhere, and keeping stuff separate lets each component decide how exactly to handle an event and just keeps the code cleaner and easier to work with. Unfortunately, it might be hard to figure out "what all happens when I shoot a bullet?" since the code is spread out everywhere.

[Gold Cray]

jnrdev has an excellent collision detection tutorial. It has always worked perfectly for me. As for moving platforms, I haven't really don't anything with them, but my suggestion would be to modify your collision detection response so that when you detect a vertical collision with a platform you set the player's velocity equal to the platform velocity plus the slight downward bias. Since you should detect that collision every frame, you should always get an accurate response.

[Zaphos]

If you want to collide with something other than a plain tile map, there's a nice tutorial at metanet: http://www.metanetsoftware.com/technique/tutorialA.html

The jnrdev method doesn't look like it will handle slopes nicely ...

[dspencer]

Hrm, I remember looking at the Meta-net tutorials a while ago and not getting any of it. But I took another look and they look really useful, so I'll give it another shot. Thanks!
--Actually, between when I started writing this post and when I'm actually posting it, it looks *really* good.



@nihilocrat Yeah, I also use (roughly) MVC. I was more asking about the model, specifically. How do you structure the event loop? Usually, I have a Level and a bunch of Game_Elements - does the Level tell each Game_element that it is colliding with something? Or, does the Level just deal with all the collisions on its own? the first seems like better structure, but the latter seems more practical...

[Zaphos]

I like to handle collision in a central place -- a game object by itself doesn't really have enough information to know how to react to collisions, usually?

[Aquin]

All, I know is that the more realistic the collision, the more complicated the code.

ie... if(x1 < x2 && y1 > y2 etc.)

turns into

  float s = (-ey * (x1 - x3) + ex * (y1 - y3)) / (-fx*ey + ex*fy);
  float t = (fx * (y1 - y3) - fy * (x1 - x3)) / (-fx*ey + ex*fy);
  if(s >=0 && s <= 1 && t >= 0 && t <= 1) Hit = true;

My advice?  Do what Boris says.  Go get Box2D. 

[Ina Vegt]

My advice?  Do what Boris says.  Go get Box2D. 

Or another lib that does collision.

[BorisTheBrave]

I'm curious just how you strip out the collision reaction out of Box2D (i.e. the physics) and leave the detection in. Do you just set all your bodies/shapes as sensors?

Yes, all sensors for just detection. Or set everything as bxoes with fixed rotation and zero restitution, effectively removing all physics, but still preventing bodies from penetrating. Admittedly implementing this for yourself is not too difficult, such as in tutorials suggested, but you get the advantage of a broadphase and continuous collision detection, which can come in handy as your games gets to more advanced.

Other libs are good too. A lot of scene graph libraries come with collision detection which is probably more on the level most people are looking for.

[Draknek]

If everything in the world is an axis-aligned box, the technique described in the first jnrdev tutorial works really well and is possibly even simpler than integrating a physics engine.

Move on the x axis; resolve collisions; move on the y axis; resolve collisions.

What I can never decide is what the behaviour should be when you fall off a ledge. You don't want the player to be overlapping horizontally with the side, but you also don't want him to be able to walk out past his centre-point (he'll appear to be floating). Immediately pushing the player out will look wrong too, as he'll appear to jump from one position to the other.

See diagram:

You can just about get away with ignoring this if you don't have slopes (you let the player stay up even if only a negligible fraction of the collision rectangle is still touching the floor) but when their centre-point is used to determine their y position, it looks much more obviously wrong.

And unfortunately a physics engine doesn't resolve this problem for you... (in fact physics engine + slopes + non-rotating player gives its own problems)

[SHilbert]

If everything in the world is an axis-aligned box, the technique described in the first jnrdev tutorial works really well and is possibly even simpler than integrating a physics engine.

Move on the x axis; resolve collisions; move on the y axis; resolve collisions.

What I can never decide is what the behaviour should be when you fall off a ledge. You don't want the player to be overlapping horizontally with the side, but you also don't want him to be able to walk out past his centre-point (he'll appear to be floating). Immediately pushing the player out will look wrong too, as he'll appear to jump from one position to the other.

See diagram:

You can just about get away with ignoring this if you don't have slopes (you let the player stay up even if only a negligible fraction of the collision rectangle is still touching the floor) but when their centre-point is used to determine their y position, it looks much more obviously wrong.

And unfortunately a physics engine doesn't resolve this problem for you... (in fact physics engine + slopes + non-rotating player gives its own problems)

I was having some trouble figuring out how to make it so you don't look like you're "floating" on slopes, and I came up with a solution, although it's sort of complicated. Essentially instead of letting the player's rectangle interpenetrate with the world geometry on slopes, you make the player's collision a vertical line, and 'extrude' out the world geometry by half the player's width -- except on slopes. So, that way your collision primitives don't interpenetrate anymore.

The problem with this is that you have all these complicated rules to decide how to extrude the edges of tiles, and your character is now a "line" so you have to be very careful with your math.

Original problem (left) and solution (right):


The tile collision data is stored using four pieces of information: the left slope height (hL), right slope height (hR), and whether the 'bumper' region is present on the left and on the right. This is all done as a preprocess after loading the map; I don't actually store a line-based collision map but it's sort of done on-the-fly when you need to do collision tests. I can't really precompute it anyway since different sprites might have different collision widths, in which case the bumpers on the sides of tiles can change size.

[Triplefox]

I had a long post written and then closed the tab by accident. Now you get the shortened version.

For collision I find that the approaches depend on how much detail you want in the collision resolution. Simple tile-based+pushout approaches work when you don't want to vary your terrain's shape a ton and are more interested in robust behavior in simple/dynamic cases. As you add more features and variation, the balance swings towards baking a lot of useful collision information into the level so that you can instantly resolve situations that would otherwise be very complex and error-prone. Things like "where to grab on to ledges" or "the behavior of a moving platform" are far easier to special-case than to make to work in all situations.

For design I have gradually thrown away a lot of OOP structure from my initial iterations. In an indie project where you are working alone or with very few people, you have a good overview of how the game is structured, so you can use naive methods with more global variables and static instancing. The more complex approaches can be added later as necessary. In team coding projects the situation is considerably different and you are better off to adopt more defensive approaches from the outset; the biggest downside of the complex approaches in OOP is that they tend to complicate memory management, with more instances being flung through various namespaces, related to other instances in complex graphs or hierarchies, and then (somehow) being destructed cleanly. The last step can be particularly onerous when it comes to resetting the game.

Definite wins I've come across:

• MVC for strategy games and other heavyweight-interface situations - you get more repeatable behavior for "free." Other game types are less clear as you often want the graphics to inform the gameplay(for example, animations), or the other way around, and MVC deliberately bottlenecks and formalizes this process.
• Formalized state machines of some sort. State transitions come up all the time in games, and it behooves you to treat them with deserved respect.
• Closures for customizing UIs or entities. It is the most elegant way I've found; with a well-designed base data type, in one block of code you can define both state and behavior without bolting on a heavyweight mechanism like object compositions or external data files.
• Hashmaps/associative arrays/bags. These complement closures very well in the situations where you need to attach a little bit of extra state.