Is there a single 'standard' solution here, from back in the days before everything was polygons? If your level is quite complicated, it doesn't actually seem that simple to get smooth run+jump motion, etc.

Since the genre has been around so long I imagine virtually every question has been solved, but it's not a type of game I've worked on before and I'd rather learn from others' mistakes over the years/decades.

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]

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 :)