Platform game collision detection

What kind of platform game, and what kind of map?
If your map is built from tiles, then do collision against the tiles close to the player. If you need better precision than just tile-sized squares, refine the test to pixels inside each tile.

There are a few ways you can deal with it assuming a 2d game.

The simplest is to do basic AABB collision detection, disallow ramps (only have flat surfaces), apply a constant "down" vector to your players and make sure they can't fall through the floors (when either bottom corner of your rectangle is in a collision square you can pop it up to be level with the ground). You could also do a distance check and correction in a similar way.

You can also try doing per pixel collision detection like games such as Scorched Earth and Worms do.

Beyond this you can really get as deep as you like in writing a physics engine which accurately reflects the world, but this is kind of reinventing the wheel. It has been done before, and so if you plan on doing something much more complicated than the two ideas above let me suggest using something like box2d or some other physics engine.

Using such a package would allow you to construct a player object which may be a simple circle (to deal with ramps and corners more gracefully) then render your character snapped to the ground when the ball is touching the ground (you'll want to interpolate between the actual ball center and the snapped position to ensure jumping/landing is smooth.) Jumping can be caused by applying an impulse, moving can be caused by rolling the sphere and dealing with whatever friction+rotational speed you've supplied should allow you to tune how the character accelerates/decelerates and top speed.

The nice thing about using a physics library is that it will typically handle collision response (moving objects to not collide anymore) for you and allow you to detect and react to those events where the simpler methods of rolling your own solutions require you to deal with this yourself. Of course, you're going with a more generic solution based on a simulated physics model and tuning the controls to be pixel perfect is more difficult.

*Edit: Updated the link to the per pixel collision detection.

[Edited by - M2tM on October 19, 2010 5:38:11 PM]

In addition to M2tM's quality response, I would say to check out: XNA Platformer Kit.

I think it does a good job of introducing the necessary concepts. Also, you may want to build some quick prototypes of the situations that M2tM outlined and see how you like them. I know you may be using C++, but the XNA kit has some good concepts/algorithms to glean; it also, is pretty responsive and smooth, so it may be a good starting point and you can extend those concepts to your specific situation.

I'd say my direction wouldn't be just right-angle boxes, ramps are likely. But these kind of games have been around way before XNA or physics engines were used... can't believe games like Sonic have a physics engine but they have pretty complex layouts.

Are there any resources how games like Worms work? Again, this was around on pretty low-power PCs and did accurate pixel-level collision as well as nice destructible scenery... hard to imagine worms could store a bitmap of the entire level in memory when it ran on systems with only a few Mb RAM and no modern GPU. The link above is about pixel-collisions between two entity objects rather than a big chunk of scenery... and also I'd rather read an algorithm/idea than code.

BTW: this is for a AS3 game so resources are limited, but I'd guess a flash game on a modern PC has the equivalent pixel-pushing power of a class Pentium or PII... which was enough for full-screen 2D games.

Since you're writing a platformer in ActionScript, you might be interested in how N did it's collision detection. Check out N Tutorial A - Collision Detection and Response, and N Tutorial B - Broad Phase Collision for an excellent write-up of a grid-based collision detection scheme as well as the seperating axis theorem (SAT).

You'll find an excellent writeup, interactive examples, and ActionScript sourcecode.

Hope it helps! [smile]

Hi John,

Actually, you'd be surprised how simple it is to do something equivalent to Worm's destructible geometry, even though back in the days it wasn't so obvious naturally :).

You don't need to hold a full blown texture for the terrain when it comes to collision detection. You can easily get away with a texture that has a depth of 1 bit per pixel.

Your graphics representation can be something else. It can be made of a composition of tiles and some predetermined sprites. Do you remember how it used
to look ?
Basically the majority of the "volume" of the level was of a certain type which
can be easily represented using a tile map. There are other objects that they
put in the environment which are either buried partly or are above the surface.

They create the level procedurally of course but given these constraints. They
can generate the tile map and the positions of the objects and only render it to
a full texture ONCE, in order to create the 1 bpp texture I was talking about
before.

Once you have it, you no longer need the big texture (with full color that is) to be kept in memory because for presentation. You can render its exact equivalent without having to allocate the entire thing.

The 1-bpp texture can also be compressed (if needed) using lossless algorithms
or RLE to conserve memory, but its probably not needed.


As for Sonic - I guess they have pixel-level collision detection but Sonic is modeled using a sphere. So its basically sphere vs. pixels and I guess the level is subdivided into parts, probably along the lines of what I described for Worms.


Naturally, this is pure speculation (except the part about sonic's collision proxy being a sphere hehe).

I don't think there's any one solution to this problem. In this day and age, I'd go for collision proxies that are geometry and only in the extreme cases if I needed pixel-perfect coldet I'd implement it. Otherwise, just approximate the graphics.

Hope that helps..

Yes, have a few rating points [wink]

I would have assumed worms didn't use a simple bitmap... even at 1-bit-per-pixel this was a game from the Dos era and I imagine that'd still be a pretty big bitmap to work with. Maybe not though.

Hi John,

Well, regarding the original Worms, consider the numbers. The screen resolution was 320x200 pixels. The entire landscape I believe was about 3 screens wide and possibly (lets assume) 3 screens high.

That makes it 960x600 = 576,000 pixels. If its 1 bit per pixel just for collision detection purposes, we're dividing by 8 to get 72,000 bytes. I think even a 286 can handle that :)

Anyways, I hope the post helped any..

Hmm, yeah I suppose the resultions were much lower. But I remember the levels being bigger, like 2 screens high and maybe 4 wide. However those numbers aren't too bad, my gut instinct must have screwed up on that one :)

You don't need to create one giant bit-mask for your whole level. Divide the level into blocks, and leave out empty ones. A grid or quadtree should do fine. It'll save you some memory and it'll potentially speed things up a bit.

Alternately, reuse bitmasks, as you would do with images in a tilemap. First check the bounding box of a collision bitmask, and only if there's overlap do you need to check the overlapping area for pixel collisions.


I normally use rectangles and line segments and all that, but I'm looking into per-pixel collisions for a prototype right now, so yeah. ;)

For pixel-based smooth collision (i.e approximating/inferring surface normals), I'd recommend looking at the source of Collision Detection Kit, which does an amazing job:
http://code.google.com/p/collisiondetectionkit/
http://www.coreyoneil.com/portfolio/index.php?project=5

That seems like the best approach these days for pixel-based collision, but if you're interested in how it works in Sonic, there's some terrific info here:
http://info.sonicretro.org/Sonic_Physics_Guide

Raigan, thanks for posting that. I wanted to read up on how they did Sonic a while back, it seemed very interesting to me to compare what I thought is the proper approach to their actual work.

np, AFAICR I found that site from a different thread on these forums :)

It's definitely super-interesting stuff.

Hi,

I'm interested in this type of stuff too. I'm creating a standard 2D platform side-scroller. I understand the physics and logic behind the various collision detections (including slopes), but having great difficulty implementing it.

I'm using a tile based system.

My issue is: How do you do this the SIMPLEST way? Right now, I am using rectangular bounding collision detection to see if the player hits walls in the X direction, using pixel-perfect collision detection based on 1 pixel (bottom middle of character) to see if it hits the ground (could be a slope), then a few other particular pixels while walking left/right to see if the player encounters a slope, etc. to decide whether to move the player up/down. Once you cover all the possibilities, you end up checking about 8 different particular pixels, just to get the slopes and everything right, and it still does not seem complete

Because while checking the bottom middle pixel to see if a player landed on a slope (to a void the player standing "next to" the slope), this doesnt work well when you test if they fell off a solid platform, because they fall off too early (its better to use rectangles for this so they have some buffer).

What's the easiest way to check all this stuff in one go?

And as a side note - is it better to apply gravity constantly, or lock the player to the ground if walking, and then only apply gravity if jumping/falling? It seems there are pros and cons to both but I can't seem to work out which is best in this context.

many thanks

PS - I am using PyGame, utilising the sprites & rect functions including collision functions, but the logic should be independent of this anyway.

Ah, this question tormented me for about 8 years, up until last year when I finally solved it. Pixel-perfect, integer based collision of variable sized rectangular sprites, versus tile based maps with slopes, which can be jump-through platforms, or tagged as ice, spikes, etc., and stand on other sprites as well.

No horizontal collision against sprites though, and slopes are limited to 4 levels of steepness, similar to Super Mario World (1 to 4, 1 to 2, 1 to 1, 2 to 1), although you may be able to add more. It's been a while since I wrote it so I don't remember all the details. I think most of the old games used simplifications to speed it up and reduce the size of the code, but I just had to know if a complete solution was possible. And it is. But it's very difficult, there are tons of iffy cases that have to be handled.

So without further ado, here's the code:
Collision.c
Collision.h
CollisionTables.c

The function CollisionMove is the main entry point. The collision grid is just a hash table optimization for sprites, to locate nearby sprites without having to loop through every active thing on the map. It's not even used by CollisionMove anyway, just for sprite collision stuff that's done separately.

The code for standing on sprites is handled in the character update function, but it's pretty simple. Basically a downward trace that shortens the Y movement if you landed on something. Here's how the player character does it:


Hopefully that helps some. Feel free to use the code directly if you can get it to run, or ask questions if you want more details of any part of it. One day I ought to write a tutorial to get the concepts across in a more readable way. So many collision tutorials out there, but all I've read simplify it until important parts are missing, and impossible to add without a total rethinking.