2d uneven terrain

Well, you can build your level from polygons.

Here's a very good and well documented example: Polycolly by Olivier Rebellion.

Or, you could just store a collision mask for each tile. A collision mask is basically a grid of the same dimension as the image, each element with 1 bit. If the bit is set, you collide, if not, you're clear. This opens an optimization where your tiles can say "all clear", "all blocked", or "consult the collision mask."

If you want to just have rolling hills with no overhangs, you can use a simple 2D heightmap. Thats what we used in our flying game to get uneven terrain:

i've already thought about heightmaps. the thing is, i'm still wondering if tile-based is the only way to go for 2d maps. the polycolly thing was helpful, and i might consider it, but that can't have been how it was done for sonic the hedgehog. too many calculations. sonic the hedgehog also didn't use tile masks (or did it?), because it didn't have the power to calculate collide or no-collide for every pixel.

games like the fancy pants adventures are exactly what i'm going after. how do all the flash developers do it?

also, what is the concept of a playing-field in a 2d game known as? map? level?

Definitly looks like tiles to me. They may even have hardcoded every single tile shape in those games instead of using masks.

I've been visiting GameDev for years, and just now registered for the first time.

Does this look like what you want?
http://www.donaldhays.com/physics/

You can view that page in Firefox, Opera, or Safari. IE doesn't work, unfortunately. The page has a simple physics engine that handles point and box collisions against an arbitrary 2D mesh. You can check the "Show Box" checkmark to display a blue box, and then use the arrow keys of your keyboard to move the blue box around.

Feel free to view the source code to see how I did it (it's all &#106avascript). I put in lots of semi-helpful comments. Essentially, what I've found over the past few years of trying to pull this off is that trying to handle box-line collisions is pretty easy until you want to handle multiple lines at once, at which point there are a massive number of edge cases that make things really difficult. The trick was to actually simulate point against line collisions, even for boxes. You can check the "Show Collision Hull" checkbox and then move the box around to see how it's simulating a point instead of a box.<br/><br/>I'm thinking I should write a tutorial on this, because, like you, I haven't found any tutorials on this technique online. The closest I came was a tutorial on colliding with a Quake BSP file, and it didn't seem to handle a few edge cases.<br/><br/>-Donald Hays

Quote:

Original post by theta4 i've already thought about heightmaps. the thing is, i'm still wondering if tile-based is the only way to go for 2d maps. the polycolly thing was helpful, and i might consider it, but that can't have been how it was done for sonic the hedgehog. too many calculations. sonic the hedgehog also didn't use tile masks (or did it?), because it didn't have the power to calculate collide or no-collide for every pixel.

A tilemap is just an optimization technique. You repeat the same images, with some variation of course, to save image memory and to provide easier collision detection, at the cost of more uniform looking levels. Using a tilemap doesn't mean you're limited to only tiles, however. Who said you can't mix polygons and tiles?

Quote:

games like the fancy pants adventures are exactly what i'm going after. how do all the flash developers do it?

Looks like either a bunch of polygons or lines to me. Keep in mind however, that you don't need to check against every polygon every time. You can organize them into regions, and first check in which region(s) the player is, so you only have to check against polygons within those regions. You can even organize these regions into super-regions if you have a lot of them. For example, quadtrees are often used for such purposes.

Quote:

also, what is the concept of a playing-field in a 2d game known as? map? level?

All are fine. Sometimes people use the term environment as well, though level and map are more commonly used.


@Donald Hays: That's an impressive piece of &#106avascript. :) Yes, that looks like the approach that Quake - and Half-Life - took. When compiling a Half-Life level, 4 collision hulls are generated. One for the player and player-sized characters, one for the player when chrouching, one for large enemies and another one for unknown or unused purposes. That is, if I remember correctly. I'll take a look at your code once I have some more time, looks usefull. :)

Quote:

Original post by theta4 ... sonic the hedgehog also didn't use tile masks (or did it?), because it didn't have the power to calculate collide or no-collide for every pixel.

Actually, that same technique was said to be used by an SNES game similar to sonic according to the poster, who claimed to have worked on that game, and the genesis processor was much more powerful than the SNES's.

I mentioned the possible optimization, but perhaps my description was too brief. There's two parts to the collision system. First, you do a quick box test against the tile map to see which tiles the sprite could possibly collide with. Each tile is tagged in one of three ways: either the entire tile has no collision, the entire tile has full collision, or tile has partial collision. Only in the last case do you have to check pixel-perfect collision against the tile's collision mask. With that, you still don't check every sprite pixel against every element of the tile's collision mask, just key points such as the central lower-bound used to determine Sonic's height offset as he runs across the uneven ground, for example.

Quote:

Original post by DonaldHays Does this look like what you want? http://www.donaldhays.com/physics/

Nice! The theory behind this is "minkowski sum" (sometimes called "minkowski difference") if you want to check out related papers. This one is recommended: http://essentialmath.com/GDC2007/5_GDC2007_Eiserloh_Squirrel_PhysicsReframing.ppt

the pretty "N" game has nice diagonals and round tiles collision,
and they wrote excellent tutorials describing how they did that efficiently (flash was too slow when the game came out)

tutorial B

Well, thanks for the help everyone. i certainly have some more insight to this issue, but i do think i'm going to stick with polygon/line-based collision detection for the map. maybe someday, when processor speeds are measured in terahertz (that day is soon), i will use bezier curve collision detection. but for now, i will just stick with line-based collision detection...kinda like line rider.

now i have to figure out how to do line-aabb collision detections...but that's for another thread.

thanks for the help everybody!