I've been thinking a lot about collision detection lately, in part because of NSMB, which does a beautiful job with it. By collision detection I mean both intersections between hit zones and intersections between a hit zone and an obstacle. It was always my nemesis in game design -- when I tried to design the basic mechanic for a Zelda-style game, I spent almost the /entire/ time trying to do proper collision with the movement system I'd designed. So I'm curious what other people's philosophies and and methods regarding it are. This isn't for any game in particular, it's just something I think about a lot.

The specific facets of the issue that interest me are:
What classes of obstruction/hit zone should exist? It's really easy/fast to check for intersection of rectangles and circles, provided the rectangles are aligned vertical/horizontal. Similarly it's pretty easy to check for straight lines aligned with either the vertical or the horizontal (aside from the problem of passing through the line without tripping it). However, slanty lines get a bit trickier, and angled rectangles seem especially problematic. From a mathematical point of view it's not too hard to see how you /could/ check for intersection between shapes of this sort, but it would probably be pretty slow, and I'm thinking VERGE specifically here, so speed is a real issue, especially when you consider the number of objects you might have to juggle in a modern game. Does anyone know a good trick for this? Also, am I right in assuming that there's no simple way to check for intersection when one of the shapes is an ellipse? Alternatively, is there a good collision detection method for general triangles?

Other concerns -- when something with a hit zone is moving quickly, it's possible for it to pass right through (or at least partly through) a one-pixel obstruction in a single logic execution. What do people do to get around this? As a related problem, sometimes if you have a solid obs, a fast-moving character will get "stuck" inside the obs and be unable to move lengthwise along it. I had this problem in the zelda clone, and I've also noticed it in (for example) Zeux. Do you think it's better to disallow such intersections in the first place (thus potentially limiting how close you can approach an obs while moving at a certain speed), or allow the collisions and then shunt the thing back out?

A related question about shunting -- this is something you need to think about even if it's not the solution to any specific problem, I find. Do people have specific tactics for shunting (particularly regarding direction)? I've always had trouble deciding how to do this -- in a platformer you might want to shunt up in general so the character doesn't fall off the screen and die, but this could lead to someone being shunted through the ceiling and out of the level proper.

If you want to determine the angle of inflection against a surface (at least in a general sense, for bounceback etc), is there a good method for doing this?

Thoughts, advice, discussion, linkage?

Edit: Afterthought -- any general timesaving measures might be useful, too. Like...do you think it's worthwhile to x-sort hit zones by lefthand side, and stuff like that?

I did think of a way one time to do angled rectangle collision, for something similar to collisions against the rotating backgrounds in the Mode4 (or can you call that 7? whatever, it's the rotating scroll) sequences of the first level in R-Type 3 for SNES, for example.

It does require having a class of rectangles that cannot rotate (ex, the player, especially if he fits nicely into a square-type rectangle which extends equally in all directions). In that case, you can simulate rotation by doing exactly the opposite -- rotate the sprite's coordinates in the opposite direction of playfield rotation, and then compare the new position of his square with the collision rects of the playfield [you could even do this with V3 map obstruction tiles].

Obviously it doesn't work for every situation -- only when there is a class of rectangles who can have their coordinates rotated, but not their actual rectangles. In essence one of the colliding classes must have a square or circle collision zone [since these don't need to be rotated].

For single-step logic that could allow an obstruction to pass through a single-line zone, I thought about stepping incrementally through each unit of movement the sprite can make. For example, if the sprite's momentum is 10 pixels per frame, I wouldn't do sprite.x+=10 -- I'd do it one pixel at a time and check for collision on each.

Shunting, no clue. Be smart and make it so that your ceiling obstructions on the level can't be passed through from the bottom, but you can fall through them from the top if you somehow get up there :)



EDIT: Also, be smart. Use rectangles :) Most of the time, the right-sized square can work for a circle (especially for small sprites).

Also, for rotating collisions, try breaking the collision zone up into two or three rectangle parts -- this allows pretty decent accuracy without any added mathematical voodoo.

Example, the swords in Castlevania: Aria of Sorrow that have the giant sweeping arc. Don't rotate a single rectangle that covers the whole sword, since you'd have to angle it and that would lead to nasty math. Instead, give it two sub-rectangles or squares -- one at the blade start to middle of blade, and one from mid-blade to tip. Rotate those two rectangles coordinates (not the rectangles themselves) around the origin point [the hand] when Soma swings the sword.

I think aen had like hundreds of dirty rects colliding in a v2 demo on a now slowish machine but maybe I'm mistaken.