nesdev.org

In a lot of NES games, it was fairly easy to get things to glitch through the walls due to poor collision detection and response between sprites and the background. The programmers may have been rushed or just inexperienced. So I decided to sit down and think about what collision detection actually is so that I can add a bit of mathematical rigor to make it more predictable. The goal is to determine whether something is overlapping one or more solid cells, and then push it out of all walls that it's overlapping.

With this clear goal in mind, I devised an algorithm to discover the contour of the walls in an object's neighborhood and act on it. Does anyone want to see a tech demo of this method on the NES, so that you have something to cheat off of when coding terrain collision in your own games? Or did I overcomplicate things?

I'd say this is one of the topics that cause most confusion to newbies once they get past the very beginning and start coding programs that actually resemble games, so any new material on this is welcome. If you have some visual aids to provide, that would be nice too. EDIT: I hadn't checked the link yet! You have a whole page on this! =)

Collision detection is very hard to wrap your mind around in the beginning, so the more you can simplify it, the better. I haven't read the article to comprehend it in great detail, but it seems to be pretty short and sweet. If not done correctly, collision code can be littered with messy comparisons and off-by-one errors. I know when I started, I had lots of problems with being off by one. If an object is 16x16 pixels in size, the corners are actually at 0,0 and 15,15; not 0,0 and 16,16. If you code this wrong, the object will not fit between 2 16x16 pixel solid objects .

A simple box-based collision detection I sometimes use between two boxes: It's written out in C-style syntax but it should be somewhat adaptable:
x1 and x2 are the left and right boundaries of box 1, and y1 and y2 are the top and bottom boundaries of box 1.
x3 and x4 are the left and right boundaries of box 1, and y3 and y4 are the top and bottom boundaries of box 2.
It checks if x1 is more to the left than x4, and a similar comparison for the other boundaries.

Basically, if any facing boundary is beyond the other, it means it is not a collision.

That's how you do collision between two objects, but collision between a tile map and an object is the subject here I think.

MottZilla wrote:That's how you do collision between two objects, but collision between a tile map and an object is the subject here I think.

True, but you can consider the tile to be a box.

In the case of tiles, it's not only collision detection but also collision response: what happens when you know two things are overlapping. Here, we know that an object overlaps multiple boxes at once, and we want to know where to move the object so that it stops overlapping them.

There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical. You need a system which can quickly determine a collision with a tile and determine where the colliding object should end up, given the original coordinates of the object and the coordinates it would be at had there been no collision.

blargg wrote:There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical.

Also, when you have slopes, not all tiles are boxes.

I remember that, back when I was a complete newb in NESdev, I had the following reflexion :

There is 256x240 pixels on the screen, so this makes 61440 pixels. For collision detection you'd need at least 61440 bits = 7.7 kB but there is only 2 kB of RAM in the NES. How can games then do collision detection ?

Well now I know the answer but back then it was really not obvious.

Simple object <-> object collision or object <-> BG collision is not too complex to do as long as you only move one pixel at a time (or simulate a faster move by moving one pixel at a time internally).
However I really wonder how games with REALLY complex collision such as Super Castlevania IV did it. It had multiple background layers in Level 4, and mode 7 a little everywhere with scaling and rotation of object. Also rotating wheels in level A and moving platforms in level B. Of course if has slopes too. Do a proper collision for this should have been a total nightmare.
(PS : And it is also the first game of the series where they got it perfectly right).

Rotating levels aren't any harder provided the object and camera positions are stored in "world space", relative to the origin of the map.

tokumaru wrote:

blargg wrote:There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical.

Also, when you have slopes, not all tiles are boxes.

Technically, in practice they still are handled as such, but the collision response is different.

While we are at topic of background colissions.
What adventages have mario bros style collisions? I mean, that player is pushed outside of the box if player is inside of the box.
Fantastic Dizzy do the same thing, but pushes player upwards, so the game can use a fake slope tiles without extra coding for it.

In inversion I have a detection point just below the player's foot to detect a tile below. If it's a solid one, then I ignore "player is falling" code.

Which one is better way to use? Pushing player out of box or stopping player from entering the box?
The first one proves to be more glitchy(?)

MarioWiki.com

This glitch is caused by the collision detection routine not seeing that the lower left corner of Mario is within air when Mario comes out of the crouch. My algorithm, sampling at each corner, would give a contour of B ▀█ which means "push to the left, then push down".

And even if an object were suddenly entirely embedded in solid tiles, one of the suggestions given on the page for how to handle contour F ██ is to remember the last tile that the object was in and then push toward that tile, which is ultimately the same as "stopping player from entering the box".

Sik wrote:

tokumaru wrote:

blargg wrote:There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical.

Also, when you have slopes, not all tiles are boxes.

Technically, in practice they still are handled as such, but the collision response is different.

I agree. Maps, as far as collision is concerned, should ultimately be broken down into boxes/tiles. Each box would have a collision "type". In the instance of a slope, rather than displacing an object to be entirely outside of the box, you could factor in the coordinates within the block to do a partial displacement. A 45 degree slope would be very easy to handle, as point of collision happens when x = y within the tile (depending on the direction of the slope).

Bregalad wrote:Simple object <-> object collision or object <-> BG collision is not too complex to do as long as you only move one pixel at a time (or simulate a faster move by moving one pixel at a time internally).

I have actually set a size/speed limit in my game as a work around. Objects which can collide with one another must not be smaller than the number of pixels they will move per frame (actually, half of that, I believe). Typically, I don't have objects smaller than 8x8 pixels, and I don't have anything moving close to 8 pixels per frame (or even 4, for that matter). This will ensure that objects do not pass through each other and miss collision. This way I don't have to waste time checking for collision multiple times in the same frame, or implement some goofy logic to check for missed collisions.